How to Find Near-Duplicate Documents in Python With MinHash and Locality-Sensitive Hashing

Open the same news story on three different sites and you will usually find one article wearing three outfits: a different headline, a cookie banner on top, a “related stories” list at the bottom, maybe a sentence trimmed here and there. To a person that is a single article. To a program that compares bytes, it is three unrelated files. Finding those copies automatically is called near-duplicate detection, and it matters anywhere text piles up: web crawlers, search indexes, support-ticket systems, retrieval-augmented generation (RAG) knowledge bases that keep returning five copies of the same paragraph, and the training sets behind large language models.

That last case has been measured. In “Deduplicating Training Data Makes Language Models Better”, Katherine Lee, Daphne Ippolito and their co-authors report that “existing language modeling datasets contain many near-duplicate examples and long repetitive substrings,” and that as a result “over 1% of the unprompted output of language models trained on these datasets is copied verbatim from the training data.” After deduplicating, they could train models that “emit memorized text ten times less frequently.” Cleaning duplicates is not housekeeping; it changes what the model learns.

In this tutorial you will build the classic tool for the job from scratch in plain Python: MinHash signatures plus locality-sensitive hashing (LSH). You will not just copy the recipe. You will run it on a corpus where the right answer is known, measure how accurate it is, find the point where it starts to beat brute force, break it on purpose in four ways, and check it against the widely used datasketch library. Along the way you will learn what each moving part is for, so you can tune it for your own data.

By the end you will have a working pipeline that:

• turns each document into a set of overlapping word runs called shingles;
• compresses every set into a short fixed-size MinHash signature whose agreement rate estimates how similar two documents are;
• uses LSH banding to find likely duplicate pairs without comparing every pair;
• verifies the candidates exactly, then groups duplicates so you can keep one document per group;
• comes with 14 automated tests that pin down the behavior you will otherwise forget.

The Four Ideas You Need Before Writing Code

If any of these terms are new, read this section slowly. Everything after it is just these four ideas, one at a time.

Idea 1: Exact hashing cannot see “almost the same”

You may already know how to detect exact duplicates: hash the whole text (SHA-256, say) and keep a set of the hashes you have seen. A Bloom filter does a similar job in far less memory, at the price of an occasional false positive. Both break the moment a single character changes, because a good hash function turns a one-character change into a completely different hash. Near-duplicates need a measure of similarity, not equality.

Idea 2: Shingles and Jaccard similarity

A shingle is a run of consecutive words. The sentence “the quick brown fox” contains two 3-word shingles: “the quick brown” and “quick brown fox.” If you turn each document into the set of its shingles, two copies of an article share almost all of their shingles, and two unrelated articles share almost none. The Jaccard similarity of two sets is the number of shingles they share divided by the number of distinct shingles in either one: |A ∩ B| / |A ∪ B|. It is 1.0 for identical sets and 0.0 for sets with nothing in common.

Idea 3: MinHash compresses a set into a short signature

Comparing every pair of documents costs n * (n - 1) / 2 comparisons, and each one touches hundreds of shingles. MinHash shrinks each document to a signature, a list of (say) 128 integers, such that the fraction of positions where two signatures agree is an estimate of the Jaccard similarity of the original sets. Step 3 shows why that works.

Idea 4: LSH finds likely pairs without checking all pairs

Even with short signatures, comparing every pair is still quadratic. Locality-sensitive hashing avoids it. You cut each signature into bands of a few numbers and put each band into a hash table. Two documents that agree on every number in at least one band land in the same bucket and become a candidate pair; everything else is never compared. Similar documents collide often, dissimilar ones rarely, and you only look at the collisions.

Prerequisites

• Python 3.10 or newer. I ran everything on Python 3.13.14 on Windows 11. The commands below use the Windows activation line; the comment shows the macOS and Linux one.
• Comfort with sets, dictionaries and functions. No math beyond fractions and powers.
• Two packages, only for the checking steps: pytest (9.1.1 here) and datasketch (2.0.0 here, which pulls in NumPy 2.5.3 and SciPy 1.18.1). The MinHash and LSH code you write uses only the standard library.
• A few minutes of computing time in total. Step 8 is the slow one, roughly a minute and a half.

Create a folder and a virtual environment. Every code block below starts with a comment holding its file name; save each one under that name in this folder.

mkdir minhash-lab
cd minhash-lab
python -m venv .venv
.venv\Scripts\activate          # macOS and Linux: source .venv/bin/activate
python -m pip install pytest datasketch

Step 1: Turn Documents Into Shingle Sets and Measure Jaccard Similarity

Start with the smallest useful module: text cleanup, shingling and the exact Jaccard formula. Everything later builds on these three functions.

# textutil.py
import re


def normalize(text):
    """Lowercase, replace punctuation with spaces, collapse runs of whitespace."""
    text = re.sub(r"[^\w\s]", " ", text.lower())
    return " ".join(text.split())


def shingles(text, size=3, clean=True):
    """Return the set of word shingles (runs of `size` consecutive words)."""
    words = (normalize(text) if clean else text).split()
    if len(words) < size:
        return {" ".join(words)} if words else set()
    return {" ".join(words[i:i + size]) for i in range(len(words) - size + 1)}


def jaccard(a, b):
    """Exact Jaccard similarity of two sets: |A & B| / |A | B|."""
    if not a and not b:
        return 1.0
    shared = len(a & b)
    return shared / (len(a) + len(b) - shared)

normalize lowercases the text, turns every punctuation mark into a space and collapses runs of whitespace, so “Hello, WORLD!!” and “hello world” become the same string. shingles slides a window of size words across the cleaned text and collects each window into a set. Two small details matter later: text shorter than the window becomes a single shingle so it can still be compared, and clean=False skips the cleanup, which Step 9 uses to show what goes wrong without it. jaccard computes the shared count first and derives the union size from it (|A| + |B| - shared), which avoids building a second set.

Now try it on three sentences. A and B differ by one word; C is unrelated.

# step1_shingles_jaccard.py
from textutil import jaccard, shingles

doc_a = "The quick brown fox jumps over the lazy dog."
doc_b = "The quick brown fox leaps over the lazy dog."
doc_c = "Quarterly revenue grew while operating costs stayed flat."

a, b, c = (shingles(doc) for doc in (doc_a, doc_b, doc_c))

print("A:", sorted(a))
print("B:", sorted(b))
print("shared by A and B:", sorted(a & b))
print(f"J(A, B) = {len(a & b)} / {len(a | b)} = {jaccard(a, b):.3f}")
print(f"J(A, C) = {jaccard(a, c):.3f}")
print(f"J(A, A) = {jaccard(a, a):.3f}")
one_word = jaccard(shingles(doc_a, size=1), shingles(doc_b, size=1))
print(f"with one-word shingles instead, J(A, B) = {one_word:.3f}")

Run it with python step1_shingles_jaccard.py. You should see:

A: ['brown fox jumps', 'fox jumps over', 'jumps over the', 'over the lazy', 'quick brown fox', 'the lazy dog', 'the quick brown']
B: ['brown fox leaps', 'fox leaps over', 'leaps over the', 'over the lazy', 'quick brown fox', 'the lazy dog', 'the quick brown']
shared by A and B: ['over the lazy', 'quick brown fox', 'the lazy dog', 'the quick brown']
J(A, B) = 4 / 10 = 0.400
J(A, C) = 0.000
J(A, A) = 1.000
with one-word shingles instead, J(A, B) = 0.778

Read the output the way the program computed it. Each sentence has nine words, so seven 3-word shingles. A and B share four of them (“the quick brown,” “quick brown fox,” “over the lazy,” “the lazy dog”) and each has three of its own, so the union is ten and J(A, B) = 4 / 10 = 0.400. One changed word out of nine dragged the similarity from 1.0 down to 0.4, because a single word sits inside up to three shingles. With one-word shingles (a plain bag of words) the same pair scores 0.778. Shingle size is a dial, and Step 9 shows what it does on longer documents.

Step 2: Build a Test Corpus and a Brute-Force Baseline

To trust a near-duplicate detector you need to know the right answer, so you will generate a corpus where it is known. This also makes every number in this tutorial reproducible on your machine.

# corpus.py
import random
from itertools import accumulate

SYLLABLES = ["ka", "to", "ri", "me", "su", "na", "lo", "ve", "di", "pa",
             "zo", "hu", "be", "fi", "gar", "len", "mor", "tis", "wen", "dal"]
