Near-Duplicate Detection With SimHash #

Exact hashing collapses byte-identical records and nothing else. The expensive duplicates are the ones a reader would call identical and a hash would not: the same article across three syndicating sites, the same listing posted twice with a reordered description, the same page recrawled after a typographical fix. SimHash turns that into a lookup rather than a comparison of every pair. This guide implements it, as part of deduplication strategies for scraped data in the Pipeline Storage, Deduplication & Monitoring section.

Problem Framing #

Comparing every new record against every stored one is quadratic and impossible past a few tens of thousands of records. What is needed is a fingerprint with a specific property: similar documents produce fingerprints that differ in few bits, so candidates can be found by looking up near-matches rather than by comparing text.

The index does the wide search; the exact comparison confirms it.

SimHash provides exactly that. Each feature of the document votes on each bit of the fingerprint, weighted by frequency; the sign of each vote total gives the bit. Two documents sharing most features vote the same way on most bits, so their fingerprints differ in only a few — and the Hamming distance between fingerprints approximates the documents’ dissimilarity.

The engineering problem then becomes finding fingerprints within a small Hamming distance without scanning them all, which is what banded indexing solves.

Step-by-Step Implementation #

1. Choose the features carefully #

Three bits is a reasonable threshold for documents of a few hundred words.

The fingerprint is only as good as its input, and this is where most implementations go wrong. Fingerprinting raw HTML measures template similarity — which is near-identical across every page of a site, so everything looks like a duplicate of everything.

import re
import unicodedata

BOILERPLATE_MIN_SHARE = 0.05      # a shingle on >5% of a host's pages is furniture

def shingles(text: str, width: int = 4) -> list[str]:
    """Overlapping word n-grams: word order matters, exact formatting does not."""
    normalised = unicodedata.normalize("NFKC", text).lower()
    tokens = re.findall(r"\w+", normalised)
    if len(tokens) < width:
        return [" ".join(tokens)] if tokens else []
    return [" ".join(tokens[i:i + width]) for i in range(len(tokens) - width + 1)]

def content_text(record: dict) -> str:
    """Extracted content only — never the markup."""
    return "\n".join(filter(None, (record.get("title"), record.get("description"),
                                   record.get("body_text"))))

Four-word shingles are a good default for prose. Shorter shingles make unrelated documents look similar because common phrases dominate; longer ones make genuinely near-duplicate documents look distinct because a single edited word removes several shingles.

Excluding boilerplate shingles — those appearing on a large share of a host’s pages — sharpens the signal considerably, since navigation and disclaimers otherwise contribute identical votes to every document on the site.

2. Compute the fingerprint #

import hashlib
from collections import Counter

def simhash(text: str, bits: int = 64, boilerplate: frozenset[str] = frozenset()) -> int:
    counts = Counter(s for s in shingles(text) if s not in boilerplate)
    if not counts:
        return 0

    vector = [0] * bits
    for shingle, weight in counts.items():
        digest = int.from_bytes(
            hashlib.blake2b(shingle.encode("utf-8"), digest_size=8).digest(), "big")
        for bit in range(bits):
            vector[bit] += weight if (digest >> bit) & 1 else -weight

    value = 0
    for bit in range(bits):
        if vector[bit] > 0:
            value |= 1 << bit
    return value

def hamming(a: int, b: int) -> int:
    return (a ^ b).bit_count()

Weighting by frequency is what makes the fingerprint reflect emphasis: a phrase appearing five times influences the result more than one appearing once, which is usually the right behaviour for editorial content. Where documents are short and repetition is not meaningful, use presence rather than count.

3. Index in bands so lookup is not a scan #

Finding fingerprints within distance 3 of a query, among millions, requires an index. The pigeonhole principle gives one: split the 64 bits into four 16-bit blocks; two fingerprints differing in at most 3 bits must agree exactly on at least one block. Indexing each block separately turns the search into four exact-match lookups.

BANDS = 4
BAND_BITS = 64 // BANDS

def band_keys(fingerprint: int) -> list[tuple[int, int]]:
    return [(band, (fingerprint >> (band * BAND_BITS)) & ((1 << BAND_BITS) - 1))
            for band in range(BANDS)]

def index_fingerprint(redis, record_id: str, fingerprint: int) -> None:
    pipe = redis.pipeline()
    for band, key in band_keys(fingerprint):
        pipe.sadd(f"simhash:{band}:{key}", f"{record_id}:{fingerprint}")
    pipe.execute()

def find_candidates(redis, fingerprint: int, max_distance: int = 3) -> list[tuple[str, int]]:
    seen, matches = set(), []
    for band, key in band_keys(fingerprint):
        for member in redis.smembers(f"simhash:{band}:{key}"):
            record_id, raw = member.decode().rsplit(":", 1)
            if record_id in seen:
                continue
            seen.add(record_id)
            distance = hamming(fingerprint, int(raw))
            if distance <= max_distance:
                matches.append((record_id, distance))
    return sorted(matches, key=lambda m: m[1])

