summaryrefslogtreecommitdiff
path: root/python/src/sa/suffix_array.pxi
blob: de4adcd905188106038d4fc7762c84529d7161ff (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
# Defines suffix arrays that can be directly written to/read from disk in binary format
# Adam Lopez <alopez@cs.umd.edu>

from libc.stdio cimport FILE, fclose, fopen

cdef class SuffixArray:
    cdef DataArray darray
    cdef IntList sa
    cdef IntList ha

    def __cinit__(self, from_binary=None, from_text=None, side=None):
        self.darray = DataArray()
        self.sa = IntList()
        self.ha = IntList()
        if from_binary:
            self.read_binary(from_binary)
        elif from_text:
            self.read_text(from_text, side)

    def __getitem__(self, i):
        return self.sa.arr[i]

    def read_text(self, filename, side):
        '''Constructs suffix array using the algorithm
        of Larsson & Sadahkane (1999)'''
        cdef int V, N, i, j, h, a_i, n, current_run, skip
        cdef IntList isa, word_count

        self.darray = DataArray(from_text=filename, side=side, use_sent_id=True)
        N = len(self.darray)
        V = len(self.darray.id2word)

        self.sa = IntList(initial_len=N)
        self.ha = IntList(initial_len=V+1)

        isa = IntList(initial_len=N)
        word_count = IntList(initial_len=V+1)

        '''Step 1: bucket sort data'''
        cdef float sort_start_time = monitor_cpu()
        cdef float start_time = sort_start_time
        for i from 0 <= i < N:
            a_i = self.darray.data.arr[i]
            word_count.arr[a_i] = word_count.arr[a_i] + 1

        n = 0
        for i from 0 <= i < V+1:
            self.ha.arr[i] = n
            n = n + word_count.arr[i]
            word_count.arr[i] = 0

        for i from 0 <= i < N:
            a_i = self.darray.data.arr[i]
            self.sa.arr[self.ha.arr[a_i] + word_count.arr[a_i]] = i
            isa.arr[i] = self.ha.arr[a_i + 1] - 1 # bucket pointer is last index in bucket
            word_count.arr[a_i] = word_count.arr[a_i] + 1

        '''Determine size of initial runs'''
        current_run = 0
        for i from 0 <= i < V+1:
            if i < V and self.ha.arr[i+1] - self.ha.arr[i] == 1:
                current_run = current_run + 1
            else:
                if current_run > 0:
                    self.sa.arr[self.ha.arr[i] - current_run] = -current_run
                    current_run = 0

        logger.info("    Bucket sort took %f seconds", (monitor_cpu() - sort_start_time))

        '''Step 2: prefix-doubling sort'''
        h = 1
        while self.sa.arr[0] != -N:
            sort_start_time = monitor_cpu()
            logger.debug("    Refining, sort depth = %d", h)
            i = 0
            skip = 0
            while i < N:
                if self.sa.arr[i] < 0:
                    skip = skip + self.sa.arr[i]
                    i = i - self.sa.arr[i]
                else:
                    if skip < 0:
                        self.sa.arr[i+skip] = skip
                        skip = 0
                    j = isa.arr[self.sa.arr[i]]
                    self.q3sort(i, j, h, isa)
                    i = j+1
            if skip < 0:
                self.sa.arr[i+skip] = skip
            h = h * 2
            logger.debug("    Refinement took %f seconds", (monitor_cpu() - sort_start_time))

        '''Step 3: read off suffix array from inverse suffix array''' 
        logger.info("    Finalizing sort...")
        for i from 0 <= i < N:
            j = isa.arr[i]
            self.sa.arr[j] = i
        logger.info("Suffix array construction took %f seconds", (monitor_cpu() - start_time))

    def q3sort(self, int i, int j, int h, IntList isa, pad=""):
        '''This is a ternary quicksort. It divides the array into
        three partitions: items less than the pivot, items equal
        to pivot, and items greater than pivot.    The first and last
        of these partitions are then recursively sorted'''
        cdef int k, midpoint, pval, phead, ptail, tmp

        if j-i < -1:
            raise Exception("Unexpected condition found in q3sort: sort from %d to %d" % (i,j))
        if j-i == -1:    # recursive base case -- empty interval
            return
        if (j-i == 0):    # recursive base case -- singleton interval
            isa.arr[self.sa.arr[i]] = i
            self.sa.arr[i] = -1
            return 

        # NOTE: choosing the first item as a pivot value resulted in 
        # stack overflow for some very large buckets.    I think there
        # is a natural bias towards order due the way the word ids are
        # assigned; thus this resulted in the range to the left of the 
        # pivot being nearly empty.     Therefore, choose the middle item.
        # If the method of assigning word_id's is changed, this method
        # may need to be reconsidered as well.
        midpoint = (i+j)/2
        pval = isa.arr[self.sa.arr[midpoint] + h]
        if i != midpoint:
            tmp = self.sa.arr[midpoint]
            self.sa.arr[midpoint] = self.sa.arr[i]
            self.sa.arr[i] = tmp
        phead = i
        ptail = i

        # find the three partitions.    phead marks the first element
        # of the middle partition, and ptail marks the last element
        for k from i+1 <= k < j+1:
            if isa.arr[self.sa.arr[k] + h] < pval:
                if k > ptail+1:
                    tmp = self.sa.arr[phead]
                    self.sa.arr[phead] = self.sa.arr[k]
                    self.sa.arr[k] = self.sa.arr[ptail+1]
                    self.sa.arr[ptail+1] = tmp
                else: # k == ptail+1
                    tmp = self.sa.arr[phead]
                    self.sa.arr[phead] = self.sa.arr[k]
                    self.sa.arr[k] = tmp
                phead = phead + 1
                ptail = ptail + 1
            else:
                if isa.arr[self.sa.arr[k] + h] == pval:
                    if k > ptail+1:
                        tmp = self.sa.arr[ptail+1]
                        self.sa.arr[ptail+1] = self.sa.arr[k]
                        self.sa.arr[k] = tmp
                    ptail = ptail + 1

        # recursively sort smaller suffixes
        self.q3sort(i, phead-1, h, isa, pad+"    ")

        # update suffixes with pivot value
        # corresponds to update_group function in Larsson & Sadakane
        for k from phead <= k < ptail+1:
            isa.arr[self.sa.arr[k]] = ptail
        if phead == ptail:
            self.sa.arr[phead] = -1

        # recursively sort larger suffixes
        self.q3sort(ptail+1, j, h, isa, pad+"    ")


    def write_text(self, char* filename):
        self.darray.write_text(filename)

    def read_binary(self, char* filename):
        cdef FILE *f
        f = fopen(filename, "r")
        self.darray.read_handle(f)
        self.sa.read_handle(f)
        self.ha.read_handle(f)
        fclose(f)

    def write_binary(self, char* filename):
        cdef FILE* f
        f = fopen(filename, "w")
        self.darray.write_handle(f)
        self.sa.write_handle(f)
        self.ha.write_handle(f)
        fclose(f)

    def write_enhanced(self, char* filename):
        with open(filename, "w") as f:
            self.darray.write_enhanced_handle(f)
            for a_i in self.sa:
                f.write("%d " % a_i)
            f.write("\n")
            for w_i in self.ha:
                f.write("%d " % w_i)
            f.write("\n")

    cdef int __search_high(self, int word_id, int offset, int low, int high):
        cdef int midpoint

        if low >= high:
            return high
        midpoint = (high + low) / 2
        if self.darray.data.arr[self.sa.arr[midpoint] + offset] == word_id:
            return self.__search_high(word_id, offset, midpoint+1, high)
        else:
            return self.__search_high(word_id, offset, low, midpoint)

    cdef int __search_low(self, int word_id, int offset, int low, int high):
        cdef int midpoint

        if low >= high:
            return high
        midpoint = (high + low) / 2
        if self.darray.data.arr[self.sa.arr[midpoint] + offset] == word_id:
            return self.__search_low(word_id, offset, low, midpoint)
        else:
            return self.__search_low(word_id, offset, midpoint+1, high)

    cdef __get_range(self, int word_id, int offset, int low, int high, int midpoint):
        return (self.__search_low(word_id, offset, low, midpoint),
                self.__search_high(word_id, offset, midpoint, high))

    cdef __lookup_helper(self, int word_id, int offset, int low, int high):
        cdef int midpoint

        if offset == 0:
            return (self.ha.arr[word_id], self.ha.arr[word_id+1])
        if low >= high:
            return None

        midpoint = (high + low) / 2
        if self.darray.data.arr[self.sa.arr[midpoint] + offset] == word_id:
            return self.__get_range(word_id, offset, low, high, midpoint)
        if self.darray.data.arr[self.sa.arr[midpoint] + offset] > word_id:
            return self.__lookup_helper(word_id, offset, low, midpoint)
        else:
            return self.__lookup_helper(word_id, offset, midpoint+1, high)

    def lookup(self, word, int offset, int low, int high):
        cdef int wordid
        if low == -1: 
            low = 0
        if high == -1:
            high = len(self.sa)
        if word in self.darray.word2id:
            word_id = self.darray.word2id[word]
            return self.__lookup_helper(word_id, offset, low, high)
        else:
            return None