N-grams: Capturing Word Order in Text

Language does not work word by word. The meaning of any given word almost always depends on what surrounds it. When you read "I need to book a flight," the word "book" is a verb. When you read "hand me that book," it is a noun. You understood the difference not from the word itself but from the words nearby. This dependence on local context is one of the most fundamental properties of natural language, and n-grams are the simplest tool that captures it.

As we saw in the previous chapter on bag of words, representing a document as a multiset of individual word counts discards every piece of word-order information. The sentence "The dog bit the man" and the sentence "The man bit the dog" produce identical bag-of-words vectors, even though they describe opposite events. For many classification tasks, word-order loss is acceptable and the simplicity of bag of words is worth the trade-off. But as soon as meaning depends on sequence, we need a richer representation.

N-grams offer a direct extension of bag of words: instead of treating single words as atomic units, we treat fixed-length sequences of consecutive words as atomic units. An n-gram is a contiguous sequence of $n$ items drawn from a text, where items can be words, characters, syllables, or any other tokens. When we work with words, we call them word n-grams. When we work with characters, we call them character n-grams. The special cases have familiar names: a 1-gram is a unigram (the same as standard bag of words), a 2-gram is a bigram, and a 3-gram is a trigram.

The intuition is straightforward: phrases like "machine learning," "New York," "not good," and "highly recommend" carry meaning as units that their individual words cannot convey in isolation. "Machine" and "learning" are common words on their own, but together they signal a technical domain. "Not" and "good" are individually neutral in many contexts, but as a bigram they express sentiment that would be lost if you only counted the word "good." N-grams capture this by including multi-word sequences in the vocabulary.

This chapter explores how n-grams preserve local word order, why vocabulary size grows explosively with n, and how the statistical properties of n-grams follow predictable mathematical patterns. You will learn to extract n-grams efficiently, understand when character n-grams outperform word n-grams, see how skip-grams relax the strict adjacency requirement, and understand how n-gram models assign probabilities to text sequences. By the end you will have a complete picture of what n-grams can do, what they cannot do, and why they remain relevant even in the age of large language models.

The bag of words model creates a vocabulary of individual words and counts how often each appears in a document. N-grams extend this idea by creating a vocabulary of word sequences and counting how often each sequence appears. This small change has large practical consequences.

Think of it this way: a unigram vocabulary for English has perhaps 50,000 to 100,000 entries, one per word form. A bigram vocabulary for the same corpus has millions of entries, one per pair of consecutive words. A trigram vocabulary has tens of millions. The vocabulary grows exponentially, but each entry carries more information about local context.

To see the difference concretely, consider how different n-gram orders segment the same sentence:

Let's see how the same sentence produces different representations at each n-gram level:

Notice the pattern: each sentence with $k$ tokens produces a different number of n-grams depending on the sequence length you choose. The relationship between sentence length, n-gram order, and count is deterministic:

where:

• $k$: the total number of tokens in the sentence
• $n$: the n-gram size (1 for unigrams, 2 for bigrams, 3 for trigrams, etc.)
• $\text{count}$: the resulting number of n-grams

The key insight behind this formula is that each n-gram starts at a unique position in the token sequence. The very first n-gram starts at position 1, and the last valid starting position is $k - n + 1$, because that is the last position where we can still find $n$ consecutive tokens. Starting any later would run past the end of the sentence. With 9 tokens, we get 9 unigrams ($9 - 1 + 1 = 9$), 8 bigrams ($9 - 2 + 1 = 8$), and 7 trigrams ($9 - 3 + 1 = 7$). As $n$ increases, we extract fewer n-grams from each document, but each n-gram carries more contextual information. The coverage decreases; the specificity increases.

Let's trace through a short, meaningful sentence step by step to build intuition for what bigrams represent. Take the sentence "cats eat fish."

After lowercasing and tokenizing, we have tokens: ["cats", "eat", "fish"]. Applying the bigram extraction algorithm:

• Position 1: window covers tokens 1 and 2, producing ("cats", "eat")
• Position 2: window covers tokens 2 and 3, producing ("eat", "fish")

We stop here because the next position would require a token 4 that does not exist. The final bigram representation is [("cats", "eat"), ("eat", "fish")].

Notice that "eat" appears in both bigrams. Each word (except the first and last) participates in exactly two bigrams: one where it is the second word, and one where it is the first. This overlapping structure means that consecutive n-grams share most of their tokens, which is why they remain sensitive to local order while still providing a sliding-window view of the text.

