[
https://issues.apache.org/jira/browse/LUCENE-2089?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12836491#action_12836491
]
Robert Muir commented on LUCENE-2089:
-------------------------------------
based on the work mike provided here (slightly modified), N=2 appears to work
correctly (all correct results so far). I will figure out a way to exhaustively
test this beast :)
For now, here are the updated benchmarks, again same 10M terms, on my regular
old HDD, you can scroll up to see how big of a difference N=2 makes, compared
to only having N=1 available!
I think with N=2 implemented, its also clear, that PQ size can actually be more
important than using a prefix. For instance, I'm very happy with the
performance here with a smaller PQ size of 64.
{{Minimum Sim = 0.73f (edit distance of 1)}}
||Prefix Length||PQ Size||Avg MS (old)||Avg MS (new)||
|0|1024|3286.0|7.8|
|0|64|3320.4|7.6|
|1|1024|316.8|5.6|
|1|64|314.3|5.6|
|2|1024|31.8|3.8|
|2|64|31.9|3.7|
{{Minimum Sim = 0.58f (edit distance of 2)}}
||Prefix Length||PQ Size||Avg MS (old)||Avg MS (new)||
|0|1024|4223.3|87.7|
|0|64|4199.7|12.6|
|1|1024|430.1|56.4|
|1|64|392.8|9.3|
|2|1024|82.5|45.5|
|2|64|38.4|6.2|
{{Minimum Sim = 0.43f (edit distance of 3)}}
||Prefix Length||PQ Size||Avg MS (old)||Avg MS (new)||
|0|1024|5299.9|424.0|
|0|64|5231.8|54.1|
|1|1024|522.9|103.6|
|1|64|480.9|14.5|
|2|1024|89.0|67.9|
|2|64|46.3|6.8|
{{Minimum Sim = 0.29f (edit distance of 4)}}
||Prefix Length||PQ Size||Avg MS (old)||Avg MS (new)||
|0|1024|6258.1|363.7|
|0|64|6247.6|75.6|
|1|1024|609.9|108.3|
|1|64|567.1|13.3|
|2|1024|98.6|66.6|
|2|64|55.6|6.8|
> explore using automaton for fuzzyquery
> --------------------------------------
>
> Key: LUCENE-2089
> URL: https://issues.apache.org/jira/browse/LUCENE-2089
> Project: Lucene - Java
> Issue Type: Improvement
> Components: Search
> Affects Versions: Flex Branch
> Reporter: Robert Muir
> Assignee: Mark Miller
> Priority: Minor
> Fix For: Flex Branch
>
> Attachments: ContrivedFuzzyBenchmark.java, gen.py, gen.py, gen.py,
> gen.py, Lev2ParametricDescription.java, Lev2ParametricDescription.java,
> Lev2ParametricDescription.java, Lev2ParametricDescription.java,
> LUCENE-2089.patch, LUCENE-2089.patch, LUCENE-2089.patch, LUCENE-2089.patch,
> LUCENE-2089.patch, LUCENE-2089_concat.patch, Moman-0.2.1.tar.gz,
> TestFuzzy.java
>
>
> 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
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: java-dev-h...@lucene.apache.org