HEADER = "Skip to main content. Accept all cookies. Sign in or create an account to keep reading."
FOOTER = "Related articles. Subscribe to our newsletter. Privacy policy. Terms of use. All rights reserved."
EDITS = ("light", "heavy", "drop", "boilerplate", "reformat")


def make_vocab(size=3000, seed=7):
    """A made-up vocabulary, so every reader gets exactly the same text."""
    rng = random.Random(seed)
    words = set()
    while len(words) < size:
        words.add("".join(rng.choice(SYLLABLES) for _ in range(rng.choice((1, 2, 2, 3)))))
    vocab = sorted(words)
    rng.shuffle(vocab)
    return vocab


def zipf_weights(size):
    """Cumulative Zipf weights: word number n is used 1/n as often as word number 1."""
    return list(accumulate(1 / (rank + 1) for rank in range(size)))


def make_document(rng, vocab, cum, sentences=14):
    parts = []
    for _ in range(sentences):
        words = rng.choices(vocab, cum_weights=cum, k=rng.randint(9, 16))
        parts.append(" ".join(words).capitalize() + ".")
    return " ".join(parts)


def replace_words(rng, text, vocab, cum, rate):
    words = text.split()
    for i in range(len(words)):
        if rng.random() < rate:
            words[i] = rng.choices(vocab, cum_weights=cum)[0]
    return " ".join(words)


def drop_sentences(text, count=2):
    sentences = text.split(". ")
    return ". ".join(sentences[:-count]) + "."


def reformat(text):
    return "  ".join(text.upper().split(" "))


def apply_edit(rng, text, vocab, cum, kind):
    if kind == "light":
        return replace_words(rng, text, vocab, cum, 0.03)
    if kind == "heavy":
        return replace_words(rng, text, vocab, cum, 0.12)
    if kind == "drop":
        return drop_sentences(text)
    if kind == "boilerplate":
        return f"{HEADER} {text} {FOOTER}"
    return reformat(text)


def build_corpus(n_base=650, seed=42):
    """Return (documents, family) where family[i] is the original article behind document i."""
    rng = random.Random(seed)
    vocab = make_vocab()
    cum = zipf_weights(len(vocab))
    docs, family = [], []
    for article_id in range(n_base):
        base = make_document(rng, vocab, cum)
        docs.append(base)
        family.append(article_id)
        for _ in range(rng.choices((0, 1, 2, 3), weights=(50, 25, 15, 10))[0]):
            text = base
            for kind in rng.sample(EDITS, rng.choice((1, 2))):
                text = apply_edit(rng, text, vocab, cum, kind)
            docs.append(text)
            family.append(article_id)
    order = list(range(len(docs)))
    rng.shuffle(order)
    return [docs[i] for i in order], [family[i] for i in order]

You do not need to study every line, but here is the plan. make_vocab invents 3,000 made-up words from syllables, and zipf_weights makes some of them far more common than others, the way real language works. make_document writes a 14-sentence article of roughly 175 words. build_corpus creates 650 original articles, then gives each one zero, one, two or three “scraped copies” (half of the articles get none). Each copy is made with one or two edits chosen from: replace 3 percent of the words (light), replace 12 percent (heavy), drop the last two sentences (drop), wrap the text in a cookie-banner header and footer (boilerplate), or change the case and spacing (reformat). It records which original each document came from in family and shuffles the order so duplicates are not neighbors.

Next, a three-line helper that prints long durations in readable units, and the brute-force baseline. “Duplicate” needs a definition, so we pick one: two documents are duplicates if the exact Jaccard similarity of their normalized 3-word shingles is at least 0.7.

# timefmt.py
def human(seconds):
    """Turn a number of seconds into the largest sensible unit."""
    for unit, size in (("days", 86400), ("hours", 3600), ("minutes", 60)):
        if seconds >= size:
            return f"{seconds / size:,.1f} {unit}"
    return f"{seconds:.1f} seconds"

# step2_bruteforce.py
import json
import time

from corpus import build_corpus
from textutil import jaccard, shingles
from timefmt import human

THRESHOLD = 0.7

docs, family = build_corpus()
sets = [shingles(doc) for doc in docs]
print(f"documents: {len(docs)} (made from {len(set(family))} original articles)")
print(f"average shingles per document: {sum(map(len, sets)) / len(sets):.0f}")
print("first document:", docs[0][:150] + "...")

start = time.perf_counter()
truth = []
for i in range(len(sets)):
    for j in range(i + 1, len(sets)):
        if jaccard(sets[i], sets[j]) >= THRESHOLD:
            truth.append([i, j])
seconds = time.perf_counter() - start

pairs = len(sets) * (len(sets) - 1) // 2
per_pair = seconds / pairs
print(f"compared {pairs:,} pairs in {seconds:.1f} s ({per_pair * 1e6:.1f} microseconds per pair)")
print(f"pairs with Jaccard >= {THRESHOLD}: {len(truth)}")
for n in (10_000, 100_000, 1_000_000):
    print(f"projected all-pairs time for {n:>9,} documents: {human(n * (n - 1) / 2 * per_pair)}")

with open("truth.json", "w") as handle:
    json.dump({"threshold": THRESHOLD, "seconds": seconds, "pairs": truth}, handle)
print("saved the exact answer to truth.json")

Run python step2_bruteforce.py:

documents: 1209 (made from 650 original articles)
average shingles per document: 173
first document: Wenbeka fipadal lokadi fipadal fipadal paveka begardal ritove todilen wenwenna pavewen hupawen kazohu kahuwen pakapa. Nanalo bena ripatis fipadal paka...
compared 730,236 pairs in 1.9 s (2.6 microseconds per pair)
pairs with Jaccard >= 0.7: 502
projected all-pairs time for    10,000 documents: 2.1 minutes
projected all-pairs time for   100,000 documents: 3.6 hours
projected all-pairs time for 1,000,000 documents: 14.9 days
saved the exact answer to truth.json

The corpus has 1,209 documents averaging 173 shingles. Comparing all 730,236 pairs took under two seconds, and 502 pairs reached 0.7. That is your ground truth, saved to truth.json, and every later step is scored against it. The last three lines are the reason this tutorial exists. The cost is quadratic in the number of documents, so the same comparison for a million documents would take about two weeks at this speed. Also note that 2.6 microseconds per pair is flattering: Python’s set intersection runs in C and these documents are short, while real web pages have thousands of shingles each.

Step 3: Compress Each Document Into a MinHash Signature

Here is the trick behind MinHash. Imagine shuffling all possible shingles into a random order, then finding which shingle of a document comes first. For two documents A and B, look at the union of their shingles and ask which one comes first in the shuffled order. If that shingle is in both documents, A and B have the same first shingle; if it belongs to only one, they differ. The chance that the first shingle of the union lies in the intersection is exactly |A ∩ B| / |A ∪ B|, which is the Jaccard similarity. So “do the two first shingles match?” is a coin flip that lands heads with probability J.

One coin flip is useless, but many are not. A hash function applied to every shingle imitates a random shuffle: the shingle with the smallest hash value plays the role of the first one. Use 128 different hash functions, keep the minimum value from each, and you have a 128-number signature. The fraction of positions where two signatures agree estimates J.

One more helper first. The next script builds pairs of sets whose similarity you control exactly, so you can measure the estimator without noise from real text.

# fixtures.py
def make_pair(size, target):
    """Two sets of `size` strings whose Jaccard similarity is as close to `target` as the sizes allow."""
    shared = round(2 * size * target / (1 + target))
    common = {f"shared-{i}" for i in range(shared)}
    only_a = {f"a-{i}" for i in range(size - shared)}
    only_b = {f"b-{i}" for i in range(size - shared)}
    return common | only_a, common | only_b

Now the MinHash module itself.

# minhash.py
import hashlib
import random

PRIME = (1 << 61) - 1  # 2**61 - 1, a Mersenne prime


def stable_hash(token):
    """64-bit hash of a string; identical in every process and on every machine."""
    digest = hashlib.blake2b(token.encode("utf-8"), digest_size=8).digest()
    return int.from_bytes(digest, "big")


class MinHasher:
    """Turns a set of strings into a fixed-length MinHash signature."""

    def __init__(self, num_perm=128, seed=1):
        rng = random.Random(seed)
        self.num_perm = num_perm
        self.params = [(rng.randrange(1, PRIME), rng.randrange(0, PRIME))
                       for _ in range(num_perm)]

    def signature(self, items):
        hashes = [stable_hash(item) for item in items]
        if not hashes:
            return [PRIME] * self.num_perm
        return [min((a * h + b) % PRIME for h in hashes) for a, b in self.params]


