lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Dawid Weiss (JIRA)" <>
Subject [jira] [Commented] (SOLR-2378) FST-based Lookup (suggestions) for prefix matches.
Date Sat, 02 Apr 2011 11:54:05 GMT


Dawid Weiss commented on SOLR-2378:

Soliciting feedback on the following questions:
- suggesters currently have float weights associated with terms; can these floats be bucketed
and returned in approximation or do they need to be exact copies of the input? For automata,
bucketed weights (to, let's say 5-10 different values) provide terrific speed/size improvements,
so if this is not a rigid requirement, I'd use them.
- is there any info on threading of Solr components? I am in particular looking for mutable
object fields in the suggester (can a single suggester instance be accessed by multiple threads
at the same time)?

I've implemented preliminary FST-based lookup (without weights yet). Speed-wise it doesn't
rock because data is converted to/from utf8 on input/output and sorted during construction,
but it is still acceptable, even at this early stage I think:

JaspellLookup        buildTime[ms]=112 lookupTime[ms]=288
TSTLookup            buildTime[ms]=115 lookupTime[ms]=103
FSTLookup            buildTime[ms]=464 lookupTime[ms]=145

now... that was speed only, check out the in-memory size :)

JaspellLookup        size[B]=81,078,997
TSTLookup            size[B]=53,453,696
FSTLookup            size[B]=2,909,396

(This benchmark stores very limited vocabulary items -- long numbers only, so it is skewed
from reality, but it's nice to see something like this, huh?).

> FST-based Lookup (suggestions) for prefix matches.
> --------------------------------------------------
>                 Key: SOLR-2378
>                 URL:
>             Project: Solr
>          Issue Type: New Feature
>          Components: spellchecker
>            Reporter: Dawid Weiss
>            Assignee: Dawid Weiss
>              Labels: lookup, prefix
>             Fix For: 4.0
> Implement a subclass of Lookup based on finite state automata/ transducers (Lucene FST
package). This issue is for implementing a relatively basic prefix matcher, we will handle
infixes and other types of input matches gradually. Impl. phases:
> - write a DFA based suggester effectively identical to ternary tree based solution right
> - baseline benchmark against tern. tree (memory consumption, rebuilding speed, indexing
speed; reuse Andrzej's benchmark code)
> - modify DFA to encode term weights directly in the automaton (optimize for onlyMostPopular
> - benchmark again
> - add infix suggestion support with prefix matches boosted higher (?)
> - benchmark again
> - modify the tutorial on the wiki []

This message is automatically generated by JIRA.
For more information on JIRA, see:

To unsubscribe, e-mail:
For additional commands, e-mail:

View raw message