fixed conflicts

1 files changed, 433 insertions, 21 deletions

diff --git a/python/src/sa/rulefactory.pxi b/python/src/sa/rulefactory.pxi
index 5f6558b3..7063c2da 100644
--- a/python/src/sa/rulefactory.pxi
+++ b/python/src/sa/rulefactory.pxi
@@ -23,7 +23,17 @@ FeatureContext = namedtuple('FeatureContext',
      'test_sentence',
      'f_text',
      'e_text',
-     'meta'
+     'meta',
+     'online'
+    ])
+
+OnlineFeatureContext = namedtuple('OnlineFeatureContext',
+    ['fcount',
+     'fsample_count',
+     'paircount',
+     'bilex_f',
+     'bilex_e',
+     'bilex_fe'
     ])
 
 cdef int PRECOMPUTE = 0
@@ -257,13 +267,23 @@ cdef class HieroCachingRuleFactory:
     cdef Alignment alignment
     cdef IntList eid2symid
     cdef IntList fid2symid
-    cdef int tight_phrases
-    cdef int require_aligned_terminal
-    cdef int require_aligned_chunks
+    cdef bint tight_phrases
+    cdef bint require_aligned_terminal
+    cdef bint require_aligned_chunks
 
     cdef IntList findexes
     cdef IntList findexes1
 
+    cdef bint online
+    cdef samples_f
+    cdef phrases_f
+    cdef phrases_e
+    cdef phrases_fe
+    cdef phrases_al
+    cdef bilex_f
+    cdef bilex_e
+    cdef bilex_fe
+
     def __cinit__(self,
             # compiled alignment object (REQUIRED)
             Alignment alignment,
@@ -299,8 +319,8 @@ cdef class HieroCachingRuleFactory:
             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,
-            # True if phrases should be tight, False otherwise (False == slower but better results)
-            bint tight_phrases=False,
+            # 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
@@ -354,28 +374,41 @@ cdef class HieroCachingRuleFactory:
         self.precompute_secondary_rank = precompute_secondary_rank
         self.use_baeza_yates = use_baeza_yates
         self.by_slack_factor = by_slack_factor
-        if tight_phrases:
-            self.tight_phrases = 1
-        else:
-            self.tight_phrases = 0
+        self.tight_phrases = tight_phrases
 
         if require_aligned_chunks:
             # one condition is a stronger version of the other.
-            self.require_aligned_chunks = 1
-            self.require_aligned_terminal = 1
+            self.require_aligned_chunks = self.require_aligned_terminal = True
         elif require_aligned_terminal:
-            self.require_aligned_chunks = 0
-            self.require_aligned_terminal = 1
+            self.require_aligned_chunks = False
+            self.require_aligned_terminal = True
         else:
-            self.require_aligned_chunks = 0
-            self.require_aligned_terminal = 0
-        
+            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)
+        
+        # Online stats 
+        
+        # True after data is added
+        self.online = False
+        
+        # Keep track of everything that can be sampled:
+        self.samples_f = defaultdict(int)
+        
+        # Phrase counts
+        self.phrases_f = defaultdict(int)
+        self.phrases_e = defaultdict(int)
+        self.phrases_fe = defaultdict(lambda: defaultdict(int))
+        self.phrases_al = defaultdict(lambda: defaultdict(tuple))
+
+        # Bilexical counts
+        self.bilex_f = defaultdict(int)
+        self.bilex_e = defaultdict(int)
+        self.bilex_fe = defaultdict(lambda: defaultdict(int))
 
     def configure(self, SuffixArray fsarray, DataArray edarray,
             Sampler sampler, Scorer scorer):
@@ -954,6 +987,11 @@ cdef class HieroCachingRuleFactory:
         hit = 0
         reachable_buffer = {}
 
+        # Phrase pairs processed by suffix array extractor.  Do not re-extract
+        # during online extraction.  This is probably the hackiest part of
+        # online grammar extraction.
+        seen_phrases = set()
+        
         # Do not cache between sentences
         self.rules.root = ExtendedTrieNode(phrase_location=PhraseLocation())
 
@@ -1109,7 +1147,12 @@ cdef class HieroCachingRuleFactory:
                                                f, e, count, fcount[f], num_samples,
                                                (k,i+spanlen), locs, input_match, 
                                                fwords, self.fda, self.eda,
