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_trgmextension 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).