Michael Brenndoerfer | Data & AI, Private Equity, Technology

Michael Brenndoerfer

N-grams › The Vocabulary Explosion Problem

Michael BrenndoerferUpdated March 22, 20254 min read

Language AI HandbookAll chapters

Part 2 of 67Classical Text Representations

Chapter 7N-grams › The Vocabulary Explosion Problem

Reading section 4 of 16 · The Vocabulary Explosion Problem · 4 minSection 4 of 16 · 4 min

Section 4 of 16 · 4 min read

N-grams › The Vocabulary Explosion ProblemOne section · Sections in this chapter4 / 16 ↓

Sections in this chapter16

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

The theoretical maximum number of distinct n-grams grows exponentially with n. If your vocabulary contains $V$ unique word types, the maximum number of possible distinct n-grams is:

V^n

where $V$ is the vocabulary size and $n$ is the n-gram order. For a modest vocabulary of 10,000 word types:

Unigrams: $10{,}000^1 = 10{,}000$ possible
Bigrams: $10{,}000^2 = 100{,}000{,}000$ possible
Trigrams: $10{,}000^3 = 1{,}000{,}000{,}000{,}000$ possible

In practice, most of these theoretical combinations never occur in natural language. The phrase "the the the" is a grammatically valid trigram structure but appears almost never in coherent writing. Real language has strong statistical regularities that constrain which sequences occur. Still, the number of observed n-grams grows rapidly with n, and even the observed vocabulary can quickly exceed what fits in memory or can be reliably estimated from finite data.

In[10]:

Code

# Download sample text
# nltk.download("gutenberg", quiet=True)
from nltk.corpus import gutenberg

# Use a substantial text for realistic statistics
text = gutenberg.raw("austen-emma.txt")
tokens = text.lower().split()

# Count unique n-grams for different values of n
ngram_vocab_sizes = {}
for n in range(1, 6):
    ngrams = extract_ngrams(tokens, n)
    unique_count = len(set(ngrams))
    ngram_vocab_sizes[n] = unique_count

Out[11]:

Console

Text: Emma by Jane Austen
Total tokens: 158,167

Vocabulary size by n-gram order:
-----------------------------------
  Unigrams         16,945  (1.0x unigrams)
  Bigrams          81,586  (4.8x unigrams)
  Trigrams        136,444  (8.1x unigrams)
  4-grams         154,062  (9.1x unigrams)
  5-grams         157,344  (9.3x unigrams)

The vocabulary roughly doubles or triples with each increment in n. A trigram vocabulary can easily be 10 times larger than the unigram vocabulary. For a large English corpus, unigrams might number around 50,000 word types, bigrams around 500,000 unique pairs, and trigrams around 2 to 5 million unique triples. This progression directly affects:

Memory usage: Each n-gram type must be stored with its count. A trigram index over a large corpus can require gigabytes of RAM.
Model complexity: A language model parameterized by trigram probabilities needs to store millions of conditional probability estimates.
Data requirements: Reliable probability estimates require that each n-gram appears many times in training data. If most trigrams appear only once, your estimates will be unreliable.
Generalization: A model trained on observed n-grams cannot assign probability to n-grams it has never seen, even if those sequences are perfectly grammatical.

Out[12]:

Visualization

Line chart showing vocabulary size increasing from about 7000 for unigrams to over 100000 for 5-grams. — Vocabulary size growth as n-gram order increases in Jane Austen's Emma. The number of unique n-gram types grows roughly exponentially with each step, scaling from about 7,000 unigrams to over 100,000 five-grams on this relatively small text. In larger modern corpora, the growth is steeper and the absolute counts are orders of magnitude higher.

The vocabulary explosion is the central engineering challenge of n-gram methods. Every design decision in n-gram systems, from vocabulary pruning to smoothing to hashing, is ultimately a strategy for managing this exponential growth.