Glossary

N-gram Indexing

A tokenization strategy that decomposes text into overlapping sequences of 'n' characters or words, enabling robust matching of sub-word patterns, misspellings, and compound words.

Get in touch Learn more

Overhead shot of a beautifully lit strategy meeting in a modern WeWork hot desk area, designers and executives gathered around a live AI system diagram projected on smart table surface.

SUB-WORD TOKENIZATION

What is N-gram Indexing?

N-gram indexing is a tokenization strategy that decomposes text into overlapping sequences of 'n' characters or words, enabling robust matching of sub-word patterns, misspellings, and compound words.

N-gram indexing is a tokenization strategy that decomposes text into overlapping sequences of n consecutive characters or words. Unlike standard word-based tokenizers that fail on misspellings, an n-gram index breaks 'hello' (trigram) into hel, ell, and llo, creating a fuzzy, position-independent fingerprint of the text that is resilient to minor typographical errors and morphological variations.

This technique is fundamental to sparse retrieval systems that must match queries against documents without relying on exact lexical overlap. By indexing sub-word units, an n-gram index bridges the vocabulary mismatch problem, allowing a search for 'color' to match 'colour' by sharing common trigrams. It is commonly implemented within an inverted index structure, where each n-gram acts as a key in the dictionary pointing to a postings list of documents containing that character sequence.

Sub-Word Matching

Key Characteristics of N-gram Indexing

N-gram indexing is a tokenization strategy that decomposes text into overlapping sequences of 'n' characters or words, enabling robust matching of sub-word patterns, misspellings, and compound words.

Sub-Word Pattern Matching

N-gram indexing enables partial matching by breaking terms into overlapping character sequences. This allows a search for 'arch' to match 'architecture', 'search', and 'monarch' without requiring exact lexical overlap. The technique is fundamental for languages with compound words like German, where 'Donaudampfschifffahrt' can be matched by a query for 'Schiff'.

Misspelling and Fuzzy Tolerance

By indexing character trigrams (n=3), the system becomes inherently fault-tolerant. A query for 'libary' will still match documents containing 'library' because they share the trigrams 'lib', 'iba', 'bar', and 'ary'. This eliminates the need for a separate spell-checker in many retrieval pipelines and provides robust matching against OCR errors and typographical noise.

Edge N-gram Specialization

Edge n-grams are generated only from the start of a token, enabling efficient prefix matching. This is critical for autocomplete and 'search-as-you-type' functionality. For example, indexing the edge trigrams of 'inference' produces 'inf', 'infe', 'infer', allowing a query for 'inf' to immediately retrieve the term without scanning the entire inverted index.

Index Size vs. Precision Trade-off

The choice of n directly impacts the index footprint and precision. Lower values (bigrams) increase recall but generate massive indices with high noise. Higher values (5-grams) improve precision but reduce fault tolerance. Production systems often use trigrams (n=3) as a balanced default, though multilingual applications may require adaptive n-gram lengths based on character set and word length.

Cross-Lingual and Script Support

N-gram indexing is language-agnostic because it operates on raw character sequences rather than linguistic rules. This makes it uniquely suited for CJK (Chinese, Japanese, Korean) languages where word boundaries are ambiguous. A unigram or bigram approach can index ideographic characters without requiring a dictionary-based tokenizer, providing consistent retrieval across mixed-script corpora.

Inverted Index Integration

N-grams are stored as standard terms in an inverted index, with each n-gram pointing to a postings list of document identifiers. During query execution, the query is decomposed into n-grams, their postings lists are intersected, and positional information is used to filter out false positives where the n-grams appear in the wrong order or with gaps. This ensures that 'cat' matches 'catalog' but not 'act'.

TOKENIZATION STRATEGY COMPARISON

N-gram Indexing vs. Standard Tokenization

A feature-level comparison between N-gram indexing and standard word-based tokenization for handling sub-word patterns, misspellings, and compound words in sparse retrieval.

Feature	N-gram Indexing	Standard Tokenization	Hybrid Approach
Matching granularity	Sub-character sequences	Whole words	Both words and sub-words
Handles misspellings
Handles compound words
Handles out-of-vocabulary terms
Index size overhead	3-5x larger	1x baseline	2-3x larger
Query latency impact	Moderate increase	Minimal	Moderate increase
Requires stemming
Suitable for CJK languages

N-GRAM INDEXING

Frequently Asked Questions

Explore the mechanics of n-gram indexing, a tokenization strategy that decomposes text into overlapping sequences to enable robust matching of sub-word patterns, misspellings, and compound words.

N-gram indexing is a tokenization strategy that decomposes text into overlapping sequences of 'n' characters or words to create searchable terms. Instead of indexing whole words, the system slides a window of fixed length (e.g., 3 characters for a trigram) across the text. For the word 'search', a character trigram index would generate 'sea', 'ear', 'arc', and 'rch'. These sub-word fragments are then stored in an inverted index. At query time, the search term is similarly decomposed, and the engine matches these fragments against the index. This allows for fuzzy matching without expensive edit-distance calculations, making it highly effective for handling misspellings, compound word splitting, and languages without clear word boundaries.

Enabling Efficiency, Speed & Accuracy

Intelligent Analysis, Decision & Execution

We build AI systems for teams that need search across company data, workflow automation across tools, or AI features inside products and internal software.

Talk to Us

Search across company data

Give teams answers from docs, tickets, runbooks, and product data with sources and permissions.

Useful when people spend too long searching or get different answers from different systems.

Enterprise searchRAGPermissions

Automate internal workflows

Use AI to route work, draft outputs, trigger actions, and keep approvals and logs in place.

Useful when repetitive work moves across multiple tools and teams.

AI agentsWorkflow automationGovernance

Add AI to products and internal tools

Build assistants, guided actions, or decision support into the software your team or customers already use.

Useful when AI needs to be part of the product, not a separate tool.

AI integrationDecision supportModel routing

N-gram Indexing Ecosystem

Related Terms

Explore the core components and related concepts that form the foundation of n-gram indexing, a critical technique for robust, fuzzy, and sub-word text matching in modern search engines.

Tokenization Strategies

N-gram indexing is a specific tokenization strategy where text is decomposed into overlapping sequences of 'n' characters or words. This contrasts with standard word tokenization by creating tokens for partial terms, enabling robust matching of sub-word patterns, prefixes, and suffixes. For example, the trigrams for 'cat' are 'ca', 'cat', and 'at' (with padding).

Inverted Index

An inverted index is the data structure that makes n-gram search efficient. Instead of mapping whole words to documents, it maps every generated n-gram to a postings list of documents containing it. At query time, the engine decomposes the search term into n-grams, retrieves their postings lists, and intersects them to find candidate documents, enabling sub-second fuzzy matching.

Vocabulary Mismatch

N-gram indexing directly addresses the vocabulary mismatch problem, where a query and document use different word forms for the same concept. By indexing character-level n-grams, the system can match 'running' against 'run' or 'runner' without a stemmer. This is especially critical for languages with complex morphology, like German or Finnish, where a single word can have dozens of inflected forms.

Spelling Correction

N-gram indexing provides a powerful foundation for fuzzy search and spelling correction. By decomposing a misspelled query like 'aple' into trigrams ('ap', 'apl', 'ple', 'le') and comparing them against the n-gram index, the engine can efficiently retrieve documents containing the correctly spelled 'apple' without needing a separate spell-check dictionary. The Jaccard coefficient between n-gram sets is a common similarity measure.

Edge N-gram

An edge n-gram is a variant generated only from the leading edge of a token. For 'hello', edge n-grams include 'h', 'he', 'hel', 'hell', and 'hello'. This technique is ideal for autocomplete and 'search-as-you-type' functionality, as a prefix query for 'hel' will instantly match documents containing 'hello' or 'help' without requiring a wildcard suffix search, which is computationally expensive.

Compound Word Splitting

In languages like German, where compound words like 'Donaudampfschifffahrtskapitän' are common, n-gram indexing enables matching against constituent parts. A search for 'Schifffahrt' (shipping) can match the full compound because its trigrams are a subset of the compound's trigrams. This technique, often combined with a decompounder filter, dramatically improves recall for long, composite terms.

About the author

Prasad Kumkar

CEO & MD, Inference Systems

Prasad Kumkar is the CEO & MD of Inference Systems and writes about AI systems architecture, LLM infrastructure, model serving, evaluation, and production deployment. Over 5+ years, he has worked across computer vision models, L5 autonomous vehicle systems, and LLM research, with a focus on taking complex AI ideas into real-world engineering systems.

His work and writing cover AI systems, large language models, AI agents, multimodal systems, autonomous systems, inference optimization, RAG, evaluation, and production AI engineering.

Limited slotsGet a Free AI Consultation

How We Work

Custom AI workflows for your Business

One-fit-all AI don't work for modern businesses. At Inferensys, we aim to understand your business & custom requirements; which we use to define most efficient agentic workflows, the data, and the tools for your business.