Now compare this to a different sentence with the same words: "fish eat cats." The tokens are identical but in reverse order, giving bigrams [("fish", "eat"), ("eat", "cats")]. These two sets share no bigrams at all, even though they use exactly the same vocabulary. This is the property that unigrams cannot provide: sensitivity to word order.

Bigrams are the most commonly used n-grams in applied NLP. They capture immediate word relationships, such as noun-adjective pairs, compound nouns, and common verbal phrases, while keeping vocabulary size manageable. Trigrams provide richer context and are standard in language modeling, where they allow conditioning on a two-word history. Longer n-grams exist but are rarely used as standalone features because the sparsity problem becomes severe.

The most revealing way to understand what bigrams encode is to look at their frequency distributions in real text. Common bigrams cluster around function word combinations like "of the," "in the," and "to be," but the bigrams with the strongest discriminative power for content-based tasks are typically noun phrase patterns and domain-specific collocations:

The co-occurrence matrix reveals the structure hidden in bigram counts. The cell at row "machine" and column "learning" shows a high count because "machine learning" is a frequent phrase. Most cells are zero. This reflects the sparsity inherent in natural language: most word pairs never occur together in the same order in any given corpus, even if both words appear individually.

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:

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.

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.

Individual words follow Zipf's law: the frequency of a word is inversely proportional to its rank in the frequency table. A small number of words account for most of the occurrences in any large corpus. The word "the" might make up 6 to 7 percent of all words in English text, while thousands of low-frequency words each appear only once or twice.

N-grams follow the same pattern, but in an even more extreme form. The top bigrams (phrases like "of the," "in the," "it is") each appear thousands of times, while the vast majority of observed bigrams appear just once. This extreme concentration at the high-frequency end and long tail at the low-frequency end is a universal property of natural language at every level of granularity.

The practical consequence of Zipf's law for n-grams is severe: most of the n-gram types you will ever observe occur exactly once in any given corpus. These single-occurrence n-grams are called hapax legomena (from Greek: "said only once"). As the n-gram order increases, the hapax ratio climbs sharply, because longer sequences are less likely to repeat.

The Zipfian distribution means that most of your n-gram model's probability mass is concentrated in a tiny fraction of all possible sequences. The top 100 trigrams in a large corpus might account for a significant fraction of all trigram occurrences, while the bottom 90 percent of trigram types each contribute almost nothing. In practice this creates an asymmetry: the common sequences are very well estimated from data, while the rare ones are estimated poorly or not at all.

One of the most powerful applications of n-gram statistics is building language models, models that assign a probability to any sequence of words. A language model answers the question: how likely is this sentence? This capability underlies autocomplete, speech recognition, machine translation, and text generation.

The probability of a sequence of words $w_1, w_2, \ldots, w_T$ can be written using the chain rule of probability:

where $P(w_t \mid w_1, \ldots, w_{t-1})$ is the conditional probability of word $w_t$ given all preceding words. The problem with this exact formulation is that the history $w_1, \ldots, w_{t-1}$ grows without bound as $t$ increases, making it impossible to estimate reliably from finite data.

The n-gram approximation solves this by applying the Markov assumption: the probability of the next word depends only on the last $n-1$ words, not the full history. For a bigram model ($n = 2$), the assumption is:

For a trigram model ($n = 3$):

In general, an n-gram model conditions on the preceding $n - 1$ words:

The intuition is that most of the predictive signal about the next word comes from the immediately preceding few words. Knowing that the last two words were "machine learning" tells you a lot about what comes next. Knowing that the word 20 positions back was "the" tells you very little.

The parameters of an n-gram language model are the conditional probabilities $P(w_t \mid w_{t-n+1}, \ldots, w_{t-1})$. The simplest way to estimate these from training data is maximum likelihood estimation (MLE):

where:

• $C(w_{t-n+1}, \ldots, w_{t-1}, w_t)$: the count of the full n-gram (the $n-1$ context words followed by $w_t$) in training data
• $C(w_{t-n+1}, \ldots, w_{t-1})$: the count of the context (the $n-1$ preceding words) alone

In plain language: the probability of word $w_t$ following a given context is the fraction of times that context in training data was followed by $w_t$. If the bigram "machine learning" appears 100 times and the word "machine" appears 200 times total, then $P_{\text{MLE}}(\text{learning} \mid \text{machine}) = 100 / 200 = 0.5$.

This estimate is intuitive and easy to compute. However, it assigns zero probability to any n-gram that did not appear in training data. Since any held-out text will contain many unseen n-grams, a pure MLE n-gram model assigns zero probability to real sentences, which makes it unusable for tasks like perplexity evaluation or speech recognition scoring.

