N-grams › N-gram Indexing for Search
Language AI HandbookAll chapters N-grams › N-gram Indexing for SearchOne section · Sections in this chapter9 / 16 ↓
Reading tools Definitions & inline links
Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.
Article links
Make inline references clickable
Beyond language modeling and document classification, n-grams have an important application in approximate string matching and search. By building an inverted index from n-grams to documents, you can efficiently retrieve documents that share specific word sequences with a query, even if the match is not exact.
The key insight is that an inverted index maps each observed n-gram to the set of document identifiers that contain it. A query can then be decomposed into its n-grams, and documents that contain the most query n-grams are ranked highest. This is fast because set intersection is much cheaper than scanning every document for every query.
from collections import defaultdict
class NGramIndex:
"""Simple n-gram based search index."""
def __init__(self, n=3):
self.n = n
self.index = defaultdict(set)
self.documents = {}
def add_document(self, doc_id, text):
"""Index a document by its n-grams."""
self.documents[doc_id] = text
tokens = text.lower().split()
ngrams = extract_ngrams(tokens, self.n)
for ngram in ngrams:
self.index[ngram].add(doc_id)
def search(self, query, min_matches=1):
"""Find documents containing query n-grams."""
query_tokens = query.lower().split()
query_ngrams = extract_ngrams(query_tokens, self.n)
# Count matches per document
doc_scores = Counter()
for ngram in query_ngrams:
for doc_id in self.index.get(ngram, []):
doc_scores[doc_id] += 1
# Filter by minimum matches
results = [
(doc_id, score)
for doc_id, score in doc_scores.items()
if score >= min_matches
]
return sorted(results, key=lambda x: -x[1])
# Build index
index = NGramIndex(n=2)
documents = [
"machine learning algorithms",
"deep learning neural networks",
"machine learning for natural language processing",
"statistical machine translation",
"reinforcement learning agents",
]
for i, doc in enumerate(documents):
index.add_document(i, doc)Indexed documents: [0] machine learning algorithms [1] deep learning neural networks [2] machine learning for natural language processing [3] statistical machine translation [4] reinforcement learning agents Query: 'machine learning' Score 1: [0] machine learning algorithms Score 1: [2] machine learning for natural language processing Query: 'deep learning' Score 1: [1] deep learning neural networks Query: 'natural language' Score 1: [2] machine learning for natural language processing
This inverted index approach is the foundation of many search engines and fuzzy matching systems. Notice how the query "machine learning" retrieves documents 0, 2, and 3, because all three contain the bigram ("machine", "learning") or the word "machine" in a bigram with a neighbor. The n-gram index trades storage space for query speed: storing all n-grams requires more memory, but queries become fast set intersection operations rather than full document scans.
In practice, n-gram indexing is used in:
- Search engines: Phrase queries rely on n-gram indices to find documents containing exact multi-word phrases
- Plagiarism detection: Fingerprinting documents with their n-gram sets allows fast detection of copied passages
- Database fuzzy matching: Finding records similar to a query string despite typos or abbreviations
- Genomics: Searching for short DNA sequences (k-mers, which are character n-grams) in large genomic databases