Deduplication › Code Implementation
Language AI HandbookAll chapters Deduplication › Code ImplementationOne section · Sections in this chapter7 / 13 ↓
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
We will implement exact deduplication, Jaccard similarity computation, and a simple near-duplicate detection pipeline in Python. The implementation follows a natural progression: first, we build exact matching using cryptographic hashes; then we build fuzzy matching using shingles and Jaccard similarity; finally, we measure how aggressively different thresholds prune the corpus.
Setting Up
Exact Deduplication
The exact deduplication function normalizes each document and computes its SHA-256 hash. Documents with the same hash are duplicates. The normalization step is the most important part: without it, two copies of the same article that differ only in whitespace or capitalization would pass through as distinct documents.
def normalize_document(text):
"""Normalize text before hashing to catch formatting variants."""
text = text.lower()
text = text.strip()
text = re.sub(r"\s+", " ", text)
return text
def exact_dedup(documents):
"""
Remove exact duplicates from a list of (id, text) tuples.
Returns the deduplicated list and the set of removed ids.
"""
seen_hashes = {}
kept = []
removed_ids = []
for doc_id, text in documents:
normalized = normalize_document(text)
doc_hash = hashlib.sha256(normalized.encode("utf-8")).hexdigest()
if doc_hash not in seen_hashes:
seen_hashes[doc_hash] = doc_id
kept.append((doc_id, text))
else:
removed_ids.append(
(doc_id, f"duplicate of {seen_hashes[doc_hash]}")
)
return kept, removed_ids# Test corpus with exact duplicates
corpus = [
("doc_001", "The quick brown fox jumps over the lazy dog."),
("doc_002", "The quick brown fox jumps over the lazy dog."), # exact copy
(
"doc_003",
" The quick brown fox jumps over the lazy dog. ",
), # whitespace variant
("doc_004", "Machine learning requires large amounts of training data."),
("doc_005", "Neural networks learn representations from raw input."),
]
kept, removed = exact_dedup(corpus)Original corpus size: 5 documents After exact dedup: 3 documents Removed 2 duplicates: doc_002: duplicate of doc_001 doc_003: duplicate of doc_001
Exact deduplication caught both the identical copy and the whitespace variant because normalization strips leading and trailing whitespace before hashing. This is why normalization is a critical preprocessing step: two documents that look identical to a human but differ in a trailing space will have completely different SHA-256 hashes without normalization. In a production corpus of billions of documents, whitespace and encoding variants are not edge cases; they are the rule. Scrapers use different HTML parsers, different character encoding libraries, and different newline conventions. Normalization unifies these variations before the hash function ever runs.
Shingling and Jaccard Similarity
Next, we implement the shingling function and Jaccard similarity computation. The shingling function slides a window of size across the normalized document, collecting all substrings. The Jaccard function then computes the overlap between any two such sets.
def get_shingles(text, k=5):
"""Convert text to a set of k-character shingles."""
normalized = normalize_document(text)
if len(normalized) < k:
return {normalized}
return {normalized[i : i + k] for i in range(len(normalized) - k + 1)}
def jaccard_similarity(set_a, set_b):
"""Compute Jaccard similarity between two sets."""
if not set_a and not set_b:
return 1.0
intersection = set_a & set_b
union = set_a | set_b
return len(intersection) / len(union)# Compute shingles for a set of near-duplicate candidates
near_dup_corpus = [
("doc_A", "The quick brown fox jumps over the lazy dog"),
("doc_B", "A quick brown fox leaped over the sleeping dog"),
("doc_C", "Machine learning requires large amounts of training data"),
("doc_D", "Machine learning requires large amounts of labeled data"),
("doc_E", "Neural networks learn representations from raw input features"),
]
# Compute shingle sets for each document
shingle_sets = {
doc_id: get_shingles(text, k=5) for doc_id, text in near_dup_corpus
}
# Compute pairwise Jaccard similarities
pairs = list(combinations(near_dup_corpus, 2))
similarities = []
for (id_a, text_a), (id_b, text_b) in pairs:
sim = jaccard_similarity(shingle_sets[id_a], shingle_sets[id_b])
similarities.append((id_a, id_b, sim))
similarities.sort(key=lambda x: x[2], reverse=True)Pairwise Jaccard Similarities (sorted by similarity): Doc A Doc B Jaccard ------------------------------ doc_C doc_D 0.6452 doc_A doc_B 0.3065 doc_C doc_E 0.0189 doc_D doc_E 0.0189 doc_B doc_C 0.0109 doc_A doc_C 0.0000 doc_A doc_D 0.0000 doc_A doc_E 0.0000 doc_B doc_D 0.0000 doc_B doc_E 0.0000
The highest-similarity pairs correspond to the near-duplicate documents in our corpus. Documents about the fox sentence share many character 5-grams despite different wording, and documents about machine learning that differ only in "training" vs "labeled" are even more similar because the differing words are short and the surrounding characters dominate the shingle set. Documents from entirely different topics (the fox sentence vs the machine learning sentences) have near-zero Jaccard similarity, confirming that the metric cleanly separates related from unrelated content.
The pairwise similarity matrix makes these relationships visible. In the heatmap below, you can see that the fox documents (doc_A and doc_B) form one cluster, the machine learning documents (doc_C and doc_D) form another, and document doc_E is isolated. Only the within-cluster pairs would exceed a deduplication threshold.
Near-Duplicate Removal
With similarity scores in hand, we can apply a threshold to decide which documents to remove. The standard approach is greedy: process documents in order, and when a near-duplicate is found, discard the later document. The earlier document survives because we want to process sources in decreasing quality order, keeping the best version.
def near_dup_remove(documents, k=5, threshold=0.5):
"""
Greedy near-duplicate removal.
For each document, check if it is similar to any previously seen document.
If so, discard it.
Args:
documents: list of (doc_id, text) tuples
k: shingle size
threshold: Jaccard similarity threshold for near-duplicate detection
Returns:
Tuple of (kept documents, list of (removed_id, similar_to_id, score))
"""
seen_shingles = [] # list of (doc_id, shingle_set) for kept docs
kept = []
removed = []
for doc_id, text in documents:
shingles = get_shingles(text, k=k)
max_sim = 0.0
most_similar_id = None
for seen_id, seen_set in seen_shingles:
sim = jaccard_similarity(shingles, seen_set)
if sim > max_sim:
max_sim = sim
most_similar_id = seen_id
if max_sim >= threshold:
removed.append((doc_id, most_similar_id, max_sim))
else:
seen_shingles.append((doc_id, shingles))
kept.append((doc_id, text))
return kept, removedkept_docs, removed_docs = near_dup_remove(near_dup_corpus, k=5, threshold=0.3)Original corpus: 5 documents After near-dup removal: 3 documents Removed near-duplicates: doc_B removed (similar to doc_A, J=0.306) doc_D removed (similar to doc_C, J=0.645) Kept documents: doc_A: The quick brown fox jumps over the lazy dog... doc_C: Machine learning requires large amounts of training data... doc_E: Neural networks learn representations from raw input feature...
The greedy approach processes documents sequentially and keeps the first document in each near-duplicate cluster. The order of processing matters: you typically want to process higher-quality sources first so that when you encounter a near-duplicate cluster, you keep the highest-quality version. In practice this means pre-sorting documents by quality signal (source domain, length, readability score) before running the greedy deduplication pass. Wikipedia articles, academic papers, and curated books should be processed before raw web pages, so that when a web page is a near-duplicate of a Wikipedia article, the web page is the one discarded.
Measuring Deduplication Impact
A useful diagnostic is to plot how the corpus size shrinks at different similarity thresholds. Lower thresholds (0.1) are very aggressive and remove even loosely similar documents. Higher thresholds (0.9) are conservative and only remove near-identical documents. By sweeping over thresholds, you can understand the sensitivity of your pipeline to this hyperparameter and choose a value appropriate for your quality requirements.
def make_synthetic_corpus(n_unique=50, n_copies_per_unique=3, noise_level=0.15):
"""
Create a synthetic corpus with controlled duplication.
Each unique document spawns copies with random character-level perturbations.
"""
base_texts = [
f"Document {i}: "
+ " ".join(
[
f"word{np.random.randint(0, 200)}"
for _ in range(np.random.randint(20, 50))
]
)
for i in range(n_unique)
]
corpus = []
doc_id = 0
for base in base_texts:
# Add original
corpus.append((f"doc_{doc_id:04d}", base))
doc_id += 1
# Add noisy copies
for _ in range(n_copies_per_unique - 1):
chars = list(base)
n_perturb = max(1, int(len(chars) * noise_level))
for _ in range(n_perturb):
pos = np.random.randint(0, len(chars))
chars[pos] = str(np.random.randint(0, 9))
corpus.append((f"doc_{doc_id:04d}", "".join(chars)))
doc_id += 1
np.random.shuffle(corpus)
return corpus
synthetic_corpus = make_synthetic_corpus(n_unique=50, n_copies_per_unique=3)
# Measure corpus size after dedup at various thresholds
thresholds = np.arange(0.1, 1.0, 0.1)
kept_sizes = []
for threshold in thresholds:
kept, _ = near_dup_remove(synthetic_corpus, k=5, threshold=threshold)
kept_sizes.append(len(kept))Original corpus: 150 documents (50 unique + 100 copies) Threshold Kept Docs Reduction % ------------------------------------ 0.1 12 92.0% 0.2 90 40.0% 0.3 90 40.0% 0.4 149 0.7% 0.5 150 0.0% 0.6 150 0.0% 0.7 150 0.0% 0.8 150 0.0% 0.9 150 0.0%
The table reveals the deduplication curve: very low thresholds aggressively remove even loosely similar documents, while high thresholds preserve near-duplicates. The plot below makes this curve explicit and marks typical practitioner thresholds.
Practitioners typically choose thresholds in the 0.7 to 0.8 range for character-based Jaccard similarity, but the right value depends on the corpus and the tolerance for false positives. In this deliberately noisy synthetic corpus, that conventional range is too conservative: changing 15% of characters destroys enough 5-shingle overlap that all copies remain. A news corpus, where articles frequently quote the same source material, may require a higher threshold to avoid over-removal. A code corpus, where many files are functional duplicates with minor variable renames, may benefit from a lower threshold. Understanding the nature of duplication in your specific corpus is essential before choosing a threshold.
Effect of Shingle Size
The shingle size is another key parameter. Smaller shingles generate many common substrings, causing unrelated documents to appear similar. Larger shingles are more specific but may miss near-duplicates that differ in small sections. The plot below shows how shingle size affects the Jaccard scores for the same document pair at different levels of similarity.
# Generate document pairs with varying similarity levels
def make_document_pair(rng, base_length=200, noise_fraction=0.0):
"""Create a document and a perturbed copy with given noise fraction."""
base = " ".join([f"word{rng.randint(0, 300)}" for _ in range(base_length)])
chars = list(base)
n_perturb = int(len(chars) * noise_fraction)
for _ in range(n_perturb):
pos = rng.randint(0, len(chars))
chars[pos] = str(rng.randint(0, 9))
copy = "".join(chars)
return base, copy
k_values = [3, 5, 7, 9, 12]
# noise_fractions represent the fraction of characters changed
noise_fractions = [0.0, 0.05, 0.10, 0.20, 0.35, 0.50]
pair_rng = np.random.RandomState(7)
document_pairs = [
make_document_pair(pair_rng, base_length=200, noise_fraction=noise)
for noise in noise_fractions
]
# For each noise level and shingle size, compute jaccard similarity
jaccard_by_k = {}
for k in k_values:
jaccard_by_k[k] = []
for doc1, doc2 in document_pairs:
s1 = get_shingles(doc1, k=k)
s2 = get_shingles(doc2, k=k)
j = jaccard_similarity(s1, s2)
jaccard_by_k[k].append(j)