Smoothing is the family of techniques used to assign non-zero probabilities to unseen n-grams by redistributing probability mass from seen n-grams to unseen ones. Every practical n-gram language model uses some form of smoothing.

Laplace (Add-one) Smoothing is the simplest approach. We add 1 to every n-gram count, including unseen ones:

where:

• $C(w_{t-1}, w_t)$: the observed bigram count
• $C(w_{t-1})$: the observed unigram count for the context word
• $V$: the vocabulary size (the number of word types)

The denominator increases by $V$ rather than by $1$ because we are adding 1 to the count of every possible next word, and there are $V$ of them. Think of it as: every word in the vocabulary is given one free observation following every context. This ensures no zero-probability outcomes.

The key insight is that adding $V$ to the denominator normalizes the distribution so that probabilities still sum to 1 over all possible next words. Without this correction, the probabilities would be inflated.

In practice, Laplace smoothing assigns far too much probability mass to unseen n-grams, which dilutes the probability of observed ones. More sophisticated methods like Kneser-Ney smoothing achieve much better results in practice by using a more careful accounting of how probability mass should be redistributed based on the diversity of contexts each word appears in. But Laplace smoothing is useful to understand because it captures the essential idea: every technique in the smoothing family is ultimately trying to solve the same problem of zero counts.

Notice how corpus-consistent sentences score much higher log-probability than nonsensical ones. The sentence "fish eat the sky purple" is grammatically unusual and uses words in combinations never seen in training, so even with Laplace smoothing its probability is much lower. This is exactly the behavior we want from a language model.

Word n-grams assume clean, correctly spelled text. But real-world text contains typos, spelling variations, invented words, and domain-specific jargon that may not appear in any vocabulary. Character n-grams handle these issues by operating on character sequences instead of word boundaries.

The key property of character n-grams is that similar words share many character n-grams. "Learning" and "learner" share the character trigrams "lea," "ear," "arn," and "rni." A typo like "lerning" still shares most trigrams with "learning." This makes character n-grams naturally tolerant of surface variation while remaining sensitive to lexical identity.

Standard n-grams require strict adjacency: every token must immediately precede the next one in the sequence. This constraint is linguistically motivated for many phrase-level patterns, but it misses relationships between words that are related despite not being immediately adjacent.

Consider the sentence "the big brown bear ate salmon." The relationship between "bear" and "ate" is meaningful, but they are separated by two words. A standard bigram representation misses this. A trigram captures "big brown bear" and "brown bear ate" but still does not directly pair "bear" with its verb "ate." Skip-grams relax the adjacency constraint to capture these longer-range dependencies.

The term "skip-gram" in the context of this chapter refers to this linguistic extension. Note that the word "skip-gram" also names a Word2Vec training objective (covered in a later chapter), but the two uses are related: the Word2Vec skip-gram model was inspired by this linguistic notion of flexible context windows.

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.

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

While we have implemented n-gram extraction from scratch to understand the mechanics, NLTK provides optimized utilities that are more convenient for production use:

NLTK's FreqDist wraps a Counter with additional NLP-specific methods. The .N() method returns the total number of tokens (sum of all counts), while .B() returns the number of unique types (vocabulary size). These are the type/token distinction applied to n-gram collections, which is important for computing statistics like the type-to-token ratio.

When working with n-grams in real applications, several engineering and modeling decisions have significant impact on your results.

Choosing n. Larger n captures more context but creates sparser data. The right choice depends on your task, your corpus size, and your tolerance for sparsity:

• Unigrams (n=1): Baseline that loses all word order, but works surprisingly well for many classification tasks
• Bigrams (n=2): Good balance for most tasks; captures immediate phrase structure while remaining tractable
• Trigrams (n=3): Richer context; standard for language modeling tasks; requires substantially more data
• n greater than 3: Rarely used as standalone features due to extreme sparsity; occasionally useful in specific applications like DNA sequence analysis or stylometry

Vocabulary pruning. You almost always want to remove n-grams that appear too rarely (below some minimum document frequency) or too frequently (above some maximum). Rare n-grams add noise rather than signal: if a trigram appears only once in your training data, your estimate of its probability is unreliable. Very frequent n-grams like "of the" and "in the" appear everywhere and carry almost no discriminative information for tasks like topic classification or sentiment analysis. Pruning reduces vocabulary size, which saves memory and often improves model quality.

Padding. For language modeling applications, you may want to add special start and end tokens to capture sentence boundary statistics:

