Merge branch 'master' of https://github.com/pauldb89/cdec

5 files changed, 492 insertions, 26 deletions

diff --git a/python/pkg/cdec/sa/__init__.py b/python/pkg/cdec/sa/__init__.py
index e0a344b7..14ba5ecb 100644
--- a/python/pkg/cdec/sa/__init__.py
+++ b/python/pkg/cdec/sa/__init__.py
@@ -1,4 +1,5 @@
 from cdec.sa._sa import make_lattice, decode_lattice, decode_sentence,\
+        encode_words, decode_words, isvar,\
         SuffixArray, DataArray, LCP, Precomputation, Alignment, BiLex,\
         HieroCachingRuleFactory, Sampler, Scorer
 from cdec.sa.extractor import GrammarExtractor
diff --git a/python/pkg/cdec/sa/extract.py b/python/pkg/cdec/sa/extract.py
index 87b7d5d4..dc72c18c 100644
--- a/python/pkg/cdec/sa/extract.py
+++ b/python/pkg/cdec/sa/extract.py
@@ -10,11 +10,13 @@ import cdec.sa
 from cdec.sa._sa import monitor_cpu
 
 extractor, prefix = None, None
+online = False
+
 def make_extractor(config, grammars, features):
-    global extractor, prefix
+    global extractor, prefix, online
     signal.signal(signal.SIGINT, signal.SIG_IGN) # Let parent process catch Ctrl+C
     load_features(features)
-    extractor = cdec.sa.GrammarExtractor(config)
+    extractor = cdec.sa.GrammarExtractor(config, online)
     prefix = grammars
 
 def load_features(features):
@@ -26,22 +28,37 @@ def load_features(features):
         sys.path.remove(prefix)
 
 def extract(inp):
-    global extractor, prefix
+    global extractor, prefix, online
     i, sentence = inp
     sentence = sentence[:-1]
     fields = re.split('\s*\|\|\|\s*', sentence)
     suffix = ''
-    if len(fields) > 1:
-        sentence = fields[0]
-        suffix = ' ||| ' + ' ||| '.join(fields[1:])
+    # 3 fields for online mode, 1 for normal
+    if online:
+        if len(fields) < 3:
+            sys.stderr.write('Error: online mode requires references and alignments.'
+                    '  Not adding sentence to training data: {0}\n'.format(sentence))
+            sentence = fields[0]
+        else:
+            sentence, reference, alignment = fields[0:3]
+        if len(fields) > 3:
+            suffix = ' ||| ' + ' ||| '.join(fields[3:])
+    else:
+        if len(fields) > 1:
+            sentence = fields[0]
+            suffix = ' ||| ' + ' ||| '.join(fields[1:])
     grammar_file = os.path.join(prefix, 'grammar.{0}'.format(i))
     with open(grammar_file, 'w') as output:
         for rule in extractor.grammar(sentence):
             output.write(str(rule)+'\n')
+    # Add training instance _after_ extracting grammars
+    if online:
+        extractor.add_instance(sentence, reference, alignment)
     grammar_file = os.path.abspath(grammar_file)
     return '<seg grammar="{0}" id="{1}"> {2} </seg>{3}'.format(grammar_file, i, sentence, suffix)
 
 def main():
+    global online
     logging.basicConfig(level=logging.INFO)
     parser = argparse.ArgumentParser(description='Extract grammars from a compiled corpus.')
     parser.add_argument('-c', '--config', required=True,
@@ -54,6 +71,8 @@ def main():
                         help='number of sentences / chunk')
     parser.add_argument('-f', '--features', nargs='*', default=[],
                         help='additional feature definitions')
+    parser.add_argument('-o', '--online', action='store_true', default=False,
+                        help='online grammar extraction')
     args = parser.parse_args()
 
     if not os.path.exists(args.grammars):
@@ -64,6 +83,8 @@ def main():
                     ' should be a python module\n'.format(featdef))
             sys.exit(1)
 
+    online = args.online
+
     start_time = monitor_cpu()
     if args.jobs > 1:
         logging.info('Starting %d workers; chunk size: %d', args.jobs, args.chunksize)
