Skip to content

LearnIndex & store

N-grams

Bigrams · Trigrams · Shingles

Runs of n consecutive words or characters, such as the word bigram "operating margin" or the character trigrams of "margin": "mar", "arg", "rgi", "gin".

In DocSlurpGlossary entry

On this page

An n-gram is a run of n consecutive units. The units can be words or characters.

  • Word n-grams. The bigrams of “operating margin beats plan” are “operating margin”, “margin beats” and “beats plan”. Indexing them, or checking for them at query time, keeps word order that a bag of single words throws away: “margin beats plan” and “plan beats margin” stop looking identical.
  • Character n-grams. The trigrams of “margin” are “mar”, “arg”, “rgi” and “gin”. Comparing trigram sets measures how similar two strings look, which tolerates typos: “forcast” still shares “for”, “cas” and “ast” with “forecast”. PostgreSQL’s pg_trgm extension and many fuzzy-search features work this way.

Character n-grams also help languages written without spaces between words, where splitting into words is itself hard.

The gotcha

N-gram indexes grow fast. Every position in the text starts a new n-gram, and the number of distinct word bigrams in a corpus is far larger than its vocabulary, so posting lists multiply. Character n-grams also produce many false matches for short queries, since a three-letter trigram appears in thousands of unrelated words. Use them for specific jobs (phrases, typo tolerance, autocomplete) rather than as the main index.

DocSlurp has no n-gram index. Instead, keyword search adds three-word windows of the query as extra phrase searches, and its BM25 reranker gives a bonus when two query words appear next to each other in a passage.

In DocSlurp

In DocSlurp

There is no n-gram index. Keyword search adds three-word phrase windows from the query as extra phrase searches (core/server/src/search/relevance.ts), and the local reranker adds a bonus when two query terms appear next to each other (core/server/src/search/rerank.ts).

Sources

Jump to