Four bands supports a maximum distance of 3, which suits documents of a few hundred words. For a higher tolerance, use more bands: with 8 bands of 8 bits, distances up to 7 are findable, at the cost of a larger index and more candidates to verify.

Storing the fingerprint inside the set member avoids a second round trip per candidate, which matters when a popular band bucket holds thousands of entries.

4. Verify before merging #

A candidate within the distance threshold is a candidate. Confirming it with a direct comparison eliminates the false positives that any fingerprint scheme produces.

def jaccard(a: str, b: str) -> float:
    sa, sb = set(shingles(a)), set(shingles(b))
    return len(sa & sb) / len(sa | sb) if (sa or sb) else 1.0

def is_near_duplicate(new_text: str, existing_text: str,
                      distance: int, threshold: float = 0.82) -> tuple[bool, float]:
    similarity = jaccard(new_text, existing_text)
    return similarity >= threshold, similarity

Two thresholds working together — Hamming distance to find candidates, Jaccard similarity to confirm them — give both scalability and precision. The fingerprint index does the cheap wide search; the exact comparison runs only on the handful of candidates it returns.

Record both numbers on the merge decision. When the threshold is later adjusted, past decisions can be re-evaluated from the stored scores rather than by recomputing everything.

Verification & Testing #

A group of thousands is an empty identity field, not real duplication.

def test_identical_text_has_distance_zero():
    text = "the quick brown fox jumps over the lazy dog " * 20
    assert hamming(simhash(text), simhash(text)) == 0

def test_small_edit_stays_close():
    original = "the quick brown fox jumps over the lazy dog " * 20
    edited = original.replace("lazy dog", "lazy cat", 1)
    assert hamming(simhash(original), simhash(edited)) <= 3

def test_unrelated_text_is_far():
    a = "quarterly earnings rose on strong demand " * 20
    b = "the football match ended in a draw after extra time " * 20
    assert hamming(simhash(a), simhash(b)) > 12

def test_banding_finds_a_near_match(redis):
    base = "syndicated article body text here " * 30
    variant = base.replace("here", "there", 2)
    index_fingerprint(redis, "rec-1", simhash(base))
    candidates = find_candidates(redis, simhash(variant), max_distance=3)
    assert "rec-1" in {c[0] for c in candidates}

def test_boilerplate_exclusion_separates_pages(host_boilerplate):
    a = NAV + "unique article one content " * 30 + FOOTER
    b = NAV + "entirely different subject matter " * 30 + FOOTER
    assert hamming(simhash(a, boilerplate=host_boilerplate),
                   simhash(b, boilerplate=host_boilerplate)) > 12

The last test is the one that justifies the boilerplate work: without exclusion, two unrelated pages from the same site share their navigation and footer and can score as near-duplicates.

Monitor the largest group size. A group containing thousands of records almost always means an identity field is empty for those records and they are collapsing onto a shared fingerprint — usually an extraction failure rather than genuine duplication.

Compliance & Operational Guardrails #

A merge preserves every contributing source URL and the earliest first-seen timestamp.
The rule and both scores are recorded, so a threshold change can be re-evaluated.
Fingerprints inherit the retention class of the records they describe.
An erasure request removes fingerprint index entries along with the record.
Merges near the decision boundary are sampled for human review each week.

Common Mistakes #

Fingerprinting raw HTML. Template similarity swamps content similarity and everything looks duplicated.
Skipping the exact verification step. Hamming distance alone produces false merges that are difficult to unpick.
Deleting the losing record outright. Its identifier and fingerprint should survive in a merge log so the decision can be reviewed.

Frequently Asked Questions #

SimHash or MinHash? #

SimHash for a compact fixed-size fingerprint with a cheap distance metric, which is what a streaming pipeline wants. MinHash with LSH gives a more accurate similarity estimate and better recall at high thresholds, at the cost of a much larger signature. For crawl deduplication SimHash is usually the better fit; MinHash earns its place when the corpus is fixed and recall matters more than throughput.

What distance threshold should I use? #

Three bits out of 64 for documents of a few hundred words, tuned against your own corpus. Build a labelled sample of a few hundred pairs — genuine duplicates and genuine distinct pairs — and pick the threshold that separates them best. A number borrowed from a paper about a different kind of document is a guess.

Does it work on very short text? #

Poorly. Fingerprints of documents under about fifty words are unstable, because a handful of shingles determines every bit. For short records — titles, listings with a one-line description — prefer exact normalised comparison or field-level matching, and reserve SimHash for documents long enough to have a stable feature distribution.

Deduplication Strategies for Scraped Data — where near-duplicate detection sits in the ladder.
Normalising Text Before Hashing for Dedup — the normalisation this depends on.
Detecting Content Changes With Rolling Hashes — the within-document counterpart.