summaryrefslogtreecommitdiff
path: root/python/src/sa/precomputation.pxi
blob: a3527f4748da3a390b354ec8b7715b0ac409dc94 (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
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
# precomputes a set of collocations by advancing over the text.
# warning: nasty C code

from libc.stdio cimport FILE, fopen, fread, fwrite, fclose
from libc.stdlib cimport malloc, realloc, free
from libc.string cimport memset, memcpy

cdef struct _Trie_Node    # forward decl

cdef struct _Trie_Edge:
    int val
    _Trie_Node* node
    _Trie_Edge* bigger
    _Trie_Edge* smaller

cdef struct _Trie_Node:
    _Trie_Edge* root
    int* arr
    int arr_len

cdef _Trie_Node* new_trie_node():
    cdef _Trie_Node* node
    node = <_Trie_Node*> malloc(sizeof(_Trie_Node))
    node.root = NULL
    node.arr_len = 0
    node.arr = <int*> malloc(sizeof(0*sizeof(int)))
    return node

cdef _Trie_Edge* new_trie_edge(int val):
    cdef _Trie_Edge* edge
    edge = <_Trie_Edge*> malloc(sizeof(_Trie_Edge))
    edge.node = new_trie_node()
    edge.bigger = NULL
    edge.smaller = NULL
    edge.val = val
    return edge

cdef free_trie_node(_Trie_Node* node):
    if node != NULL:
        free_trie_edge(node.root)
        free(node.arr)

cdef free_trie_edge(_Trie_Edge* edge):
    if edge != NULL:
        free_trie_node(edge.node)
        free_trie_edge(edge.bigger)
        free_trie_edge(edge.smaller)

cdef _Trie_Node* trie_find(_Trie_Node* node, int val):
    cdef _Trie_Edge* cur
    cur = node.root
    while cur != NULL and cur.val != val:
        if val > cur.val:
            cur = cur.bigger
        elif val < cur.val:
            cur = cur.smaller
    if cur == NULL:
        return NULL
    else:
        return cur.node

cdef trie_node_data_append(_Trie_Node* node, int val):
    cdef int new_len
    new_len = node.arr_len + 1
    node.arr = <int*> realloc(node.arr, new_len*sizeof(int))
    node.arr[node.arr_len] = val
    node.arr_len = new_len

cdef trie_node_data_extend(_Trie_Node* node, int* vals, int num_vals):
    cdef int new_len
    new_len = node.arr_len + num_vals
    node.arr = <int*> realloc(node.arr, new_len*sizeof(int))
    memcpy(node.arr + node.arr_len, vals, num_vals*sizeof(int))
    node.arr_len = new_len


cdef _Trie_Node* trie_insert(_Trie_Node* node, int val):
    cdef _Trie_Edge** cur
    cur = &node.root
    while cur[0] != NULL and cur[0].val != val:
        if val > cur[0].val:
            cur = &cur[0].bigger
        elif val < cur[0].val:
            cur = &cur[0].smaller
    if cur[0] == NULL:
        cur[0] = new_trie_edge(val)
    return cur[0].node

cdef trie_node_to_map(_Trie_Node* node, result, prefix, int include_zeros):
    cdef IntList arr

    if include_zeros or node.arr_len > 0:
        arr = IntList()
        free(arr.arr)
        arr.arr = <int*> malloc(node.arr_len * sizeof(int))
        memcpy(arr.arr, node.arr, node.arr_len * sizeof(int))
        arr.len = node.arr_len
        arr.size = node.arr_len
        result[prefix] = arr
    trie_edge_to_map(node.root, result, prefix, include_zeros)

cdef trie_edge_to_map(_Trie_Edge* edge, result, prefix, int include_zeros):
    if edge != NULL:
        trie_edge_to_map(edge.smaller, result, prefix, include_zeros)
        trie_edge_to_map(edge.bigger, result, prefix, include_zeros)
        prefix = prefix + (edge.val,)
        trie_node_to_map(edge.node, result, prefix, include_zeros)

cdef class TrieMap:

    cdef _Trie_Node** root
    cdef int V

    def __cinit__(self, int alphabet_size):
        self.V = alphabet_size
        self.root = <_Trie_Node**> malloc(self.V * sizeof(_Trie_Node*))
        memset(self.root, 0, self.V * sizeof(_Trie_Node*))


    def __dealloc__(self):
        cdef int i
        for i from 0 <= i < self.V:
            if self.root[i] != NULL:
                free_trie_node(self.root[i])
        free(self.root)


    def insert(self, pattern):
        cdef int* p
        cdef int i, l
        l = len(pattern)
        p = <int*> malloc(l*sizeof(int))
        for i from 0 <= i < l:
            p[i] = pattern[i]
        self._insert(p,l)
        free(p)


    cdef _Trie_Node* _insert(self, int* pattern, int pattern_len):
        cdef int i
        cdef _Trie_Node* node
        if self.root[pattern[0]] == NULL:
            self.root[pattern[0]] = new_trie_node()
        node = self.root[pattern[0]]
        for i from 1 <= i < pattern_len:
            node = trie_insert(node, pattern[i])
        return node

    def contains(self, pattern):
        cdef int* p
        cdef int i, l
        cdef _Trie_Node* node
        l = len(pattern)
        p = <int*> malloc(l*sizeof(int))
        for i from 0 <= i < l:
            p[i] = pattern[i]
        node = self._contains(p,l)
        free(p)
        if node == NULL:
            return False
        else:
            return True

    cdef _Trie_Node* _contains(self, int* pattern, int pattern_len):
        cdef int i
        cdef _Trie_Node* node
        node = self.root[pattern[0]]
        i = 1
        while node != NULL and i < pattern_len:
            node = trie_find(node, pattern[i])
            i = i+1
        return node

    def toMap(self, flag):
        cdef int i, include_zeros

        if flag:
            include_zeros=1
        else:
            include_zeros=0
        result = {}
        for i from 0 <= i < self.V:
            if self.root[i] != NULL:
                trie_node_to_map(self.root[i], result, (i,), include_zeros)
        return result


cdef class Precomputation:
    cdef int precompute_rank
    cdef int precompute_secondary_rank
    cdef int max_length
    cdef int max_nonterminals
    cdef int train_max_initial_size
    cdef int train_min_gap_size
    cdef precomputed_index
    cdef precomputed_collocations
    cdef read_map(self, FILE* f)
    cdef write_map(self, m, FILE* f)

    def __cinit__(self, fsarray=None, from_stats=None, from_binary=None,
            precompute_rank=1000, precompute_secondary_rank=20,
            max_length=5, max_nonterminals=2,
            train_max_initial_size=10, train_min_gap_size=2):
        self.precompute_rank = precompute_rank
        self.precompute_secondary_rank = precompute_secondary_rank
        self.max_length = max_length
        self.max_nonterminals = max_nonterminals
        self.train_max_initial_size = train_max_initial_size
        self.train_min_gap_size = train_min_gap_size
        if from_binary:
            self.read_binary(from_binary)
        elif from_stats:
            self.precompute(from_stats, fsarray)


    def read_binary(self, char* filename):
        cdef FILE* f
        f = fopen(filename, "r")
        fread(&(self.precompute_rank), sizeof(int), 1, f)
        fread(&(self.precompute_secondary_rank), sizeof(int), 1, f)
        fread(&(self.max_length), sizeof(int), 1, f)
        fread(&(self.max_nonterminals), sizeof(int), 1, f)
        fread(&(self.train_max_initial_size), sizeof(int), 1, f)
        fread(&(self.train_min_gap_size), sizeof(int), 1, f)
        self.precomputed_index = self.read_map(f)
        self.precomputed_collocations = self.read_map(f)
        fclose(f)


    def write_binary(self, char* filename):
        cdef FILE* f
        f = fopen(filename, "w")
        fwrite(&(self.precompute_rank), sizeof(int), 1, f)
        fwrite(&(self.precompute_secondary_rank), sizeof(int), 1, f)
        fwrite(&(self.max_length), sizeof(int), 1, f)
        fwrite(&(self.max_nonterminals), sizeof(int), 1, f)
        fwrite(&(self.train_max_initial_size), sizeof(int), 1, f)
        fwrite(&(self.train_min_gap_size), sizeof(int), 1, f)
        self.write_map(self.precomputed_index, f)
        self.write_map(self.precomputed_collocations, f)
        fclose(f)


    cdef write_map(self, m, FILE* f):
        cdef int i, N
        cdef IntList arr

        N = len(m)
        fwrite(&(N), sizeof(int), 1, f)
        for pattern, val in m.iteritems():
            N = len(pattern)
            fwrite(&(N), sizeof(int), 1, f)
            for word_id in pattern:
                i = word_id
                fwrite(&(i), sizeof(int), 1, f)
            arr = val
            arr.write_handle(f)


    cdef read_map(self, FILE* f):
        cdef int i, j, k, word_id, N
        cdef IntList arr

        m = {}
        fread(&(N), sizeof(int), 1, f)
        for j from 0 <= j < N:
            fread(&(i), sizeof(int), 1, f)
            key = ()
            for k from 0 <= k < i:
                fread(&(word_id), sizeof(int), 1, f)
                key = key + (word_id,)
            arr = IntList()
            arr.read_handle(f)
            m[key] = arr
        return m


    def precompute(self, stats, SuffixArray sarray):
        cdef int i, l, N, max_pattern_len, i1, l1, i2, l2, i3, l3, ptr1, ptr2, ptr3, is_super, sent_count, max_rank
        cdef DataArray darray = sarray.darray
        cdef IntList data, queue, cost_by_rank, count_by_rank
        cdef TrieMap frequent_patterns, super_frequent_patterns, collocations
        cdef _Trie_Node* node

        data = darray.data

        frequent_patterns = TrieMap(len(darray.id2word))
        super_frequent_patterns = TrieMap(len(darray.id2word))
        collocations = TrieMap(len(darray.id2word))

        I_set = set()
        J_set = set()
        J2_set = set()
        IJ_set = set()
        pattern_rank = {}

        logger.info("Precomputing frequent intersections")
        cdef float start_time = monitor_cpu()

        max_pattern_len = 0
        for rank, (_, _, phrase) in enumerate(stats):
            if rank >= self.precompute_rank:
                break
            max_pattern_len = max(max_pattern_len, len(phrase))
            frequent_patterns.insert(phrase)
            I_set.add(phrase)
            pattern_rank[phrase] = rank
            if rank < self.precompute_secondary_rank:
                super_frequent_patterns.insert(phrase)
                J_set.add(phrase)

        queue = IntList(increment=1000)

        logger.info("    Computing inverted indexes...")
        N = len(data)
        for i from 0 <= i < N:
            sa_word_id = data.arr[i]
            if sa_word_id == 1:
                queue._append(-1)
            else:
                for l from 1 <= l <= max_pattern_len:
                    node = frequent_patterns._contains(data.arr+i, l)
                    if node == NULL:
                        break
                    queue._append(i)
                    queue._append(l)
                    trie_node_data_append(node, i)

        logger.info("    Computing collocations...")
        N = len(queue)
        ptr1 = 0
        sent_count = 0
        while ptr1 < N:    # main loop
            i1 = queue.arr[ptr1]
            if i1 > -1:
                l1 = queue.arr[ptr1+1]
                ptr2 = ptr1 + 2
                while ptr2 < N:
                    i2 = queue.arr[ptr2]
                    if i2 == -1 or i2 - i1 >= self.train_max_initial_size:
                        break
                    l2 = queue.arr[ptr2+1]
                    if (i2 - i1 - l1 >= self.train_min_gap_size and
                            i2 + l2 - i1 <= self.train_max_initial_size and
                            l1+l2+1 <= self.max_length):
                        node = collocations._insert(data.arr+i1, l1)
                        node = trie_insert(node, -1)
                        for i from i2 <= i < i2+l2:
                            node = trie_insert(node, data.arr[i])
                        trie_node_data_append(node, i1)
                        trie_node_data_append(node, i2)
                        if super_frequent_patterns._contains(data.arr+i2, l2) != NULL:
                            if super_frequent_patterns._contains(data.arr+i1, l1) != NULL:
                                is_super = 1
                            else:
                                is_super = 0
                            ptr3 = ptr2 + 2
                            while ptr3 < N:
                                i3 = queue.arr[ptr3]
                                if i3 == -1 or i3 - i1 >= self.train_max_initial_size:
                                    break
                                l3 = queue.arr[ptr3+1]
                                if (i3 - i2 - l2 >= self.train_min_gap_size and
                                        i3 + l3 - i1 <= self.train_max_initial_size and
                                        l1+l2+l3+2 <= self.max_length):
                                    if is_super or super_frequent_patterns._contains(data.arr+i3, l3) != NULL:
                                        node = collocations._insert(data.arr+i1, l1)
                                        node = trie_insert(node, -1)
                                        for i from i2 <= i < i2+l2:
                                            node = trie_insert(node, data.arr[i])
                                        node = trie_insert(node, -1)
                                        for i from i3 <= i < i3+l3:
                                            node = trie_insert(node, data.arr[i])
                                        trie_node_data_append(node, i1)
                                        trie_node_data_append(node, i2)
                                        trie_node_data_append(node, i3)
                                ptr3 = ptr3 + 2
                    ptr2 = ptr2 + 2
                ptr1 = ptr1 + 2
            else:
                sent_count = sent_count + 1
                if sent_count % 10000 == 0:
                    logger.debug("        %d sentences", sent_count)
                ptr1 = ptr1 + 1

        self.precomputed_collocations = collocations.toMap(False)
        self.precomputed_index = frequent_patterns.toMap(True)

        x = 0
        for pattern1 in J_set:
            for pattern2 in J_set:
                if len(pattern1) + len(pattern2) + 1 < self.max_length:
                    combined_pattern = pattern1 + (-1,) + pattern2
                    J2_set.add(combined_pattern)

        for pattern1 in I_set:
            for pattern2 in I_set:
                x = x+1
                if len(pattern1) + len(pattern2) + 1 <= self.max_length:
                    combined_pattern = pattern1 + (-1,) + pattern2
                    IJ_set.add(combined_pattern)

        for pattern1 in I_set:
            for pattern2 in J2_set:
                x = x+2
                if len(pattern1) + len(pattern2) + 1<= self.max_length:
                    combined_pattern = pattern1 + (-1,) + pattern2
                    IJ_set.add(combined_pattern)
                    combined_pattern = pattern2 + (-1,) + pattern1
                    IJ_set.add(combined_pattern)

        N = len(pattern_rank)
        cost_by_rank = IntList(initial_len=N)
        count_by_rank = IntList(initial_len=N)
        for pattern, arr in self.precomputed_collocations.iteritems():
            if pattern not in IJ_set:
                s = ""
                for word_id in pattern:
                    if word_id == -1:
                        s = s + "X "
                    else:
                        s = s + darray.id2word[word_id] + " "
                logger.warn("ERROR: unexpected pattern %s in set of precomputed collocations", s)
            else:
                chunk = ()
                max_rank = 0
                arity = 0
                for word_id in pattern:
                    if word_id == -1:
                        max_rank = max(max_rank, pattern_rank[chunk])
                        arity = arity + 1
                        chunk = ()
                    else:
                        chunk = chunk + (word_id,)
                max_rank = max(max_rank, pattern_rank[chunk])
                cost_by_rank.arr[max_rank] = cost_by_rank.arr[max_rank] + (4*len(arr))
                count_by_rank.arr[max_rank] = count_by_rank.arr[max_rank] + (len(arr)/(arity+1))

        cumul_cost = 0
        cumul_count = 0
        for i from 0 <= i < N:
            cumul_cost = cumul_cost + cost_by_rank.arr[i]
            cumul_count = cumul_count + count_by_rank.arr[i]
            logger.debug("RANK %d\tCOUNT, COST: %d    %d\tCUMUL: %d, %d", i, count_by_rank.arr[i], cost_by_rank.arr[i], cumul_count, cumul_cost)

        num_found_patterns = len(self.precomputed_collocations)
        for pattern in IJ_set:
            if pattern not in self.precomputed_collocations:
                self.precomputed_collocations[pattern] = IntList()

        cdef float stop_time = monitor_cpu()
        logger.info("Precomputed collocations for %d patterns out of %d possible (upper bound %d)", num_found_patterns, len(self.precomputed_collocations), x)
        logger.info("Precomputed inverted index for %d patterns ", len(self.precomputed_index))
        logger.info("Precomputation took %f seconds", (stop_time - start_time))