Near Duplicates

A review bot posts the same fake review thousands of times, changing one word each time. To compare each review with every other is billions of comparisons. It'd take forever. But there's a brilliant trick, invented to clean up the early web, that turns any document into a tiny signature.

• The same fake review, thousands of times
• Billions of comparisons
• A tiny signature

MinHash

First, each text becomes a set of three word phrases, called shingles. Overlap between sets tells us how similar two texts are. Then comes the magic. For a random hash function, the chance that two sets share the same smallest hash is exactly equal to their overlap. So four hundred hashes give us a good estimate. Run it. The true overlap between the two similar messages is fifty eight percent, and the signature estimates sixty, using only four hundred numbers. The unrelated message scores zero. Now you can compare small signatures, rather than whole documents.

import random, re, zlib

def shingles(text, k=3):
    w = re.findall(r"\w+", text.lower())
    return {" ".join(w[i:i + k]) for i in range(len(w) - k + 1)}

random.seed(0)
seeds = [random.getrandbits(32) for _ in range(400)]

def signature(s):
    return [min(zlib.crc32(f"{seed} {x}".encode()) for x in s) for seed in seeds]

a = "my order arrived late and the box was crushed in transit"
b = "my order arrived very late and the box was crushed in transit"
c = "the book has missing pages in chapter four of the novel"

A, B, C = shingles(a), shingles(b), shingles(c)
print(f"True overlap a,b: {len(A & B) / len(A | B):.2f}")
sa, sb, sc = map(signature, (A, B, C))
print(f"Estimated a,b: {sum(x == y for x, y in zip(sa, sb)) / 400:.2f}")
print(f"Estimated a,c: {sum(x == y for x, y in zip(sa, sc)) / 400:.2f}")

True overlap a,b: 0.58
Estimated a,b: 0.60
Estimated a,c: 0.00

Scaling further

With signatures alone, you'd still need to compare every pair. So a second trick helps, called locality sensitive hashing. It groups signatures into buckets, so that similar items land together, and you only compare within a bucket. Together, these let search engines remove duplicate pages across billions of documents.

Summary