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.

#-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.

+ 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