🔗 N-gram

Concept · 21 key papers · all concepts

Part of: 🗨️ Natural language processing

An n-gram is a contiguous sequence of n items, usually words or characters, taken from a text. Counting n-grams gives the statistics behind n-gram language models, classic text features, and automatic evaluation metrics such as BLEU and chrF.

Also: Ngram, unigram (n = 1), bigram (n = 2), trigram (n = 3), character n-gram, word n-gram, shingle, n-gram language model, Markov language model

What it is

An n-gram is a run of n consecutive units cut from a text. The units may be words, characters, subword pieces or even phonemes. N-grams are one of the oldest tools in natural language processing. They make the order of a text countable without requiring a grammar.

Take the sentence «the cat sat on the mat», split by tokenization into six words.

A sequence of N tokens contains N − n + 1 n-grams of order n. Counting means sliding a window across a corpus and tallying each distinct sequence. Here the unigram «the» has count 2, and every other n-gram has count 1. At the level of characters, the word «cat» padded with boundary marks gives the trigrams «ca», «cat» and «at».

Word frequencies follow Zipf's law, so a few n-grams are very common and most are rare. The share of n-grams seen only once grows with n.

The key idea

A language model built from counts

An n-gram language model predicts the next word from only the previous n − 1 words. This is the Markov assumption, named after Andrei Markov and used for English text by Shannon (1948). The probability of a whole sentence becomes a product of these local predictions. The maximum-likelihood estimate is:

P(w_i | w_{i−n+1} … w_{i−1}) = count(w_{i−n+1} … w_i) / count(w_{i−n+1} … w_{i−1})

Here w_i is the word being predicted, and w_{i−n+1} … w_{i−1} are the n − 1 words before it, called the context. The function count( ) gives how often a sequence occurs in the training corpus. The fraction is therefore the share of the context's occurrences that are followed by w_i.

The sparsity problem and smoothing

Maximum likelihood gives zero probability to any n-gram that never appeared in training, and most plausible sequences never appear. Bengio and colleagues describe this as the curse of dimensionality: the number of possible word sequences grows exponentially with their length. For 10 consecutive words over a 100,000-word vocabulary, a joint table would need roughly 10^50 free parameters (Bengio et al. 2003). Smoothing moves some probability mass from seen events to unseen ones. The simplest method is add-one (Laplace) smoothing:

P_add1(w_i | h) = (count(h w_i) + 1) / (count(h) + V)

In this formula, h is the context and V is the vocabulary size. Each possible continuation receives one imaginary extra occurrence.

Better estimators came later. Good (1953), crediting the idea to Turing, re-estimated a count r from the number of types seen r + 1 times. In that scheme, the number of types seen exactly once fixes the mass reserved for unseen events. Katz (1987) proposed backing off to a shorter context when the full context is unseen. Kneser and Ney (1995) based lower-order estimates on how many different contexts a word follows, rather than on its raw frequency.

The comparison by Chen and Goodman covered additive baselines, Jelinek–Mercer interpolation, Katz and Church–Gale on Brown and TIPSTER newswire text. It showed that the best method changes with training-set size and n-gram order, so a ranking from a single setting can mislead (Chen & Goodman 1996).

At web scale, a much cruder rule proved enough. Stupid Backoff uses plain relative frequencies and multiplies by a fixed factor of 0.4 each time it falls back to a shorter context. Its scores are not normalized probabilities (Brants et al. 2007):

S(w_i | h) = count(h w_i) / count(h)     if count(h w_i) > 0
S(w_i | h) = 0.4 · S(w_i | h′)           otherwise
S(w_i)     = count(w_i) / N              (unigram case)

Here h′ is the context h with its oldest word removed, and N is the corpus size in tokens.

The label smoothing used to train neural classifiers shares the name with n-gram smoothing but is a separate technique (Müller et al. 2019).

History and founding papers

From association statistics to probabilistic models

Corpus statistics over word pairs entered lexicography with the association ratio of Church and Hanks. It is a mutual-information score over words that co-occur within a five-word window. They kept it asymmetric so that word order still counts. It captures pairs such as fixed phrases and verb–preposition patterns (Church & Hanks 1990).

In speech recognition, trigram models were the standard predictors. Grammar-based alternatives had to match the n-gram model's left-to-right interface. Jelinek and Lafferty did this by computing prefix probabilities for stochastic context-free grammars (Jelinek & Lafferty 1991).

Data against sparsity

One response to sparse counts was simply more text. Keller and Lapata found that web search hit counts for bigrams missing from the British National Corpus correlated reliably with human plausibility ratings and with smoothed estimates (Keller & Lapata 2003).

Brants and colleagues at Google trained 5-gram models on up to 2 trillion tokens using MapReduce. In Arabic–English translation, BLEU grew about linearly with every doubling of the training data. Stupid Backoff caught up with Kneser–Ney once the data was large enough (Brants et al. 2007).