diff --git a/python/pkg/cdec/sa/extractor.py b/python/pkg/cdec/sa/extractor.py
index e09f79ea..acc13cbc 100644
--- a/python/pkg/cdec/sa/extractor.py
+++ b/python/pkg/cdec/sa/extractor.py
@@ -1,15 +1,16 @@
 from itertools import chain
-import os
+import os, sys
 import cdec.configobj
 from cdec.sa.features import EgivenFCoherent, SampleCountF, CountEF,\
-        MaxLexEgivenF, MaxLexFgivenE, IsSingletonF, IsSingletonFE
+        MaxLexEgivenF, MaxLexFgivenE, IsSingletonF, IsSingletonFE,\
+        IsSupportedOnline
 import cdec.sa
 
 # maximum span of a grammar rule in TEST DATA
 MAX_INITIAL_SIZE = 15
 
 class GrammarExtractor:
-    def __init__(self, config, features=None):
+    def __init__(self, config, online=False, features=None):
         if isinstance(config, basestring):
             if not os.path.exists(config):
                 raise IOError('cannot read configuration from {0}'.format(config))
@@ -57,11 +58,19 @@ class GrammarExtractor:
         # lexical weighting tables
         tt = cdec.sa.BiLex(from_binary=config['lex_file'])
 
+        # TODO: clean this up
+        extended_features = []
+        if online:
+            extended_features.append(IsSupportedOnline)
+            
         # TODO: use @cdec.sa.features decorator for standard features too
         # + add a mask to disable features
+        for f in cdec.sa._SA_FEATURES:
+            extended_features.append(f)
+            
         scorer = cdec.sa.Scorer(EgivenFCoherent, SampleCountF, CountEF, 
             MaxLexFgivenE(tt), MaxLexEgivenF(tt), IsSingletonF, IsSingletonFE,
-            *cdec.sa._SA_FEATURES)
+            *extended_features)
 
         fsarray = cdec.sa.SuffixArray(from_binary=config['f_sa_file'])
         edarray = cdec.sa.DataArray(from_binary=config['e_file'])
@@ -82,3 +91,16 @@ class GrammarExtractor:
         meta = cdec.sa.annotate(words)
         cnet = cdec.sa.make_lattice(words)
         return self.factory.input(cnet, meta)
+
+    # Add training instance to data
+    def add_instance(self, sentence, reference, alignment):
+        f_words = cdec.sa.encode_words(sentence.split())
+        e_words = cdec.sa.encode_words(reference.split())
+        al = sorted(tuple(int(i) for i in pair.split('-')) for pair in alignment.split())
+        self.factory.add_instance(f_words, e_words, al)
+    
+    # Debugging
+    def dump_online_stats(self):
+        self.factory.dump_online_stats()
+    def dump_online_rules(self):
+        self.factory.dump_online_rules()
\ No newline at end of file
diff --git a/python/pkg/cdec/sa/features.py b/python/pkg/cdec/sa/features.py
index a4ae23e8..46412cd5 100644
--- a/python/pkg/cdec/sa/features.py
+++ b/python/pkg/cdec/sa/features.py
@@ -1,57 +1,142 @@
 from __future__ import division
 import math
 
+from cdec.sa import isvar
+
 MAXSCORE = 99
 
 def EgivenF(ctx): # p(e|f) = c(e, f)/c(f)
-    return -math.log10(ctx.paircount/ctx.fcount)
+    if not ctx.online:
+        prob = ctx.paircount/ctx.fcount
+    else:
+        prob = (ctx.paircount + ctx.online.paircount) / (ctx.fcount + ctx.online.fcount)
+    return -math.log10(prob)
 
 def CountEF(ctx): # c(e, f)
-    return math.log10(1 + ctx.paircount)
+    if not ctx.online:
+        count = 1 + ctx.paircount
+    else:
+        count = 1 + ctx.paircount + ctx.online.paircount
+    return math.log10(count)
 
 def SampleCountF(ctx): # sample c(f)
-    return math.log10(1 + ctx.fsample_count)
+    if not ctx.online:
+        count = 1 + ctx.fsample_count
+    else:
+        count = 1 + ctx.fsample_count + ctx.online.fsample_count
+    return math.log10(count)
 
 def EgivenFCoherent(ctx): # c(e, f) / sample c(f)