-                                               meta))
+                                               meta,
+                                               # Include online stats.  None if none.
+                                               self.online_ctx_lookup(f, e)))
+                                    # Phrase pair processed
+                                    if self.online:
+                                        seen_phrases.add((f, e))
                                     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:
@@ -1133,7 +1176,29 @@ cdef class HieroCachingRuleFactory:
                         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
-                
+        
+        # Online rule extraction and scoring
+        if self.online:
+            f_syms = tuple(word[0][0] for word in fwords)
+            for (f, lex_i, lex_j) in self.get_f_phrases(f_syms):
+                spanlen = (lex_j - lex_i) + 1
+                if not sym_isvar(f[0]):
+                    spanlen += 1
+                if not sym_isvar(f[1]):
+                    spanlen += 1
+                for e in self.phrases_fe.get(f, ()):
+                    if (f, e) not in seen_phrases:
+                        # Don't add multiple instances of the same phrase here
+                        seen_phrases.add((f, e))
+                        scores = self.scorer.score(FeatureContext(
+                                f, e, 0, 0, 0,
+                                spanlen, None, None, 
+                                fwords, self.fda, self.eda,
+                                meta,
+                                self.online_ctx_lookup(f, e)))
+                        alignment = self.phrases_al[f][e]
+                        yield Rule(self.category, f, e, scores, alignment)
+             
         stop_time = monitor_cpu()
         logger.info("Total time for rule lookup, extraction, and scoring = %f seconds", (stop_time - start_time))
         gc.collect()
@@ -1315,7 +1380,7 @@ cdef class HieroCachingRuleFactory:
 
         e_x_low = e_low
         e_x_high = e_high
-        if self.tight_phrases == 0:
+        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:
@@ -1331,7 +1396,7 @@ cdef class HieroCachingRuleFactory:
             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:
+            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:
@@ -1804,3 +1869,350 @@ cdef class HieroCachingRuleFactory:
         free(e_gap_high)
 
         return extracts