def estimate_jaccard(sig_a, sig_b):
    """Fraction of signature positions where the two signatures agree."""
    if len(sig_a) != len(sig_b):
        raise ValueError("signatures must come from the same MinHasher")
    return sum(x == y for x, y in zip(sig_a, sig_b)) / len(sig_a)


def merge(sig_a, sig_b):
    """Signature of the union of the two original sets."""
    return [min(x, y) for x, y in zip(sig_a, sig_b)]

Three things deserve explanation. stable_hash turns each shingle into a 64-bit number using BLAKE2b from the standard library’s hashlib; Step 4 explains why this is not simply Python’s built-in hash(). MinHasher creates the 128 “shuffles” as random affine maps, (a * h + b) % PRIME, where a and b come from a seeded random generator and PRIME is the Mersenne prime 2**61 - 1. It is a cheap way to get many different hash functions out of one base hash (the maps are not perfect random shuffles, but they are good enough for this job, and datasketch also uses random maps of the form a * h + b). signature applies every map to every shingle and keeps the minimum for each. estimate_jaccard is the fraction of agreeing positions, and merge shows a handy property: the signature of a union is the element-wise minimum of the two signatures, so you can build signatures for sharded data and combine them later.

Now see the estimator in action. The script has three parts: a tiny example, signatures for real documents, and a measurement of how the error shrinks as the signature grows.

# step3_minhash_accuracy.py
import math

from corpus import build_corpus
from fixtures import make_pair
from minhash import MinHasher, estimate_jaccard
from textutil import jaccard, shingles

print("=== The one idea: a tiny example")
small_a = {"a", "b", "c", "d"}
small_b = {"c", "d", "e", "f"}
big = MinHasher(num_perm=2000, seed=1)
print(f"exact J = {jaccard(small_a, small_b):.3f}")
print(f"estimate from 2000 hash functions = "
      f"{estimate_jaccard(big.signature(small_a), big.signature(small_b)):.3f}")

=== The one idea: a tiny example
exact J = 0.333
estimate from 2000 hash functions = 0.316

The sets {a, b, c, d} and {c, d, e, f} share two of six items, so J = 0.333. With 2,000 hash functions the estimate is 0.316: close but not exact, because the estimate is itself random. Now real documents.

# step3_minhash_accuracy.py (continued)
print("=== Signatures for real documents")
docs, family = build_corpus()
sets = [shingles(doc) for doc in docs]
hasher = MinHasher(num_perm=128, seed=1)
signature = hasher.signature(sets[0])
print(f"document 0 has {len(sets[0])} shingles and a signature of {len(signature)} integers")
print("first four values:", signature[:4])

members = {}
for index, article_id in enumerate(family):
    members.setdefault(article_id, []).append(index)
related = [(m[0], m[1]) for m in members.values() if len(m) > 1]
scored = sorted((jaccard(sets[i], sets[j]), i, j) for i, j in related)
picks = [scored[round(q * (len(scored) - 1))] for q in (0, 0.25, 0.5, 0.75, 1)]
stranger = next(i for i in range(1, len(docs)) if family[i] != family[0])
picks.append((jaccard(sets[0], sets[stranger]), 0, stranger))

print(f"{'documents':>12} {'exact J':>8} {'seed 1':>8} {'seed 2':>8} {'seed 3':>8}   (three different sets of 128 hash functions)")
hashers = [MinHasher(num_perm=128, seed=s) for s in (1, 2, 3)]
for exact, i, j in picks:
    estimates = [estimate_jaccard(h.signature(sets[i]), h.signature(sets[j])) for h in hashers]
    print(f"{i:>5},{j:<6} {exact:>8.3f} " + " ".join(f"{e:>8.3f}" for e in estimates))

=== Signatures for real documents
document 0 has 181 shingles and a signature of 128 integers
first four values: [21262609004303714, 3157003786393184, 4441900359085641, 4204092650252016]
   documents  exact J   seed 1   seed 2   seed 3   (three different sets of 128 hash functions)
  641,696       0.199    0.188    0.203    0.219
  323,405       0.550    0.609    0.508    0.500
  498,933       0.815    0.867    0.844    0.812
  106,271       0.861    0.922    0.828    0.883
 1193,1194      1.000    1.000    1.000    1.000
    0,1         0.000    0.000    0.000    0.000

Document 0 has 181 shingles, and its signature is just 128 integers. The table compares the exact Jaccard similarity with estimates from three different sets of 128 hash functions (seeds 1, 2 and 3). Each estimate wobbles around the truth by a few hundredths: for the pair with J = 0.550 the estimates are 0.609, 0.508 and 0.500. Identical documents (1193 and 1194) always give 1.000 and unrelated ones (0 and 1) give 0.000. How much wobble should you expect? The estimate is an average of k coin flips with success probability J, so its standard deviation is sqrt(J * (1 - J) / k). The third part of the script measures that.

# step3_minhash_accuracy.py (continued)
print("=== How the error shrinks as the signature grows")
SIZE, TRIALS, KS = 200, 100, (16, 64, 128, 256)
print(f"{'exact J':>8}  " + "  ".join(f"{'k=' + str(k):>14}" for k in KS) + "   (measured RMS error, theory in brackets)")
for target in (0.2, 0.5, 0.8):
    a, b = make_pair(SIZE, target)
    exact = jaccard(a, b)
    errors = {k: [] for k in KS}
    for trial in range(TRIALS):
        trial_hasher = MinHasher(num_perm=max(KS), seed=1000 + trial)
        sig_a, sig_b = trial_hasher.signature(a), trial_hasher.signature(b)
        for k in KS:
            errors[k].append(estimate_jaccard(sig_a[:k], sig_b[:k]) - exact)
    cells = []
    for k in KS:
        rms = math.sqrt(sum(e * e for e in errors[k]) / TRIALS)
        theory = math.sqrt(exact * (1 - exact) / k)
        cells.append(f"{rms:.3f} ({theory:.3f})")
    print(f"{exact:>8.3f}  " + "  ".join(f"{cell:>14}" for cell in cells))

=== How the error shrinks as the signature grows
 exact J            k=16            k=64           k=128           k=256   (measured RMS error, theory in brackets)
   0.201   0.106 (0.100)   0.049 (0.050)   0.035 (0.035)   0.026 (0.025)
   0.498   0.120 (0.125)   0.057 (0.062)   0.042 (0.044)   0.031 (0.031)
   0.802   0.107 (0.100)   0.049 (0.050)   0.033 (0.035)   0.024 (0.025)

Each cell shows the root-mean-square error of 100 independent runs, with the theoretical value in brackets. They agree closely. At J = 0.5 and 128 hash functions the typical error is about 0.04, and every fourfold increase in signature length only halves it (from 16 to 64 hash functions the error falls from 0.120 to 0.057). Wikipedia’s MinHash article gives the same trade-off as a rule of thumb, noting that “400 hashes would be required to estimate” a Jaccard similarity with an expected error of at most 0.05. That is a safe upper bound; the table shows that 128 hashes already land at about 0.04 in the worst case, and you rarely need more than that to separate “duplicate” from “not a duplicate.”

Step 4: Make the Hashes Reproducible (the hash() Trap)

You may be wondering why stable_hash bothers with BLAKE2b when Python already has hash(). This step shows what happens if you use it. The first script is a tiny child program that computes a signature in a fresh process, using either Python’s built-in hash() or stable_hash.

# child_signature.py
import json
import sys

from minhash import PRIME, MinHasher
from textutil import shingles

mode = sys.argv[1]
text = "the quick brown fox jumps over the lazy dog and keeps running through the quiet forest at dawn"
items = shingles(text)
hasher = MinHasher(num_perm=8, seed=1)

if mode == "builtin":
    hashes = [hash(item) & 0xFFFFFFFFFFFFFFFF for item in items]  # Python's built-in hash()
    signature = [min((a * h + b) % PRIME for h in hashes) for a, b in hasher.params]
else:
    signature = hasher.signature(items)  # blake2b-based stable_hash()
print(json.dumps(signature))

The second script runs the child twice for each mode, with two different values of the PYTHONHASHSEED environment variable, and compares the signatures of the same document.

# step4_hash_pitfall.py
import json
import os
import subprocess
import sys


def signature(mode, hashseed):
    env = dict(os.environ, PYTHONHASHSEED=str(hashseed))
    result = subprocess.run([sys.executable, "child_signature.py", mode],
                            capture_output=True, text=True, env=env, check=True)
    return json.loads(result.stdout)


