Edge n-gram.
also: edge n-grams · edge ngram · edge ngrams · autocomplete · completion suggesterIndexing every prefix of a word (n, ni, nik, nike) so autocomplete becomes a fast exact lookup instead of a prefix scan.
the two-minute refresher
- Autocomplete must answer on every keystroke in under about 50 ms.
- Pre-compute prefixes at index time; query with the normal analyzer, not the n-gram one.
- Bigger index in exchange for cheap queries.
- The completion suggester (an in-memory structure) is the faster, less flexible alternative.