Edge N-Gram

What it is

An edge n-gram is a sequence of characters generated from the beginning of a token, growing one character at a time up to a configured maximum length. Where a regular n-gram slides freely across a string and produces all possible substrings of a given width, an edge n-gram is anchored to the left edge — every sequence it produces starts at character one.

The practical consequence is that every edge n-gram is a prefix of the original token. Index those prefixes, and a partial query typed so far will match the full term stored in the index. That property makes edge n-grams the standard mechanism for as-you-type autocomplete in Lucene-based search engines such as Elasticsearch and OpenSearch.

How it works

An edge n-gram token filter takes two parameters:

• min_gram — the shortest prefix to emit (typically 2 or 3; single characters are usually too noisy).
• max_gram — the longest prefix to emit; often set to the maximum expected query length.

For each input token, the filter emits every prefix of length min_gram through min(max_gram, token_length). Those prefix tokens are written into the inverted index alongside — or instead of — the original token, depending on the analyser configuration.

At query time, the standard analyser is used rather than the edge n-gram analyser. The user’s partial input is looked up as a literal string, which matches one of the pre-indexed prefixes exactly. This asymmetry — edge n-grams at index time, standard analysis at query time — is intentional: applying edge n-gram expansion at query time would generate multiple tokens from the query string and produce incorrect results.

[illustrate: pipeline diagram — two parallel paths labelled “Index time” and “Query time”; index-time path shows token “search” entering the edge n-gram filter and fanning out into prefix tokens se, sea, sear, searc, search stored in the inverted index; query-time path shows the partial query “sear” passing through the standard analyser unchanged and matching directly against the “sear” posting]

Example

Token: "search" — min_gram: 2, max_gram: 5

The filter emits the following tokens, all stored as separate entries in the index:

The original token "search" is longer than max_gram, so it is not emitted by the edge n-gram filter. If you want the full token to be retrievable by an exact query, configure a separate sub-field with a standard analyser, or raise max_gram to cover the longest token you expect.

A user typing "sea" triggers a lookup for the literal string sea, which hits the index entry shown above and returns every document that contained the word "search" at index time.

The Elasticsearch / OpenSearch index mapping that produces this behaviour:

{
  "settings": {
    "analysis": {
      "filter": {
        "edge_ngram_filter": {
          "type": "edge_ngram",
          "min_gram": 2,
          "max_gram": 10
        }
      },
      "analyzer": {
        "edge_ngram_analyzer": {
          "type": "custom",
          "tokenizer": "standard",
          "filter": ["lowercase", "edge_ngram_filter"]
        },
        "search_analyzer": {
          "type": "custom",
          "tokenizer": "standard",
          "filter": ["lowercase"]
        }
      }
    }
  },
  "mappings": {
    "properties": {
      "title": {
        "type": "text",
        "analyzer": "edge_ngram_analyzer",
        "search_analyzer": "search_analyzer"
      }
    }
  }
}

analyzer is applied at index time; search_analyzer is applied at query time. The two are deliberately different.

Variants and history

Trailing edge n-grams (suffix-anchored). Some engines support generating n-grams from the end of a token rather than the start. These are called trailing or back edge n-grams. They are rarely used in practice because users type from left to right, making prefix matching the overwhelmingly common case. Suffix autocomplete (e.g. matching file extensions) is usually handled by reversing the token before applying a standard edge n-gram filter.

Edge n-gram vs. prefix query. A prefix query in Elasticsearch/OpenSearch skips the inverted index and iterates over the term dictionary at query time to find all terms starting with the given string. This avoids index bloat but is slower under load and does not benefit from scoring or highlighting based on the matched prefix. Edge n-grams pay the cost at index time and make prefix lookups as fast as any other term query.

search_as_you_type field type. Elasticsearch 7.2 introduced a dedicated search_as_you_type field that automates the edge n-gram setup described above, also adding shingle-based (word-level n-gram) sub-fields for multi-word prefix matching. It is a convenience wrapper, not a different underlying mechanism.

When to use it

Reach for edge n-grams when:

• You are building as-you-type autocomplete and want fast, relevance-ranked prefix completion across a large document set.
• The terms being completed are free-form user content (product names, article titles, person names) where a curated completion list is impractical to maintain.
• You need prefix matches to participate in BM25 scoring and multi-field boosting, which raw prefix queries do not support natively.

Prefer alternatives when:

• Your completion set is small and static — a simple in-memory prefix trie or a terms aggregation on a keyword field will be faster with no index overhead.
• You need infix matching (e.g. the user types a middle fragment of a word). Edge n-grams cover only prefixes; for infix use standard character n-grams.
• Index size is tightly constrained. Edge n-grams can multiply the token count for long-token fields significantly. Tune max_gram conservatively and measure the storage delta before deploying to production.

See also

• N-Gram
• Tokenisation
• Inverted Index