Uploaded image for project: 'Lucene - Core'
  1. Lucene - Core
  2. LUCENE-2792

Add a simple FST impl to Lucene


    • New Feature
    • Status: Closed
    • Major
    • Resolution: Fixed
    • None
    • 4.0-ALPHA
    • core/index
    • None
    • New


      I implemented the algo described at
      http://citeseerx.ist.psu.edu/viewdoc/summary?doi= for
      incrementally building a finite state transducer (FST) from sorted

      This is not a fully general FST impl – it's only able to build up an
      FST incrementally from input/output pairs that are pre-sorted.

      Currently the inputs are BytesRefs, and the outputs are pluggable –
      NoOutputs gets you a simple FSA, PositiveIntOutputs maps to a long,
      ByteSequenceOutput maps to a BytesRef.

      The implementation has a low memory overhead, so that it can handle a
      fairly large set of terms. For example, it can build the FSA for the
      9.8M terms from a 10M document wikipedia index in ~8 seconds (on
      beast), using ~256 MB peak RAM, resulting in an FSA that's ~60 MB.

      It packs the FST as-it-builds into a compact byte[], and then exposes
      the API to read nodes/arcs directly from the byte[]. The FST can be
      quickly saved/loaded to/from a Directory since it's just a big byte[].

      The format is similar to what Morfologik uses

      I think there are a number of possible places we can use this in
      Lucene. For example, I think many apps could hold the entire terms
      dict in RAM, either at the multi-reader level or maybe per-segment
      (mapping to file offset or to something else custom to the app), which
      may possibly be a good speedup for certain MTQs (though, because the
      format is packed into a byte[], there is a decode cost when visiting

      The builder can also prune as it goes, so you get a prefix trie pruned
      according to how many terms run through the nodes, which makes it
      faster and even less memory consuming. This may be useful as a
      replacement for our current binary search terms index since it can
      achieve higher term density for the same RAM consumption of our
      current index.

      As an initial usage to make sure this is exercised, I cutover the
      SimpleText codec, which currently fully loads all terms into a
      TreeMap (and has caused intermittent OOME in some tests), to use an FST
      instead. SimpleText uses a PairOutputs which is able to "pair up" any
      two other outputs, since it needs to map each input term to an int
      docFreq and long filePosition.

      All tests pass w/ SimpleText forced codec, and I think this is
      committable except I'd love to get some help w/ the generics
      (confession to the policeman: I had to add


      )) all over!! Ideally an FST is
      parameterized by its output type (Integer, BytesRef, etc.).

      I even added a new @nightly test that makes a largeish set of random
      terms and tests the resulting FST on different outputs

      I think it would also be easy to make a variant that uses char[]
      instead of byte[] as its inputs, so we could eg use this during analysis
      (Robert's idea). It's already be easy to have a CharSequence
      output type since the outputs are pluggable.

      Dawid Weiss (author of HPPC – http://labs.carrotsearch.com/hppc.html – and
      Morfologik – http://sourceforge.net/projects/morfologik/)
      was very helpful iterating with me on this (thank you!).


        1. FSTExample.png
          69 kB
          Michael McCandless
        2. LUCENE-2792.patch
          157 kB
          Uwe Schindler
        3. LUCENE-2792.patch
          157 kB
          Michael McCandless
        4. LUCENE-2792.patch
          145 kB
          Uwe Schindler
        5. LUCENE-2792.patch
          145 kB
          Robert Muir
        6. LUCENE-2792.patch
          141 kB
          Michael McCandless
        7. LUCENE-2792.patch
          99 kB
          Michael McCandless
        8. LUCENE-2792-ArrayUtil-grow.patch
          11 kB
          Uwe Schindler
        9. SimpleBench.java
          2 kB
          Robert Muir



            mikemccand Michael McCandless
            mikemccand Michael McCandless
            1 Vote for this issue
            2 Start watching this issue