summaryrefslogtreecommitdiff
path: root/sa-extract/precomputation.pyx
diff options
context:
space:
mode:
Diffstat (limited to 'sa-extract/precomputation.pyx')
-rw-r--r--sa-extract/precomputation.pyx478
1 files changed, 478 insertions, 0 deletions
diff --git a/sa-extract/precomputation.pyx b/sa-extract/precomputation.pyx
new file mode 100644
index 00000000..ce4c21aa
--- /dev/null
+++ b/sa-extract/precomputation.pyx
@@ -0,0 +1,478 @@
+# precomputes a set of collocations by advancing over the text.
+# warning: nasty C code
+
+import log
+import monitor
+
+cimport csuf
+cimport cdat
+cimport cintlist
+
+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 cintlist.CIntList arr
+
+ if include_zeros or node.arr_len > 0:
+ arr = cintlist.CIntList()
+ 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 __init__(self, 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:
+
+# Defined in .pxd file, here for reference:
+# 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
+
+ def __init__(self, filename, sa=None, precompute_rank=1000, precompute_secondary_rank=20, max_length=5,
+ max_nonterminals=2, train_max_initial_size=10, train_min_gap_size=2, from_binary=False):
+ 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(filename)
+ else:
+ self.precompute(filename, sa)
+
+
+ def read_binary(self, filename):
+ cdef FILE* f
+ cdef bytes bfilename = filename
+ cdef char* cfilename = bfilename
+ f = fopen(cfilename, "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, filename):
+ cdef FILE* f
+ cdef bytes bfilename = filename
+ cdef char* cfilename = bfilename
+
+ f = fopen(cfilename, "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 cintlist.CIntList 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 cintlist.CIntList 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 = cintlist.CIntList()
+ arr.read_handle(f)
+ m[key] = arr
+ return m
+
+
+ def precompute(self, filename, sa):
+ cdef int i, l, N, max_pattern_len, i1, l1, i2, l2, i3, l3, ptr1, ptr2, ptr3, is_super, sent_count, max_rank
+ cdef csuf.SuffixArray sarray
+ cdef cdat.DataArray darray
+ cdef cintlist.CIntList data, queue, cost_by_rank, count_by_rank
+ cdef TrieMap frequent_patterns, super_frequent_patterns, collocations
+ cdef _Trie_Node* node
+
+ sarray = sa
+ darray = sarray.darray
+ 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 = {}
+
+ log.writeln("Precomputing frequent intersections\n", 1)
+ start_time = monitor.cpu()
+
+ max_pattern_len = 0
+ if filename is not None:
+ precompute_file = open(filename)
+ for rank, line in enumerate(precompute_file):
+ if rank >= self.precompute_rank:
+ break
+ phrase_words = line.split()[2:]
+ phrase = ()
+ for word in phrase_words:
+ phrase = phrase + (darray.word2id[word],)
+ 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)
+ precompute_file.close()
+
+ queue = cintlist.CIntList(increment=1000)
+
+ log.writeln(" Computing inverted indexes...", 1)
+ 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)
+
+ log.writeln(" Computing collocations...", 1)
+ 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:
+ log.writeln(" %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 = cintlist.CIntList(initial_len=N)
+ count_by_rank = cintlist.CIntList(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] + " "
+ log.writeln("ERROR: unexpected pattern %s in set of precomputed collocations" % (s), 1)
+ 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]
+ log.writeln("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] = cintlist.CIntList()
+
+ stop_time = monitor.cpu()
+ log.writeln("Precomputed collocations for %d patterns out of %d possible (upper bound %d)" % (num_found_patterns,len(self.precomputed_collocations),x))
+ log.writeln("Precomputed inverted index for %d patterns " % len(self.precomputed_index))
+ log.writeln("Precomputation took %f seconds" % (stop_time - start_time))
+ log.writeln("Detailed statistics:")
+
+
+
+
+
+
+
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-29 09:07:45 +0000