The padding approach ensures that the beginning and end of a sentence are treated as a special context rather than being silently ignored. Without padding, the first and last words of a sentence only appear as the second element of starting bigrams or the first element of ending bigrams, which underestimates how often they occur in those boundary positions. With <s> and </s> boundary markers, the model can learn that certain words frequently begin or end sentences.

Memory efficiency. For large corpora, string-based n-gram storage becomes prohibitively expensive. In practice:

• Store n-grams as hashed integer tuples rather than string tuples. The hash reduces memory by roughly 4-8x.
• Use sparse matrix representations (scipy.sparse) when building document-term matrices from n-gram features.
• Apply feature hashing (the "hashing trick") to map n-grams to a fixed-dimensional vector without storing the vocabulary explicitly. This bounds memory at the cost of hash collisions.
• Use count sketches or min-count thresholding to discard rare n-grams during construction rather than after.

Combining n-gram orders. In practice, the best results often come from combining multiple n-gram orders. Scikit-learn's CountVectorizer and TfidfVectorizer accept ngram_range=(1, 2) to include both unigrams and bigrams, or ngram_range=(1, 3) to include unigrams through trigrams. Combining orders gives the model access to both word-level and phrase-level patterns, usually improving performance on classification tasks at the cost of a larger feature space.

N-grams improve on bag of words by preserving local word order and capturing multi-word phrases as single units. But they carry significant limitations that motivate the development of richer representations.

The most fundamental limitation is the fixed context window. An n-gram of size $n$ captures exactly $n$ consecutive words, no more and no less. Any relationship between words separated by more than $n - 1$ positions is invisible to the model. The phrase "if she studies consistently throughout the semester, then her exam results improve" carries a long-range correlation between "if" and "then" that spans many words. No practical n-gram can capture this. Language models that use trigrams model context three words at a time; the rest of the sentence history is discarded by the Markov approximation.

The vocabulary explosion is a fundamental challenge. Moving from bigrams to trigrams multiplies the number of possible n-gram types by the vocabulary size. For a 50,000-word vocabulary, that means going from 2.5 billion possible bigrams to 125 trillion possible trigrams. The observed fraction in any corpus is tiny, making most of the probability space inaccessible and forcing heavy reliance on smoothing. Smoothing helps but cannot fully solve the zero-count problem; it only redistributes probability mass according to heuristics that may not reflect the true distribution.

No semantic understanding is perhaps the most limiting aspect of n-gram representations. "Excellent movie" and "great film" share no n-grams despite expressing the same sentiment. A synonym substitution produces a completely different n-gram fingerprint. This means that n-gram models cannot generalize across synonymous expressions, different phrasings of the same meaning, or across languages. Every surface form is treated as a completely distinct symbol, with no connection to any other symbol that happens to mean the same thing.

Data requirements grow exponentially with n. A reliable bigram model might require millions of words of training data; a trigram model might need tens of millions; 5-gram models used in machine translation systems were trained on billions of words. This makes high-order n-gram models inaccessible to researchers and applications that do not have access to massive corpora.

The sensitivity to tokenization is also important in practice. Whether "New York" is one token or two, whether contractions are split, whether punctuation is attached to words or separated: all of these decisions change the n-gram representation significantly. N-gram models can be brittle when the tokenization of training data differs from the tokenization of test data, because even a slight mismatch propagates through every n-gram that spans a tokenization boundary.

Despite these limitations, n-grams occupied the center of NLP for decades because they are simple and fast, with interpretable features that often work surprisingly well. They require no deep learning infrastructure, no GPU, and no careful architecture design. A trigram language model trained on a large corpus achieves reasonable performance on speech recognition and machine translation with nothing but counting and smoothing.

The impact of n-gram methods on the history of language technology is hard to overstate. Before neural networks became practical in the late 2000s and early 2010s, n-gram language models were the dominant approach for any application requiring statistical knowledge about word sequences.

Language modeling and speech recognition was the original application and remained dominated by n-gram models for three decades. IBM's trigram models from the 1980s reduced word error rates in dictation systems by more than half compared to earlier methods. Google's voice search and Apple's Siri relied on n-gram language models as core components well into the 2010s.

Statistical machine translation used n-gram language models as one of two key components (alongside a translation model). The language model ensured that the target-side output was fluent English (or whatever target language), scored by a trigram or 5-gram model trained on billions of words of text. This approach produced the first practically useful machine translation systems.

Text classification benefits substantially from adding bigrams to a bag-of-words feature set. In spam detection, sentiment analysis, and topic classification, bigrams capture phrases that single words cannot. The bigram "not good" carries entirely different sentiment from either "not" or "good" individually.

