Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## org.apache.lucene.search.suggest.fst
Class FSTCompletionBuilder

    java.lang.Object
      org.apache.lucene.search.suggest.fst.FSTCompletionBuilder

    public class FSTCompletionBuilder

extends Object

Finite state automata based implementation of "autocomplete" functionality.

## Implementation details

The construction step in `Object.finalize()` works as follows:

- A set of input terms and their buckets is given.
- All terms in the input are prefixed with a synthetic pseudo-character (code) of the weight bucket the term fell into. For example a term `abc` with a discretized weight equal '1' would become `1abc`.
- The terms are then sorted by their raw value of UTF-8 character values (including the synthetic bucket code in front).
- A finite state automaton (`FST`) is constructed from the input. The root node has arcs labeled with all possible weights. We cache all these arcs, highest-weight first.

At runtime, in `FSTCompletion.lookup(CharSequence, int)`, the automaton is utilized as follows:

- For each possible term weight encoded in the automaton (cached arcs from the root above), starting with the highest one, we descend along the path of the input key. If the key is not a prefix of a sequence in the automaton (path ends prematurely), we exit immediately -- no completions.
- Otherwise, we have found an internal automaton node that ends the key. The entire subautomaton (all paths) starting from this node form the key's completions. We start the traversal of this subautomaton. Every time we reach a final state (arc), we add a single suggestion to the list of results (the weight of this suggestion is constant and equal to the root path we started from). The tricky part is that because automaton edges are sorted and we scan depth-first, we can terminate the entire procedure as soon as we collect enough suggestions the user requested.
- In case the number of suggestions collected in the step above is still insufficient, we proceed to the next (smaller) weight leaving the root node and repeat the same algorithm again.

## Runtime behavior and performance characteristic

The algorithm described above is optimized for finding suggestions to short prefixes in a top-weights-first order. This is probably the most common use case: it allows presenting suggestions early and sorts them by the global frequency (and then alphabetically).

If there is an exact match in the automaton, it is returned first on the results list (even with by-weight sorting).

Note that the maximum lookup time for any prefix is the time of descending to the subtree, plus traversal of the subtree up to the number of requested suggestions (because they are already presorted by weight on the root level and alphabetically at any node level).

To order alphabetically only (no ordering by priorities), use identical term weights for all terms. Alphabetical suggestions are returned even if non-constant weights are used, but the algorithm for doing this is suboptimal.

"alphabetically" in any of the documentation above indicates UTF-8 representation order, nothing else.

NOTE: the FST file format is experimental and subject to suddenly change, requiring you to rebuild the FST suggest index.

See Also:
  `FSTCompletion`
WARNING: This API is experimental and might change in incompatible ways in the next release.

Field Summary
`static int` | `DEFAULT_BUCKETS` Default number of buckets.

Constructor Summary
`FSTCompletionBuilder()` Creates an `FSTCompletion` with default options: 10 buckets, exact match promoted to first position and `InMemorySorter` with a comparator obtained from `BytesRef.getUTF8SortedAsUnicodeComparator()`.
`FSTCompletionBuilder(int buckets, BytesRefSorter sorter, int shareMaxTailLength)`

Method Summary
`void` | `add(org.apache.lucene.util.BytesRef utf8, int bucket)` Appends a single suggestion and its weight to the internal buffers.
`FSTCompletion` | `build()` Builds the final automaton from a list of added entries.

Methods inherited from class java.lang.Object
`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

Field Detail

### DEFAULT_BUCKETS

    public static final int DEFAULT_BUCKETS

  Default number of buckets.

  See Also:
    Constant Field Values

Constructor Detail

### FSTCompletionBuilder

    public FSTCompletionBuilder()

  Creates an `FSTCompletion` with default options: 10 buckets, exact match promoted to first position and `InMemorySorter` with a comparator obtained from `BytesRef.getUTF8SortedAsUnicodeComparator()`.

### FSTCompletionBuilder

    public FSTCompletionBuilder(int buckets,
                                BytesRefSorter sorter,
                                int shareMaxTailLength)

Parameters:
  `buckets` - The number of buckets for weight discretization. Buckets are used in `add(BytesRef, int)` and must be smaller than the number given here.
  `sorter` - `BytesRefSorter` used for re-sorting input for the automaton. For large inputs, use on-disk sorting implementations. The sorter is closed automatically in `build()` if it implements `Closeable`.
  `shareMaxTailLength` - Max shared suffix sharing length. See the description of this parameter in `Builder`'s constructor. In general, for very large inputs you'll want to construct a non-minimal automaton which will be larger, but the construction will take far less ram. For minimal automata, set it to `Integer.MAX_VALUE`.

Method Detail

### add

    public void add(org.apache.lucene.util.BytesRef utf8,
                    int bucket)
             throws IOException

  Appends a single suggestion and its weight to the internal buffers.

  Parameters:
    `utf8` - The suggestion (utf8 representation) to be added. The content is copied and the object can be reused.
    `bucket` - The bucket to place this suggestion in. Must be non-negative and smaller than the number of buckets passed in the constructor. Higher numbers indicate suggestions that should be presented before suggestions placed in smaller buckets.
  Throws:
    `IOException`

### build

    public FSTCompletion build()
                        throws IOException

  Builds the final automaton from a list of added entries. This method may take a longer while as it needs to build the automaton.

  Throws:
    `IOException`

Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD