# Pyrex 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 sys import sym import log import rule import monitor import cintlist import csuf import cdat import cveb import precomputation import gc import cn import sgml cimport cmath cimport csuf cimport cdat cimport cintlist cimport rule cimport cveb cimport precomputation cimport calignment from libc.stdlib cimport malloc, realloc, free from libc.string cimport memset, memcpy from libc.math cimport fmod, ceil, floor cdef int PRECOMPUTE cdef int MERGE cdef int BAEZA_YATES PRECOMPUTE = 0 MERGE = 1 BAEZA_YATES = 2 #cdef int node_count #node_count = 0 cdef class TrieNode: cdef public children #cdef int id def __init__(self): self.children = {} #self.id = node_count #node_count += 1 cdef class ExtendedTrieNode(TrieNode): cdef public phrase cdef public phrase_location cdef public suffix_link def __init__(self, phrase=None, phrase_location=None, suffix_link=None): TrieNode.__init__(self) 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 cdef class BaselineRuleFactory: cdef grammar, context_manager cdef int max_terminals, max_nonterminals cdef int max_initial_size, train_max_initial_size cdef int min_gap_size, train_min_gap_size cdef int category cdef int visit cdef float intersect_time, extract_time cdef ruleFile, timingFile cdef int* last_visit1 cdef int* last_visit2 cdef match_node** intersector1 cdef match_node** intersector2 cdef csuf.SuffixArray sa cdef cintlist.CIntList sent_id def input(self, fwords): flen = len(fwords) start_time = monitor.cpu() self.intersect_time = 0.0 self.extract_time = 0.0 pyro_phrase_count = 0 hiero_phrase_count = 0 frontier = [] for i in xrange(len(fwords)): frontier.append((i, (), False)) while len(frontier) > 0: this_iter_intersect_time = self.intersect_time new_frontier = [] for i, prefix, is_shadow_path in frontier: word_id = fwords[i][0][0] #print "word_id = %i" % word_id phrase = prefix + (word_id,) str_phrase = map(sym.tostring, phrase) hiero_phrase = rule.Phrase(phrase) #log.writeln("pos %2d, '%s'" % (i, hiero_phrase)) self.lookup(hiero_phrase) if hiero_phrase.arity() == 0: pyro_phrase_count = pyro_phrase_count + 1 else: hiero_phrase_count = hiero_phrase_count + 1 if len(phrase) - hiero_phrase.arity() < self.max_terminals and i+1 < len(fwords): new_frontier.append((i+1, phrase, is_shadow_path)) if hiero_phrase.arity() < self.max_nonterminals: xcat = sym.setindex(self.category, hiero_phrase.arity()+1) for j in xrange(i+1+self.min_gap_size, min(i+self.max_initial_size, len(fwords))): new_frontier.append((j, phrase+(xcat,), is_shadow_path)) log.writeln("This iteration intersect time = %f" % (self.intersect_time - this_iter_intersect_time)) frontier = new_frontier stop_time = monitor.cpu() log.writeln("COUNT %d %d" % (pyro_phrase_count, hiero_phrase_count)) def lookup(self, phrase): cdef int j, g, start, stop, sent_id, num_ranges, arity cdef match_node** cur_intersector cdef match_node** next_intersector cdef match_node** tmp_intersector cdef match_node* node cdef match_node* cur_node cdef match_node* prev_node cdef match_node** node_ptr cdef int* cur_visit cdef int* next_visit cdef int* tmp_visit cdef int* chunklen #print "\n\nLOOKUP\n\n" ranges = [] sizes = [] arity = phrase.arity() chunklen = malloc(arity*sizeof(int)) for i from 0 <= i < arity+1: chunk = phrase.getchunk(i) chunklen[i] = len(chunk) sa_range = None phr = () for offset, word_id in enumerate(chunk): word = sym.tostring(word_id) sa_range = self.context_manager.fsarray.lookup(word, offset, sa_range[0], sa_range[1]) if sa_range is None: #log.writeln("Returned for phrase %s" % rule.Phrase(phr)) return #log.writeln("Found range %s for phrase %s" % (sa_range, rule.Phrase(phr))) ranges.append(sa_range) sizes.append(sa_range[1]-sa_range[0]) if phrase.arity() == 0: return cur_intersector = self.intersector1 next_intersector = self.intersector2 cur_visit = self.last_visit1 next_visit = self.last_visit2 num_ranges = len(ranges) for i from 0 <= i < num_ranges: sa_range = ranges[i] start_time = monitor.cpu() self.visit = self.visit + 1 intersect_count = 0 start = sa_range[0] stop = sa_range[1] for j from start <= j < stop: g = self.sa.sa.arr[j] sent_id = self.sent_id.arr[g] if i==0: if next_visit[sent_id] != self.visit: # clear intersector node = next_intersector[sent_id] next_intersector[sent_id] = NULL while node != NULL: prev_node = node node = node.next free(prev_node.match) free(prev_node) next_visit[sent_id] = self.visit node_ptr = &(next_intersector[sent_id]) while node_ptr[0] != NULL: node_ptr = &(node_ptr[0].next) node_ptr[0] = malloc(sizeof(match_node)) node_ptr[0].match = malloc(sizeof(int)) node_ptr[0].match[0] = g node_ptr[0].next = NULL intersect_count = intersect_count + 1 else: if cur_visit[sent_id] == self.visit-1: cur_node = cur_intersector[sent_id] while cur_node != NULL: if g - cur_node.match[0] + chunklen[i] <= self.train_max_initial_size and g - cur_node.match[i-1] - chunklen[i-1] >= self.train_min_gap_size: if next_visit[sent_id] != self.visit: # clear intersector -- note that we only do this if we've got something to put there node = next_intersector[sent_id] next_intersector[sent_id] = NULL while node != NULL: prev_node = node node = node.next free(prev_node.match) free(prev_node) next_visit[sent_id] = self.visit node_ptr = &(next_intersector[sent_id]) while node_ptr[0] != NULL: node_ptr = &(node_ptr[0].next) node_ptr[0] = malloc(sizeof(match_node)) node_ptr[0].match = malloc((i+1) * sizeof(int)) memcpy(node_ptr[0].match, cur_node.match, i*sizeof(int)) node_ptr[0].match[i] = g node_ptr[0].next = NULL intersect_count = intersect_count + 1 cur_node = cur_node.next tmp_intersector = cur_intersector cur_intersector = next_intersector next_intersector = tmp_intersector tmp_visit = cur_visit cur_visit = next_visit next_visit = tmp_visit intersect_time = monitor.cpu() - start_time if i > 0: log.writeln("INT %d %d %d %d %f baseline" % (arity, prev_intersect_count, sa_range[1]-sa_range[0], intersect_count, intersect_time)) if intersect_count == 0: return None prev_intersect_count = intersect_count free(chunklen) def __init__(self, max_terminals=5, max_nonterminals=2, max_initial_size=10, train_max_initial_size=10, min_gap_size=1, train_min_gap_size=2, category='[PHRASE]', grammar=None, ruleFile=None, timingFile=None): self.grammar = grammar self.max_terminals = max_terminals 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) self.ruleFile = ruleFile self.timingFile = timingFile self.visit = 0 def registerContext(self, context_manager): cdef int num_sents self.context_manager = context_manager self.sa = context_manager.fsarray self.sent_id = self.sa.darray.sent_id num_sents = len(self.sa.darray.sent_index) self.last_visit1 = malloc(num_sents * sizeof(int)) memset(self.last_visit1, 0, num_sents * sizeof(int)) self.last_visit2 = malloc(num_sents * sizeof(int)) memset(self.last_visit2, 0, num_sents * sizeof(int)) self.intersector1 = malloc(num_sents * sizeof(match_node*)) memset(self.intersector1, 0, num_sents * sizeof(match_node*)) self.intersector2 = malloc(num_sents * sizeof(match_node*)) memset(self.intersector2, 0, num_sents * sizeof(match_node*)) # 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 cintlist.CIntList arr cdef int num_subpatterns # returns true if sent_id is contained cdef int contains(self, int sent_id): return 1 def __init__(self, sa_low=-1, sa_high=-1, arr_low=-1, arr_high=-1, arr=None, 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 sampleSize cdef context_manager cdef cintlist.CIntList sa def __init__(self, sampleSize=0): self.sampleSize = sampleSize if sampleSize > 0: log.writeln("Sampling strategy: uniform, max sample size = %d" % sampleSize, 1) else: log.writeln("Sampling strategy: no sampling", 1) def registerContext(self, context_manager): self.context_manager = context_manager self.sa = ( context_manager.fsarray).sa def sample(self, PhraseLocation phrase_location): '''Returns a sample of the locations for the phrase. If there are less than self.sampleSize locations, return all of them; otherwise, return up to self.sampleSize 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 cintlist.CIntList sample cdef double i, stepsize cdef int num_locations, val, j sample = cintlist.CIntList() if phrase_location.arr is None: num_locations = phrase_location.sa_high - phrase_location.sa_low if self.sampleSize == -1 or num_locations <= self.sampleSize: sample._extend_arr(self.sa.arr + phrase_location.sa_low, num_locations) else: stepsize = float(num_locations)/float(self.sampleSize) i = phrase_location.sa_low while i < phrase_location.sa_high and sample.len < self.sampleSize: '''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.sampleSize == -1 or num_locations <= self.sampleSize: sample = phrase_location.arr else: stepsize = float(num_locations)/float(self.sampleSize) i = phrase_location.arr_low while i < num_locations and sample.len < self.sampleSize * 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 cdef long nGramCount(PhraseLocation loc): return (loc.arr_high - loc.arr_low)/ loc.num_subpatterns # 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 matching2str(Matching* m): # cdef int i # cdef result # result = "(" # for i from m.start <= i < m.end: # result = result + str(m.arr[i]) + " " # result = result + ")" # return result cdef int median(int low, int high, int step): return low + (((high - low)/step)/2)*step cdef void findComparableMatchings(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 rules, grammar, context_manager 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 cacheBetweenSents cdef precomputed_index cdef precomputed_collocations cdef precompute_file cdef max_rank cdef int precompute_rank, precompute_secondary_rank cdef useBaezaYates cdef use_index cdef use_collocations cdef float by_slack_factor cdef per_sentence_grammar cdef rule_filehandler cdef rule_file cdef pruned_rule_file cdef extract_file cdef sample_file cdef search_file cdef timingFile cdef log_int_stats cdef prev_norm_prefix cdef float intersect_time, extract_time cdef csuf.SuffixArray fsa cdef cdat.DataArray fda cdef cdat.DataArray eda cdef calignment.Alignment alignment cdef cintlist.CIntList eid2symid cdef cintlist.CIntList fid2symid cdef int tight_phrases cdef int require_aligned_terminal cdef int require_aligned_chunks cdef cintlist.CIntList findexes cdef cintlist.CIntList findexes1 cdef int excluded_sent_id # exclude a sentence id def __init__(self, alignment=None, # compiled alignment object (REQUIRED) by_slack_factor=1.0, # parameter for double-binary search; doesn't seem to matter much category="[PHRASE]", # name of generic nonterminal used by Hiero cacheBetweenSents=False, # prevent flushing of tree between sents; use carefully or you'll run out of memory extract_file=None, # print raw extracted rules to this file grammar=None, # empty grammar object -- must be supplied from outside (REQUIRED) log_int_stats=False, # prints timing data on intersections to stderr max_chunks=None, # maximum number of contiguous chunks of terminal symbols in RHS of a rule. If None, defaults to max_nonterminals+1 max_initial_size=10, # maximum span of a grammar rule in TEST DATA max_length=5, # maximum number of symbols (both T and NT) allowed in a rule max_nonterminals=2, # maximum number of nonterminals allowed in a rule (set >2 at your own risk) max_target_chunks=None, # maximum number of contiguous chunks of terminal symbols in target-side RHS of a rule. If None, defaults to max_nonterminals+1 max_target_length=None, # maximum number of target side symbols (both T and NT) allowed in a rule. If None, defaults to max_initial_size min_gap_size=2, # minimum span of a nonterminal in the RHS of a rule in TEST DATA precompute_file=None, # filename of file containing precomputed collocations precompute_secondary_rank=20, # maximum frequency rank of patterns used to compute triples (don't set higher than 20). precompute_rank=100, # maximum frequency rank of patterns used to compute collocations (no need to set higher than maybe 200-300) pruned_rule_file=None, # if specified, pruned grammars will be written to this filename require_aligned_terminal=True, # require extracted rules to have at least one aligned word require_aligned_chunks=False, # require each contiguous chunk of extracted rules to have at least one aligned word per_sentence_grammar=True, # generate grammar files for each input segment rule_file=None, # UNpruned grammars will be written to this filename sample_file=None, # Sampling statistics will be written to this filename search_file=None, # lookup statistics will be written to this filename train_max_initial_size=10, # maximum span of a grammar rule extracted from TRAINING DATA train_min_gap_size=2, # minimum span of an RHS nonterminal in a rule extracted from TRAINING DATA tight_phrases=False, # True if phrases should be tight, False otherwise (False == slower but better results) timingFile=None, # timing statistics will be written to this filename useBaezaYates=True, # True to require use of double-binary alg, false otherwise use_collocations=True, # True to enable used of precomputed collocations use_index=True # True to enable use of precomputed inverted indices ): '''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()) self.grammar = grammar if alignment is None: raise Exception("Must specify an alignment object") self.alignment = alignment self.excluded_sent_id = -1 # 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) 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.cacheBetweenSents = not per_sentence_grammar 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.useBaezaYates = useBaezaYates self.by_slack_factor = by_slack_factor if tight_phrases: self.tight_phrases = 1 else: self.tight_phrases = 0 if require_aligned_chunks: # one condition is a stronger version of the other. self.require_aligned_chunks = 1 self.require_aligned_terminal = 1 elif require_aligned_terminal: self.require_aligned_chunks = 0 self.require_aligned_terminal = 1 else: self.require_aligned_chunks = 0 self.require_aligned_terminal = 0 self.per_sentence_grammar = per_sentence_grammar if not self.per_sentence_grammar: self.rule_filehandler = open(rule_file, "w") # diagnostics #if rule_file is None: # self.rule_file = None self.rule_file = rule_file if extract_file is None: self.extract_file = None else: self.extract_file = open(extract_file, "w") if sample_file is None: self.sample_file = None else: self.sample_file = open(sample_file, "w") if search_file is None: self.search_file = None else: self.search_file = open(search_file, "w") self.pruned_rule_file = pruned_rule_file self.timingFile = timingFile self.log_int_stats = log_int_stats self.prev_norm_prefix = () self.findexes = cintlist.CIntList(initial_len=10) self.findexes1 = cintlist.CIntList(initial_len=10) def registerContext(self, context_manager): '''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.context_manager = context_manager self.fsa = context_manager.fsarray self.fda = self.fsa.darray self.eda = context_manager.edarray self.fid2symid = self.set_idmap(self.fda) self.eid2symid = self.set_idmap(self.eda) self.precompute() cdef set_idmap(self, cdat.DataArray darray): cdef int word_id, new_word_id, N cdef cintlist.CIntList idmap N = len(darray.id2word) idmap = cintlist.CIntList(initial_len=N) for word_id from 0 <= word_id < N: new_word_id = sym.fromstring(darray.id2word[word_id], terminal=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 rule.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.id2word[word_id]) result = result + (new_id,) return rule.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.id2word[word_id]) result = result + (new_id,) patterns.append(rule.Phrase(result)) patterns.append(rule.Phrase(result + (sym.setindex(self.category, 1),))) patterns.append(rule.Phrase((sym.setindex(self.category, 1),) + result)) return patterns def precompute(self): cdef precomputation.Precomputation pre if self.precompute_file is not None: start_time = monitor.cpu() log.write("Reading precomputed data from file %s... " % self.precompute_file, 1) pre = precomputation.Precomputation(self.precompute_file, from_binary=True) # check parameters of precomputation -- some are critical and some are not if pre.max_nonterminals != self.max_nonterminals: log.writeln("\nWARNING: Precomputation done with max nonterminals %d, decoder uses %d" % (pre.max_nonterminals, self.max_nonterminals)) if pre.max_length != self.max_length: log.writeln("\nWARNING: 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: log.writeln("\nERROR: Precomputation done with max initial size %d, decoder uses %d" % (pre.train_max_initial_size, self.train_max_initial_size)) raise Exception("Parameter mismatch with precomputed data") if pre.train_min_gap_size != self.train_min_gap_size: log.writeln("\nERROR: Precomputation done with min gap size %d, decoder uses %d" % (pre.train_min_gap_size, self.train_min_gap_size)) raise Exception("Parameter mismatch with precomputed data") log.writeln("done.", 1) if self.use_index: log.write("Converting %d hash keys on precomputed inverted index... " % (len(pre.precomputed_index)), 1) for pattern, arr in pre.precomputed_index.iteritems(): phrases = self.pattern2phrase_plus(pattern) for phrase in phrases: self.precomputed_index[phrase] = arr log.writeln("done.", 1) if self.use_collocations: log.write("Converting %d hash keys on precomputed collocations... " % (len(pre.precomputed_collocations)), 1) for pattern, arr in pre.precomputed_collocations.iteritems(): phrase = self.pattern2phrase(pattern) self.precomputed_collocations[phrase] = arr log.writeln("done.", 1) stop_time = monitor.cpu() log.writeln("Processing precomputations took %f seconds" % (stop_time - start_time), 1) def getPrecomputedCollocation(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* baezaYatesHelper(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*)) # log.writeln("%sBY: [%d, %d, %d] [%d, %d, %d]" % (pad, low1, high1, step1, low2, high2, step2,), 5) d_first = 0 if high1 - low1 > high2 - low2: # log.writeln("%sD first" % (pad), 5) d_first = 1 # else: # log.writeln("%sQ first" % (pad), 5) # '''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: # log.writeln("%sRETURN: set is empty" % (pad), 5) 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: # log.writeln("%s %s < %s" % (pad, tuple(arr1[high1-step1:high1]), tuple(arr2[low2:low2+step2])),5) # log.writeln("%sRETURN: non-overlapping sets" % (pad), 5) 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: # log.writeln("%s %s > %s" % (pad, tuple(arr1[low1:low1+step1]), tuple(arr2[high2-step2:high2])),5) # log.writeln("%sRETURN: non-overlapping sets" % (pad), 5) 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 * cmath.log(dsetsize) / cmath.log(2) > dsetsize: free(result) return self.mergeHelper(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) findComparableMatchings(low1, high1, arr1, step1, med1, &med1_minus, &med1_plus) comparison = self.compareMatchingsSet(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) findComparableMatchings(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.compareMatchingsSet(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.baezaYatesHelper(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.baezaYatesHelper(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 compareMatchingsSet(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* mergeHelper(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 # cdef int i # pad = " " # log.writeln("->mergeHelper", 5) result_len[0] = 0 result = malloc(0*sizeof(int)) i1 = low1 i2 = low2 # if log.level==5: # log.writeln("%sMERGE lists [%d,%d,%d] and [%d,%d,%d]" % (pad,low1,high1,step1,low2,high2,step2), 5) # log.writeln("%soffset_by_one: %d, len_last: %d" % (pad, offset_by_one, len_last), 5) # log.write("[") # for i from low1 <= i < high1: # log.write("%d, " % arr1.arr[i],5) # log.writeln("]") # log.write("[") # for i from low2 <= i < high2: # log.write("%d, " % arr2.arr[i],5) # log.writeln("]") 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) # if log.level==5: # log.writeln("%s TOP1 %s" % (pad,matching2str(loc1)),5) 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: # if log.level==5: # log.writeln("%s %s > %s" % (pad,matching2str(loc1),matching2str(loc2)),5) # log.writeln("%s POP2 %s" % (pad,matching2str(loc2)),5) 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: # if log.level==5: # log.writeln("%s %s == %s" % (pad,matching2str(loc1),matching2str(loc2)),5) result = append_combined_matching(result, &loc1, &loc2, offset_by_one, num_subpatterns, result_len) if comparison == 1: # if log.level==5: # log.writeln("%s %s > %s" % (pad,matching2str(loc1),matching2str(loc2)),5) pass if comparison == -1: # if log.level==5: # log.writeln("%s %s < %s" % (pad,matching2str(loc1),matching2str(loc2)),5) break else: j2 = j2 + step2 # if log.level==5: # log.writeln("%s POP1 %s" % (pad,matching2str(loc1)),5) i1 = i1 + step1 # log.writeln("<-mergeHelper", 5) return result cdef void sortPhraseLoc(self, cintlist.CIntList arr, PhraseLocation loc, rule.Phrase phrase): cdef int i, j cdef cveb.VEB veb cdef cintlist.CIntList result if phrase in self.precomputed_index: loc.arr = self.precomputed_index[phrase] else: loc.arr = cintlist.CIntList(initial_len=loc.sa_high-loc.sa_low) veb = cveb.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 intersectHelper(self, rule.Phrase prefix, rule.Phrase suffix, PhraseLocation prefix_loc, PhraseLocation suffix_loc, int algorithm): cdef cintlist.CIntList arr1, arr2, result cdef int low1, high1, step1, low2, high2, step2, offset_by_one, len_last, num_subpatterns, result_len cdef int* result_ptr cdef csuf.SuffixArray suf 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: suf = self.context_manager.fsarray self.sortPhraseLoc(suf.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: suf = self.context_manager.fsarray self.sortPhraseLoc(suf.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.mergeHelper(low1, high1, arr1.arr, step1, low2, high2, arr2.arr, step2, offset_by_one, len_last, num_subpatterns, &result_len) else: result_ptr = self.baezaYatesHelper(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 = cintlist.CIntList() 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 compareResults(self, PhraseLocation loc1, PhraseLocation loc2, phrase, type1, type2): # cdef i # if loc1 is None and type1=="pre": # return # if loc1 is None: # if loc2 is None or loc2.arr_high == 0: # return # if loc2 is None: # if loc1.arr_high == 0: # return # if loc1.arr_high != loc2.arr_high: # log.writeln("ERROR: %d vs %d (%s vs %s)" % (loc1.arr_high, loc2.arr_high, type1, type2)) # #log.writeln(" %s" % self.loc2str(loc2)) # if loc1.arr_high == 0: # return # elif loc1.num_subpatterns != loc2.num_subpatterns: # log.writeln("ERROR 2: %d vs %d (%d v %d) %s" % (loc1.num_subpatterns, loc2.num_subpatterns, loc1.arr_high, loc2.arr_high, phrase)) # for i from 0 <= i < loc1.arr_high: # if loc1.arr[i] != loc2.arr[i]: # log.writeln("ERROR 3") # cdef PhraseLocation intersect(self, prefix_node, suffix_node, rule.Phrase phrase): cdef rule.Phrase prefix, suffix cdef PhraseLocation prefix_loc, suffix_loc, result start_time = monitor.cpu() prefix = prefix_node.phrase suffix = suffix_node.phrase prefix_loc = prefix_node.phrase_location suffix_loc = suffix_node.phrase_location result = self.getPrecomputedCollocation(phrase) if result is not None: intersect_method = "precomputed" if result is None: if self.useBaezaYates: result = self.intersectHelper(prefix, suffix, prefix_loc, suffix_loc, BAEZA_YATES) intersect_method="double binary" else: result = self.intersectHelper(prefix, suffix, prefix_loc, suffix_loc, MERGE) intersect_method="merge" stop_time = monitor.cpu() intersect_time = stop_time - start_time if self.log_int_stats: if intersect_method == "precomputed": sort1 = "none" sort2 = "none" else: if prefix in self.precomputed_index: sort1 = "index" else: sort1 = "veb" if suffix in self.precomputed_index: sort2 = "index" else: sort2 = "veb" result_len=0 if result is not None: result_len = len(result.arr)/result.num_subpatterns rank = 0 # if phrase in self.max_rank: # rank = self.max_rank[phrase] # else: # rank = self.precompute_rank + 10 log.writeln("INT %d %d %d %d %d %f %d %s %s %s" % (len(prefix)+1 - prefix.arity(), prefix.arity(), nGramCount(prefix_node.phrase_location), nGramCount(suffix_node.phrase_location), result_len, intersect_time, rank, intersect_method, sort1, sort2)) return result def advance(self, frontier, res, fwords): nf = [] for (toskip, (i, alt, pathlen)) in frontier: spanlen = fwords[i][alt][2] if (toskip == 0): #log.writeln("RES: (%d %d %d)" % (i, alt, pathlen), 3) res.append((i, alt, pathlen)) ni = i + spanlen #log.writeln("proc: %d (%d %d %d) sl=%d ni=%d len(fwords)=%d" % (toskip, i, alt, pathlen, spanlen, ni, len(fwords)), 3) if (ni < len(fwords) and (pathlen + 1) < self.max_initial_size): for na in xrange(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): frontier = [] if (i+spanlen+skip >= len(next_states)): return frontier #print "get_all_nodes_isteps_away from %i" % (i) 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 #print "reachable(from=%i,dist=%i) = " % (i,spanlen) #print reachable for nextreachable in reachable: for next_id in next_states[nextreachable]: jump = self.shortest(fwords,i,next_id) #print "checking next_id = %i, pathlen[sofar] = %i, jump = %i" % (next_id,pathlen,jump) #if (next_id - (i+spanlen)) < skip: if jump < skip: continue #if next_id-(i-pathlen) < self.max_initial_size: if pathlen+jump <= self.max_initial_size: for alt_id in xrange(len(fwords[next_id])): if (fwords[next_id][alt_id][0] != cn.epsilon): #frontier.append((next_id,alt_id,next_id-(i-pathlen))); #print "finding the shortest from %i to %i" % (i, next_id) newel = (next_id,alt_id,pathlen+jump) if newel not in frontier: frontier.append((next_id,alt_id,pathlen+jump)) #print "appending to frontier = next_id=%i, alt_id=%i, pathlen=%i" % (next_id,alt_id,pathlen+jump) #else: #print "NOT appending to frontier = next_id=%i, alt_id=%i, pathlen=%i" % (next_id,alt_id,pathlen+jump) #else: #print "next_id = %s is aborted\n" % next_id #print "returning frontier" #print frontier return frontier def reachable(self, fwords, ifrom, dist): #print "inside reachable(%i,%i)" % (ifrom,dist) ret = [] if (ifrom >= len(fwords)): return ret for alt_id in xrange(len(fwords[ifrom])): if (fwords[ifrom][alt_id][0] == cn.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): min = 1000 #print "shortest ifrom=%i, ito=%i" % (ifrom,ito) if (ifrom > ito): return min if (ifrom == ito): return 0 for alt_id in xrange(len(fwords[ifrom])): currmin = self.shortest(fwords,ifrom+fwords[ifrom][alt_id][2],ito) if (fwords[ifrom][alt_id][0] != cn.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] == cn.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 cdef float start_time cdef PhraseLocation phrase_location cdef cintlist.CIntList sample, chunklen cdef Matching matching cdef rule.Phrase hiero_phrase #fwords = [ ((1,0.0,1),), fwords1 ] #word id for = 1, cost = 0.0, next = 1 #print fwords flen = len(fwords) #print "length = %i" % flen start_time = monitor.cpu() self.intersect_time = 0.0 self.extract_time = 0.0 nodes_isteps_away_buffer = {} hit = 0 reachable_buffer = {} #print "id = ",meta #print "rule_file = ",self.rule_file dattrs = sgml.attrs_to_dict(meta) id = dattrs.get('id', 'NOID') if self.per_sentence_grammar: self.rule_filehandler = open(self.rule_file+'.'+id, 'w') self.excluded_sent_id = int(dattrs.get('exclude', '-1')) #print "max_initial_size = %i" % self.max_initial_size if not self.cacheBetweenSents: self.rules.root = ExtendedTrieNode(phrase_location=PhraseLocation()) self.grammar.root = [None, {}] frontier = [] for i in xrange(len(fwords)): for alt in xrange(0, len(fwords[i])): if fwords[i][alt][0] != cn.epsilon: frontier.append((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 xrange(self.min_gap_size, len(fwords)): for alt in xrange(0, len(fwords[i])): if fwords[i][alt][0] != cn.epsilon: frontier.append((i-self.min_gap_size, i, alt, self.min_gap_size, xroot, (x1,), True)) '''for k, i, alt, pathlen, node, prefix, is_shadow_path in frontier: if len(prefix)>0: print k, i, alt, pathlen, node, map(sym.tostring,prefix), is_shadow_path else: print k, i, alt, pathlen, node, prefix, is_shadow_path''' #for wid in xrange(1000): # print "%i = %s" % (wid, sym.tostring(wid)) next_states = [] for i in xrange(len(fwords)): next_states.append(self.get_next_states(fwords,i,self.min_gap_size)) #print "next state of %i" % i #print next_states[i] while len(frontier) > 0: #print "frontier = %i" % len(frontier) this_iter_intersect_time = self.intersect_time new_frontier = [] for k, i, alt, pathlen, node, prefix, is_shadow_path in frontier: #print "looking at: " #if len(prefix)>0: # print k, i, alt, pathlen, node, map(sym.tostring,prefix), is_shadow_path #else: # print k, i, alt, pathlen, node, prefix, is_shadow_path word_id = fwords[i][alt][0] spanlen = fwords[i][alt][2] #print "word_id = %i, %s" % (word_id, sym.tostring(word_id)) # to prevent .. [X] #print "prefix = ",prefix #if word_id == 2 and len(prefix)>=2: #print "at the end: %s" % (prefix[len(prefix)-1]) #if prefix[len(prefix)-1]<0: #print "break" #continue #print "continuing" #if pathlen + spanlen > self.max_initial_size: #continue # TODO get rid of k -- pathlen is replacing it if word_id == cn.epsilon: #print "skipping because word_id is epsilon" if i+spanlen >= len(fwords): continue for nualt in xrange(0,len(fwords[i+spanlen])): frontier.append((k, i+spanlen, nualt, pathlen, node, prefix, is_shadow_path)) continue phrase = prefix + (word_id,) str_phrase = map(sym.tostring, phrase) hiero_phrase = rule.Phrase(phrase) arity = hiero_phrase.arity() #print "pos %2d, node %5d, '%s'" % (i, node.id, hiero_phrase) if self.search_file is not None: self.search_file.write("%s\n" % hiero_phrase) lookup_required = False if word_id in node.children: if node.children[word_id] is None: #print "Path dead-ends at this node\n" continue else: #print "Path continues at this node\n" node = node.children[word_id] else: if node.suffix_link is None: #print "Current node is root; lookup required\n" lookup_required = True else: if word_id in node.suffix_link.children: if node.suffix_link.children[word_id] is None: #print "Suffix link reports path is dead end\n" node.children[word_id] = None continue else: #print "Suffix link indicates lookup is reqired\n" lookup_required = True else: #print "ERROR: We never get here\n" raise Exception("Keyword trie error") #new_frontier.append((k, i, alt, pathlen, node, prefix, is_shadow_path)) #print "checking whether lookup_required\n" if lookup_required: new_node = None if is_shadow_path: #print "Extending shadow path for %s \n" # 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: #print "Intersecting for %s because of arity > 0\n" % hiero_phrase phrase_location = self.intersect(node, node.suffix_link.children[word_id], hiero_phrase) else: #print "Suffix array search for %s" % hiero_phrase phrase_location = node.phrase_location sa_range = self.context_manager.fsarray.lookup(str_phrase[-1], len(str_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 #print "Search failed\n" continue #print "Search succeeded\n" 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 #print "Added node %d with suffix link %d\n" % (node.id, node.suffix_link.id) '''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= rule.Phrase(phrase + (xcat,))) #log.writeln("Added node %d with suffix link %d (for X)" % (node.children[xcat].id, node.children[xcat].suffix_link.id), 4) # sample from range if not is_shadow_path: #print "is_not_shadow_path" sample = self.context_manager.sampler.sample(node.phrase_location) #print "node.phrase_location %s" % str(node.phrase_location) #print "sample.len = %i" % len(sample) num_subpatterns = ( node.phrase_location).num_subpatterns chunklen = cintlist.CIntList(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() '''orig_tight_phrases = self.tight_phrases orig_require_aligned_terminal = self.require_aligned_terminal orig_require_aligned_chunks = self.require_aligned_chunks if k==0 or i==len(fwords)-1: self.tight_phrases = 0 self.require_aligned_terminal = 0 self.require_aligned_chunks = 0''' while j < sample.len: extract = [] assign_matching(&matching, sample.arr, j, num_subpatterns, self.fda.sent_id.arr) '''print "tight_phrase = " print self.tight_phrases print "require_aligned_terminal = " print self.require_aligned_terminal print "require_aligned_chunks = " print self.require_aligned_chunks''' extract = self.extract(hiero_phrase, &matching, chunklen.arr, num_subpatterns) extracts.extend(extract) j = j + num_subpatterns '''self.tight_phrases = orig_tight_phrases sttice+sa.nw.normelf.require_aligned_terminal = orig_require_aligned_terminal self.require_aligned_chunks = orig_require_aligned_chunks''' num_samples = sample.len/num_subpatterns extract_stop = monitor.cpu() self.extract_time = self.extract_time + extract_stop - extract_start #print "extract.size = %i" % len(extracts) if len(extracts) > 0: fphrases = {} fals = {} fcount = {} for f, e, count, als in extracts: fcount.setdefault(f, 0.0) fcount[f] = fcount[f] + count fphrases.setdefault(f, {}) fphrases[f].setdefault(e, {}) #fphrases[f][e] = fphrases[f][e] + count fphrases[f][e].setdefault(als,0.0) fphrases[f][e][als] = fphrases[f][e][als] + count #print "f,e,als ",f," : ",e," : ",als," count = ",fphrases[f][e][als] #fals[str(f)+" ||| "+str(e)] = als for f, elist in fphrases.iteritems(): #print "f = '%s'" % f #if (str(f) in ['','',' [X,1]','[X,1] ']): # print "rejected" # continue f_margin = fcount[f] for e, alslist in elist.iteritems(): alignment = None count = 0 for als, currcount in alslist.iteritems(): #print "als = ",als,", count = ",currcount if currcount > count: alignment = als count = currcount #alignment = fals[str(f)+" ||| "+str(e)] #print "selected = ",alignment," with count = ",count scores = [] for m in self.context_manager.models: scores.append(m.compute_contextless_score(f, e, count, fcount[f], num_samples)) r = rule.Rule(self.category, f, e, scores=scores, owner="context", word_alignments = alignment) self.grammar.add(r) if self.rule_filehandler is not None: self.rule_filehandler.write("%s\n" % r.to_line()) #print "adding a rule = %s" % r #if len(phrase) < self.max_length and i+spanlen < len(fwords) and pathlen+spanlen < self.max_initial_size: if len(phrase) < self.max_length and i+spanlen < len(fwords) and pathlen+1 <= self.max_initial_size: #to prevent [X] #print "lexicalized" for alt_id in xrange(len(fwords[i+spanlen])): #if (fwords[i+spanlen][alt_id][2]+pathlen+spanlen <= self.max_initial_size): #new_frontier.append((k, i+spanlen, alt_id, pathlen + spanlen, node, phrase, is_shadow_path)) #print "alt_id = %d\n" % alt_id new_frontier.append((k, i+spanlen, alt_id, pathlen + 1, node, phrase, is_shadow_path)) #print (k, i+spanlen, alt_id, pathlen + spanlen, node, map(sym.tostring,phrase), is_shadow_path) #print "end lexicalized" num_subpatterns = arity if not is_shadow_path: num_subpatterns = num_subpatterns + 1 #to avoid X ... we want next to a lexicalized item #if k>0 and i X_1 w X_2 / X_1 X_2. This is probably # not worth the bother, though. #print "find_fixpoint0" 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: #print "find_fixpoint1" return 0 if e_high[0] - e_low[0] > max_e_len: #print "find_fixpoint2" 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: #print "find_fixpoint3" 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: # log.writeln(" FAIL: f phrase is not tight") #print " FAIL: f phrase is not tight" return 0 if f_back_high[0] - f_back_low[0] > max_f_len: # log.writeln(" FAIL: f back projection is too wide") #print " FAIL: f back projection is too wide" return 0 if allow_high_x == 0 and f_back_high[0] > f_high: # log.writeln(" FAIL: extension on high side not allowed") #print " 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: # log.writeln(" FAIL: extension required on low side violates max # of gaps") #print " 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: # log.writeln(" FAIL: extension required on low side violates max initial length") #print " FAIL: extension required on low side violates max initial length" return 0 if f_back_low[0] < 0: # log.writeln(" FAIL: extension required on low side violates sentence boundary") #print " 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: # log.writeln(" FAIL: extension required on high side violates max # of gaps") #print " 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: # log.writeln(" FAIL: extension required on high side violates max initial length") #print " FAIL: extension required on high side violates max initial length" return 0 if f_back_high[0] > f_sent_len: # log.writeln(" FAIL: extension required on high side violates sentence boundary") #print " 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: # log.writeln(" FAIL: arbitrary expansion not permitted") #print " FAIL: arbitrary expansion not permitted" return 0 if e_high[0] - e_low[0] > max_e_len: # log.writeln(" FAIL: re-projection violates sentence max phrase length") #print " 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 cintlist.CIntList ephr_arr cdef result #print "inside extract_phrases" #print "f_low=%d, f_high=%d" % (f_low,f_high) result = [] len1 = 0 e_gaps1 = malloc(0) ephr_arr = cintlist.CIntList() 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 self.tight_phrases == 0: 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 self.tight_phrases == 0: 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((rule.Phrase(ephr_arr),indexes)) free(e_gaps1) free(e_gap_order) return result cdef create_alignments(self, int* sent_links, int num_links, findexes, eindexes): #print "create_alignments" #s = "sent_links = " #i = 0 #while (i < num_links*2): # s = s+"%d-%d " % (sent_links[i],sent_links[i+1]) # i += 2 #print s #print findexes #print eindexes ret = cintlist.CIntList() for i in xrange(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, rule.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 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 float available_mass cdef extracts, phrase_list cdef cintlist.CIntList fphr_arr cdef rule.Phrase fphr cdef reason_for_failure fphr_arr = cintlist.CIntList() 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 available_mass = 1.0 if matching.sent_id == self.excluded_sent_id: available_mass = 0.0 self.findexes1.reset() sofar = 0 for i in xrange(num_chunks): for j in xrange(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 xrange(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 = rule.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) #print "e_low=%d, e_high=%d, gap_start=%d, num_gaps=%d, f_back_low=%d, f_back_high=%d" & (e_low, e_high, gap_start, num_gaps, f_back_low, f_back_high) if len(phrase_list) > 0: pair_count = available_mass / 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 self.extract_file: self.extract_file.write("%s ||| %s ||| %f ||| %d: [%d, %d] -> [%d, %d]\n" % (fphr, phrase2, pair_count, matching.sent_id+1, f_back_low, f_back_high, e_low, e_high)) #print "extract_phrases1: %s ||| %s ||| %f ||| %d: [%d, %d] -> [%d, %d]\n" % (fphr, phrase2, pair_count, matching.sent_id+1, f_back_low, f_back_high, e_low, e_high) 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 = rule.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 = available_mass / 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 self.extract_file: self.extract_file.write("%s ||| %s ||| %f ||| %d: [%d, %d] -> [%d, %d]\n" % (fphr, phrase2, pair_count, matching.sent_id+1, f_x_low, f_x_high, e_x_low, e_x_high)) #print "extract_phrases2: %s ||| %s ||| %f ||| %d: [%d, %d] -> [%d, %d]\n" % (fphr, phrase2, pair_count, matching.sent_id+1, f_x_low, f_x_high, e_x_low, e_x_high) 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 = rule.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 = available_mass / 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 self.extract_file: self.extract_file.write("%s ||| %s ||| %f ||| %d: [%d, %d] -> [%d, %d]\n" % (fphr, phrase2, pair_count, matching.sent_id+1, f_x_low, f_x_high, e_x_low, e_x_high)) #print "extract_phrases3: %s ||| %s ||| %f ||| %d: [%d, %d] -> [%d, %d]\n" % (fphr, phrase2, pair_count, matching.sent_id+1, f_x_low, f_x_high, e_x_low, e_x_high) 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 = rule.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 = available_mass / 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))) if self.extract_file: self.extract_file.write("%s ||| %s ||| %f ||| %d: [%d, %d] -> [%d, %d]\n" % (fphr, phrase2, pair_count, matching.sent_id+1, f_x_low, f_x_high, e_x_low, e_x_high)) #print "extract_phrases4 %s ||| %s ||| %f ||| %d: [%d, %d] -> [%d, %d]\n" % (fphr, phrase2, pair_count, matching.sent_id+1, f_x_low, f_x_high, e_x_low, e_x_high) 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) if self.sample_file is not None: self.sample_file.write("%s ||| %d: [%d, %d] ||| %d ||| %s\n" % (phrase, matching.sent_id+1, f_low, f_high, len(extracts), reason_for_failure)) #print "%s ||| %d: [%d, %d] ||| %d ||| %s\n" % (phrase, matching.sent_id+1, f_low, f_high, len(extracts), reason_for_failure) return extracts