Indexing Strategies: Trigrams (N-Grams)

How to Search Without Scanning

Standard search engines like Elasticsearch use inverted indices built on whole words. When you search for "login", the engine looks up the word "login" in a dictionary and retrieves the list of documents containing it. This works well for natural language, where words are separated by spaces.

Code is not natural language. Consider these two identifiers:

• doLogin() — a Java method
• do_login_now — a Python function

A word-based index might store doLogin and do_login_now as single opaque tokens. A developer searching for login might miss both, because neither matches the exact token "login". You could add tokenization rules to split on camelCase and underscores, but then you introduce false positives and miss cases where the exact substring matters (like searching for a specific string literal "login" inside a larger expression).

The Solution: Trigrams (3-grams)

Tools like Zoekt — the open-source engine that powers Sourcegraph's indexed search — break every piece of source code into overlapping sequences of exactly 3 characters, called trigrams.

For the string func:
- Trigrams: fun, unc

For the string limit:
- Trigrams: lim, imi, mit

For the string hello:
- Trigrams: hel, ell, llo

Why Trigrams Work

When you search for limit, the search engine does not open a single file. Instead it asks the index:

"Give me the set of files that contain the trigram lim AND the set that contains imi AND the set that contains mit. Return the intersection."

Set intersection is a mathematically cheap operation. If your codebase has 10 million files, the trigram lim might appear in 50,000 of them. The trigram imi might appear in 8,000. The trigram mit might appear in 12,000. The intersection of all three might be 400 files. The engine then only needs to verify those 400 files with a direct text scan — ignoring 99.996% of the codebase entirely.

This is the core insight: trigrams convert a linear scan problem into a set intersection problem, and set intersection scales logarithmically rather than linearly.

The choice of 3 characters is deliberate. Two-character pairs (bigrams) are too common — almost every file contains if, in, or — so the intersection sets stay large and the filtering is weak. Four-character sequences (4-grams) are more selective but the index itself becomes enormous, since every additional character multiplies the number of possible n-grams. Three characters hits the sweet spot between index size and filtering power for typical source code.

Key Point: Trigrams are a deliberate engineering trade-off. They produce an index small enough to fit in memory (Zoekt keeps the trigram index in RAM for speed) while being selective enough to reduce candidate files by 99%+ before any file is opened.