n-gram overlap
**N-gram overlap** is a text similarity measure that quantifies how many **contiguous word sequences** (n-grams) two texts share. It is one of the simplest and most widely used methods for comparing textual similarity, with applications ranging from plagiarism detection to training data decontamination.
**What Are N-Grams**
- **Unigrams (n=1)**: Individual words — "the", "chip", "foundry"
- **Bigrams (n=2)**: Two-word sequences — "the chip", "chip foundry"
- **Trigrams (n=3)**: Three-word sequences — "the chip foundry"
- **Higher-order**: 4-grams, 5-grams, etc. capture longer phrases and more specific matches.
**Computing N-Gram Overlap**
- **Jaccard Similarity**: $\frac{|\text{ngrams}(A) \cap \text{ngrams}(B)|}{|\text{ngrams}(A) \cup \text{ngrams}(B)|}$ — the fraction of shared n-grams out of total unique n-grams. Range 0–1.
- **Containment**: $\frac{|\text{ngrams}(A) \cap \text{ngrams}(B)|}{|\text{ngrams}(A)|}$ — what fraction of A's n-grams appear in B. Useful when texts differ in length.
- **ROUGE-N**: Recall-oriented n-gram overlap used for summarization evaluation.
- **BLEU**: Precision-oriented n-gram overlap used for translation evaluation.
**Applications**
- **Data Contamination**: Check if benchmark test questions appear in training data using **8–13 gram** overlap. Used by GPT-4, Llama, and other model evaluations.
- **Deduplication**: Near-duplicate documents share high n-gram overlap.
- **Plagiarism Detection**: High n-gram overlap between student submissions or documents.
- **Evaluation Metrics**: BLEU and ROUGE are fundamentally n-gram overlap measures.
**Limitations**
- **No Semantic Understanding**: "The car is fast" and "The automobile is speedy" share zero bigrams despite identical meaning.
- **Sensitivity to N**: Low n captures common phrases with false positives; high n may miss valid similarities.
- **Word Order Only**: Only captures exact sequential matches — misses rearranged content.
N-gram overlap remains a **workhorse metric** due to its simplicity, speed, and interpretability, complementing more sophisticated semantic similarity measures.