Spell checking and autocomplete both rely on character n-grams and word n-grams respectively. Character n-gram similarity identifies likely corrections for misspelled words. Word n-grams predict likely next words given the current context, which is the core of every autocomplete system.

Plagiarism detection uses n-gram fingerprinting, also called "shingling." A document is represented as the set of its k-grams (typically with k around 5 to 10 words). Two documents that share many k-grams are likely to contain copied passages. This approach tolerates minor paraphrasing and word substitutions because it requires matching sequences of five or more consecutive words, which is hard to achieve by coincidence.

Information retrieval and phrase-based search use bigram and trigram indices to answer phrase queries efficiently. Searching for "New York Times" as a phrase requires matching the trigram instead of checking only for all three words somewhere in the document.

The transition from n-gram models to neural language models beginning around 2010 to 2013 did not eliminate n-grams from the field. Modern subword tokenizers like BPE (Byte Pair Encoding) and WordPiece operate by iteratively merging the most frequent character n-grams until a target vocabulary size is reached. In a sense, BPE learns which character sequences deserve to be treated as atomic units, automating the process of vocabulary construction that n-gram methods handled by counting. Understanding n-grams provides direct intuition for why these newer tokenization methods work: they are learning the most informative character-level sequence patterns from data, rather than treating every possible sequence uniformly.

When working with n-grams in Python, these are the essential functions and their most important parameters:

nltk.ngrams(sequence, n, pad_left=False, pad_right=False)

• sequence: The input tokens (list of words or characters)
• n: The size of the n-gram (2 for bigrams, 3 for trigrams, etc.)
• pad_left, pad_right: Whether to add padding symbols at boundaries. Useful for language modeling where start and end context matters

nltk.bigrams(sequence) and nltk.trigrams(sequence)

• Convenience functions equivalent to ngrams(sequence, 2) and ngrams(sequence, 3)
• Return generators, so wrap in list() if you need to iterate multiple times

nltk.everygrams(sequence, min_len=1, max_len=-1)

• min_len: Minimum n-gram size to include
• max_len: Maximum n-gram size to include (-1 means use the full sequence length)
• Useful when you want to combine multiple n-gram orders in a single feature set

collections.Counter(iterable)

• Essential for counting n-gram frequencies from any iterable of n-gram tuples
• .most_common(n): Returns the n most frequent items as (item, count) pairs
• Supports arithmetic operations for combining counts across documents

Custom extraction parameters:

• max_skip: For skip-grams, controls how many words can be skipped between selected words. Higher values capture more distant relationships at the cost of larger vocabulary
• pad_symbol: The token used for boundary padding (commonly <s>, </s>, or <PAD>)

Scikit-learn integration:

• CountVectorizer(ngram_range=(1, 2)): Extracts both unigrams and bigrams as a combined feature vector
• TfidfVectorizer(ngram_range=(1, 3)): Extracts unigrams through trigrams with TF-IDF weighting
• analyzer='char': Switches from word n-grams to character n-grams, useful for noisy text or morphologically rich languages

N-grams extend bag of words by preserving local word order, turning text from a multiset of isolated symbols into a collection of overlapping sequences. Key takeaways:

• N-grams are contiguous sequences of $n$ tokens (words or characters), with unigrams, bigrams, and trigrams as the most common orders
• Bigrams capture immediate word relationships and collocations; trigrams add one more word of context and are standard in language modeling
• Vocabulary explosion means the number of unique n-gram types grows exponentially with $n$, increasing memory use and sparsity while demanding more data
• Zipf's law applies to n-grams at every order, with most types appearing only once and a few appearing extremely often
• N-gram language models use the Markov assumption to approximate the full chain rule of probability, conditioning each word's probability on the preceding $n - 1$ words
• Smoothing is essential in any n-gram language model because maximum likelihood estimation assigns zero probability to unseen n-grams
• Character n-grams tolerate typos and spelling variation while capturing morphological complexity below the word boundary
• Skip-grams relax strict adjacency to capture relationships between non-adjacent words at the cost of larger vocabulary
• N-gram indexing enables fast approximate search and phrase matching through inverted index construction
• Trade-offs are inherent: more context requires more data, creates sparser representations, and makes the zero-count problem worse

N-grams bridge the gap between treating words as isolated units and understanding them in context. In the next chapter, we will explore TF-IDF, which adds statistical weighting to distinguish informative terms from common ones. This provides a complementary approach to improving text representations beyond simple count-based methods.

Ready to test your understanding? Take this quick quiz to reinforce what you've learned about n-grams and text representation.