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

explore using automaton for fuzzyquery

    Details

    • Type: Improvement
    • Status: Closed
    • Priority: Minor
    • Resolution: Fixed
    • Affects Version/s: 4.0-ALPHA
    • Fix Version/s: 4.0-ALPHA
    • Component/s: core/search
    • Labels:
      None
    • Lucene Fields:
      New, Patch Available

      Description

      we can optimize fuzzyquery by using AutomatonTermsEnum. The idea is to speed up the core FuzzyQuery in similar fashion to Wildcard and Regex speedups, maintaining all backwards compatibility.

      The advantages are:

      • we can seek to terms that are useful, instead of brute-forcing the entire terms dict
      • we can determine matches faster, as true/false from a DFA is array lookup, don't even need to run levenshtein.

      We build Levenshtein DFAs in linear time with respect to the length of the word: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.16.652

      To implement support for 'prefix' length, we simply concatenate two DFAs, which doesn't require us to do NFA->DFA conversion, as the prefix portion is a singleton. the concatenation is also constant time with respect to the size of the fuzzy DFA, it only need examine its start state.

      with this algorithm, parametric tables are precomputed so that DFAs can be constructed very quickly.
      if the required number of edits is too large (we don't have a table for it), we use "dumb mode" at first (no seeking, no DFA, just brute force like now).

      As the priority queue fills up during enumeration, the similarity score required to be a competitive term increases, so, the enum gets faster and faster as this happens. This is because terms in core FuzzyQuery are sorted by boost value, then by term (in lexicographic order).

      For a large term dictionary with a low minimal similarity, you will fill the pq very quickly since you will match many terms.
      This not only provides a mechanism to switch to more efficient DFAs (edit distance of 2 -> edit distance of 1 -> edit distance of 0) during enumeration, but also to switch from "dumb mode" to "smart mode".

      With this design, we can add more DFAs at any time by adding additional tables. The tradeoff is the tables get rather large, so for very high K, we would start to increase the size of Lucene's jar file. The idea is we don't have include large tables for very high K, by using the 'competitive boost' attribute of the priority queue.

      For more information, see http://en.wikipedia.org/wiki/Levenshtein_automaton

        Attachments

        1. LUCENE-2089.patch
          108 kB
          Robert Muir
        2. LUCENE-2089.patch
          66 kB
          Robert Muir
        3. createLevAutomata.py
          14 kB
          Michael McCandless
        4. LUCENE-2089.patch
          63 kB
          Robert Muir
        5. moman-57f5dc9dd0e7.diff
          3 kB
          Robert Muir
        6. LUCENE-2089.patch
          224 kB
          Robert Muir
        7. LUCENE-2089.patch
          224 kB
          Robert Muir
        8. LUCENE-2089.patch
          221 kB
          Michael McCandless
        9. LUCENE-2089.patch
          58 kB
          Robert Muir
        10. LUCENE-2089.patch
          225 kB
          Michael McCandless
        11. LUCENE-2089.patch
          215 kB
          Michael McCandless
        12. LUCENE-2089.patch
          180 kB
          Robert Muir
        13. gen.py
          7 kB
          Michael McCandless
        14. LUCENE-2089.patch
          257 kB
          Robert Muir
        15. gen.py
          5 kB
          Robert Muir
        16. Lev2ParametricDescription.java
          214 kB
          Michael McCandless
        17. gen.py
          5 kB
          Michael McCandless
        18. Lev2ParametricDescription.java
          214 kB
          Michael McCandless
        19. gen.py
          5 kB
          Michael McCandless
        20. Lev2ParametricDescription.java
          213 kB
          Michael McCandless
        21. gen.py
          5 kB
          Michael McCandless
        22. Lev2ParametricDescription.java
          212 kB
          Michael McCandless
        23. gen.py
          3 kB
          Michael McCandless
        24. ContrivedFuzzyBenchmark.java
          5 kB
          Robert Muir
        25. LUCENE-2089.patch
          30 kB
          Robert Muir
        26. LUCENE-2089_concat.patch
          1 kB
          Robert Muir
        27. LUCENE-2089.patch
          29 kB
          Robert Muir
        28. LUCENE-2089.patch
          29 kB
          Robert Muir
        29. LUCENE-2089.patch
          28 kB
          Robert Muir
        30. LUCENE-2089.patch
          21 kB
          Robert Muir
        31. TestFuzzy.java
          3 kB
          Robert Muir
        32. Moman-0.2.1.tar.gz
          18 kB
          Mark Miller

          Issue Links

            Activity

              People

              • Assignee:
                rcmuir Robert Muir
                Reporter:
                rcmuir Robert Muir
              • Votes:
                0 Vote for this issue
                Watchers:
                1 Start watching this issue

                Dates

                • Created:
                  Updated:
                  Resolved: