Near-Duplicate Detection

Same Content, Different Pages

A news story is syndicated to twenty sites, each adding its own footer. A shop serves the same product description under five category paths. A blog has a printer-friendly copy of every post, and an article is republished with a corrected paragraph. URL normalisation collapses URL variants of one page, but none of these share a URL. They share content, and some of them share only most of it.

Near-duplicate detection answers "have I already stored essentially this text?" Unlike entity resolution, which matches short structured records, it compares whole documents, often millions of them, so comparing every pair is out of the question.

Three Layers, Cheapest First

Run them in that order and stop at the first hit. Every layer works on the main content only: navigation, footers, cookie banners and "related articles" widgets must be stripped first (the incremental scraping lesson shows how). If you shingle whole pages, two different products on the same template look like near-duplicates because the template text dominates, a false positive that is very common on short product pages.

Exact Duplicates After Normalisation

Normalise before hashing so that trivial differences do not produce different keys: Unicode normalisation, case folding, and punctuation and whitespace removal. The test corpus below is used throughout the lesson:

import hashlib
import re
import unicodedata

BASE = ("The city council approved a new budget on Tuesday that raises spending on public "
        "transport by 12 percent. The plan adds three bus routes in the northern districts "
        "and extends evening service on the tram network. The mayor said the new routes "
        "would start in the spring and promised a review after one year.")
DOCS = {
    "orig": BASE,
    "syndicated": BASE + " This story was first published by the Daily Ledger.",
    "edited": BASE.replace("approved a new budget on Tuesday", "on Tuesday approved a new budget")
                  .replace("would start in the spring", "will begin operating in spring"),
    "other": ("The city council postponed a vote on the housing plan on Tuesday. The plan "
              "would allow taller buildings near tram stops and cut parking requirements. "
              "The mayor said a revised proposal would be presented in the spring."),
}

def words(text):
    return re.findall(r"\w+", unicodedata.normalize("NFKC", text).casefold())

def exact_key(text):
    return hashlib.sha256(" ".join(words(text)).encode()).hexdigest()

Store exact_key in a unique index and most duplicates vanish at almost no cost. But all four documents above get different keys, including the syndicated copy that differs only by one sentence. That is the job of the next layer.

Shingles and Jaccard Similarity

A shingle is a run of k consecutive words. Two documents that share most of their shingles share most of their text, in order. The Jaccard similarity of the two shingle sets, the size of the intersection divided by the size of the union, gives a score between 0 and 1:

def shingles(text, k=3):
    w = words(text)
    return {" ".join(w[i:i + k]) for i in range(max(1, len(w) - k + 1))}

def jaccard(a, b):
    return len(a & b) / len(a | b)

for name in ("syndicated", "edited", "other"):
    row = [f"k={k}: {jaccard(shingles(DOCS['orig'], k), shingles(DOCS[name], k)):.2f}" for k in (1, 3, 5)]
    print(f"orig vs {name:10}", "  ".join(row))

orig vs syndicated k=1: 0.85  k=3: 0.85  k=5: 0.85
orig vs edited     k=1: 0.89  k=3: 0.62  k=5: 0.49
orig vs other      k=1: 0.25  k=3: 0.04  k=5: 0.00

The choice of k decides what "similar" means. With k=1 (a bag of words), the reworded copy scores higher than the syndicated one and an unrelated article on the same topic reaches 0.25, because council stories share vocabulary. Larger k punishes every edit more: a single changed word breaks k shingles. Short texts such as product descriptions suit k of 3 to 5 words; long articles tolerate larger k. Pick k on your own data, using the evaluation below.

Exact Jaccard needs the full shingle sets of both documents, and comparing each new page against every stored page is quadratic. The next two techniques fix both problems.

MinHash and LSH: Finding Candidates Fast

MinHash compresses a shingle set into a fixed-length signature, typically 128 numbers, such that the fraction of positions where two signatures agree estimates their Jaccard similarity. Locality-sensitive hashing (LSH) splits each signature into b bands of r rows and hashes each band; two documents become candidates if any band matches exactly. The datasketch library implements both:

from datasketch import MinHash, MinHashLSH

def minhash(text, num_perm=128):
    m = MinHash(num_perm=num_perm)
    for sh in shingles(text):
        m.update(sh.encode("utf-8"))
    return m

sigs = {name: minhash(text) for name, text in DOCS.items()}
lsh = MinHashLSH(threshold=0.5, num_perm=128, weights=(0.2, 0.8))
print("bands x rows:", lsh.b, "x", lsh.r)

THRESHOLD = 0.6
for name, sig in sigs.items():
    candidates = sorted(lsh.query(sig))
    dups = [c for c in candidates if sig.jaccard(sigs[c]) >= THRESHOLD]
    print(f"{name:10} candidates={candidates} duplicates_of={dups}")
    lsh.insert(name, sig)

bands x rows: 30 x 4
orig       candidates=[] duplicates_of=[]
syndicated candidates=['orig'] duplicates_of=['orig']
edited     candidates=['orig', 'syndicated'] duplicates_of=['orig']
other      candidates=[] duplicates_of=[]

Three details carry the design. The loop queries before inserting, as a crawler would: each new page is checked against everything seen so far without pairwise comparison. Candidates are verified with the signature estimate (sig.jaccard), because LSH only promises that similar pairs are likely to collide; edited collided with syndicated, but their estimate is below 0.6. And the LSH threshold is deliberately below the decision threshold.

That last point comes from the shape of the collision probability. With b bands of r rows, a pair with similarity s becomes a candidate with probability 1 - (1 - s^r)^b. For datasketch's default choice at threshold=0.6 (18 bands of 7 rows), that probability is only about 0.40 at s = 0.6 and 0.79 at s = 0.7, so many pairs just above your threshold would never be compared. Lowering the LSH threshold to 0.5 and weighting false negatives more heavily (weights=(0.2, 0.8)) gives 30 bands of 4 rows, which catches almost every pair above 0.6 in exchange for more candidates to verify. Verification is cheap, missed duplicates are not recoverable, so err toward more candidates.

SimHash: One 64-Bit Fingerprint per Page

SimHash reduces a document to a single integer. Each shingle is hashed to 64 bits; for each bit position, shingles with a 1 add a vote and shingles with a 0 subtract one; the fingerprint has a 1 wherever the total is positive. Similar documents get fingerprints that differ in few bits:

def simhash(text, bits=64):
    counts = [0] * bits
    for sh in shingles(text):
        h = int.from_bytes(hashlib.blake2b(sh.encode(), digest_size=8).digest(), "big")
        for i in range(bits):
            counts[i] += 1 if (h >> i) & 1 else -1
    return sum(1 << i for i in range(bits) if counts[i] > 0)

def hamming(a, b):
    return (a ^ b).bit_count()            # Python 3.10+

fp = {name: simhash(text) for name, text in DOCS.items()}
for name in ("syndicated", "edited", "other"):
    print(f"orig vs {name:10} differing bits: {hamming(fp['orig'], fp[name])}")

orig vs syndicated differing bits: 11
orig vs edited     differing bits: 23
orig vs other      differing bits: 31

The ordering is right, but the gaps are small: on 50-word texts every shingle moves the vote noticeably, and unrelated documents differ in about half of the 64 bits, so edited at 23 bits is not clearly separated from other at 31. SimHash works well on longer pages, where a footer or a few edited sentences shift only a few bits; Google's 2007 paper on near-duplicate detection for web crawling used 64-bit fingerprints and treated pages within 3 bits as near-duplicates. Production versions also weight features, for example by term frequency, instead of giving every shingle one vote.

The fingerprint is small enough to index cleverly. If two 64-bit values differ in at most 3 bits, then at least one of their four 16-bit blocks is identical (3 differences cannot touch all 4 blocks). Index each fingerprint under each of its blocks and compare only within matching blocks:

from collections import defaultdict

blocks = [defaultdict(list) for _ in range(4)]

def add(doc_id, f):
    for i in range(4):
        blocks[i][(f >> 16 * i) & 0xFFFF].append((doc_id, f))

def near(f, max_bits=3):
    return {doc for i in range(4)
            for doc, g in blocks[i].get((f >> 16 * i) & 0xFFFF, []) if hamming(f, g) <= max_bits}

MinHash or SimHash?

For most scraping projects, which store thousands to millions of pages, MinHash with datasketch is the easier choice to reason about and tune.

Choosing and Checking the Threshold

A threshold is a claim about your data, so test it. Collect candidate pairs with a deliberately low LSH threshold, bucket them by estimated similarity (0.4-0.5, 0.5-0.6, and so on), and label twenty or thirty pairs per bucket by reading them. The bucket where most pairs stop being true duplicates is your threshold. Weigh the cost of each error: collapsing two product variants with near-identical descriptions loses real records, while keeping a syndicated copy only wastes storage. For product pages, add a hard rule that identifiers or prices must also match.

Keep the Duplicates, Mark Them

Do not delete near-duplicates at scrape time. Store every page with a cluster_id and pick one representative per cluster by an explicit rule: the declared canonical URL, else the earliest first_seen, else the most trusted source. Merging pairwise matches into clusters is the union-find step from the entity-resolution lesson. Record the similarity and method on each link so a new threshold can be replayed from stored signatures without re-crawling. For shared crawls, datasketch can keep the LSH index in Redis.

Practice

Scrape 500 articles from two permitted sites that syndicate each other or a common wire service. Extract the main text, compute exact keys and MinHash signatures with k = 3 and k = 7, and list the clusters each setting produces. Label 50 candidate pairs by hand and pick the k and threshold with the best precision at acceptable recall.