+
+    #
+    # Online grammar extraction handling
+    #
+    
+    # Aggregate stats from a training instance
+    # (Extract rules, update counts)
+    def add_instance(self, f_words, e_words, alignment):
+
+        self.online = True
+        
+        # Rules extracted from this instance
+        # Track span of lexical items (terminals) to make
+        # sure we don't extract the same rule for the same
+        # span more than once.
+        # (f, e, al, lex_f_i, lex_f_j)
+        rules = set()
+
+        f_len = len(f_words)
+        e_len = len(e_words)
+
+        # Pre-compute alignment info
+        al = [[] for i in range(f_len)]
+        fe_span = [[e_len + 1, -1] for i in range(f_len)]
+        ef_span = [[f_len + 1, -1] for i in range(e_len)]
+        for (f, e) in alignment:
+            al[f].append(e)
+            fe_span[f][0] = min(fe_span[f][0], e)
+            fe_span[f][1] = max(fe_span[f][1], e)
+            ef_span[e][0] = min(ef_span[e][0], f)
+            ef_span[e][1] = max(ef_span[e][1], f)
+
+        # Target side word coverage
+        cover = [0] * e_len
+        # Non-terminal coverage
+        f_nt_cover = [0] * f_len
+        e_nt_cover = [0] * e_len
+        
+        # Extract all possible hierarchical phrases starting at a source index
+        # f_ i and j are current, e_ i and j are previous
+        # We care _considering_ f_j, so it is not yet in counts
+        def extract(f_i, f_j, e_i, e_j, min_bound, wc, links, nt, nt_open):
+            # Phrase extraction limits
+            if f_j > (f_len - 1) or (f_j - f_i) + 1 > self.max_initial_size:
+                return
+            # Unaligned word
+            if not al[f_j]:
+                # Adjacent to non-terminal: extend (non-terminal now open)
+                if nt and nt[-1][2] == f_j - 1:
+                    nt[-1][2] += 1
+                    extract(f_i, f_j + 1, e_i, e_j, min_bound, wc, links, nt, True)
+                    nt[-1][2] -= 1
+                # Unless non-terminal already open, always extend with word
+                # Make sure adding a word doesn't exceed length
+                if not nt_open and wc < self.max_length:
+                    extract(f_i, f_j + 1, e_i, e_j, min_bound, wc + 1, links, nt, False)
+                return
+            # Aligned word
+            link_i = fe_span[f_j][0]
+            link_j = fe_span[f_j][1]
+            new_e_i = min(link_i, e_i)
+            new_e_j = max(link_j, e_j)
+            # Check reverse links of newly covered words to see if they violate left
+            # bound (return) or extend minimum right bound for chunk
+            new_min_bound = min_bound
+            # First aligned word creates span
+            if e_j == -1: 
+                for i from new_e_i <= i <= new_e_j:
+                    if ef_span[i][0] < f_i:
+                        return
+                    new_min_bound = max(new_min_bound, ef_span[i][1])
+            # Other aligned words extend span
+            else:
+                for i from new_e_i <= i < e_i:
+                    if ef_span[i][0] < f_i:
+                        return
+                    new_min_bound = max(new_min_bound, ef_span[i][1])
+                for i from e_j < i <= new_e_j:
+                    if ef_span[i][0] < f_i:
+                        return
+                    new_min_bound = max(new_min_bound, ef_span[i][1])
+            # Extract, extend with word (unless non-terminal open)
+            if not nt_open:
+                nt_collision = False
+                for link in al[f_j]:
+                    if e_nt_cover[link]:
+                        nt_collision = True
+                # Non-terminal collisions block word extraction and extension, but
+                # may be okay for continuing non-terminals
+                if not nt_collision and wc < self.max_length:
+                    plus_links = []
+                    for link in al[f_j]:
+                        plus_links.append((f_j, link))
+                        cover[link] += 1
+                    links.append(plus_links)
+                    if links and f_j >= new_min_bound:
+                        rules.add(self.form_rule(f_i, new_e_i, f_words[f_i:f_j + 1], e_words[new_e_i:new_e_j + 1], nt, links))
+                    extract(f_i, f_j + 1, new_e_i, new_e_j, new_min_bound, wc + 1, links, nt, False)
+                    links.pop()
+                    for link in al[f_j]:
+                        cover[link] -= 1
+            # Try to add a word to current non-terminal (if any), extract, extend
+            if nt and nt[-1][2] == f_j - 1:
+                # Add to non-terminal, checking for collisions
+                old_last_nt = nt[-1][:]
+                nt[-1][2] = f_j
+                if link_i < nt[-1][3]:
+                    if not span_check(cover, link_i, nt[-1][3] - 1):
+                        nt[-1] = old_last_nt
+                        return
+                    span_inc(cover, link_i, nt[-1][3] - 1)
+                    span_inc(e_nt_cover, link_i, nt[-1][3] - 1)
+                    nt[-1][3] = link_i
+                if link_j > nt[-1][4]:
+                    if not span_check(cover, nt[-1][4] + 1, link_j):
+                        nt[-1] = old_last_nt
+                        return
+                    span_inc(cover, nt[-1][4] + 1, link_j)
+                    span_inc(e_nt_cover, nt[-1][4] + 1, link_j)
+                    nt[-1][4] = link_j
+                if links and f_j >= new_min_bound:
+                    rules.add(self.form_rule(f_i, new_e_i, f_words[f_i:f_j + 1], e_words[new_e_i:new_e_j + 1], nt, links))
+                extract(f_i, f_j + 1, new_e_i, new_e_j, new_min_bound, wc, links, nt, False)
+                nt[-1] = old_last_nt
+                if link_i < nt[-1][3]:
+                    span_dec(cover, link_i, nt[-1][3] - 1)
+                    span_dec(e_nt_cover, link_i, nt[-1][3] - 1)
+                if link_j > nt[-1][4]:
+                    span_dec(cover, nt[-1][4] + 1, link_j)
+                    span_dec(e_nt_cover, nt[-1][4] + 1, link_j)
+            # Try to start a new non-terminal, extract, extend
+            if (not nt or f_j - nt[-1][2] > 1) and wc < self.max_length and len(nt) < self.max_nonterminals:
+                # Check for collisions
+                if not span_check(cover, link_i, link_j):
+                    return
+                span_inc(cover, link_i, link_j)
+                span_inc(e_nt_cover, link_i, link_j)
+                nt.append([(nt[-1][0] + 1) if nt else 1, f_j, f_j, link_i, link_j])
+                # Require at least one word in phrase
+                if links and f_j >= new_min_bound:
+                    rules.add(self.form_rule(f_i, new_e_i, f_words[f_i:f_j + 1], e_words[new_e_i:new_e_j + 1], nt, links))
+                extract(f_i, f_j + 1, new_e_i, new_e_j, new_min_bound, wc + 1, links, nt, False)
+                nt.pop()
+                span_dec(cover, link_i, link_j)
+                span_dec(e_nt_cover, link_i, link_j)
+
+        # Try to extract phrases from every f index
+        for f_i from 0 <= f_i < f_len:
+            # Skip if phrases won't be tight on left side
+            if not al[f_i]:
+                continue
+            extract(f_i, f_i, f_len + 1, -1, f_i, 0, [], [], False)
+        
+        # Update possible phrases (samples)
+        # This could be more efficiently integrated with extraction
+        # at the cost of readability
+        for (f, lex_i, lex_j) in self.get_f_phrases(f_words):
+            self.samples_f[f] += 1
+            
+        # Update phrase counts
+        for rule in rules:
+            (f_ph, e_ph, al) = rule[:3]
+            self.phrases_f[f_ph] += 1
+            self.phrases_e[e_ph] += 1
+            self.phrases_fe[f_ph][e_ph] += 1
+            if not self.phrases_al[f_ph][e_ph]:
+                self.phrases_al[f_ph][e_ph] = al
+            
+        # Update Bilexical counts
+        for e_w in e_words:
+            self.bilex_e[e_w] += 1
+        for f_w in f_words:
+            self.bilex_f[f_w] += 1
+            for e_w in e_words:
+                self.bilex_fe[f_w][e_w] += 1
+
+    # Create a rule from source, target, non-terminals, and alignments
+    def form_rule(self, f_i, e_i, f_span, e_span, nt, al):
+    
+        # Substitute in non-terminals
+        nt_inv = sorted(nt, cmp=lambda x, y: cmp(x[3], y[3]))
+        f_sym = list(f_span[:])
+        off = f_i
+        for next_nt in nt:
+            nt_len = (next_nt[2] - next_nt[1]) + 1
+            i = 0
+            while i < nt_len:
+                f_sym.pop(next_nt[1] - off)
+                i += 1
+            f_sym.insert(next_nt[1] - off, sym_setindex(self.category, next_nt[0]))
+            off += (nt_len - 1)
+        e_sym = list(e_span[:])
+        off = e_i
+        for next_nt in nt_inv:
+            nt_len = (next_nt[4] - next_nt[3]) + 1
+            i = 0
+            while i < nt_len:
+                e_sym.pop(next_nt[3] - off)
+                i += 1
+            e_sym.insert(next_nt[3] - off, sym_setindex(self.category, next_nt[0]))
+            off += (nt_len - 1)
+    
+        # Adjusting alignment links takes some doing
+        links = [list(link) for sub in al for link in sub]
+        links_inv = sorted(links, cmp=lambda x, y: cmp(x[1], y[1]))
+        links_len = len(links)
+        nt_len = len(nt)
+        nt_i = 0
+        off = f_i
+        i = 0
+        while i < links_len:
+            while nt_i < nt_len and links[i][0] > nt[nt_i][1]:
+                off += (nt[nt_i][2] - nt[nt_i][1])
+                nt_i += 1
+            links[i][0] -= off
+            i += 1
+        nt_i = 0
+        off = e_i
+        i = 0
+        while i < links_len:
+            while nt_i < nt_len and links_inv[i][1] > nt_inv[nt_i][3]:
+                off += (nt_inv[nt_i][4] - nt_inv[nt_i][3])
+                nt_i += 1
+            links_inv[i][1] -= off
+            i += 1
+        
+        # Find lexical span
+        lex_f_i = f_i
+        lex_f_j = f_i + (len(f_span) - 1)
+        if nt:
+            if nt[0][1] == lex_f_i:
+                lex_f_i += (nt[0][2] - nt[0][1]) + 1
+            if nt[-1][2] == lex_f_j:
+                lex_f_j -= (nt[-1][2] - nt[-1][1]) + 1
+
+        # Create rule (f_phrase, e_phrase, links, f_link_min, f_link_max)
+        f = Phrase(f_sym)
+        e = Phrase(e_sym)
+        a = tuple(self.alignment.link(i, j) for (i, j) in links)
+        return (f, e, a, lex_f_i, lex_f_j)
+
+    # Rule string from rule
+    def fmt_rule(self, f, e, a):
+        a_str = ' '.join('{0}-{1}'.format(*self.alignment.unlink(packed)) for packed in a)
+        return '[X] ||| {0} ||| {1} ||| {2}'.format(f, e, a_str)
+    
+    # Debugging
+    def dump_online_stats(self):
+        logger.info('------------------------------')
+        logger.info('         Online Stats         ')
+        logger.info('------------------------------')
+        logger.info('f')
+        for w in self.bilex_f:
+            logger.info(sym_tostring(w) + ' : ' + str(self.bilex_f[w]))
+        logger.info('e')
+        for w in self.bilex_e:
+            logger.info(sym_tostring(w) + ' : ' + str(self.bilex_e[w]))
+        logger.info('fe')
+        for w in self.bilex_fe:
+            for w2 in self.bilex_fe[w]:
+                logger.info(sym_tostring(w) + ' : ' + sym_tostring(w2) + ' : ' + str(self.bilex_fe[w][w2]))
+        logger.info('F')
+        for ph in self.phrases_f:
+            logger.info(str(ph) + ' ||| ' + str(self.phrases_f[ph]))
+        logger.info('E')
+        for ph in self.phrases_e:
+            logger.info(str(ph) + ' ||| ' + str(self.phrases_e[ph]))
+        logger.info('FE')
+        self.dump_online_rules()
+
+    def dump_online_rules(self):
+        for ph in self.phrases_fe:
+            for ph2 in self.phrases_fe[ph]:
+                logger.info(self.fmt_rule(str(ph), str(ph2), self.phrases_al[ph][ph2]) + ' ||| ' + str(self.phrases_fe[ph][ph2]))
+                    
+    # Lookup online stats for phrase pair (f, e).  Return None if no match.
+    # IMPORTANT: use get() to avoid adding items to defaultdict
+    def online_ctx_lookup(self, f, e):
+        if self.online:
+            fcount = self.phrases_f.get(f, 0)
+            fsample_count = self.samples_f.get(f, 0)
+            d = self.phrases_fe.get(f, None)
+            paircount = d.get(e, 0) if d else 0
+            return OnlineFeatureContext(fcount, fsample_count, paircount, self.bilex_f, self.bilex_e, self.bilex_fe)
+        return None
+    
+    # Find all phrases that we might try to extract
+    # (Used for EGivenFCoherent)
+    # Return set of (fphrase, lex_i, lex_j)
+    def get_f_phrases(self, f_words):
+
+        f_len = len(f_words)
+        phrases = set() # (fphrase, lex_i, lex_j)
+        
+        def extract(f_i, f_j, lex_i, lex_j, wc, ntc, syms):
+            # Phrase extraction limits
+            if f_j > (f_len - 1) or (f_j - f_i) + 1 > self.max_initial_size:
+                return
+            # Extend with word
+            if wc + ntc < self.max_length:
+                syms.append(f_words[f_j])
+                f = Phrase(syms)
+                new_lex_i = min(lex_i, f_j)
+                new_lex_j = max(lex_j, f_j)
+                phrases.add((f, new_lex_i, new_lex_j))
+                extract(f_i, f_j + 1, new_lex_i, new_lex_j, wc + 1, ntc, syms)
+                syms.pop()
+            # Extend with existing non-terminal
+            if syms and sym_isvar(syms[-1]):
+                # Don't re-extract the same phrase
+                extract(f_i, f_j + 1, lex_i, lex_j, wc, ntc, syms)
+            # Extend with new non-terminal
+            if wc + ntc < self.max_length:
+                if not syms or (ntc < self.max_nonterminals and not sym_isvar(syms[-1])):
+                    syms.append(sym_setindex(self.category, ntc + 1))
+                    f = Phrase(syms)
+                    if wc > 0:
+                        phrases.add((f, lex_i, lex_j))
+                    extract(f_i, f_j + 1, lex_i, lex_j, wc, ntc + 1, syms)
+                    syms.pop()
+            
+        # Try to extract phrases from every f index
+        for f_i from 0 <= f_i < f_len:
+            extract(f_i, f_i, f_len, -1, 0, 0, [])
+
+        return phrases
+    
+# Spans are _inclusive_ on both ends [i, j]
+def span_check(vec, i, j):
+    k = i
+    while k <= j:
+        if vec[k]:
+            return False
+        k += 1
+    return True
+
+def span_inc(vec, i, j):
+    k = i
+    while k <= j:
+        vec[k] += 1
+        k += 1
+
+def span_dec(vec, i, j):
+    k = i
+    while k <= j:
+        vec[k] -= 1
+        k += 1