-    prob = ctx.paircount/ctx.fsample_count
+    if not ctx.online:
+        prob = ctx.paircount/ctx.fsample_count
+    else:
+        prob = (ctx.paircount + ctx.online.paircount) / (ctx.fsample_count + ctx.online.fsample_count)
     return -math.log10(prob) if prob > 0 else MAXSCORE
 
 def CoherenceProb(ctx): # c(f) / sample c(f)
-    return -math.log10(ctx.fcount/ctx.fsample_count)
+    if not ctx.online:
+        prob = ctx.fcount/ctx.fsample_count
+    else:
+        prob = (ctx.fcount + ctx.online.fcount) / (ctx.fsample_count + ctx.online.fsample_count)
+    return -math.log10(prob)
 
 def MaxLexEgivenF(ttable):
     def MaxLexEgivenF(ctx):
         fwords = ctx.fphrase.words
         fwords.append('NULL')
-        def score():
+        # Always use this for now
+        if not ctx.online or ctx.online:
+            maxOffScore = 0.0
+            for e in ctx.ephrase.words:
+                maxScore = max(ttable.get_score(f, e, 0) for f in fwords)
+                maxOffScore += -math.log10(maxScore) if maxScore > 0 else MAXSCORE
+            return maxOffScore
+        else:
+            # For now, straight average
+            maxOffScore = 0.0
+            maxOnScore = 0.0
             for e in ctx.ephrase.words:
-              maxScore = max(ttable.get_score(f, e, 0) for f in fwords)
-              yield -math.log10(maxScore) if maxScore > 0 else MAXSCORE
-        return sum(score())
+                maxScore = max(ttable.get_score(f, e, 0) for f in fwords)
+                maxOffScore += -math.log10(maxScore) if maxScore > 0 else MAXSCORE
+            for e in ctx.ephrase:
+                if not isvar(e):
+                    maxScore = 0.0
+                    for f in ctx.fphrase:
+                        if not isvar(f):
+                            b_f = ctx.online.bilex_f.get(f, 0)
+                            if b_f:
+                                maxScore = max(maxScore, ctx.online.bilex_fe.get(f, {}).get(e))
+                    maxOnScore += -math.log10(maxScore) if maxScore > 0 else MAXSCORE
+            return (maxOffScore + maxOnScore) / 2
     return MaxLexEgivenF
 
 def MaxLexFgivenE(ttable):
     def MaxLexFgivenE(ctx):
         ewords = ctx.ephrase.words
         ewords.append('NULL')
-        def score():
+        # Always use this for now
+        if not ctx.online or ctx.online:
+            maxOffScore = 0.0
             for f in ctx.fphrase.words:
-              maxScore = max(ttable.get_score(f, e, 1) for e in ewords)
-              yield -math.log10(maxScore) if maxScore > 0 else MAXSCORE
-        return sum(score())
+                maxScore = max(ttable.get_score(f, e, 1) for e in ewords)
+                maxOffScore += -math.log10(maxScore) if maxScore > 0 else MAXSCORE
+            return maxOffScore
+        else:
+            # For now, straight average
+            maxOffScore = 0.0
+            maxOnScore = 0.0
+            for f in ctx.fphrase.words:
+                maxScore = max(ttable.get_score(f, e, 1) for e in ewords)
+                maxOffScore += -math.log10(maxScore) if maxScore > 0 else MAXSCORE
+            for f in ctx.fphrase:
+                if not isvar(f):
+                    maxScore = 0.0
+                    for e in ctx.ephrase:
+                        if not isvar(e):
+                            b_e = ctx.online.bilex_e.get(e, 0)
+                            if b_e:
+                                maxScore = max(maxScore, ctx.online.bilex_fe.get(f, {}).get(e, 0) / b_e )
+                    maxOnScore += -math.log10(maxScore) if maxScore > 0 else MAXSCORE
+            return (maxOffScore + maxOnScore) / 2
     return MaxLexFgivenE
 
 def IsSingletonF(ctx):