for mode in ("builtin", "stable"):
    first, second = signature(mode, 1), signature(mode, 2)
    agree = sum(x == y for x, y in zip(first, second))
    print(f"{mode:>8}: process 1 starts {first[:2]}")
    print(f"{'':>8}  process 2 starts {second[:2]}")
    print(f"{'':>8}  the same document, positions that agree: {agree} of {len(first)}"
          f" -> estimated similarity {agree / len(first):.3f}")

Run python step4_hash_pitfall.py:

 builtin: process 1 starts [135953258627529172, 46041442810172695]
          process 2 starts [11001994244956579, 660605051290590525]
          the same document, positions that agree: 0 of 8 -> estimated similarity 0.000
  stable: process 1 starts [46089119792672254, 26578909448904163]
          process 2 starts [46089119792672254, 26578909448904163]
          the same document, positions that agree: 8 of 8 -> estimated similarity 1.000

With the built-in hash(), the same document produced completely different signatures in two processes: zero of eight positions agree, so the estimated similarity of a document with itself is 0.000. With stable_hash all eight agree. Nothing crashes in the first case; you just get silent garbage the moment signatures computed in different runs, or on different machines, meet each other. The Python documentation explains why: for str and bytes objects the hash values are salted, and “although they remain constant within an individual Python process, they are not predictable between repeated invocations of Python.” You can freeze the salt with the PYTHONHASHSEED variable, which “allows you to set a fixed value for the hash seed secret,” but that relies on every worker being launched with the right environment. A hash that is stable by construction is safer.

Step 5: Group Signatures Into Bands and Meet the S-Curve

You now have 128 numbers per document and a fast way to estimate similarity, but comparing all pairs of signatures is still quadratic. LSH fixes that with banding. Cut a signature of b × r numbers into b bands of r rows each. Each band gets its own hash table. Two documents become a candidate pair if their signatures are identical on all r rows of at least one band.

signature of 100 numbers        one hash table per band
------------------------        -----------------------
numbers   1 to   5   (band 1)   -> table 1: key = those 5 numbers
numbers   6 to  10   (band 2)   -> table 2: key = those 5 numbers
...
numbers  96 to 100   (band 20)  -> table 20: key = those 5 numbers

candidate pair = two documents that share a key in ANY table

Why does this favor similar documents? Suppose two documents have Jaccard similarity s. Each signature position agrees with probability s. All r rows of one band agree with probability s**r. A band fails to match with probability 1 - s**r, all b bands fail with probability (1 - s**r)**b, so the pair becomes a candidate with probability 1 - (1 - s**r)**b. Plotted against s, this is an S-shaped curve: low for dissimilar pairs, high for similar ones, with a steep climb in between. The textbook Mining of Massive Datasets, chapter 3 derives the same formula and notes that “the threshold, that is, the value of similarity s at which the probability of becoming a candidate is 1/2, is a function of b and r.” A handy approximation for that midpoint is (1/b)^1/r.

# lsh.py
from collections import defaultdict
from itertools import combinations


def s_curve(similarity, bands, rows):
    """Probability that two sets with this Jaccard similarity become a candidate pair."""
    return 1 - (1 - similarity ** rows) ** bands


def approx_threshold(bands, rows):
    """Similarity at which the S-curve is roughly halfway up."""
    return (1 / bands) ** (1 / rows)


def split_bands(signature, bands, rows):
    if bands * rows > len(signature):
        raise ValueError(f"{bands} bands x {rows} rows needs {bands * rows} values, "
                         f"but the signature has {len(signature)}")
    return [tuple(signature[i * rows:(i + 1) * rows]) for i in range(bands)]


def is_candidate(sig_a, sig_b, bands, rows):
    """True if the two signatures agree on every row of at least one band."""
    return any(x == y for x, y in zip(split_bands(sig_a, bands, rows),
                                      split_bands(sig_b, bands, rows)))


def candidate_pairs(signatures, bands, rows):
    """signatures maps doc id -> signature. Returns {(id_a, id_b)} with id_a < id_b."""
    tables = [defaultdict(list) for _ in range(bands)]  # one table per band
    for doc_id, signature in signatures.items():
        for table, key in zip(tables, split_bands(signature, bands, rows)):
            table[key].append(doc_id)
    pairs = set()
    for table in tables:
        for bucket in table.values():
            if len(bucket) > 1:
                pairs.update(combinations(sorted(bucket), 2))
    return pairs

s_curve and approx_threshold are the two formulas. split_bands slices a signature into tuples and refuses to run if b × r is larger than the signature (if it is smaller, the leftover numbers are silently unused, so keep b × r equal to or just under the signature length). candidate_pairs builds one dictionary per band, drops every document into the bucket named by its band tuple, and turns each bucket with more than one document into pairs. Using a separate table per band matters: if you shared one table, a band-1 key that happened to equal a band-2 key would create a false match, a bug that Step 11 pins down with a test.

The book works through one example with 20 bands of 5 rows (a 100-number signature) and prints a table of the S-curve. The next script checks our formula against that table, then measures the real thing: for each target similarity it draws 300 different sets of hash functions and counts how often the pair becomes a candidate.

# step5_scurve.py
from fixtures import make_pair
from lsh import approx_threshold, is_candidate, s_curve
from minhash import MinHasher
from textutil import jaccard

BANDS, ROWS, TRIALS, SIZE = 20, 5, 300, 60
BOOK = {0.2: 0.006, 0.3: 0.047, 0.4: 0.186, 0.5: 0.470, 0.6: 0.802, 0.7: 0.975, 0.8: 0.9996}

print(f"{BANDS} bands x {ROWS} rows = {BANDS * ROWS} hash values; "
      f"approximate threshold (1/b)^(1/r) = {approx_threshold(BANDS, ROWS):.3f}")
print("=== The formula against the table in Mining of Massive Datasets (figure 3.9)")
for s, printed in BOOK.items():
    print(f"  s = {s:.1f}   1 - (1 - s^{ROWS})^{BANDS} = {s_curve(s, BANDS, ROWS):.4f}   book: {printed}")

20 bands x 5 rows = 100 hash values; approximate threshold (1/b)^(1/r) = 0.549
=== The formula against the table in Mining of Massive Datasets (figure 3.9)
  s = 0.2   1 - (1 - s^5)^20 = 0.0064   book: 0.006
  s = 0.3   1 - (1 - s^5)^20 = 0.0475   book: 0.047
  s = 0.4   1 - (1 - s^5)^20 = 0.1860   book: 0.186
  s = 0.5   1 - (1 - s^5)^20 = 0.4701   book: 0.47
  s = 0.6   1 - (1 - s^5)^20 = 0.8019   book: 0.802
  s = 0.7   1 - (1 - s^5)^20 = 0.9748   book: 0.975
  s = 0.8   1 - (1 - s^5)^20 = 0.9996   book: 0.9996

The formula reproduces every row of the book’s table to the digits printed there (the book’s .047 for s = 0.3 is the formula’s 0.0475 truncated). The midpoint, about 0.549, is just above 0.5, exactly as the book describes. Now the measured version.

# step5_scurve.py (continued)
print(f"=== Measured: {TRIALS} independent hash seeds for each similarity")
for target in (0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9):
    a, b = make_pair(SIZE, target)
    exact = jaccard(a, b)
    hits = 0
    for seed in range(TRIALS):
        hasher = MinHasher(num_perm=BANDS * ROWS, seed=seed)
        hits += is_candidate(hasher.signature(a), hasher.signature(b), BANDS, ROWS)
    print(f"  J = {exact:.3f}   measured {hits / TRIALS:.3f}   formula {s_curve(exact, BANDS, ROWS):.3f}")

=== Measured: 300 independent hash seeds for each similarity
  J = 0.200   measured 0.000   formula 0.006
  J = 0.304   measured 0.043   formula 0.051
  J = 0.395   measured 0.137   formula 0.176
  J = 0.500   measured 0.437   formula 0.470
  J = 0.600   measured 0.807   formula 0.802
  J = 0.690   measured 0.963   formula 0.967
  J = 0.791   measured 1.000   formula 0.999
  J = 0.905   measured 1.000   formula 1.000

The measured rates follow the formula. With only 300 trials per row, a measured rate can sit a few hundredths away from the curve by chance, which is what you see at J = 0.395 (0.137 against 0.176). The shape is the point: pairs near 0.2 almost never collide, pairs near 0.6 collide about 80 percent of the time, and pairs at 0.69 and above are caught more than 96 percent of the time. The book makes the same observation: “Only roughly one in 3000 pairs that are as high as 80% similar will fail to become a candidate pair and thus be a false negative.” Our row for J = 0.791 caught all 300.

Step 6: Choose Bands and Rows for Your Threshold

