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.