-    return (ctx.fcount == 1)
+    if not ctx.online:
+        count = ctx.fcount
+    else:
+        count = ctx.fcount + ctx.online.fcount  
+    return (count == 1)
 
 def IsSingletonFE(ctx):
-    return (ctx.paircount == 1)
+    if not ctx.online:
+        count = ctx.paircount
+    else:
+        count = ctx.paircount + ctx.online.paircount
+    return (count == 1)
 
 def IsNotSingletonF(ctx):
-    return (ctx.fcount > 1)
+    if not ctx.online:
+        count = ctx.fcount
+    else:
+        count = ctx.fcount + ctx.online.fcount
+    return (count > 1)
 
 def IsNotSingletonFE(ctx):
+    if not ctx.online:
+        count = ctx.paircount
+    else:
+        count = ctx.paircount + ctx.online.paircount
     return (ctx.paircount > 1)
 
 def IsFEGreaterThanZero(ctx):
+    if not ctx.online:
+        count = ctx.paircount
+    else:
+        count = ctx.paircount + ctx.online.paircount
     return (ctx.paircount > 0.01)
+
+def IsSupportedOnline(ctx): # Occurs in online data?
+    if ctx.online:
+        return (ctx.online.paircount > 0.01)
+    else:
+        return False
\ No newline at end of file
diff --git a/python/pkg/cdec/sa/online_extractor.py b/python/pkg/cdec/sa/online_extractor.py
new file mode 100755
index 00000000..03a46b3b
--- /dev/null
+++ b/python/pkg/cdec/sa/online_extractor.py
@@ -0,0 +1,337 @@
+#!/usr/bin/env python
+
+import collections, sys
+
+import cdec.configobj
+
+CAT = '[X]'  # Default non-terminal
+MAX_SIZE = 15  # Max span of a grammar rule (source)
+MAX_LEN = 5  # Max number of terminals and non-terminals in a rule (source)
+MAX_NT = 2  # Max number of non-terminals in a rule
+MIN_GAP = 1  # Min number of terminals between non-terminals (source)
+
+# Spans are _inclusive_ on both ends [i, j]
+# TODO: Replace all of this with bit vectors?
+def span_check(vec, i, j):
+    k = i
+    while k <= j:
+        if vec[k]:
+            return False
+        k += 1
+    return True
+
+def span_flip(vec, i, j):
+    k = i
+    while k <= j:
+        vec[k] = ~vec[k]
+        k += 1
+
+# Next non-terminal
+def next_nt(nt):
+     if not nt:
+         return 1
+     return nt[-1][0] + 1
+
+class NonTerminal:
+    def __init__(self, index):
+        self.index = index
+    def __str__(self):
+        return '[X,{0}]'.format(self.index)
+
+def fmt_rule(f_sym, e_sym, links):
+    a_str = ' '.join('{0}-{1}'.format(i, j) for (i, j) in links)
+    return '[X] ||| {0} ||| {1} ||| {2}'.format(' '.join(str(sym) for sym in f_sym),
+                                                ' '.join(str(sym) for sym in e_sym),
+                                                a_str)
+
+class OnlineGrammarExtractor:
+
+    def __init__(self, config=None):
+        if isinstance(config, str) or isinstance(config, unicode):
+            if not os.path.exists(config):
+                raise IOError('cannot read configuration from {0}'.format(config))
+            config = cdec.configobj.ConfigObj(config, unrepr=True)
+        elif not config:
+            config = collections.defaultdict(lambda: None)
+        self.category = CAT
+        self.max_size = MAX_SIZE
+        self.max_length = config['max_len'] or MAX_LEN
+        self.max_nonterminals = config['max_nt'] or MAX_NT
+        self.min_gap_size = MIN_GAP
+        # Hard coded: require at least one aligned word
+        # Hard coded: require tight phrases
+
+        # Phrase counts
+        self.phrases_f = collections.defaultdict(lambda: 0)
+        self.phrases_e = collections.defaultdict(lambda: 0)
+        self.phrases_fe = collections.defaultdict(lambda: collections.defaultdict(lambda: 0))
+
+        # Bilexical counts
+        self.bilex_f = collections.defaultdict(lambda: 0)
+        self.bilex_e = collections.defaultdict(lambda: 0)
+        self.bilex_fe = collections.defaultdict(lambda: collections.defaultdict(lambda: 0))
+
+    # Aggregate bilexical counts
+    def aggr_bilex(self, f_words, e_words):
+
+        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
+
+    # Aggregate stats from a training instance:
+    # Extract hierarchical phrase pairs
+    # Update bilexical counts
+    def add_instance(self, f_words, e_words, alignment):
+
+        # Bilexical counts
+        self.aggr_bilex(f_words, e_words)
+
+        # Phrase pairs extracted from this instance
+        phrases = set()
+
+        f_len = len(f_words)
+        e_len = len(e_words)
+
+        # Pre-compute alignment info
+        al = [[] for i in range(f_len)]
+        al_span = [[f_len + 1, -1] for i in range(f_len)]
+        for (f, e) in alignment:
+            al[f].append(e)
+            al_span[f][0] = min(al_span[f][0], e)
+            al_span[f][1] = max(al_span[f][1], e)
+
+        # Target side word coverage
+        # TODO: Does Cython do bit vectors?
+        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
+        def extract(f_i, f_j, e_i, e_j, wc, links, nt, nt_open):
+            # Phrase extraction limits
+            if wc + len(nt) > self.max_length or (f_j + 1) > f_len or \
+                    (f_j - f_i) + 1 > self.max_size:
+                return
+            # Unaligned word
+            if not al[f_j]:
+                # Open non-terminal: extend
+                if nt_open:
+                    nt[-1][2] += 1
+                    extract(f_i, f_j + 1, e_i, e_j, wc, links, nt, True)
+                    nt[-1][2] -= 1
+                # No open non-terminal: extend with word
+                else:
+                    extract(f_i, f_j + 1, e_i, e_j, wc + 1, links, nt, False)
+                return
+            # Aligned word
+            link_i = al_span[f_j][0]
+            link_j = al_span[f_j][1]
+            new_e_i = min(link_i, e_i)
+            new_e_j = max(link_j, e_j)
+            # Open non-terminal: close, extract, extend
+            if nt_open:
+                # Close 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_flip(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_flip(cover, nt[-1][4] + 1, link_j)
+                    nt[-1][4] = link_j
+                for rule in self.form_rules(f_i, new_e_i, f_words[f_i:f_j + 1], e_words[new_e_i:new_e_j + 1], nt, links):
+                    phrases.add(rule)
+                extract(f_i, f_j + 1, new_e_i, new_e_j, wc, links, nt, False)
+                nt[-1] = old_last_nt
+                if link_i < nt[-1][3]:
+                    span_flip(cover, link_i, nt[-1][3] - 1)
+                if link_j > nt[-1][4]:
+                    span_flip(cover, nt[-1][4] + 1, link_j)
+                return
+            # No open non-terminal
+            # Extract, extend with word
+            collision = False
+            for link in al[f_j]:
+                if cover[link]:
+                    collision = True
+            # Collisions block extraction and extension, but may be okay for
+            # continuing non-terminals
+            if not collision:
+                plus_links = []
+                for link in al[f_j]:
+                    plus_links.append((f_j, link))
+                    cover[link] = ~cover[link]
+                links.append(plus_links)
+                for rule in self.form_rules(f_i, new_e_i, f_words[f_i:f_j + 1], e_words[new_e_i:new_e_j + 1], nt, links):
+                    phrases.add(rule)
+                extract(f_i, f_j + 1, new_e_i, new_e_j, wc + 1, links, nt, False)
+                links.pop()
+                for link in al[f_j]:
+                    cover[link] = ~cover[link]
+            # Try to add a word to a (closed) non-terminal, 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_flip(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_flip(cover, nt[-1][4] + 1, link_j)
+                    nt[-1][4] = link_j
+                # Require at least one word in phrase
+                if links:
+                    for rule in self.form_rules(f_i, new_e_i, f_words[f_i:f_j + 1], e_words[new_e_i:new_e_j + 1], nt, links):
+                        phrases.add(rule)
+                extract(f_i, f_j + 1, new_e_i, new_e_j, wc, links, nt, False)
+                nt[-1] = old_last_nt
+                if new_e_i < nt[-1][3]:
+                    span_flip(cover, link_i, nt[-1][3] - 1)
+                if link_j > nt[-1][4]:
+                    span_flip(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 len(nt) < self.max_nonterminals:
+                # Check for collisions
+                if not span_check(cover, link_i, link_j):
+                    return
+                span_flip(cover, link_i, link_j)
+                nt.append([next_nt(nt), f_j, f_j, link_i, link_j])
+                # Require at least one word in phrase
+                if links:
+                    for rule in self.form_rules(f_i, new_e_i, f_words[f_i:f_j + 1], e_words[new_e_i:new_e_j + 1], nt, links):
+                        phrases.add(rule)
+                extract(f_i, f_j + 1, new_e_i, new_e_j, wc, links, nt, False)
+                nt.pop()
+                span_flip(cover, link_i, link_j)
+            # TODO: try adding NT to start, end, both
+            # check: one aligned word on boundary that is not part of a NT
+
+        # Try to extract phrases from every f index
+        f_i = 0
+        while f_i < f_len:
+            # Skip if phrases won't be tight on left side
+            if not al[f_i]:
+                f_i += 1
+                continue
+            extract(f_i, f_i, f_len + 1, -1, 1, [], [], False)
+            f_i += 1
+
+        for rule in sorted(phrases):
+            print rule
+
+    # Create a rule from source, target, non-terminals, and alignments
+    def form_rules(self, f_i, e_i, f_span, e_span, nt, al):
+    
+        # This could be more efficient but is unlikely to be the bottleneck
+    
+        rules = []
+    
+        nt_inv = sorted(nt, cmp=lambda x, y: cmp(x[3], y[3]))
+    
+        f_sym = 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, NonTerminal(next_nt[0]))
+            off += (nt_len - 1)
+    
+        e_sym = 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, NonTerminal(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_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[i][1] > nt_inv[nt_i][3]:
+                off += (nt_inv[nt_i][4] - nt_inv[nt_i][3])
+                nt_i += 1
+            links[i][1] -= off
+            i += 1
+    
+        # Rule
+        rules.append(fmt_rule(f_sym, e_sym, links))
+        if len(f_sym) >= self.max_length or len(nt) >= self.max_nonterminals:
+            return rules
+        last_index = nt[-1][0] if nt else 0
+        # Rule [X]
+        if not nt or not isinstance(f_sym[-1], NonTerminal):
+            f_sym.append(NonTerminal(last_index + 1))
+            e_sym.append(NonTerminal(last_index + 1))
+            rules.append(fmt_rule(f_sym, e_sym, links))
+            f_sym.pop()
+            e_sym.pop()
+        # [X] Rule
+        if not nt or not isinstance(f_sym[0], NonTerminal):
+            for sym in f_sym:
+                if isinstance(sym, NonTerminal):
+                    sym.index += 1
+            for sym in e_sym:
+                if isinstance(sym, NonTerminal):
+                    sym.index += 1
+            for link in links:
+                link[0] += 1
+                link[1] += 1
+            f_sym.insert(0, NonTerminal(1))
+            e_sym.insert(0, NonTerminal(1))
+            rules.append(fmt_rule(f_sym, e_sym, links))
+        if len(f_sym) >= self.max_length or len(nt) + 1 >= self.max_nonterminals:
+            return rules
+        # [X] Rule [X]
+        if not nt or not isinstance(f_sym[-1], NonTerminal):
+            f_sym.append(NonTerminal(last_index + 2))
+            e_sym.append(NonTerminal(last_index + 2))
+            rules.append(fmt_rule(f_sym, e_sym, links))
+        return rules
+
+def main(argv):
+
+    extractor = OnlineGrammarExtractor()
+
+    for line in sys.stdin:
+        print >> sys.stderr, line.strip()
+        f_words, e_words, a_str = (x.split() for x in line.split('|||'))
+        alignment = sorted(tuple(int(y) for y in x.split('-')) for x in a_str)
+        extractor.add_instance(f_words, e_words, alignment)
+
+if __name__ == '__main__':
+    main(sys.argv)