# Implementation of the algorithms described in # Lopez, EMNLP-CoNLL 2007 # Much faster than the Python numbers reported there. # Note to reader: this code is closer to C than Python import gc import itertools from libc.stdlib cimport malloc, realloc, free from libc.string cimport memset, memcpy from libc.math cimport fmod, ceil, floor, log from collections import defaultdict, Counter, namedtuple FeatureContext = namedtuple('FeatureContext', ['fphrase', 'ephrase', 'paircount', 'fcount', 'fsample_count', 'input_span', 'matches', 'input_match', 'test_sentence', 'f_text', 'e_text', 'meta' ]) cdef int PRECOMPUTE = 0 cdef int MERGE = 1 cdef int BAEZA_YATES = 2 # NOTE: was encoded as a non-terminal in the previous version cdef int EPSILON = sym_fromstring('*EPS*', True) cdef class TrieNode: cdef public children def __cinit__(self): self.children = {} cdef class ExtendedTrieNode(TrieNode): cdef public phrase cdef public phrase_location cdef public suffix_link def __cinit__(self, phrase=None, phrase_location=None, suffix_link=None): self.phrase = phrase self.phrase_location = phrase_location self.suffix_link = suffix_link cdef class TrieTable: cdef public int extended cdef public int count cdef public root def __cinit__(self, extended=False): self.count = 0 self.extended = extended if extended: self.root = ExtendedTrieNode() else: self.root = TrieNode() # linked list structure for storing matches in BaselineRuleFactory cdef struct match_node: int* match match_node* next # encodes information needed to find a (hierarchical) phrase # in the text. If phrase is contiguous, that's just a range # in the suffix array; if discontiguous, it is the set of # actual locations (packed into an array) cdef class PhraseLocation: cdef int sa_low cdef int sa_high cdef int arr_low cdef int arr_high cdef IntList arr cdef int num_subpatterns # returns true if sent_id is contained cdef int contains(self, int sent_id): return 1 def __cinit__(self, int sa_low=-1, int sa_high=-1, int arr_low=-1, int arr_high=-1, arr=None, int num_subpatterns=1): self.sa_low = sa_low self.sa_high = sa_high self.arr_low = arr_low self.arr_high = arr_high self.arr = arr self.num_subpatterns = num_subpatterns cdef class Sampler: '''A Sampler implements a logic for choosing samples from a population range''' cdef int sample_size cdef IntList sa def __cinit__(self, int sample_size, SuffixArray fsarray): self.sample_size = sample_size self.sa = fsarray.sa if sample_size > 0: logger.info("Sampling strategy: uniform, max sample size = %d", sample_size) else: logger.info("Sampling strategy: no sampling") def sample(self, PhraseLocation phrase_location): '''Returns a sample of the locations for the phrase. If there are less than self.sample_size locations, return all of them; otherwise, return up to self.sample_size locations. In the latter case, we choose to sample UNIFORMLY -- that is, the locations are chosen at uniform intervals over the entire set, rather than randomly. This makes the algorithm deterministic, which is good for things like MERT''' cdef IntList sample cdef double i, stepsize cdef int num_locations, val, j sample = IntList() if phrase_location.arr is None: num_locations = phrase_location.sa_high - phrase_location.sa_low if self.sample_size == -1 or num_locations <= self.sample_size: sample._extend_arr(self.sa.arr + phrase_location.sa_low, num_locations) else: stepsize = float(num_locations)/float(self.sample_size) i = phrase_location.sa_low while i < phrase_location.sa_high and sample.len < self.sample_size: '''Note: int(i) not guaranteed to have the desired effect, according to the python documentation''' if fmod(i,1.0) > 0.5: val = int(ceil(i)) else: val = int(floor(i)) sample._append(self.sa.arr[val]) i = i + stepsize else: num_locations = (phrase_location.arr_high - phrase_location.arr_low) / phrase_location.num_subpatterns if self.sample_size == -1 or num_locations <= self.sample_size: sample = phrase_location.arr else: stepsize = float(num_locations)/float(self.sample_size) i = phrase_location.arr_low while i < num_locations and sample.len < self.sample_size * phrase_location.num_subpatterns: '''Note: int(i) not guaranteed to have the desired effect, according to the python documentation''' if fmod(i,1.0) > 0.5: val = int(ceil(i)) else: val = int(floor(i)) j = phrase_location.arr_low + (val*phrase_location.num_subpatterns) sample._extend_arr(phrase_location.arr.arr + j, phrase_location.num_subpatterns) i = i + stepsize return sample # struct used to encapsulate a single matching cdef struct Matching: int* arr int start int end int sent_id int size cdef void assign_matching(Matching* m, int* arr, int start, int step, int* sent_id_arr): m.arr = arr m.start = start m.end = start + step m.sent_id = sent_id_arr[arr[start]] m.size = step cdef int* append_combined_matching(int* arr, Matching* loc1, Matching* loc2, int offset_by_one, int num_subpatterns, int* result_len): cdef int i, new_len new_len = result_len[0] + num_subpatterns arr = realloc(arr, new_len*sizeof(int)) for i from 0 <= i < loc1.size: arr[result_len[0]+i] = loc1.arr[loc1.start+i] if num_subpatterns > loc1.size: arr[new_len-1] = loc2.arr[loc2.end-1] result_len[0] = new_len return arr cdef int* extend_arr(int* arr, int* arr_len, int* appendix, int appendix_len): cdef int new_len new_len = arr_len[0] + appendix_len arr = realloc(arr, new_len*sizeof(int)) memcpy(arr+arr_len[0], appendix, appendix_len*sizeof(int)) arr_len[0] = new_len return arr cdef int median(int low, int high, int step): return low + (((high - low)/step)/2)*step cdef void find_comparable_matchings(int low, int high, int* arr, int step, int loc, int* loc_minus, int* loc_plus): # Returns (minus, plus) indices for the portion of the array # in which all matchings have the same first index as the one # starting at loc loc_plus[0] = loc + step while loc_plus[0] < high and arr[loc_plus[0]] == arr[loc]: loc_plus[0] = loc_plus[0] + step loc_minus[0] = loc while loc_minus[0]-step >= low and arr[loc_minus[0]-step] == arr[loc]: loc_minus[0] = loc_minus[0] - step cdef class HieroCachingRuleFactory: '''This RuleFactory implements a caching method using TrieTable, which makes phrase generation somewhat speedier -- phrases only need to be extracted once (however, it is quite possible they need to be scored for each input sentence, for contextual models)''' cdef TrieTable rules cdef Sampler sampler cdef Scorer scorer cdef int max_chunks cdef int max_target_chunks cdef int max_length cdef int max_target_length cdef int max_nonterminals cdef int max_initial_size cdef int train_max_initial_size cdef int min_gap_size cdef int train_min_gap_size cdef int category cdef precomputed_index cdef precomputed_collocations cdef precompute_file cdef max_rank cdef int precompute_rank, precompute_secondary_rank cdef bint use_baeza_yates cdef bint use_index cdef bint use_collocations cdef float by_slack_factor cdef prev_norm_prefix cdef float extract_time cdef SuffixArray fsa cdef DataArray fda cdef DataArray eda cdef Alignment alignment cdef IntList eid2symid cdef IntList fid2symid cdef bint tight_phrases cdef bint require_aligned_terminal cdef bint require_aligned_chunks cdef IntList findexes cdef IntList findexes1 def __cinit__(self, # compiled alignment object (REQUIRED) Alignment alignment, # parameter for double-binary search; doesn't seem to matter much float by_slack_factor=1.0, # name of generic nonterminal used by Hiero char* category="[X]", # maximum number of contiguous chunks of terminal symbols in RHS of a rule. If None, defaults to max_nonterminals+1 max_chunks=None, # maximum span of a grammar rule in TEST DATA unsigned max_initial_size=10, # maximum number of symbols (both T and NT) allowed in a rule unsigned max_length=5, # maximum number of nonterminals allowed in a rule (set >2 at your own risk) unsigned max_nonterminals=2, # maximum number of contiguous chunks of terminal symbols in target-side RHS of a rule. If None, defaults to max_nonterminals+1 max_target_chunks=None, # maximum number of target side symbols (both T and NT) allowed in a rule. If None, defaults to max_initial_size max_target_length=None, # minimum span of a nonterminal in the RHS of a rule in TEST DATA unsigned min_gap_size=2, # filename of file containing precomputed collocations precompute_file=None, # maximum frequency rank of patterns used to compute triples (don't set higher than 20). unsigned precompute_secondary_rank=20, # maximum frequency rank of patterns used to compute collocations (no need to set higher than maybe 200-300) unsigned precompute_rank=100, # require extracted rules to have at least one aligned word bint require_aligned_terminal=True, # require each contiguous chunk of extracted rules to have at least one aligned word bint require_aligned_chunks=False, # maximum span of a grammar rule extracted from TRAINING DATA unsigned train_max_initial_size=10, # minimum span of an RHS nonterminal in a rule extracted from TRAINING DATA unsigned train_min_gap_size=2, # False if phrases should be loose (better but slower), True otherwise bint tight_phrases=True, # True to require use of double-binary alg, false otherwise bint use_baeza_yates=True, # True to enable used of precomputed collocations bint use_collocations=True, # True to enable use of precomputed inverted indices bint use_index=True): '''Note: we make a distinction between the min_gap_size and max_initial_size used in test and train. The latter are represented by train_min_gap_size and train_max_initial_size, respectively. This is because Chiang's model does not require them to be the same, therefore we don't either.''' self.rules = TrieTable(True) # cache self.rules.root = ExtendedTrieNode(phrase_location=PhraseLocation()) if alignment is None: raise Exception("Must specify an alignment object") self.alignment = alignment # grammar parameters and settings # NOTE: setting max_nonterminals > 2 is not currently supported in Hiero self.max_length = max_length self.max_nonterminals = max_nonterminals self.max_initial_size = max_initial_size self.train_max_initial_size = train_max_initial_size self.min_gap_size = min_gap_size self.train_min_gap_size = train_min_gap_size self.category = sym_fromstring(category, False) if max_chunks is None: self.max_chunks = self.max_nonterminals + 1 else: self.max_chunks = max_chunks if max_target_chunks is None: self.max_target_chunks = self.max_nonterminals + 1 else: self.max_target_chunks = max_target_chunks if max_target_length is None: self.max_target_length = max_initial_size else: self.max_target_length = max_target_length # algorithmic parameters and settings self.precomputed_collocations = {} self.precomputed_index = {} self.use_index = use_index self.use_collocations = use_collocations self.max_rank = {} self.precompute_file = precompute_file self.precompute_rank = precompute_rank self.precompute_secondary_rank = precompute_secondary_rank self.use_baeza_yates = use_baeza_yates self.by_slack_factor = by_slack_factor self.tight_phrases = tight_phrases if require_aligned_chunks: # one condition is a stronger version of the other. self.require_aligned_chunks = self.require_aligned_terminal = True elif require_aligned_terminal: self.require_aligned_chunks = False self.require_aligned_terminal = True else: self.require_aligned_chunks = self.require_aligned_terminal = False # diagnostics self.prev_norm_prefix = () self.findexes = IntList(initial_len=10) self.findexes1 = IntList(initial_len=10) def configure(self, SuffixArray fsarray, DataArray edarray, Sampler sampler, Scorer scorer): '''This gives the RuleFactory access to the Context object. Here we also use it to precompute the most expensive intersections in the corpus quickly.''' self.fsa = fsarray self.fda = fsarray.darray self.eda = edarray self.fid2symid = self.set_idmap(self.fda) self.eid2symid = self.set_idmap(self.eda) self.precompute() self.sampler = sampler self.scorer = scorer cdef set_idmap(self, DataArray darray): cdef int word_id, new_word_id, N cdef IntList idmap N = len(darray.voc) idmap = IntList(initial_len=N) for word_id from 0 <= word_id < N: new_word_id = sym_fromstring(darray.voc.id2word[word_id], True) idmap.arr[word_id] = new_word_id return idmap def pattern2phrase(self, pattern): # pattern is a tuple, which we must convert to a hiero Phrase result = () arity = 0 for word_id in pattern: if word_id == -1: arity = arity + 1 new_id = sym_setindex(self.category, arity) else: new_id = sym_fromstring(self.fda.voc.id2word[word_id], True) result = result + (new_id,) return Phrase(result) def pattern2phrase_plus(self, pattern): # returns a list containing both the pattern, and pattern # suffixed/prefixed with the NT category. patterns = [] result = () arity = 0 for word_id in pattern: if word_id == -1: arity = arity + 1 new_id = sym_setindex(self.category, arity) else: new_id = sym_fromstring(self.fda.voc.id2word[word_id], True) result = result + (new_id,) patterns.append(Phrase(result)) patterns.append(Phrase(result + (sym_setindex(self.category, 1),))) patterns.append(Phrase((sym_setindex(self.category, 1),) + result)) return patterns def precompute(self): cdef Precomputation pre if self.precompute_file is not None: start_time = monitor_cpu() logger.info("Reading precomputed data from file %s... ", self.precompute_file) pre = Precomputation(from_binary=self.precompute_file) # check parameters of precomputation -- some are critical and some are not if pre.max_nonterminals != self.max_nonterminals: logger.warn("Precomputation done with max nonterminals %d, decoder uses %d", pre.max_nonterminals, self.max_nonterminals) if pre.max_length != self.max_length: logger.warn("Precomputation done with max terminals %d, decoder uses %d", pre.max_length, self.max_length) if pre.train_max_initial_size != self.train_max_initial_size: raise Exception("Precomputation done with max initial size %d, decoder uses %d" % (pre.train_max_initial_size, self.train_max_initial_size)) if pre.train_min_gap_size != self.train_min_gap_size: raise Exception("Precomputation done with min gap size %d, decoder uses %d" % (pre.train_min_gap_size, self.train_min_gap_size)) if self.use_index: logger.info("Converting %d hash keys on precomputed inverted index... ", len(pre.precomputed_index)) for pattern, arr in pre.precomputed_index.iteritems(): phrases = self.pattern2phrase_plus(pattern) for phrase in phrases: self.precomputed_index[phrase] = arr if self.use_collocations: logger.info("Converting %d hash keys on precomputed collocations... ", len(pre.precomputed_collocations)) for pattern, arr in pre.precomputed_collocations.iteritems(): phrase = self.pattern2phrase(pattern) self.precomputed_collocations[phrase] = arr stop_time = monitor_cpu() logger.info("Processing precomputations took %f seconds", stop_time - start_time) def get_precomputed_collocation(self, phrase): if phrase in self.precomputed_collocations: arr = self.precomputed_collocations[phrase] return PhraseLocation(arr=arr, arr_low=0, arr_high=len(arr), num_subpatterns=phrase.arity()+1) return None cdef int* baeza_yates_helper(self, int low1, int high1, int* arr1, int step1, int low2, int high2, int* arr2, int step2, int offset_by_one, int len_last, int num_subpatterns, int* result_len): cdef int i1, i2, j1, j2, med1, med2, med1_plus, med1_minus, med2_minus, med2_plus cdef int d_first, qsetsize, dsetsize, tmp, search_low, search_high cdef int med_result_len, low_result_len, high_result_len cdef long comparison cdef int* result cdef int* low_result cdef int* med_result cdef int* high_result cdef Matching loc1, loc2 result = malloc(0*sizeof(int*)) d_first = 0 if high1 - low1 > high2 - low2: d_first = 1 # First, check to see if we are at any of the recursive base cases # Case 1: one of the sets is empty if low1 >= high1 or low2 >= high2: return result # Case 2: sets are non-overlapping assign_matching(&loc1, arr1, high1-step1, step1, self.fda.sent_id.arr) assign_matching(&loc2, arr2, low2, step2, self.fda.sent_id.arr) if self.compare_matchings(&loc1, &loc2, offset_by_one, len_last) == -1: return result assign_matching(&loc1, arr1, low1, step1, self.fda.sent_id.arr) assign_matching(&loc2, arr2, high2-step2, step2, self.fda.sent_id.arr) if self.compare_matchings(&loc1, &loc2, offset_by_one, len_last) == 1: return result # Case 3: query set and data set do not meet size mismatch constraints; # We use mergesort instead in this case qsetsize = (high1-low1) / step1 dsetsize = (high2-low2) / step2 if d_first: tmp = qsetsize qsetsize = dsetsize dsetsize = tmp if self.by_slack_factor * qsetsize * log(dsetsize) / log(2) > dsetsize: free(result) return self.merge_helper(low1, high1, arr1, step1, low2, high2, arr2, step2, offset_by_one, len_last, num_subpatterns, result_len) # binary search. There are two flavors, depending on # whether the queryset or dataset is first if d_first: med2 = median(low2, high2, step2) assign_matching(&loc2, arr2, med2, step2, self.fda.sent_id.arr) search_low = low1 search_high = high1 while search_low < search_high: med1 = median(search_low, search_high, step1) find_comparable_matchings(low1, high1, arr1, step1, med1, &med1_minus, &med1_plus) comparison = self.compare_matchings_set(med1_minus, med1_plus, arr1, step1, &loc2, offset_by_one, len_last) if comparison == -1: search_low = med1_plus elif comparison == 1: search_high = med1_minus else: break else: med1 = median(low1, high1, step1) find_comparable_matchings(low1, high1, arr1, step1, med1, &med1_minus, &med1_plus) search_low = low2 search_high = high2 while search_low < search_high: med2 = median(search_low, search_high, step2) assign_matching(&loc2, arr2, med2, step2, self.fda.sent_id.arr) comparison = self.compare_matchings_set(med1_minus, med1_plus, arr1, step1, &loc2, offset_by_one, len_last) if comparison == -1: search_high = med2 elif comparison == 1: search_low = med2 + step2 else: break med_result_len = 0 med_result = malloc(0*sizeof(int*)) if search_high > search_low: # Then there is a match for the median element of Q # What we want to find is the group of all bindings in the first set # s.t. their first element == the first element of med1. Then we # want to store the bindings for all of those elements. We can # subsequently throw all of them away. med2_minus = med2 med2_plus = med2 + step2 i1 = med1_minus while i1 < med1_plus: assign_matching(&loc1, arr1, i1, step1, self.fda.sent_id.arr) while med2_minus-step2 >= low2: assign_matching(&loc2, arr2, med2_minus-step2, step2, self.fda.sent_id.arr) if self.compare_matchings(&loc1, &loc2, offset_by_one, len_last) < 1: med2_minus = med2_minus - step2 else: break i2 = med2_minus while i2 < high2: assign_matching(&loc2, arr2, i2, step2, self.fda.sent_id.arr) comparison = self.compare_matchings(&loc1, &loc2, offset_by_one, len_last) if comparison == 0: pass med_result = append_combined_matching(med_result, &loc1, &loc2, offset_by_one, num_subpatterns, &med_result_len) if comparison == -1: break i2 = i2 + step2 if i2 > med2_plus: med2_plus = i2 i1 = i1 + step1 tmp = med1_minus med1_minus = med1_plus med1_plus = tmp else: # No match; need to figure out the point of division in D and Q med2_minus = med2 med2_plus = med2 if d_first: med2_minus = med2_minus + step2 if comparison == -1: med1_minus = med1_plus if comparison == 1: med1_plus = med1_minus else: tmp = med1_minus med1_minus = med1_plus med1_plus = tmp if comparison == 1: med2_minus = med2_minus + step2 med2_plus = med2_plus + step2 low_result_len = 0 low_result = self.baeza_yates_helper(low1, med1_plus, arr1, step1, low2, med2_plus, arr2, step2, offset_by_one, len_last, num_subpatterns, &low_result_len) high_result_len = 0 high_result = self.baeza_yates_helper(med1_minus, high1, arr1, step1, med2_minus, high2, arr2, step2, offset_by_one, len_last, num_subpatterns, &high_result_len) result = extend_arr(result, result_len, low_result, low_result_len) result = extend_arr(result, result_len, med_result, med_result_len) result = extend_arr(result, result_len, high_result, high_result_len) free(low_result) free(med_result) free(high_result) return result cdef long compare_matchings_set(self, int i1_minus, int i1_plus, int* arr1, int step1, Matching* loc2, int offset_by_one, int len_last): """ Compares a *set* of bindings, all with the same first element, to a single binding. Returns -1 if all comparisons == -1, 1 if all comparisons == 1, and 0 otherwise. """ cdef int i1, comparison, prev_comparison cdef Matching l1_stack cdef Matching* loc1 loc1 = &l1_stack i1 = i1_minus while i1 < i1_plus: assign_matching(loc1, arr1, i1, step1, self.fda.sent_id.arr) comparison = self.compare_matchings(loc1, loc2, offset_by_one, len_last) if comparison == 0: prev_comparison = 0 break elif i1 == i1_minus: prev_comparison = comparison else: if comparison != prev_comparison: prev_comparison = 0 break i1 = i1 + step1 return prev_comparison cdef long compare_matchings(self, Matching* loc1, Matching* loc2, int offset_by_one, int len_last): cdef int i if loc1.sent_id > loc2.sent_id: return 1 if loc2.sent_id > loc1.sent_id: return -1 if loc1.size == 1 and loc2.size == 1: if loc2.arr[loc2.start] - loc1.arr[loc1.start] <= self.train_min_gap_size: return 1 elif offset_by_one: for i from 1 <= i < loc1.size: if loc1.arr[loc1.start+i] > loc2.arr[loc2.start+i-1]: return 1 if loc1.arr[loc1.start+i] < loc2.arr[loc2.start+i-1]: return -1 else: if loc1.arr[loc1.start]+1 > loc2.arr[loc2.start]: return 1 if loc1.arr[loc1.start]+1 < loc2.arr[loc2.start]: return -1 for i from 1 <= i < loc1.size: if loc1.arr[loc1.start+i] > loc2.arr[loc2.start+i]: return 1 if loc1.arr[loc1.start+i] < loc2.arr[loc2.start+i]: return -1 if loc2.arr[loc2.end-1] + len_last - loc1.arr[loc1.start] > self.train_max_initial_size: return -1 return 0 cdef int* merge_helper(self, int low1, int high1, int* arr1, int step1, int low2, int high2, int* arr2, int step2, int offset_by_one, int len_last, int num_subpatterns, int* result_len): cdef int i1, i2, j1, j2 cdef long comparison cdef int* result cdef Matching loc1, loc2 result_len[0] = 0 result = malloc(0*sizeof(int)) i1 = low1 i2 = low2 while i1 < high1 and i2 < high2: # First, pop all unneeded loc2's off the stack assign_matching(&loc1, arr1, i1, step1, self.fda.sent_id.arr) while i2 < high2: assign_matching(&loc2, arr2, i2, step2, self.fda.sent_id.arr) if self.compare_matchings(&loc1, &loc2, offset_by_one, len_last) == 1: i2 = i2 + step2 else: break # Next: process all loc1's with the same starting val j1 = i1 while i1 < high1 and arr1[j1] == arr1[i1]: assign_matching(&loc1, arr1, i1, step1, self.fda.sent_id.arr) j2 = i2 while j2 < high2: assign_matching(&loc2, arr2, j2, step2, self.fda.sent_id.arr) comparison = self.compare_matchings(&loc1, &loc2, offset_by_one, len_last) if comparison == 0: result = append_combined_matching(result, &loc1, &loc2, offset_by_one, num_subpatterns, result_len) if comparison == 1: pass if comparison == -1: break else: j2 = j2 + step2 i1 = i1 + step1 return result cdef void sort_phrase_loc(self, IntList arr, PhraseLocation loc, Phrase phrase): cdef int i, j cdef VEB veb cdef IntList result if phrase in self.precomputed_index: loc.arr = self.precomputed_index[phrase] else: loc.arr = IntList(initial_len=loc.sa_high-loc.sa_low) veb = VEB(arr.len) for i from loc.sa_low <= i < loc.sa_high: veb._insert(arr.arr[i]) i = veb.veb.min_val for j from 0 <= j < loc.sa_high-loc.sa_low: loc.arr.arr[j] = i i = veb._findsucc(i) loc.arr_low = 0 loc.arr_high = loc.arr.len cdef intersect_helper(self, Phrase prefix, Phrase suffix, PhraseLocation prefix_loc, PhraseLocation suffix_loc, int algorithm): cdef IntList arr1, arr2, result cdef int low1, high1, step1, low2, high2, step2, offset_by_one, len_last, num_subpatterns, result_len cdef int* result_ptr result_len = 0 if sym_isvar(suffix[0]): offset_by_one = 1 else: offset_by_one = 0 len_last = len(suffix.getchunk(suffix.arity())) if prefix_loc.arr is None: self.sort_phrase_loc(self.fsa.sa, prefix_loc, prefix) arr1 = prefix_loc.arr low1 = prefix_loc.arr_low high1 = prefix_loc.arr_high step1 = prefix_loc.num_subpatterns if suffix_loc.arr is None: self.sort_phrase_loc(self.fsa.sa, suffix_loc, suffix) arr2 = suffix_loc.arr low2 = suffix_loc.arr_low high2 = suffix_loc.arr_high step2 = suffix_loc.num_subpatterns num_subpatterns = prefix.arity()+1 if algorithm == MERGE: result_ptr = self.merge_helper(low1, high1, arr1.arr, step1, low2, high2, arr2.arr, step2, offset_by_one, len_last, num_subpatterns, &result_len) else: result_ptr = self.baeza_yates_helper(low1, high1, arr1.arr, step1, low2, high2, arr2.arr, step2, offset_by_one, len_last, num_subpatterns, &result_len) if result_len == 0: free(result_ptr) return None else: result = IntList() free(result.arr) result.arr = result_ptr result.len = result_len result.size = result_len return PhraseLocation(arr_low=0, arr_high=result_len, arr=result, num_subpatterns=num_subpatterns) cdef loc2str(self, PhraseLocation loc): cdef int i, j result = "{" i = 0 while i < loc.arr_high: result = result + "(" for j from i <= j < i + loc.num_subpatterns: result = result + ("%d " %loc.arr[j]) result = result + ")" i = i + loc.num_subpatterns result = result + "}" return result cdef PhraseLocation intersect(self, prefix_node, suffix_node, Phrase phrase): cdef Phrase prefix, suffix cdef PhraseLocation prefix_loc, suffix_loc, result prefix = prefix_node.phrase suffix = suffix_node.phrase prefix_loc = prefix_node.phrase_location suffix_loc = suffix_node.phrase_location result = self.get_precomputed_collocation(phrase) if result is not None: intersect_method = "precomputed" if result is None: if self.use_baeza_yates: result = self.intersect_helper(prefix, suffix, prefix_loc, suffix_loc, BAEZA_YATES) intersect_method="double binary" else: result = self.intersect_helper(prefix, suffix, prefix_loc, suffix_loc, MERGE) intersect_method="merge" return result def advance(self, frontier, res, fwords): cdef unsigned na nf = [] for (toskip, (i, alt, pathlen)) in frontier: spanlen = fwords[i][alt][2] if (toskip == 0): res.append((i, alt, pathlen)) ni = i + spanlen if (ni < len(fwords) and (pathlen + 1) < self.max_initial_size): for na in range(len(fwords[ni])): nf.append((toskip - 1, (ni, na, pathlen + 1))) if (len(nf) > 0): return self.advance(nf, res, fwords) else: return res def get_all_nodes_isteps_away(self, skip, i, spanlen, pathlen, fwords, next_states, reachable_buffer): cdef unsigned alt_it frontier = [] if (i+spanlen+skip >= len(next_states)): return frontier key = tuple([i,spanlen]) reachable = [] if (key in reachable_buffer): reachable = reachable_buffer[key] else: reachable = self.reachable(fwords, i, spanlen) reachable_buffer[key] = reachable for nextreachable in reachable: for next_id in next_states[nextreachable]: jump = self.shortest(fwords,i,next_id) if jump < skip: continue if pathlen+jump <= self.max_initial_size: for alt_id in range(len(fwords[next_id])): if (fwords[next_id][alt_id][0] != EPSILON): newel = (next_id,alt_id,pathlen+jump) if newel not in frontier: frontier.append((next_id,alt_id,pathlen+jump)) return frontier def reachable(self, fwords, ifrom, dist): ret = [] if (ifrom >= len(fwords)): return ret for alt_id in range(len(fwords[ifrom])): if (fwords[ifrom][alt_id][0] == EPSILON): ret.extend(self.reachable(fwords,ifrom+fwords[ifrom][alt_id][2],dist)) else: if (dist==0): if (ifrom not in ret): ret.append(ifrom) else: for ifromchild in self.reachable(fwords,ifrom+fwords[ifrom][alt_id][2],dist-1): if (ifromchild not in ret): ret.append(ifromchild) return ret def shortest(self, fwords, ifrom, ito): cdef unsigned alt_id min = 1000 if (ifrom > ito): return min if (ifrom == ito): return 0 for alt_id in range(len(fwords[ifrom])): currmin = self.shortest(fwords,ifrom+fwords[ifrom][alt_id][2],ito) if (fwords[ifrom][alt_id][0] != EPSILON): currmin += 1 if (currmin 0: curr = candidate.pop() if curr[0] >= len(_columns): continue if curr[0] not in result and min_dist <= curr[1] <= self.max_initial_size: result.append(curr[0]); curr_col = _columns[curr[0]] for alt in curr_col: next_id = curr[0]+alt[2] jump = 1 if (alt[0] == EPSILON): jump = 0 if next_id not in result and min_dist <= curr[1]+jump <= self.max_initial_size+1: candidate.append([next_id,curr[1]+jump]) return sorted(result); def input(self, fwords, meta): '''When this function is called on the RuleFactory, it looks up all of the rules that can be used to translate the input sentence''' cdef int i, j, k, flen, arity, num_subpatterns, num_samples, alt, alt_id, nualt cdef float start_time cdef PhraseLocation phrase_location cdef IntList sample, chunklen cdef Matching matching cdef Phrase hiero_phrase flen = len(fwords) start_time = monitor_cpu() self.extract_time = 0.0 nodes_isteps_away_buffer = {} hit = 0 reachable_buffer = {} # Do not cache between sentences self.rules.root = ExtendedTrieNode(phrase_location=PhraseLocation()) frontier = [] for i in range(len(fwords)): for alt in range(0, len(fwords[i])): if fwords[i][alt][0] != EPSILON: frontier.append((i, i, (i,), alt, 0, self.rules.root, (), False)) xroot = None x1 = sym_setindex(self.category, 1) if x1 in self.rules.root.children: xroot = self.rules.root.children[x1] else: xroot = ExtendedTrieNode(suffix_link=self.rules.root, phrase_location=PhraseLocation()) self.rules.root.children[x1] = xroot for i in range(self.min_gap_size, len(fwords)): for alt in range(0, len(fwords[i])): if fwords[i][alt][0] != EPSILON: frontier.append((i-self.min_gap_size, i, (i,), alt, self.min_gap_size, xroot, (x1,), True)) next_states = [] for i in range(len(fwords)): next_states.append(self.get_next_states(fwords,i,self.min_gap_size)) while len(frontier) > 0: new_frontier = [] for k, i, input_match, alt, pathlen, node, prefix, is_shadow_path in frontier: word_id = fwords[i][alt][0] spanlen = fwords[i][alt][2] # TODO get rid of k -- pathlen is replacing it if word_id == EPSILON: # skipping because word_id is epsilon if i+spanlen >= len(fwords): continue for nualt in range(0,len(fwords[i+spanlen])): frontier.append((k, i+spanlen, input_match, nualt, pathlen, node, prefix, is_shadow_path)) continue phrase = prefix + (word_id,) hiero_phrase = Phrase(phrase) arity = hiero_phrase.arity() lookup_required = False if word_id in node.children: if node.children[word_id] is None: # Path dead-ends at this node continue else: # Path continues at this node node = node.children[word_id] else: if node.suffix_link is None: # Current node is root; lookup required lookup_required = True else: if word_id in node.suffix_link.children: if node.suffix_link.children[word_id] is None: # Suffix link reports path is dead end node.children[word_id] = None continue else: # Suffix link indicates lookup is reqired lookup_required = True else: #ERROR: We never get here raise Exception("Keyword trie error") # checking whether lookup_required if lookup_required: new_node = None if is_shadow_path: # Extending shadow path # on the shadow path we don't do any search, we just use info from suffix link new_node = ExtendedTrieNode(phrase_location=node.suffix_link.children[word_id].phrase_location, suffix_link=node.suffix_link.children[word_id], phrase=hiero_phrase) else: if arity > 0: # Intersecting because of arity > 0 phrase_location = self.intersect(node, node.suffix_link.children[word_id], hiero_phrase) else: # Suffix array search phrase_location = node.phrase_location sa_range = self.fsa.lookup(sym_tostring(phrase[-1]), len(phrase)-1, phrase_location.sa_low, phrase_location.sa_high) if sa_range is not None: phrase_location = PhraseLocation(sa_low=sa_range[0], sa_high=sa_range[1]) else: phrase_location = None if phrase_location is None: node.children[word_id] = None # Search failed continue # Search succeeded suffix_link = self.rules.root if node.suffix_link is not None: suffix_link = node.suffix_link.children[word_id] new_node = ExtendedTrieNode(phrase_location=phrase_location, suffix_link=suffix_link, phrase=hiero_phrase) node.children[word_id] = new_node node = new_node '''Automatically add a trailing X node, if allowed -- This should happen before we get to extraction (so that the node will exist if needed)''' if arity < self.max_nonterminals: xcat_index = arity+1 xcat = sym_setindex(self.category, xcat_index) suffix_link_xcat_index = xcat_index if is_shadow_path: suffix_link_xcat_index = xcat_index-1 suffix_link_xcat = sym_setindex(self.category, suffix_link_xcat_index) node.children[xcat] = ExtendedTrieNode(phrase_location=node.phrase_location, suffix_link=node.suffix_link.children[suffix_link_xcat], phrase= Phrase(phrase + (xcat,))) # sample from range if not is_shadow_path: sample = self.sampler.sample(node.phrase_location) num_subpatterns = ( node.phrase_location).num_subpatterns chunklen = IntList(initial_len=num_subpatterns) for j from 0 <= j < num_subpatterns: chunklen.arr[j] = hiero_phrase.chunklen(j) extracts = [] j = 0 extract_start = monitor_cpu() while j < sample.len: extract = [] assign_matching(&matching, sample.arr, j, num_subpatterns, self.fda.sent_id.arr) loc = tuple(sample[j:j+num_subpatterns]) extract = self.extract(hiero_phrase, &matching, chunklen.arr, num_subpatterns) extracts.extend([(e, loc) for e in extract]) j = j + num_subpatterns num_samples = sample.len/num_subpatterns extract_stop = monitor_cpu() self.extract_time = self.extract_time + extract_stop - extract_start if len(extracts) > 0: fcount = Counter() fphrases = defaultdict(lambda: defaultdict(lambda: defaultdict(list))) for (f, e, count, als), loc in extracts: fcount[f] += count fphrases[f][e][als].append(loc) for f, elist in fphrases.iteritems(): for e, alslist in elist.iteritems(): alignment, max_locs = max(alslist.iteritems(), key=lambda x: len(x[1])) locs = tuple(itertools.chain.from_iterable(alslist.itervalues())) count = len(locs) scores = self.scorer.score(FeatureContext( f, e, count, fcount[f], num_samples, (k,i+spanlen), locs, input_match, fwords, self.fda, self.eda, meta)) yield Rule(self.category, f, e, scores, alignment) if len(phrase) < self.max_length and i+spanlen < len(fwords) and pathlen+1 <= self.max_initial_size: for alt_id in range(len(fwords[i+spanlen])): new_frontier.append((k, i+spanlen, input_match, alt_id, pathlen + 1, node, phrase, is_shadow_path)) num_subpatterns = arity if not is_shadow_path: num_subpatterns = num_subpatterns + 1 if len(phrase)+1 < self.max_length and arity < self.max_nonterminals and num_subpatterns < self.max_chunks: xcat = sym_setindex(self.category, arity+1) xnode = node.children[xcat] # I put spanlen=1 below key = tuple([self.min_gap_size, i, 1, pathlen]) frontier_nodes = [] if (key in nodes_isteps_away_buffer): frontier_nodes = nodes_isteps_away_buffer[key] else: frontier_nodes = self.get_all_nodes_isteps_away(self.min_gap_size, i, 1, pathlen, fwords, next_states, reachable_buffer) nodes_isteps_away_buffer[key] = frontier_nodes for (i, alt, pathlen) in frontier_nodes: new_frontier.append((k, i, input_match + (i,), alt, pathlen, xnode, phrase +(xcat,), is_shadow_path)) frontier = new_frontier stop_time = monitor_cpu() logger.info("Total time for rule lookup, extraction, and scoring = %f seconds", (stop_time - start_time)) gc.collect() logger.info(" Extract time = %f seconds", self.extract_time) cdef int find_fixpoint(self, int f_low, f_high, int* f_links_low, int* f_links_high, int* e_links_low, int* e_links_high, int e_in_low, int e_in_high, int* e_low, int* e_high, int* f_back_low, int* f_back_high, int f_sent_len, int e_sent_len, int max_f_len, int max_e_len, int min_fx_size, int min_ex_size, int max_new_x, int allow_low_x, int allow_high_x, int allow_arbitrary_x, int write_log): cdef int e_low_prev, e_high_prev, f_low_prev, f_high_prev, new_x, new_low_x, new_high_x e_low[0] = e_in_low e_high[0] = e_in_high self.find_projection(f_low, f_high, f_links_low, f_links_high, e_low, e_high) if e_low[0] == -1: # low-priority corner case: if phrase w is unaligned, # but we don't require aligned terminals, then returning # an error here might prevent extraction of allowed # rule X -> X_1 w X_2 / X_1 X_2. This is probably # not worth the bother, though. return 0 elif e_in_low != -1 and e_low[0] != e_in_low: if e_in_low - e_low[0] < min_ex_size: e_low[0] = e_in_low - min_ex_size if e_low[0] < 0: return 0 if e_high[0] - e_low[0] > max_e_len: return 0 elif e_in_high != -1 and e_high[0] != e_in_high: if e_high[0] - e_in_high < min_ex_size: e_high[0] = e_in_high + min_ex_size if e_high[0] > e_sent_len: return 0 f_back_low[0] = -1 f_back_high[0] = -1 f_low_prev = f_low f_high_prev = f_high new_x = 0 new_low_x = 0 new_high_x = 0 while True: if f_back_low[0] == -1: self.find_projection(e_low[0], e_high[0], e_links_low, e_links_high, f_back_low, f_back_high) else: self.find_projection(e_low[0], e_low_prev, e_links_low, e_links_high, f_back_low, f_back_high) self.find_projection(e_high_prev, e_high[0], e_links_low, e_links_high, f_back_low, f_back_high) if f_back_low[0] > f_low: f_back_low[0] = f_low if f_back_high[0] < f_high: f_back_high[0] = f_high if f_back_low[0] == f_low_prev and f_back_high[0] == f_high_prev: return 1 if allow_low_x == 0 and f_back_low[0] < f_low: # FAIL: f phrase is not tight return 0 if f_back_high[0] - f_back_low[0] > max_f_len: # FAIL: f back projection is too wide return 0 if allow_high_x == 0 and f_back_high[0] > f_high: # FAIL: extension on high side not allowed return 0 if f_low != f_back_low[0]: if new_low_x == 0: if new_x >= max_new_x: # FAIL: extension required on low side violates max # of gaps return 0 else: new_x = new_x + 1 new_low_x = 1 if f_low - f_back_low[0] < min_fx_size: f_back_low[0] = f_low - min_fx_size if f_back_high[0] - f_back_low[0] > max_f_len: # FAIL: extension required on low side violates max initial length return 0 if f_back_low[0] < 0: # FAIL: extension required on low side violates sentence boundary return 0 if f_high != f_back_high[0]: if new_high_x == 0: if new_x >= max_new_x: # FAIL: extension required on high side violates max # of gaps return 0 else: new_x = new_x + 1 new_high_x = 1 if f_back_high[0] - f_high < min_fx_size: f_back_high[0] = f_high + min_fx_size if f_back_high[0] - f_back_low[0] > max_f_len: # FAIL: extension required on high side violates max initial length return 0 if f_back_high[0] > f_sent_len: # FAIL: extension required on high side violates sentence boundary return 0 e_low_prev = e_low[0] e_high_prev = e_high[0] self.find_projection(f_back_low[0], f_low_prev, f_links_low, f_links_high, e_low, e_high) self.find_projection(f_high_prev, f_back_high[0], f_links_low, f_links_high, e_low, e_high) if e_low[0] == e_low_prev and e_high[0] == e_high_prev: return 1 if allow_arbitrary_x == 0: # FAIL: arbitrary expansion not permitted return 0 if e_high[0] - e_low[0] > max_e_len: # FAIL: re-projection violates sentence max phrase length return 0 f_low_prev = f_back_low[0] f_high_prev = f_back_high[0] cdef find_projection(self, int in_low, int in_high, int* in_links_low, int* in_links_high, int* out_low, int* out_high): cdef int i for i from in_low <= i < in_high: if in_links_low[i] != -1: if out_low[0] == -1 or in_links_low[i] < out_low[0]: out_low[0] = in_links_low[i] if out_high[0] == -1 or in_links_high[i] > out_high[0]: out_high[0] = in_links_high[i] cdef int* int_arr_extend(self, int* arr, int* arr_len, int* data, int data_len): cdef int new_len new_len = arr_len[0] + data_len arr = realloc(arr, new_len*sizeof(int)) memcpy(arr+arr_len[0], data, data_len*sizeof(int)) arr_len[0] = new_len return arr cdef extract_phrases(self, int e_low, int e_high, int* e_gap_low, int* e_gap_high, int* e_links_low, int num_gaps, int f_low, int f_high, int* f_gap_low, int* f_gap_high, int* f_links_low, int sent_id, int e_sent_len, int e_sent_start): cdef int i, j, k, m, n, *e_gap_order, e_x_low, e_x_high, e_x_gap_low, e_x_gap_high cdef int *e_gaps1, *e_gaps2, len1, len2, step, num_chunks cdef IntList ephr_arr cdef result result = [] len1 = 0 e_gaps1 = malloc(0) ephr_arr = IntList() e_gap_order = malloc(num_gaps*sizeof(int)) if num_gaps > 0: e_gap_order[0] = 0 for i from 1 <= i < num_gaps: for j from 0 <= j < i: if e_gap_low[i] < e_gap_low[j]: for k from j <= k < i: e_gap_order[k+1] = e_gap_order[k] e_gap_order[j] = i break else: e_gap_order[i] = i e_x_low = e_low e_x_high = e_high if not self.tight_phrases: while e_x_low > 0 and e_high - e_x_low < self.train_max_initial_size and e_links_low[e_x_low-1] == -1: e_x_low = e_x_low - 1 while e_x_high < e_sent_len and e_x_high - e_low < self.train_max_initial_size and e_links_low[e_x_high] == -1: e_x_high = e_x_high + 1 for i from e_x_low <= i <= e_low: e_gaps1 = self.int_arr_extend(e_gaps1, &len1, &i, 1) for i from 0 <= i < num_gaps: e_gaps2 = malloc(0) len2 = 0 j = e_gap_order[i] e_x_gap_low = e_gap_low[j] e_x_gap_high = e_gap_high[j] if not self.tight_phrases: while e_x_gap_low > e_x_low and e_links_low[e_x_gap_low-1] == -1: e_x_gap_low = e_x_gap_low - 1 while e_x_gap_high < e_x_high and e_links_low[e_x_gap_high] == -1: e_x_gap_high = e_x_gap_high + 1 k = 0 step = 1+(i*2) while k < len1: for m from e_x_gap_low <= m <= e_gap_low[j]: if m >= e_gaps1[k+step-1]: for n from e_gap_high[j] <= n <= e_x_gap_high: if n-m >= 1: # extractor.py doesn't restrict target-side gap length e_gaps2 = self.int_arr_extend(e_gaps2, &len2, e_gaps1+k, step) e_gaps2 = self.int_arr_extend(e_gaps2, &len2, &m, 1) e_gaps2 = self.int_arr_extend(e_gaps2, &len2, &n, 1) k = k + step free(e_gaps1) e_gaps1 = e_gaps2 len1 = len2 step = 1+(num_gaps*2) e_gaps2 = malloc(0) len2 = 0 for i from e_high <= i <= e_x_high: j = 0 while j < len1: if i - e_gaps1[j] <= self.train_max_initial_size and i >= e_gaps1[j+step-1]: e_gaps2 = self.int_arr_extend(e_gaps2, &len2, e_gaps1+j, step) e_gaps2 = self.int_arr_extend(e_gaps2, &len2, &i, 1) j = j + step free(e_gaps1) e_gaps1 = e_gaps2 len1 = len2 step = (num_gaps+1)*2 i = 0 while i < len1: ephr_arr._clear() num_chunks = 0 indexes = [] for j from 0 <= j < num_gaps+1: if e_gaps1[i+2*j] < e_gaps1[i+(2*j)+1]: num_chunks = num_chunks + 1 for k from e_gaps1[i+2*j] <= k < e_gaps1[i+(2*j)+1]: indexes.append(k) ephr_arr._append(self.eid2symid[self.eda.data.arr[e_sent_start+k]]) if j < num_gaps: indexes.append(sym_setindex(self.category, e_gap_order[j]+1)) ephr_arr._append(sym_setindex(self.category, e_gap_order[j]+1)) i = i + step if ephr_arr.len <= self.max_target_length and num_chunks <= self.max_target_chunks: result.append((Phrase(ephr_arr),indexes)) free(e_gaps1) free(e_gap_order) return result cdef IntList create_alignments(self, int* sent_links, int num_links, findexes, eindexes): cdef unsigned i cdef IntList ret = IntList() for i in range(len(findexes)): s = findexes[i] if (s<0): continue idx = 0 while (idx < num_links*2): if (sent_links[idx] == s): j = eindexes.index(sent_links[idx+1]) ret.append(i*65536+j) idx += 2 return ret cdef extract(self, Phrase phrase, Matching* matching, int* chunklen, int num_chunks): cdef int* sent_links, *e_links_low, *e_links_high, *f_links_low, *f_links_high cdef int *f_gap_low, *f_gap_high, *e_gap_low, *e_gap_high, num_gaps, gap_start cdef int i, j, k, e_i, f_i, num_links, num_aligned_chunks, met_constraints, x cdef int f_low, f_high, e_low, e_high, f_back_low, f_back_high cdef int e_sent_start, e_sent_end, f_sent_start, f_sent_end, e_sent_len, f_sent_len cdef int e_word_count, f_x_low, f_x_high, e_x_low, e_x_high, phrase_len cdef float pair_count cdef extracts, phrase_list cdef IntList fphr_arr cdef Phrase fphr cdef reason_for_failure fphr_arr = IntList() phrase_len = phrase.n extracts = [] sent_links = self.alignment._get_sent_links(matching.sent_id, &num_links) e_sent_start = self.eda.sent_index.arr[matching.sent_id] e_sent_end = self.eda.sent_index.arr[matching.sent_id+1] e_sent_len = e_sent_end - e_sent_start - 1 f_sent_start = self.fda.sent_index.arr[matching.sent_id] f_sent_end = self.fda.sent_index.arr[matching.sent_id+1] f_sent_len = f_sent_end - f_sent_start - 1 self.findexes1.reset() sofar = 0 for i in range(num_chunks): for j in range(chunklen[i]): self.findexes1.append(matching.arr[matching.start+i]+j-f_sent_start); sofar += 1 if (i+1 malloc(e_sent_len*sizeof(int)) e_links_high = malloc(e_sent_len*sizeof(int)) f_links_low = malloc(f_sent_len*sizeof(int)) f_links_high = malloc(f_sent_len*sizeof(int)) f_gap_low = malloc((num_chunks+1)*sizeof(int)) f_gap_high = malloc((num_chunks+1)*sizeof(int)) e_gap_low = malloc((num_chunks+1)*sizeof(int)) e_gap_high = malloc((num_chunks+1)*sizeof(int)) memset(f_gap_low, 0, (num_chunks+1)*sizeof(int)) memset(f_gap_high, 0, (num_chunks+1)*sizeof(int)) memset(e_gap_low, 0, (num_chunks+1)*sizeof(int)) memset(e_gap_high, 0, (num_chunks+1)*sizeof(int)) reason_for_failure = "" for i from 0 <= i < e_sent_len: e_links_low[i] = -1 e_links_high[i] = -1 for i from 0 <= i < f_sent_len: f_links_low[i] = -1 f_links_high[i] = -1 # this is really inefficient -- might be good to # somehow replace with binary search just for the f # links that we care about (but then how to look up # when we want to check something on the e side?) i = 0 while i < num_links*2: f_i = sent_links[i] e_i = sent_links[i+1] if f_links_low[f_i] == -1 or f_links_low[f_i] > e_i: f_links_low[f_i] = e_i if f_links_high[f_i] == -1 or f_links_high[f_i] < e_i + 1: f_links_high[f_i] = e_i + 1 if e_links_low[e_i] == -1 or e_links_low[e_i] > f_i: e_links_low[e_i] = f_i if e_links_high[e_i] == -1 or e_links_high[e_i] < f_i + 1: e_links_high[e_i] = f_i + 1 i = i + 2 als = [] for x in range(matching.start,matching.end): al = (matching.arr[x]-f_sent_start,f_links_low[matching.arr[x]-f_sent_start]) als.append(al) # check all source-side alignment constraints met_constraints = 1 if self.require_aligned_terminal: num_aligned_chunks = 0 for i from 0 <= i < num_chunks: for j from 0 <= j < chunklen[i]: if f_links_low[matching.arr[matching.start+i]+j-f_sent_start] > -1: num_aligned_chunks = num_aligned_chunks + 1 break if num_aligned_chunks == 0: reason_for_failure = "No aligned terminals" met_constraints = 0 if self.require_aligned_chunks and num_aligned_chunks < num_chunks: reason_for_failure = "Unaligned chunk" met_constraints = 0 if met_constraints and self.tight_phrases: # outside edge constraints are checked later for i from 0 <= i < num_chunks-1: if f_links_low[matching.arr[matching.start+i]+chunklen[i]-f_sent_start] == -1: reason_for_failure = "Gaps are not tight phrases" met_constraints = 0 break if f_links_low[matching.arr[matching.start+i+1]-1-f_sent_start] == -1: reason_for_failure = "Gaps are not tight phrases" met_constraints = 0 break f_low = matching.arr[matching.start] - f_sent_start f_high = matching.arr[matching.start + matching.size - 1] + chunklen[num_chunks-1] - f_sent_start if met_constraints: if self.find_fixpoint(f_low, f_high, f_links_low, f_links_high, e_links_low, e_links_high, -1, -1, &e_low, &e_high, &f_back_low, &f_back_high, f_sent_len, e_sent_len, self.train_max_initial_size, self.train_max_initial_size, self.train_min_gap_size, 0, self.max_nonterminals - num_chunks + 1, 1, 1, 0, 0): gap_error = 0 num_gaps = 0 if f_back_low < f_low: f_gap_low[0] = f_back_low f_gap_high[0] = f_low num_gaps = 1 gap_start = 0 phrase_len = phrase_len+1 if phrase_len > self.max_length: gap_error = 1 if self.tight_phrases: if f_links_low[f_back_low] == -1 or f_links_low[f_low-1] == -1: gap_error = 1 reason_for_failure = "Inside edges of preceding subphrase are not tight" else: gap_start = 1 if self.tight_phrases and f_links_low[f_low] == -1: # this is not a hard error. we can't extract this phrase # but we still might be able to extract a superphrase met_constraints = 0 for i from 0 <= i < matching.size - 1: f_gap_low[1+i] = matching.arr[matching.start+i] + chunklen[i] - f_sent_start f_gap_high[1+i] = matching.arr[matching.start+i+1] - f_sent_start num_gaps = num_gaps + 1 if f_high < f_back_high: f_gap_low[gap_start+num_gaps] = f_high f_gap_high[gap_start+num_gaps] = f_back_high num_gaps = num_gaps + 1 phrase_len = phrase_len+1 if phrase_len > self.max_length: gap_error = 1 if self.tight_phrases: if f_links_low[f_back_high-1] == -1 or f_links_low[f_high] == -1: gap_error = 1 reason_for_failure = "Inside edges of following subphrase are not tight" else: if self.tight_phrases and f_links_low[f_high-1] == -1: met_constraints = 0 if gap_error == 0: e_word_count = e_high - e_low for i from 0 <= i < num_gaps: # check integrity of subphrases if self.find_fixpoint(f_gap_low[gap_start+i], f_gap_high[gap_start+i], f_links_low, f_links_high, e_links_low, e_links_high, -1, -1, e_gap_low+gap_start+i, e_gap_high+gap_start+i, f_gap_low+gap_start+i, f_gap_high+gap_start+i, f_sent_len, e_sent_len, self.train_max_initial_size, self.train_max_initial_size, 0, 0, 0, 0, 0, 0, 0) == 0: gap_error = 1 reason_for_failure = "Subphrase [%d, %d] failed integrity check" % (f_gap_low[gap_start+i], f_gap_high[gap_start+i]) break if gap_error == 0: i = 1 self.findexes.reset() if f_back_low < f_low: fphr_arr._append(sym_setindex(self.category, i)) i = i+1 self.findexes.append(sym_setindex(self.category, i)) self.findexes.extend(self.findexes1) for j from 0 <= j < phrase.n: if sym_isvar(phrase.syms[j]): fphr_arr._append(sym_setindex(self.category, i)) i = i + 1 else: fphr_arr._append(phrase.syms[j]) if f_back_high > f_high: fphr_arr._append(sym_setindex(self.category, i)) self.findexes.append(sym_setindex(self.category, i)) fphr = Phrase(fphr_arr) if met_constraints: phrase_list = self.extract_phrases(e_low, e_high, e_gap_low + gap_start, e_gap_high + gap_start, e_links_low, num_gaps, f_back_low, f_back_high, f_gap_low + gap_start, f_gap_high + gap_start, f_links_low, matching.sent_id, e_sent_len, e_sent_start) if len(phrase_list) > 0: pair_count = 1.0 / len(phrase_list) else: pair_count = 0 reason_for_failure = "Didn't extract anything from [%d, %d] -> [%d, %d]" % (f_back_low, f_back_high, e_low, e_high) for (phrase2,eindexes) in phrase_list: als1 = self.create_alignments(sent_links,num_links,self.findexes,eindexes) extracts.append((fphr, phrase2, pair_count, tuple(als1))) if (num_gaps < self.max_nonterminals and phrase_len < self.max_length and f_back_high - f_back_low + self.train_min_gap_size <= self.train_max_initial_size): if (f_back_low == f_low and f_low >= self.train_min_gap_size and ((not self.tight_phrases) or (f_links_low[f_low-1] != -1 and f_links_low[f_back_high-1] != -1))): f_x_low = f_low-self.train_min_gap_size met_constraints = 1 if self.tight_phrases: while f_x_low >= 0 and f_links_low[f_x_low] == -1: f_x_low = f_x_low - 1 if f_x_low < 0 or f_back_high - f_x_low > self.train_max_initial_size: met_constraints = 0 if (met_constraints and self.find_fixpoint(f_x_low, f_back_high, f_links_low, f_links_high, e_links_low, e_links_high, e_low, e_high, &e_x_low, &e_x_high, &f_x_low, &f_x_high, f_sent_len, e_sent_len, self.train_max_initial_size, self.train_max_initial_size, 1, 1, 1, 1, 0, 1, 0) and ((not self.tight_phrases) or f_links_low[f_x_low] != -1) and self.find_fixpoint(f_x_low, f_low, # check integrity of new subphrase f_links_low, f_links_high, e_links_low, e_links_high, -1, -1, e_gap_low, e_gap_high, f_gap_low, f_gap_high, f_sent_len, e_sent_len, self.train_max_initial_size, self.train_max_initial_size, 0, 0, 0, 0, 0, 0, 0)): fphr_arr._clear() i = 1 self.findexes.reset() self.findexes.append(sym_setindex(self.category, i)) fphr_arr._append(sym_setindex(self.category, i)) i = i+1 self.findexes.extend(self.findexes1) for j from 0 <= j < phrase.n: if sym_isvar(phrase.syms[j]): fphr_arr._append(sym_setindex(self.category, i)) i = i + 1 else: fphr_arr._append(phrase.syms[j]) if f_back_high > f_high: fphr_arr._append(sym_setindex(self.category, i)) self.findexes.append(sym_setindex(self.category, i)) fphr = Phrase(fphr_arr) phrase_list = self.extract_phrases(e_x_low, e_x_high, e_gap_low, e_gap_high, e_links_low, num_gaps+1, f_x_low, f_x_high, f_gap_low, f_gap_high, f_links_low, matching.sent_id, e_sent_len, e_sent_start) if len(phrase_list) > 0: pair_count = 1.0 / len(phrase_list) else: pair_count = 0 for phrase2,eindexes in phrase_list: als2 = self.create_alignments(sent_links,num_links,self.findexes,eindexes) extracts.append((fphr, phrase2, pair_count, tuple(als2))) if (f_back_high == f_high and f_sent_len - f_high >= self.train_min_gap_size and ((not self.tight_phrases) or (f_links_low[f_high] != -1 and f_links_low[f_back_low] != -1))): f_x_high = f_high+self.train_min_gap_size met_constraints = 1 if self.tight_phrases: while f_x_high <= f_sent_len and f_links_low[f_x_high-1] == -1: f_x_high = f_x_high + 1 if f_x_high > f_sent_len or f_x_high - f_back_low > self.train_max_initial_size: met_constraints = 0 if (met_constraints and self.find_fixpoint(f_back_low, f_x_high, f_links_low, f_links_high, e_links_low, e_links_high, e_low, e_high, &e_x_low, &e_x_high, &f_x_low, &f_x_high, f_sent_len, e_sent_len, self.train_max_initial_size, self.train_max_initial_size, 1, 1, 1, 0, 1, 1, 0) and ((not self.tight_phrases) or f_links_low[f_x_high-1] != -1) and self.find_fixpoint(f_high, f_x_high, f_links_low, f_links_high, e_links_low, e_links_high, -1, -1, e_gap_low+gap_start+num_gaps, e_gap_high+gap_start+num_gaps, f_gap_low+gap_start+num_gaps, f_gap_high+gap_start+num_gaps, f_sent_len, e_sent_len, self.train_max_initial_size, self.train_max_initial_size, 0, 0, 0, 0, 0, 0, 0)): fphr_arr._clear() i = 1 self.findexes.reset() if f_back_low < f_low: fphr_arr._append(sym_setindex(self.category, i)) i = i+1 self.findexes.append(sym_setindex(self.category, i)) self.findexes.extend(self.findexes1) for j from 0 <= j < phrase.n: if sym_isvar(phrase.syms[j]): fphr_arr._append(sym_setindex(self.category, i)) i = i + 1 else: fphr_arr._append(phrase.syms[j]) fphr_arr._append(sym_setindex(self.category, i)) self.findexes.append(sym_setindex(self.category, i)) fphr = Phrase(fphr_arr) phrase_list = self.extract_phrases(e_x_low, e_x_high, e_gap_low+gap_start, e_gap_high+gap_start, e_links_low, num_gaps+1, f_x_low, f_x_high, f_gap_low+gap_start, f_gap_high+gap_start, f_links_low, matching.sent_id, e_sent_len, e_sent_start) if len(phrase_list) > 0: pair_count = 1.0 / len(phrase_list) else: pair_count = 0 for phrase2, eindexes in phrase_list: als3 = self.create_alignments(sent_links,num_links,self.findexes,eindexes) extracts.append((fphr, phrase2, pair_count, tuple(als3))) if (num_gaps < self.max_nonterminals - 1 and phrase_len+1 < self.max_length and f_back_high == f_high and f_back_low == f_low and f_back_high - f_back_low + (2*self.train_min_gap_size) <= self.train_max_initial_size and f_low >= self.train_min_gap_size and f_high <= f_sent_len - self.train_min_gap_size and ((not self.tight_phrases) or (f_links_low[f_low-1] != -1 and f_links_low[f_high] != -1))): met_constraints = 1 f_x_low = f_low-self.train_min_gap_size if self.tight_phrases: while f_x_low >= 0 and f_links_low[f_x_low] == -1: f_x_low = f_x_low - 1 if f_x_low < 0: met_constraints = 0 f_x_high = f_high+self.train_min_gap_size if self.tight_phrases: while f_x_high <= f_sent_len and f_links_low[f_x_high-1] == -1: f_x_high = f_x_high + 1 if f_x_high > f_sent_len or f_x_high - f_x_low > self.train_max_initial_size: met_constraints = 0 if (met_constraints and self.find_fixpoint(f_x_low, f_x_high, f_links_low, f_links_high, e_links_low, e_links_high, e_low, e_high, &e_x_low, &e_x_high, &f_x_low, &f_x_high, f_sent_len, e_sent_len, self.train_max_initial_size, self.train_max_initial_size, 1, 1, 2, 1, 1, 1, 1) and ((not self.tight_phrases) or (f_links_low[f_x_low] != -1 and f_links_low[f_x_high-1] != -1)) and self.find_fixpoint(f_x_low, f_low, f_links_low, f_links_high, e_links_low, e_links_high, -1, -1, e_gap_low, e_gap_high, f_gap_low, f_gap_high, f_sent_len, e_sent_len, self.train_max_initial_size, self.train_max_initial_size, 0, 0, 0, 0, 0, 0, 0) and self.find_fixpoint(f_high, f_x_high, f_links_low, f_links_high, e_links_low, e_links_high, -1, -1, e_gap_low+1+num_gaps, e_gap_high+1+num_gaps, f_gap_low+1+num_gaps, f_gap_high+1+num_gaps, f_sent_len, e_sent_len, self.train_max_initial_size, self.train_max_initial_size, 0, 0, 0, 0, 0, 0, 0)): fphr_arr._clear() i = 1 self.findexes.reset() self.findexes.append(sym_setindex(self.category, i)) fphr_arr._append(sym_setindex(self.category, i)) i = i+1 self.findexes.extend(self.findexes1) for j from 0 <= j < phrase.n: if sym_isvar(phrase.syms[j]): fphr_arr._append(sym_setindex(self.category, i)) i = i + 1 else: fphr_arr._append(phrase.syms[j]) fphr_arr._append(sym_setindex(self.category, i)) self.findexes.append(sym_setindex(self.category, i)) fphr = Phrase(fphr_arr) phrase_list = self.extract_phrases(e_x_low, e_x_high, e_gap_low, e_gap_high, e_links_low, num_gaps+2, f_x_low, f_x_high, f_gap_low, f_gap_high, f_links_low, matching.sent_id, e_sent_len, e_sent_start) if len(phrase_list) > 0: pair_count = 1.0 / len(phrase_list) else: pair_count = 0 for phrase2, eindexes in phrase_list: als4 = self.create_alignments(sent_links,num_links,self.findexes,eindexes) extracts.append((fphr, phrase2, pair_count, tuple(als4))) else: reason_for_failure = "Unable to extract basic phrase" free(sent_links) free(f_links_low) free(f_links_high) free(e_links_low) free(e_links_high) free(f_gap_low) free(f_gap_high) free(e_gap_low) free(e_gap_high) return extracts