Lt-trim

lt-trim is the lttoolbox application responsible for trimming compiled dictionaries. The analyses (right-side when compiling lr) of analyser_binary are trimmed to the input side of bidix_binary (left-side when compiling lr, right-side when compiling rl), such that only analyses which would pass through `lt-proc -b bidix_binary' are kept.

Both compund tags (`<compound-only-L>', `<compound-R>') and join elements (`<j/>' in XML, `+' in the stream) and the group element (`<g/>' in XML, `#' in the stream) should be handled correctly, even combinations of + followed by # in monodix are handled.

One minor caveat: If you have the capitalised lemma "Foo" in the monodix, but "foo" in the bidix, an analysis "^Foo<tag>$" would pass through bidix when doing lt-proc -b, but will not make it through trimming. Make sure your lemmas have the same capitalisation in the different dictionaries.

You should not trim a generator unless you have a very simple translator pipeline, since the output of bidix seldom goes unchanged through transfer.

Usage

$ lt-trim analyser_binary bidix_binary trimmed_analyser_binary

E.g. to trim ca-en.automorf.bin using ca-en.autobil.bin:

$ lt-trim ca-en.automorf.bin ca-en.autobil.bin ca-en.automorf-trimmed.bin

Implementation

lt-trim expects regular compiled analyser and bidix binaries as input, and produces a new analyser binary as output.

It loads analyser and bidix (named trimmer in the code), and loops through all the analyser states, trying to do the same steps in parallel with the bidix. Transitions which are possible to do in both, are added to the trimmed analyser.

First, the bidix binary is preprocessed a bit, in memory:

• all sections are unioned into one big section
  • see Transducer::unionWith
• the final state gets a "loopback" transition to itself for every tag in the monodix
  • see Transducer::appendDotStar and Alphabet::createLoopbackSymbols
  • This is because foo<n><ind> should pass through lt-proc -b bidix.bin even if only foo<n> is actually in bidix
• all lemq's (the # or <g> group elements) are moved so they are after the tags
  • monodix always has the # part after tags, while bidix has them on the lemma
  • see Transducer::moveLemqsLast, and the below sections on multiwords

Then, in Transducer::intersect we do a depth first traversal of the states of the monodix, building up a new trimmed monodix.

Pseudocode for intersect

Transducer trimmed;
m = { initial: trimmed.initial }
SearchState current = (initial, trimmer.initial, trimmer.initial)
todo = [ current ]
seen = {}
while(todo):
  current = todo.pop()
  seen.insert(current)
  (this_src, trimmer_src, trimmer_preplus) = current
  for this_trg, this_left, this_right in transitions[this_src]:
    if this_right == '+':
      SearchState next = (this_trg, trimmer.initial, trimmer_src)
      if not next in seen: todo.push(next)
      if not this_trg in m: m[this_trg]=trimmed.newState()
      trimmed.linkStates(m[this_src], m[this_trg], this_right, this_left)
    else:
      if this_right == '#' and trimmer_preplus != trimmer_src:
        # We've seen a '#' after a '+':
        trimmer_src = trimmer_preplus
      for trimmer_trg, trimmer_left, trimmer_right in trimmer.transitions[trimmer_src]:
        if trimmer_preplus == trimmer_src:
          trimmer_preplus_next = trimmer_trg
        else:
          trimmer_preplus_next = trimmer_preplus
        if trimmer_left==ε and this_right!=ε:
          # Just skip the epsilon in trimmer:
          SearchState next = (this_src, trimmer_trg, trimmer_preplus_next)
          if not next in seen: todo.push(next)
        elif this_right == trimmer_left or isCompoundSymbol(this_right) or this_right==ε:
          if isCompoundSymbol(this_right) or this_right==ε: 
            # Just skip the epsilon/cmp-sym in this:
            trimmer_trg = trimmer_src
          SearchState next = (this_trg, trimmer_trg, trimmer_preplus_next)
          if not next in seen: todo.push(next)
          if not this_trg in m: m[this_trg]=trimmed.newState()
          trimmed.linkStates(m[this_src], m[this_trg], this_right, this_left)

trimmed.finals = m[this.finals]

#-type multiwords

The implementation: first "preprocess" (in memory) the bidix FST so it has the same format as the analyser, ie. instead of "take# out<vblex>" it has "take<vblex># out".

Say you have these entries in the bidix:

take# out<vblex>
take# out<n>
take# in<vblex>
take<n>
take<vblex>

We do a depth-first traversal, and then after reading all of "take", we see t=transition(A, B, ε, #). We remove that transition, and instead add the result of copyWithTagsFirst(t), which returns a new transducer that represents these partial analyses:

<vblex># out
<n># out
<vblex># in

Pseudocode for #-type multiwords

def moveLemqsLast()
  new_t = Transducer()
  seen = set()
  todo = [initial]
  while todo:
    src = todo.pop()
    for left, right, trg in transitions[src]:
      if left == '#':
        new_t.transitions[src][epsilon].insertTransducer( copyWithTagsFirst(trg) )
      else:
        new_t.linkStates(src, trg, left, right)
        if trg not in seen:
          todo.push(trg)
    seen.insert(trg)
  return new_t

def copyWithTagsFirst(start):
  seen = set()
  new_t = Transducer()
  lemq = Transducer()
  # not shown below since it's quite trivial: states in new_t/lemq will get 
  # different indices from corresponding states in this, so we need to record 
  # those correspondences in a table in order to use the right one:
  states_this_new = { start: new_t.initial }
  states_this_lemq = { start: lemq.initial }
  # In the first loop, "finally" is filled with states from lemq and 
  # new_t that need to be reconnected:
  finally = []
  todo = [(start,start)]
  while todo:
    src,lemq_last = todo.pop()
    for left, right, trg in transitions[src]:
      if not isTag(left):
        lemq.linkStates(src, trg, label)
        if trg,trg not in seen:
          todo.push((trg, trg))
      else:
        if src == lemq_last
          new_t.linkState(start, trg, epsilon)
        else:
          new_t.linkState(src, trg, label)
        if src in finals:
          finally.insert((src, lemq_last))
        if src,lemq_last not in seen:
          todo.push((trg, lemq_last)) 
    seen.insert((src, lemq_last))
  # lemq_last was the last non-tag connected to the tag sequence that lead to lasttag:
  for lasttag, lemq_last in finally:
    newlemq = Transducer(lemq) # copy lemq
    newlemq.finals = set(lemq_last) # let lemq_last be the only final state in newlemq
    newlemq.minimize()
    new_t.insertTransducer(lasttag, newlemq) # append newlemq after finaltag
  return new_t

+ type multiwords

join (<j>) is handled by setting the next trimmer (bidix) target state to be trimmer.initial, so we simply skip to the start in the bidix. However, + and # together can get a bit complicated, see below.

+ and # together

If we have a + followed by a # in monodix, we need to get back to where we were after reading the + part. An example:

monodix, one entry:
foo<n><ind>+bar<pr># fie

bidix, two entries:
foo# fie<n>
bar<pr>

preprocessed (prefixed+lemq-moved) bidix, two entries:
foo<n>[<n>|<ind>|<pr>]*# fie
bar<pr>[<n>|<ind>|<pr>]*

We start by matching on these paths:

monodix string  foo<n><ind> + bar<pr> # fie
monodix states g           i j       k
  bidix string  foo<n>[<n>|<ind>|<pr>]* # fie
  bidix states l                       m

and get as far as state pair (i,m), having consumed

foo<n><ind>

before seeing a +.

Now, the next SearchState records both the next monodix state (j, the state after +), the next bidix state (l, the bidix initial state), and the bidix state we were in when we saw the plus (m, at the end of the bidix tag list). So in the code SearchState next = (this_trg, trimmer.initial, trimmer_src).

At (i,l,m) we've consumed

foo<n><ind>

and have

bar<pr># fie

left, and can read from bidix initial l:

monodix string  bar<pr> # fie
monodix states j       k
__bidix string  bar<n>[<n>|<ind>|<pr>]*
__bidix states l                       n

We match all of

bar<pr>

and then see a # in monodix, giving SearchState (k,n,m). Since both the third part of SearchState is set to state m (where m!=n), and we've seen a #, we jump back to that state m, from where we can match # fie, and we're done.

TODO

• Would it make things faster if we first clear out the right-sides of the bidix and minimize that?
• remove all those ifdef DEBUG's and wcerr's
• more tests?
• if no objections: git svn dcommit

See also

• Automatically trimming a monodix#lttoolbox