Class FSTCompletion
- java.lang.Object
-
- org.apache.lucene.search.suggest.fst.FSTCompletion
-
public class FSTCompletion extends java.lang.Object
Finite state automata based implementation of "autocomplete" functionality.- See Also:
FSTCompletionBuilder
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description static class
FSTCompletion.Completion
A single completion for a given key.
-
Field Summary
Fields Modifier and Type Field Description private FST<java.lang.Object>
automaton
Finite state automaton encoding all the lookup terms.static int
DEFAULT_BUCKETS
Default number of buckets.private static java.util.ArrayList<FSTCompletion.Completion>
EMPTY_RESULT
An empty result.private boolean
exactFirst
private boolean
higherWeightsFirst
private FST.Arc<java.lang.Object>[]
rootArcs
An array of arcs leaving the root automaton state and encoding weights of all completions in their sub-trees.
-
Constructor Summary
Constructors Constructor Description FSTCompletion(FST<java.lang.Object> automaton)
Defaults to higher weights first and exact first.FSTCompletion(FST<java.lang.Object> automaton, boolean higherWeightsFirst, boolean exactFirst)
Constructs an FSTCompletion, specifying higherWeightsFirst and exactFirst.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description private static FST.Arc<java.lang.Object>[]
cacheRootArcs(FST<java.lang.Object> automaton)
Cache the root node's output arcs starting with completions with the highest weights.private java.util.stream.Stream<? extends FSTCompletion.Completion>
completionStream(BytesRef output, int bucket, FST.Arc<java.lang.Object> fromArc)
Return a stream of all completions starting from the provided arc.private boolean
descendWithPrefix(FST.Arc<java.lang.Object> arc, BytesRef utf8)
Descend along the path starting atarc
and going through bytes in the argument.int
getBucket(java.lang.CharSequence key)
Returns the bucket assigned to a given key (if found) or-1
if no exact match exists.int
getBucketCount()
Returns the bucket count (discretization thresholds).private int
getExactMatchStartingFromRootArc(int rootArcIndex, BytesRef utf8)
Returns the first exact match by traversing root arcs, starting from the arcrootArcIndex
.FST<java.lang.Object>
getFST()
Returns the internal automaton.java.util.stream.Stream<FSTCompletion.Completion>
lookup(java.lang.CharSequence key)
Lookup suggestions tokey
and return a stream of matching completions.java.util.List<FSTCompletion.Completion>
lookup(java.lang.CharSequence key, int num)
Lookup suggestions tokey
.private java.util.stream.Stream<FSTCompletion.Completion>
lookupSortedByWeight(BytesRef key)
Lookup suggestions sorted by weight (descending order).
-
-
-
Field Detail
-
DEFAULT_BUCKETS
public static final int DEFAULT_BUCKETS
Default number of buckets.- See Also:
- Constant Field Values
-
EMPTY_RESULT
private static final java.util.ArrayList<FSTCompletion.Completion> EMPTY_RESULT
An empty result. Keep this anArrayList
to keep all the returned lists of single type (monomorphic calls).
-
automaton
private final FST<java.lang.Object> automaton
Finite state automaton encoding all the lookup terms. See class notes for details.
-
rootArcs
private final FST.Arc<java.lang.Object>[] rootArcs
An array of arcs leaving the root automaton state and encoding weights of all completions in their sub-trees.
-
exactFirst
private boolean exactFirst
- See Also:
FSTCompletion(FST, boolean, boolean)
-
higherWeightsFirst
private boolean higherWeightsFirst
- See Also:
FSTCompletion(FST, boolean, boolean)
-
-
Constructor Detail
-
FSTCompletion
public FSTCompletion(FST<java.lang.Object> automaton, boolean higherWeightsFirst, boolean exactFirst)
Constructs an FSTCompletion, specifying higherWeightsFirst and exactFirst.- Parameters:
automaton
- Automaton with completions. SeeFSTCompletionBuilder
.higherWeightsFirst
- Return most popular suggestions first. This is the default behavior for this implementation. Setting it tofalse
has no effect (use constant term weights to sort alphabetically only).exactFirst
- Find and push an exact match to the first position of the result list if found.
-
FSTCompletion
public FSTCompletion(FST<java.lang.Object> automaton)
Defaults to higher weights first and exact first.- See Also:
FSTCompletion(FST, boolean, boolean)
-
-
Method Detail
-
cacheRootArcs
private static FST.Arc<java.lang.Object>[] cacheRootArcs(FST<java.lang.Object> automaton)
Cache the root node's output arcs starting with completions with the highest weights.
-
getExactMatchStartingFromRootArc
private int getExactMatchStartingFromRootArc(int rootArcIndex, BytesRef utf8)
Returns the first exact match by traversing root arcs, starting from the arcrootArcIndex
.- Parameters:
rootArcIndex
- The first root arc index inrootArcs
to consider when matching.utf8
- The sequence of utf8 bytes to follow.- Returns:
- Returns the bucket number of the match or
-1
if no match was found.
-
lookup
public java.util.List<FSTCompletion.Completion> lookup(java.lang.CharSequence key, int num)
Lookup suggestions tokey
.- Parameters:
key
- The prefix to which suggestions should be sought.num
- At most this number of suggestions will be returned.- Returns:
- Returns the suggestions, sorted by their approximated weight first (decreasing) and then alphabetically (UTF-8 codepoint order).
-
lookup
public java.util.stream.Stream<FSTCompletion.Completion> lookup(java.lang.CharSequence key)
Lookup suggestions tokey
and return a stream of matching completions. The stream fetches completions dynamically - it can be filtered and limited to acquire the desired number of completions without collecting all of them.- Parameters:
key
- The prefix to which suggestions should be sought.- Returns:
- Returns the suggestions
-
lookupSortedByWeight
private java.util.stream.Stream<FSTCompletion.Completion> lookupSortedByWeight(BytesRef key) throws java.io.IOException
Lookup suggestions sorted by weight (descending order).- Throws:
java.io.IOException
-
completionStream
private java.util.stream.Stream<? extends FSTCompletion.Completion> completionStream(BytesRef output, int bucket, FST.Arc<java.lang.Object> fromArc) throws java.io.IOException
Return a stream of all completions starting from the provided arc.- Throws:
java.io.IOException
-
descendWithPrefix
private boolean descendWithPrefix(FST.Arc<java.lang.Object> arc, BytesRef utf8) throws java.io.IOException
Descend along the path starting atarc
and going through bytes in the argument.- Parameters:
arc
- The starting arc. This argument is modified in-place.utf8
- The term to descend along.- Returns:
- If
true
,arc
will be set to the arc matching last byte ofterm
.false
is returned if no such prefix exists. - Throws:
java.io.IOException
-
getBucketCount
public int getBucketCount()
Returns the bucket count (discretization thresholds).
-
getBucket
public int getBucket(java.lang.CharSequence key)
Returns the bucket assigned to a given key (if found) or-1
if no exact match exists.
-
getFST
public FST<java.lang.Object> getFST()
Returns the internal automaton.
-
-