The pair (20, 5) suited that example, but your threshold will differ. You choose b and r so that the S-curve climbs near the similarity you care about, and you have to decide which mistake costs more. A false positive is a candidate pair that is not really similar; a false negative is a truly similar pair that never collides. Book and library agree on the framing: those dissimilar pairs that land in one bucket “are false positives; we hope these will be only a small fraction of all pairs.” The datasketch documentation states the same trade-off for its index, and notes that LSH “can be used with MinHash to achieve sub-linear query cost.”

A principled way to pick is to measure the area under the S-curve below the threshold (false-positive mass) and the area above it that the curve fails to reach (false-negative mass), weight the two, and try every (b, r) with b × r no larger than the signature length. That is what datasketch does internally with SciPy. Here is a plain-Python version using the trapezoid rule:

# tuning.py
from lsh import s_curve


def _area(f, low, high, steps=400):
    """Trapezoid-rule area under f between low and high."""
    width = (high - low) / steps
    inner = sum(f(low + i * width) for i in range(1, steps))
    return (0.5 * (f(low) + f(high)) + inner) * width


def optimal_params(threshold, num_perm, fp_weight=0.5, fn_weight=0.5):
    """Pick (bands, rows) with bands * rows <= num_perm that minimise the weighted area of
    false positives (the S-curve below the threshold) and false negatives (above it)."""
    best, best_error = (1, 1), float("inf")
    for bands in range(1, num_perm + 1):
        for rows in range(1, num_perm // bands + 1):
            false_pos = _area(lambda s: s_curve(s, bands, rows), 0.0, threshold)
            false_neg = _area(lambda s: 1 - s_curve(s, bands, rows), threshold, 1.0)
            error = fp_weight * false_pos + fn_weight * false_neg
            if error < best_error:
                best, best_error = (bands, rows), error
    return best

The next script compares our choices with the ones datasketch makes for the same threshold and weights, and prints how likely a pair is to become a candidate at the threshold minus 0.1, at the threshold, and at the threshold plus 0.1.

# step6_choose_params.py
import time

from datasketch import MinHashLSH

from lsh import approx_threshold, s_curve
from tuning import optimal_params

NUM_PERM = 128
print(f"{'threshold':>9} {'weights':>10} {'mine':>9} {'datasketch':>11} {'midpoint':>9}"
      f"   P(candidate) at t-0.1, t, t+0.1")
for threshold, weights in ((0.5, (0.5, 0.5)), (0.7, (0.5, 0.5)), (0.9, (0.5, 0.5)), (0.7, (0.2, 0.8))):
    start = time.perf_counter()
    bands, rows = optimal_params(threshold, NUM_PERM, *weights)
    seconds = time.perf_counter() - start
    index = MinHashLSH(threshold=threshold, num_perm=NUM_PERM, weights=weights)
    curve = " ".join(f"{s_curve(threshold + d, bands, rows):.3f}" for d in (-0.1, 0.0, 0.1))
    print(f"{threshold:>9.1f} {str(weights):>10} {str((bands, rows)):>9} "
          f"{str((index.b, index.r)):>11} {approx_threshold(bands, rows):>9.3f}   {curve}   ({seconds:.2f} s)")

threshold    weights      mine  datasketch  midpoint   P(candidate) at t-0.1, t, t+0.1
      0.5 (0.5, 0.5)   (25, 5)     (25, 5)     0.525   0.227 0.548 0.868   (0.07 s)
      0.7 (0.5, 0.5)   (14, 9)     (14, 9)     0.746   0.132 0.438 0.867   (0.07 s)
      0.9 (0.5, 0.5)   (5, 25)     (5, 25)     0.938   0.019 0.311 1.000   (0.07 s)
      0.7 (0.2, 0.8)   (18, 7)     (18, 7)     0.662   0.400 0.787 0.986   (0.07 s)

Two results stand out. First, our function picks exactly the same (bands, rows) as datasketch in all four cases, using 400 trapezoid steps instead of SciPy’s integrator. Second, look at the row for threshold 0.7 with equal weights: the best (b, r) is (14, 9), whose midpoint is 0.746, and the chance that a pair exactly at 0.7 becomes a candidate is only 0.438. Equal weights balance two areas; they do not promise to catch every pair at the threshold. If missing a duplicate hurts more than checking an extra pair, shift the weights toward false negatives. With (0.2, 0.8) the choice becomes (18, 7), the midpoint drops to 0.662, and a pair at 0.7 is caught 0.787 of the time. The next step shows what that does to real recall.

Step 7: Run the Whole Pipeline and Measure What You Lose

Time to put the pieces together: signatures, banding, exact verification of candidates, and grouping. The grouping needs one more small structure, a union-find (also called disjoint-set) that merges documents connected by duplicate pairs into clusters. It is short:

# clusters.py
class UnionFind:
    """Groups documents that are connected by at least one duplicate pair."""

    def __init__(self, size):
        self.parent = list(range(size))

    def find(self, item):
        while self.parent[item] != item:
            self.parent[item] = self.parent[self.parent[item]]  # path halving
            item = self.parent[item]
        return item

    def union(self, a, b):
        root_a, root_b = self.find(a), self.find(b)
        if root_a != root_b:
            self.parent[max(root_a, root_b)] = min(root_a, root_b)  # smallest id stays the root

find follows parent links to a cluster’s representative (shortening the path as it goes), and union joins two clusters, keeping the smallest document id as the representative so the “keep the first one” policy is deterministic. Now the pipeline, in three parts. The first builds signatures and compares the two weightings from Step 6 against the ground truth.

# step7_pipeline.py
import json
import time

from clusters import UnionFind
from corpus import build_corpus
from lsh import approx_threshold, candidate_pairs
from minhash import MinHasher
from textutil import jaccard, shingles
from tuning import optimal_params

THRESHOLD, NUM_PERM = 0.7, 128

docs, family = build_corpus()
sets = [shingles(doc) for doc in docs]
saved = json.load(open("truth.json"))
truth = {tuple(pair) for pair in saved["pairs"]}

start = time.perf_counter()
hasher = MinHasher(NUM_PERM, seed=1)
signatures = {i: hasher.signature(s) for i, s in enumerate(sets)}
print(f"signatures for {len(docs)} documents: {time.perf_counter() - start:.1f} s")
all_pairs = len(docs) * (len(docs) - 1) // 2

print("=== Two ways to weigh the mistakes (false positives, false negatives)")
print(f"{'weights':>11} {'b x r':>7} {'midpoint':>9} {'candidates':>11} {'recall':>7} {'precision':>10}")
runs = {}
for weights in ((0.5, 0.5), (0.2, 0.8)):
    bands, rows = optimal_params(THRESHOLD, NUM_PERM, *weights)
    candidates = candidate_pairs(signatures, bands, rows)
    found = candidates & truth
    runs[weights] = candidates
    print(f"{str(weights):>11} {bands:>3}x{rows:<3} {approx_threshold(bands, rows):>9.3f} {len(candidates):>11,} "
          f"{len(found) / len(truth):>7.3f} {len(found) / len(candidates):>10.3f}")
print(f"(exact all-pairs would have compared {all_pairs:,} pairs)")

signatures for 1209 documents: 2.9 s
=== Two ways to weigh the mistakes (false positives, false negatives)
    weights   b x r  midpoint  candidates  recall  precision
 (0.5, 0.5)  14x9       0.746         500   0.928      0.932
 (0.2, 0.8)  18x7       0.662         573   0.988      0.866
(exact all-pairs would have compared 730,236 pairs)

Both settings generate a few hundred candidate pairs out of 730,236 possible, a reduction of more than a thousand times. Equal weights give recall 0.928, so about 7 percent of the true duplicates are missed, which is what Step 6 predicted for pairs sitting just above 0.7. Weighting false negatives more raises recall to 0.988 at the price of more candidates (573 instead of 500) and lower candidate precision (0.866). Because the next stage is an exact check, extra candidates are cheap. Verification looks only at the few hundred surviving pairs.

# step7_pipeline.py (continued)
print("=== Exact check on the candidates from the (0.2, 0.8) setting")
candidates = runs[(0.2, 0.8)]
verified = {p for p in candidates if jaccard(sets[p[0]], sets[p[1]]) >= THRESHOLD}
print(f"{len(candidates)} candidates -> {len(verified)} verified pairs, "
      f"precision {len(verified & truth) / len(verified):.3f}, recall {len(verified & truth) / len(truth):.3f}")
extra = sorted(jaccard(sets[i], sets[j]) for i, j in candidates - truth)
print(f"the {len(extra)} candidates under the threshold have exact J from {extra[0]:.3f} to {extra[-1]:.3f}; "
      f"{sum(s >= 0.5 for s in extra)} of them are at or above 0.5")
missed = sorted(truth - candidates)
scores = [jaccard(sets[i], sets[j]) for i, j in missed]
print(f"missed {len(missed)} of {len(truth)} true pairs; their exact J ranges from {min(scores):.3f} to {max(scores):.3f}")

=== Exact check on the candidates from the (0.2, 0.8) setting
573 candidates -> 496 verified pairs, precision 1.000, recall 0.988
the 77 candidates under the threshold have exact J from 0.377 to 0.698; 65 of them are at or above 0.5
missed 6 of 502 true pairs; their exact J ranges from 0.713 to 0.790

After the exact check, precision is a perfect 1.000: every reported pair really has Jaccard 0.7 or more, and the 77 candidates that were thrown out all sat between 0.377 and 0.698, with 65 of them at 0.5 or higher. They were near-duplicates by a looser definition, which is exactly where the S-curve is still rising. The check cannot add back what banding missed, so recall stays at 0.988. The 6 missed pairs all had exact similarity between 0.713 and 0.790, close to the threshold, which is where a probabilistic filter should make its mistakes. Finally, group the verified pairs and keep one document per cluster.

# step7_pipeline.py (continued)
print("=== Keeping one document per cluster")
groups = UnionFind(len(docs))
for i, j in verified:
    groups.union(i, j)
roots = [groups.find(i) for i in range(len(docs))]
exact_groups = UnionFind(len(docs))
for i, j in truth:
    exact_groups.union(i, j)
print(f"documents: {len(docs)}, kept after dedup: {len(set(roots))}, "
      f"kept by the exact method: {len({exact_groups.find(i) for i in range(len(docs))})}")
wrong = sum(family[i] != family[roots[i]] for i in range(len(docs)))
print(f"documents merged into a different original article: {wrong}")

=== Keeping one document per cluster
documents: 1209, kept after dedup: 819, kept by the exact method: 814
documents merged into a different original article: 0

The LSH pipeline keeps 819 of the 1,209 documents; the exact method would keep 814, so the approximate pipeline left five extra copies behind. Not one document was merged into a cluster belonging to a different original article. That last number is worth checking in your own data. Union-find merges transitively: if A matches B and B matches C, all three end up together even if A and C are below the threshold. With verified edges and a sensible threshold that is usually what you want, but chains can grow in noisy data.

Step 8: Find Out Where MinHash Starts to Pay Off

Here is the uncomfortable part of the story. On this corpus the exact method finished in under two seconds, and the MinHash pipeline needed about three. Does MinHash even help? Measure it. This script builds corpora of increasing size and times both approaches, recording recall as well.

# step8_scaling.py
import time

from corpus import build_corpus
from lsh import candidate_pairs
from minhash import MinHasher
from textutil import jaccard, shingles
from timefmt import human
from tuning import optimal_params

THRESHOLD, NUM_PERM = 0.7, 128
bands, rows = optimal_params(THRESHOLD, NUM_PERM, 0.2, 0.8)
hasher = MinHasher(NUM_PERM, seed=1)

print(f"{'documents':>10} {'all pairs (s)':>14} {'MinHash + LSH (s)':>18} {'speed-up':>9} {'recall':>7}")
for n_base in (150, 325, 650, 1300, 2600):
    docs, _ = build_corpus(n_base=n_base)
    sets = [shingles(doc) for doc in docs]

    start = time.perf_counter()
    exact = {(i, j) for i in range(len(sets)) for j in range(i + 1, len(sets))
             if jaccard(sets[i], sets[j]) >= THRESHOLD}
    all_pairs_seconds = time.perf_counter() - start

    start = time.perf_counter()
    signatures = {i: hasher.signature(s) for i, s in enumerate(sets)}
    found = {p for p in candidate_pairs(signatures, bands, rows) if jaccard(sets[p[0]], sets[p[1]]) >= THRESHOLD}
    lsh_seconds = time.perf_counter() - start

    print(f"{len(docs):>10,} {all_pairs_seconds:>14.1f} {lsh_seconds:>18.1f} "
          f"{all_pairs_seconds / lsh_seconds:>8.2f}x {len(found & exact) / len(exact):>7.3f}")

per_pair = all_pairs_seconds / (len(sets) * (len(sets) - 1) / 2)
per_doc = lsh_seconds / len(sets)
print("=== Projection from the largest run (a straight extrapolation, not a measurement)")
for n in (100_000, 1_000_000):
    print(f"{n:>9,} documents: all pairs {human(n * (n - 1) / 2 * per_pair):>14}, "
          f"MinHash + LSH {human(n * per_doc):>14}")

Run python step8_scaling.py (it takes about a minute and a half, because the largest exact comparison is 11 million pairs):

 documents  all pairs (s)  MinHash + LSH (s)  speed-up  recall
       296            0.1                0.7     0.16x   0.983
       616            0.5                1.5     0.31x   0.992
     1,209            2.4                3.5     0.69x   0.988
     2,356           11.1                7.5     1.47x   0.976
     4,770           48.4               15.1     3.20x   0.979
=== Projection from the largest run (a straight extrapolation, not a measurement)
  100,000 documents: all pairs      5.9 hours, MinHash + LSH    5.3 minutes
1,000,000 documents: all pairs      24.6 days, MinHash + LSH   52.8 minutes

For small corpora the exact method wins easily: at 296 documents it is more than six times faster than MinHash plus LSH, and at 1,209 documents it still wins. Somewhere between 1,209 and 2,356 documents the lines cross. By 4,770 documents MinHash plus LSH is more than three times faster, while recall stays between 0.976 and 0.992 at every size. The reason is the shape of the cost. Building a signature costs a few milliseconds per document in pure Python (128 hash functions over about 180 shingles) and grows linearly with the number of documents. The exact check costs microseconds per pair, but the number of pairs grows with the square of the corpus.

The last two lines are an extrapolation, not a measurement: they assume the per-pair and per-document costs measured at 4,770 documents stay the same and that the number of candidate pairs keeps growing roughly in line with the corpus. Under those assumptions, 100,000 documents would take hours with all pairs and minutes with MinHash plus LSH, and a million documents would take weeks versus under an hour. The practical lesson is the one the crossover teaches: if you have a couple of thousand short documents or fewer, compare them directly. MinHash earns its complexity when the corpus is big, when documents are long, or when you must store a small fixed-size fingerprint per document (128 numbers, whatever the document’s length) instead of keeping every shingle set in memory.

Step 9: Four Pitfalls That Quietly Break Deduplication

None of these mistakes raises an exception. Each one just makes the results wrong. The script below reproduces all four; it is shown in four parts so you can read each experiment next to its output.

Pitfall 1: forgetting to normalize

# step9_pitfalls.py
import random
from collections import Counter
from itertools import combinations

from corpus import make_document, make_vocab, reformat, replace_words, zipf_weights
from textutil import jaccard, normalize, shingles

rng = random.Random(81)
vocab = make_vocab()
cum = zipf_weights(len(vocab))
article = make_document(rng, vocab, cum)

print("=== Pitfall 1: forgetting to normalize")
shouty = reformat(article)
print(f"split on whitespace only : J = {jaccard(shingles(article, clean=False), shingles(shouty, clean=False)):.3f}")
print(f"normalized first         : J = {jaccard(shingles(article), shingles(shouty)):.3f}")

=== Pitfall 1: forgetting to normalize
split on whitespace only : J = 0.000
normalized first         : J = 1.000

The same article reformatted in capitals with doubled spaces scores 0.000 against itself if you shingle the raw text, because “KATO” and “Kato.” are different strings. After normalizing, it scores 1.000. If your corpus mixes formats (HTML text, scraped pages, PDFs), decide on one normalization and apply it to everything, including the query side.

Pitfall 2: choosing the wrong shingle size

# step9_pitfalls.py (continued)
print("=== Pitfall 2: the shingle size")
edited = replace_words(rng, article, vocab, cum, 0.03)
words = article.split()
rng.shuffle(words)
scrambled = " ".join(words)
print(f"{'size':>5} {'3% of words edited':>20} {'same words, scrambled':>22}")
for size in (1, 2, 3, 5, 8):
    light = jaccard(shingles(article, size), shingles(edited, size))
    salad = jaccard(shingles(article, size), shingles(scrambled, size))
    print(f"{size:>5} {light:>20.3f} {salad:>22.3f}")

=== Pitfall 2: the shingle size
 size   3% of words edited  same words, scrambled
    1                0.961                  1.000
    2                0.878                  0.067
    3                0.822                  0.000
    5                0.729                  0.000
    8                0.625                  0.000

The first column shows what happens when 3 percent of the words are replaced: bigger shingles are more sensitive, so similarity falls from 0.961 with one-word shingles to 0.625 with eight-word shingles. The second column shows the opposite danger. A document whose words were randomly shuffled still scores a perfect 1.000 with one-word shingles, since a bag of words cannot see order, and drops to 0.067 with two-word shingles and to 0.000 from three words up. Short shingles forgive edits but cannot tell a document from word salad; long shingles notice order but punish small edits. A size of three to five words is a reasonable place to start. Lee and colleagues, for example, hashed each consecutive 5-gram of space-tokenized text in their MinHash step.

Pitfall 3: boilerplate that makes unrelated pages look identical

# step9_pitfalls.py (continued)
print("=== Pitfall 3: boilerplate shared by unrelated pages")
head = make_document(rng, vocab, cum)
tail = make_document(rng, vocab, cum)
pages = [f"{head} {make_document(rng, vocab, cum, sentences=5)} {tail}" for _ in range(20)]
page_sets = [shingles(page) for page in pages]
scores = [jaccard(a, b) for a, b in combinations(page_sets, 2)]
print(f"20 unrelated pages, {len(scores)} pairs: mean J = {sum(scores) / len(scores):.3f}, "
      f"pairs at or above 0.7: {sum(s >= 0.7 for s in scores)}")
frequency = Counter(sh for s in page_sets for sh in s)
common = {sh for sh, count in frequency.items() if count > len(page_sets) / 2}
trimmed = [s - common for s in page_sets]
scores = [jaccard(a, b) for a, b in combinations(trimmed, 2)]
print(f"after dropping {len(common)} shingles found on more than half of the pages: "
      f"mean J = {sum(scores) / len(scores):.3f}, pairs at or above 0.7: {sum(s >= 0.7 for s in scores)}")

=== Pitfall 3: boilerplate shared by unrelated pages
20 unrelated pages, 190 pairs: mean J = 0.732, pairs at or above 0.7: 190
after dropping 344 shingles found on more than half of the pages: mean J = 0.000, pairs at or above 0.7: 0

These 20 pages have different bodies but share a long header and footer, as templated product pages and forum threads can. Their average similarity is 0.732, and all 190 pairs are flagged as duplicates at 0.7, although no two pages say anything alike. The fix used here is a document-frequency filter: drop every shingle that appears on more than half of the pages. That removes 344 template shingles and the mean similarity falls to 0.000. Extracting the main content before shingling is the other common approach. Pick whichever matches your data, but do not skip the question.

Pitfall 4: an excerpt hidden inside a long article

# step9_pitfalls.py (continued)
print("=== Pitfall 4: a short excerpt of a long article")
long_article = " ".join(make_document(rng, vocab, cum) for _ in range(12))
sentences = long_article.split(". ")
excerpt = ". ".join(sentences[40:52]) + "."
whole, part = shingles(long_article), shingles(excerpt)
print(f"article: {len(whole)} shingles, excerpt: {len(part)} shingles")
print(f"Jaccard = {jaccard(whole, part):.3f}, containment of the excerpt in the article = {len(whole & part) / len(part):.3f}")
tokens = normalize(long_article).split()
chunks = [" ".join(tokens[i:i + 200]) for i in range(0, len(tokens) - 199, 50)]
best = max(jaccard(shingles(chunk), part) for chunk in chunks)
print(f"{len(chunks)} chunks of 200 words, stride 50: best chunk Jaccard = {best:.3f}")

=== Pitfall 4: a short excerpt of a long article
article: 2046 shingles, excerpt: 141 shingles
Jaccard = 0.069, containment of the excerpt in the article = 1.000
38 chunks of 200 words, stride 50: best chunk Jaccard = 0.712

A 141-shingle excerpt copied out of a 2,046-shingle article has a Jaccard similarity of only 0.069 with it, so a 0.7 threshold will never flag it, even though every shingle of the excerpt appears in the article (containment 1.000). Jaccard measures overall overlap, not “is A inside B.” If you need to catch excerpts, which matters a lot for RAG corpora full of overlapping chunks, compare at the chunk level instead. Splitting the article into 200-word chunks that start every 50 words, the best chunk scores 0.712 against the excerpt, which clears the threshold. The cost is more items to index: 38 chunks for one article here.

Step 10: Cross-Check Against datasketch

You should not ship a hand-rolled MinHash if a well-tested library exists, and the library is also the best check on your own code. datasketch provides MinHash and MinHashLSH. This script computes signatures with both implementations for the same shingle sets and compares accuracy, banding choice and recall.

# step10_datasketch_check.py
import json
import time
from itertools import combinations

from datasketch import MinHash, MinHashLSH

from corpus import build_corpus
from lsh import candidate_pairs
from minhash import MinHasher, estimate_jaccard
from textutil import jaccard, shingles
from tuning import optimal_params

THRESHOLD, NUM_PERM = 0.7, 128
docs, family = build_corpus()
sets = [shingles(doc) for doc in docs]
truth = {tuple(pair) for pair in json.load(open("truth.json"))["pairs"]}

start = time.perf_counter()
mine_hasher = MinHasher(NUM_PERM, seed=1)
mine = [mine_hasher.signature(s) for s in sets]
mine_seconds = time.perf_counter() - start

start = time.perf_counter()
theirs = []
for s in sets:
    minhash = MinHash(num_perm=NUM_PERM)
    minhash.update_batch([shingle.encode("utf-8") for shingle in s])
    theirs.append(minhash)
their_seconds = time.perf_counter() - start
print(f"signatures for {len(sets)} documents: mine {mine_seconds:.1f} s, datasketch {their_seconds:.1f} s")

members = {}
for index, article_id in enumerate(family):
    members.setdefault(article_id, []).append(index)
error_mine, error_theirs = [], []
for group in members.values():
    for i, j in combinations(group, 2):
        exact = jaccard(sets[i], sets[j])
        error_mine.append(abs(estimate_jaccard(mine[i], mine[j]) - exact))
        error_theirs.append(abs(theirs[i].jaccard(theirs[j]) - exact))
print(f"mean absolute error over {len(error_mine)} related pairs: "
      f"mine {sum(error_mine) / len(error_mine):.4f}, datasketch {sum(error_theirs) / len(error_theirs):.4f}")

bands, rows = optimal_params(THRESHOLD, NUM_PERM)
index = MinHashLSH(threshold=THRESHOLD, num_perm=NUM_PERM)
for key, minhash in enumerate(theirs):
    index.insert(key, minhash)
their_pairs = set()
for key, minhash in enumerate(theirs):
    for other in index.query(minhash):
        if other != key:
            their_pairs.add((min(key, other), max(key, other)))
my_pairs = candidate_pairs(dict(enumerate(mine)), bands, rows)

print(f"banding: mine {bands}x{rows}, datasketch {index.b}x{index.r}")
for name, pairs in (("mine", my_pairs), ("datasketch", their_pairs)):
    found = pairs & truth
    print(f"{name:>10}: {len(pairs):>4} candidate pairs, recall {len(found) / len(truth):.3f}, "
          f"precision {len(found) / len(pairs):.3f}")
print(f"candidate pairs found by both: {len(my_pairs & their_pairs)}")
only_one = my_pairs ^ their_pairs
below = sum(jaccard(sets[i], sets[j]) < THRESHOLD for i, j in only_one)
print(f"proposed by only one of them: {len(only_one)} pairs, {below} below {THRESHOLD} "
      f"and {len(only_one) - below} true duplicates that the other one missed")

Run python step10_datasketch_check.py:

signatures for 1209 documents: mine 3.0 s, datasketch 0.2 s
mean absolute error over 861 related pairs: mine 0.0293, datasketch 0.0294
banding: mine 14x9, datasketch 14x9
      mine:  500 candidate pairs, recall 0.928, precision 0.932
datasketch:  482 candidate pairs, recall 0.910, precision 0.948
candidate pairs found by both: 442
proposed by only one of them: 98 pairs, 35 below 0.7 and 63 true duplicates that the other one missed

The two implementations are statistically indistinguishable where it counts: a mean absolute error of 0.0293 for ours and 0.0294 for datasketch across 861 related document pairs, and the same banding choice, 14 bands of 9 rows. The sets of candidate pairs overlap heavily (442 pairs found by both) but are not identical, because each implementation draws its own hash functions. The last line measures the disagreement: 98 pairs were proposed by only one of them. Of those, 35 are candidates below 0.7 that the exact check would discard, and 63 are true duplicates that the other implementation missed. Each one misses a somewhat different set of pairs, which is what a probabilistic filter does. Recall is 0.928 for ours and 0.910 for datasketch, and I would not read a two-point gap on one corpus as one library being better than the other. The big difference is speed: datasketch built the 1,209 signatures about fifteen times faster than our pure-Python loop (0.2 seconds against 3.0 here), because it vectorizes the work with NumPy. Use your code to understand the method and the library to run it.

Step 11: Lock the Behavior In With Tests

The pitfalls above are the kind of bug you fix once and reintroduce a year later. Pin them down with a small test suite.

# test_minhash.py
import os
import subprocess
import sys

import pytest

from clusters import UnionFind
from fixtures import make_pair
from lsh import approx_threshold, candidate_pairs, s_curve, split_bands
from minhash import MinHasher, estimate_jaccard, merge
from textutil import jaccard, normalize, shingles
from tuning import optimal_params


def test_normalize_ignores_case_punctuation_and_spacing():
    assert normalize("Hello,   WORLD!!") == "hello world"
    assert shingles("Hello, world again") == shingles("hello   WORLD again.")


def test_short_text_still_gives_a_shingle():
    assert shingles("one two", size=3) == {"one two"}
    assert shingles("") == set()


def test_jaccard_basics():
    assert jaccard({1, 2, 3}, {2, 3, 4}) == 0.5
    assert jaccard(set(), set()) == 1.0
    assert jaccard({1}, {2}) == 0.0


def test_identical_sets_have_identical_signatures():
    hasher = MinHasher(64, seed=4)
    items = {"a b c", "b c d", "c d e"}
    assert hasher.signature(items) == hasher.signature(set(items))
    assert estimate_jaccard(hasher.signature(items), hasher.signature(items)) == 1.0


def test_estimate_is_close_to_exact():
    a, b = make_pair(200, 0.5)
    hasher = MinHasher(256, seed=5)
    estimate = estimate_jaccard(hasher.signature(a), hasher.signature(b))
    assert abs(estimate - jaccard(a, b)) < 0.1


def test_disjoint_sets_estimate_near_zero():
    hasher = MinHasher(128, seed=2)
    assert estimate_jaccard(hasher.signature({"a", "b", "c"}), hasher.signature({"x", "y", "z"})) < 0.05


def test_merge_gives_the_signature_of_the_union():
    a, b = make_pair(50, 0.4)
    hasher = MinHasher(64, seed=3)
    assert merge(hasher.signature(a), hasher.signature(b)) == hasher.signature(a | b)


def test_signature_is_the_same_in_another_process():
    code = "from minhash import MinHasher; print(MinHasher(8, 1).signature({'a b c', 'b c d'}))"
    outputs = []
    for seed in ("1", "2"):
        env = dict(os.environ, PYTHONHASHSEED=seed)
        run = subprocess.run([sys.executable, "-c", code], capture_output=True, text=True, check=True, env=env)
        outputs.append(run.stdout)
    assert outputs[0] == outputs[1]


def test_s_curve_matches_the_book():
    assert round(s_curve(0.5, 20, 5), 3) == 0.470
    assert round(s_curve(0.8, 20, 5), 4) == 0.9996
    assert approx_threshold(16, 4) == pytest.approx(0.5)


def test_split_bands_rejects_too_many_bands():
    with pytest.raises(ValueError):
        split_bands([1] * 10, bands=4, rows=5)


def test_candidate_pairs_needs_one_matching_band():
    signatures = {0: [1, 2, 3, 4], 1: [1, 2, 9, 9], 2: [7, 7, 7, 7]}
    assert candidate_pairs(signatures, bands=2, rows=2) == {(0, 1)}


def test_bands_use_separate_tables():
    signatures = {0: [1, 2, 3, 4], 1: [3, 4, 1, 2]}
    assert candidate_pairs(signatures, bands=2, rows=2) == set()


def test_optimal_params_put_the_midpoint_near_the_threshold():
    bands, rows = optimal_params(0.7, 64)
    assert bands * rows <= 64
    assert abs(approx_threshold(bands, rows) - 0.7) < 0.1


def test_union_find_keeps_the_smallest_id():
    groups = UnionFind(5)
    groups.union(3, 1)
    groups.union(4, 3)
    assert {groups.find(i) for i in (1, 3, 4)} == {1}

Run python -m pytest -q test_minhash.py:

..............                                                                                                                                                     [100%]
14 passed in 0.17s

Several tests encode lessons from earlier steps. test_signature_is_the_same_in_another_process starts two interpreters with different hash seeds and requires identical signatures, which is the Step 4 trap. test_bands_use_separate_tables makes sure a number in band 1 can never match the same number in band 2. test_merge_gives_the_signature_of_the_union checks the element-wise-minimum property. test_s_curve_matches_the_book ties the formula to the published values. The estimator tests use fixed seeds, so they never flake.

Confirm the Whole Thing Works End to End

Run the steps in order. Steps 7 and 10 read truth.json, which Step 2 creates, so do not skip it.

python step1_shingles_jaccard.py
python step2_bruteforce.py
python step3_minhash_accuracy.py
python step4_hash_pitfall.py
python step5_scurve.py
python step6_choose_params.py
python step7_pipeline.py
python step8_scaling.py
python step9_pitfalls.py
python step10_datasketch_check.py
python -m pytest -q test_minhash.py

You have a correct setup if you see these signs. Step 2 reports 502 pairs at or above 0.7. Step 4 shows 0 of 8 agreeing positions for the built-in hash and 8 of 8 for the stable one. Step 5’s formula column matches the book’s table. Step 6 shows the same (bands, rows) from both implementations. Step 7 ends with precision 1.000 after verification, recall 0.988, and zero documents merged into the wrong cluster. Step 10 reports nearly identical errors for both libraries, and pytest finishes with 14 passed. Timings will differ on your machine, and the crossover in Step 8 may move, but its shape should not.

If something looks wrong

• Everything is a candidate, or nothing is. Check b and r against your threshold (Step 6), and check that every document went through the same normalization and shingle size (Step 9).
• Signatures never match across runs. You are probably using the built-in hash() somewhere (Step 4), or two MinHasher objects with different seeds.
• ValueError: signatures must come from the same MinHasher. You compared signatures of different lengths. Signatures are comparable only if they came from the same seed and the same number of hash functions.
• Very similar pairs are missing. Move the weights toward false negatives (Step 6), or add bands by using a longer signature.

Where This Is Used, and What It Cannot Do

MinHash is old and still current. Wikipedia’s article on the technique records that Andrei Broder published it in 1997 and that it was first used in the AltaVista search engine to detect duplicate web pages and drop them from search results. The deduplication paper quoted at the start uses it for language-model training data, and its authors follow the same shape as the pipeline you built: a cheap MinHash match first, then a stricter check. As they put it, “we identify two documents as duplicates if they are matched by the MinHash algorithm and their edit similarity is greater than 0.8.”

Know the limits before you rely on it:

• It measures shared wording, not meaning. A paraphrase with different words has a low Jaccard similarity. For semantic near-duplicates you need embeddings; the hybrid search tutorial shows how to compute and combine them.
• It is probabilistic. You choose where on the S-curve to sit, and some true pairs near the threshold will be missed, as the 6 missed pairs in Step 7 show.
• Whitespace-delimited shingles assume words. For languages written without spaces, use character n-grams instead.
• Containment is a different question. Excerpt detection needs chunking or a containment measure (Pitfall 4).
• The threshold is yours to define. 0.7 on 3-word shingles is a choice. Inspect pairs just above and just below your threshold by eye before trusting it.

Where to Go Next

• This is the fourth tool in a small family of fixed-memory algorithms on this site. See the Bloom filter (exact “have I seen this?”), the HyperLogLog counter (how many distinct items?), and the Count-Min sketch (how often did each appear?). MinHash answers “how alike are these two?”
• The same idea works on images: the perceptual hashing tutorial finds near-duplicate pictures.
• If you deduplicate chunks before indexing them for RAG, pair this with the chunk-size tuning tutorial, since chunk size changes both retrieval quality and the Jaccard similarity of overlapping chunks.
• Stable hashing shows up again in the feature-flag tutorial, where the same hash() trap would break sticky rollouts, and in consistent hashing.
• Try changing one thing at a time in the lab: use 5-word shingles, a threshold of 0.5, or 256 hash functions, and watch the recall, the number of candidates and the clusters move.