Heafield and coauthors then showed that full modified Kneser–Ney need not be simplified. Their disk-based streaming estimator in KenLM built an unpruned 5-gram model from 126 billion tokens on a single server (Heafield et al. 2013). The same tools produced multilingual, deduplicated models from the Common Crawl (Buck et al. 2014).

N-gram translation models

N-grams also served as the translation model itself. Mariño and colleagues treated translation as a back-off n-gram model over bilingual tuples (Mariño et al. 2006). LM-style smoothing, including Good–Turing and Kneser–Ney, improved phrase-table estimates (Foster et al. 2006).

The neural turn

Bengio and colleagues replaced count tables with learned word vectors and a neural network. On Brown and AP News text, their model had lower perplexity than smoothed trigrams, and mixing the two helped further. This work laid the ground for word embeddings and for the neural language models that modern NLP builds on (Bengio et al. 2003).

How it is used today

Evaluation metrics

The BLEU score, introduced by Papineni and colleagues in 2002, scores machine translation output by clipped n-gram precision against reference translations. Lin and Hovy turned this into recall over model summaries, which gave rise to ROUGE (Lin & Hovy 2003). Lin and Och then added longest-common-subsequence and skip-bigram variants (Lin & Och 2004).

Sentence-level BLEU collapses to zero when a sentence has no matching 4-gram, which is why it needs its own smoothing (Chen & Cherry 2014). Maja Popović's chrF computes an F-score over character n-grams. It needs no tokenizer and works well for morphologically rich target languages (Popović 2015). Its chrF++ variant adds word unigrams and bigrams to the character n-grams (Popović 2017).

Features for classification and representation

In text classification, unigram-plus-bigram baselines were shown to be hard to beat. Wang and Manning found that bigrams consistently improved sentiment classification, and their NBSVM model matched more complex systems (Wang & Manning 2012).

Character 3–5-grams weighted with TF-IDF outperformed a fine-tuned AraBERT model on Arabic dialect identification, and an ensemble of the two did best (Mekki et al. 2020). Order-free n-gram embeddings have also served sentiment analysis across Arabic dialects (Mulki et al. 2019).

Character n-grams give compact word and sentence vectors that cope with misspellings and rare words (Wieting et al. 2016). Sent2Vec averages embeddings of a sentence's words and n-grams (Pagliardini et al. 2018).

Indexed Twitter bigram statistics help choose normalizations for noisy tweets (Berend & Tasnádi 2015). Skip n-grams, which allow gaps between items, have been used to predict script events (Jans et al. 2012).

Syntactic and diachronic n-grams

The Google Books Ngram corpus received part-of-speech annotation (Lin et al. 2012). A companion dataset counts dependency-tree fragments, called syntactic n-grams, by year (Goldberg & Orwant 2013). Syntactic n-grams have also driven rule-based grammar correction for learners (Sidorov et al. 2013). Bigram counts from different decades support distributional semantics studies of language change (Gulordava & Baroni 2011).

Inside neural models

Neural pretraining has absorbed the idea. ProphetNet trains a decoder to predict the next several tokens at once (Qi et al. 2020). ERNIE-Gram masks whole n-grams and predicts each one as a single unit drawn from an n-gram lexicon (Xiao et al. 2020).

Open questions

Can count-based models still complement large language models? The ∞-gram model indexes trillions of tokens with a suffix array and backs off only when a context is unseen. Interpolating it with neural models lowers perplexity substantially, but the gain does not carry over to open-ended generation (Liu et al. 2024). It is still unclear whether exact long matches help factuality or mainly reflect memorized text.

A second question concerns metrics. Surface n-gram overlap rewards wording rather than meaning. The steady line of variants, from recall-oriented scores to skip-bigrams and character F-scores, suggests that no single n-gram metric agrees fully with human judgment (Lin & Och 2004; Popović 2017).

A third question is the choice of unit. With subword tokenization, the boundary between character, word and subword n-grams depends on the tokenizer. For Arabic dialects, whose word order is free, order-free n-gram embeddings came close to deeper neural sentiment systems (Mulki et al. 2019). Which unit best serves languages with rich morphology or free word order in general remains an empirical question.

Key papers

The works this page cites, the most cited first; citations as counted by OpenAlex plus the papers of this library that cite the work, read 2026-10-24.

Related concepts

• Language model — A language model is a probability distribution over sequences of tokens (words, subwords or characters). It is usually factored into…
• BLEU score — BLEU score (Bilingual Evaluation Understudy) is an automatic metric for machine translation. It rates a candidate text by how many of its…
• Zipf's law — Zipf's law is the empirical regularity that, when the items of a collection such as the words of a text are ranked by frequency, each…
• TF-IDF — Term frequency–inverse document frequency (TF-IDF) is a weighting scheme that scores how important a word is to one document in a…

More papers

Topics: 🧠 Language models & pretraining · 🔁 Machine translation

Shelves: 🤖 Artificial Intelligence

Updated 24 October 2026

This page in Markdown → https://md.research.elamur.ai/free/en/concepts/n-gram/