# Autocomplete with n-grams

For a search box that matches while people type, there are two approaches:

- **Prefix queries at search time.** The [`text` query language](synonyms-and-rules.md) matches
  the last word as a prefix, with no change to the index. Start here.
- **Grams at index time.** An analyzer indexes the beginnings of each word (`edge_ngram`), so a
  partial word is an ordinary term lookup. This is faster on large collections, works in every
  query language, and lets you choose the shortest prefix that matches.

## Edge n-grams

Index each word's first 2 to 10 characters, so `mes`, `mess` and `messiah` all find `Messiah`:

```json
{
  "fields": {
    "title": {
      "type": "text",
      "analyzer": {
        "tokenizer": {"name": "edge_ngram", "params": {
          "min_gram": 2, "max_gram": 10, "token_chars": ["letter", "digit"]}},
        "filters": ["lowercase"]
      },
      "variants": {"full": {"type": "text", "analyzer": "standard"}}
    }
  }
}
```

The analyzer also splits the query into grams. A query for `mes` becomes `me` and `mes`, which
matches more than the prefix you typed, but documents that hold all of a query's grams rank first.
For exact prefix behaviour, search the gram field with the `and` operator, or search a whole-word
[variant](schemas-and-fields.md#variants) (`title__full` above) for the finished words and boost it.

The `edge_ngram` tokenizer:

| Param | Default | Meaning |
|---|---|---|
| `min_gram` | `1` | Shortest gram. |
| `max_gram` | `2` | Longest gram. Words longer than this are indexed only up to it. |
| `token_chars` | all | Character classes that belong to a word: `letter`, `digit`, `whitespace`, `punctuation`, `symbol`, `custom`. Others split words. With none, the whole value is one word. |
| `custom_token_chars` | | Characters that `custom` adds, such as `+-_`. |

`edge_ngram` is also a filter, which grams the words another tokenizer made. It keeps each gram
at its word's position, so phrase queries still work. Params `min_gram`, `max_gram` and
`preserve_original` (also index the whole word, even when it is longer than `max_gram`):

```json
{
  "tokenizer": "unicode_word",
  "filters": ["lowercase", {"name": "edge_ngram", "params": {"min_gram": 1, "max_gram": 15, "preserve_original": true}}]
}
```

## N-grams inside words

The `ngram` filter indexes every gram of each word, not only its beginning, so `phone` finds
`smartphone`. It takes the same params as the `edge_ngram` filter. The index grows with every
gram, so keep the range narrow, for example 3 to 3.

For substrings anywhere in long values, such as URLs, file paths and command lines, see
[Substring search](substring-search.md), which matches exactly and verifies every hit.

## Shingles

`shingle` indexes word pairs (or longer runs) next to the words, so a query for `new york`
matches the pair `new york` and ranks documents with the words together higher. Shingles also
serve as phrase suggestions.

```json
{
  "tokenizer": "unicode_word",
  "filters": ["lowercase", {"name": "shingle", "params": {"min_shingle_size": 2, "max_shingle_size": 3}}]
}
```

| Param | Default | Meaning |
|---|---|---|
| `min_shingle_size` | `2` | Fewest words in a shingle. |
| `max_shingle_size` | `2` | Most words in a shingle, up to 64. |
| `output_unigrams` | `true` | Also index the single words. |
| `output_unigrams_if_no_shingles` | `false` | Index single words when a value is too short for a shingle. |
| `token_separator` | a space | Text between the words of a shingle. |
| `filler_token` | `_` | Stands in for a removed stop word, so `quick the fox` gives `quick _` and `_ fox`, not `quick fox`. |

`common_grams` is a lighter form for phrase queries with very common words: it joins each word in
`common_words` with its neighbours (`the_quick`), so a phrase that contains `the` looks up the rarer
pair. Params `common_words` (required), `ignore_case` and `query_mode` (`true` keeps only the
pairs, for a query-side analyzer).

## Limits and differences

- `min_gram` and `max_gram` are at most 1024. Elasticsearch caps the gap between them with the
  `index.max_ngram_diff` setting; WarpSearch has no such setting.
- Gram lengths count characters (code points).
- Grams are not applied to prefix and fuzzy query terms.

## Through the compatible APIs

Elasticsearch's `edge_ngram` tokenizer and filter, the `ngram` filter, `shingle` and
`common_grams` map to these components with their parameters, as do Solr's `EdgeNGram`, `NGram`,
`Shingle` and `CommonGrams` factories. Elasticsearch's `ngram` tokenizer is translated as a
tokenizer that splits on the characters outside `token_chars`, followed by the `ngram` filter,
with a warning: the grams of a word share its position. The `search_as_you_type` field type is
indexed as plain text, with a warning.
