MinHash › Implementation
Language AI HandbookAll chapters MinHash › ImplementationOne section · Sections in this chapter7 / 13 ↓
Reading tools Definitions & inline links
Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.
Article links
Make inline references clickable
This section walks through a complete MinHash LSH implementation from scratch, starting with shingle extraction and working up to candidate pair detection and verification.
Setting Up
We begin by importing required libraries. No external packages beyond NumPy are required for the core implementation.
Shingle Extraction
The first step converts each document into a set of character-level shingles. We normalize whitespace and lowercase the text before shingling to ensure consistent matching across minor formatting differences.
def get_shingles(text: str, k: int = 5) -> set[int]:
"""Extract character-level k-shingles from text, returned as hashed integers."""
text = re.sub(r"\s+", " ", text.lower().strip())
shingles = set()
for i in range(len(text) - k + 1):
shingle = text[i : i + k]
# Hash shingle to integer for efficiency
h = int(hashlib.md5(shingle.encode()).hexdigest(), 16) % (2**32)
shingles.add(h)
return shinglesThe function slides a window of width over the normalized text, hashing each shingle to a 32-bit integer. Using MD5 here is acceptable for hashing purposes (not security), and in production you would use a faster non-cryptographic hash like xxHash.
Document A shingle count: 28 Document B shingle count: 28 Document C shingle count: 52 Exact Jaccard(A, B): 0.6970 Exact Jaccard(A, C): 0.0000 Exact Jaccard(B, C): 0.0000
Documents A and B are near-duplicates (one word differs), so they share most of their 5-character shingles and receive a high Jaccard similarity score. Document C is completely unrelated to both, giving near-zero overlap with either. This confirms that the 5-gram character shingling correctly separates similar from dissimilar documents.
MinHash Signature Generation
Next, we implement the MinHash signature computation. We use independent hash functions, each parameterized by a distinct random pair drawn from a Mersenne prime field.
class MinHash:
"""MinHash signature generator using random linear hash functions."""
_PRIME = (1 << 31) - 1 # Mersenne prime 2^31 - 1
_MAX_HASH = 2**32
def __init__(self, num_hashes: int = 128, seed: int = 42):
self.num_hashes = num_hashes
rng = random.Random(seed)
# Generate random coefficients for each hash function
self.a = [rng.randint(1, self._PRIME - 1) for _ in range(num_hashes)]
self.b = [rng.randint(0, self._PRIME - 1) for _ in range(num_hashes)]
def signature(self, shingles: set[int]) -> np.ndarray:
"""Compute MinHash signature: minimum hash value under each hash function."""
sig = np.full(self.num_hashes, self._MAX_HASH, dtype=np.uint64)
for shingle in shingles:
for i in range(self.num_hashes):
h = (self.a[i] * shingle + self.b[i]) % self._PRIME
if h < sig[i]:
sig[i] = h
return sig
def similarity(self, sig1: np.ndarray, sig2: np.ndarray) -> float:
"""Estimate Jaccard similarity from two signatures."""
return float(np.mean(sig1 == sig2))The signature method initializes each position to the maximum possible hash value (serving as infinity), then iterates over all shingles in the document. For each shingle, it computes the hash value under each of the linear hash functions and updates the minimum if the new value is smaller. After processing all shingles, the vector of minimums is the MinHash signature.
MinHash similarity estimates (128 hashes): A vs B (expected ~high): 0.7734 | exact: 0.6970 A vs C (expected ~low): 0.0000 | exact: 0.0000 B vs C (expected ~low): 0.0000 | exact: 0.0000
The MinHash estimates closely track the exact Jaccard values. Documents A and B, which differ by a single word, receive a high estimated similarity close to the exact value. Document C, which is unrelated, receives near-zero estimates for both A vs C and B vs C. With 128 hash functions, the estimates are quite accurate.
LSH Banding
Now we implement the banding technique that makes near-duplicate detection scalable. We divide the signature into bands of rows each, and bucket documents by their band values.
class LSH:
"""Locality Sensitive Hashing for MinHash signatures using the band technique."""
def __init__(self, num_bands: int, rows_per_band: int):
self.num_bands = num_bands
self.rows_per_band = rows_per_band
self.num_hashes = num_bands * rows_per_band
# Each band maintains its own hash table mapping band-hash -> list of doc ids
self.buckets: list[dict[int, list]] = [
defaultdict(list) for _ in range(num_bands)
]
def add(self, doc_id: int, signature: np.ndarray) -> None:
"""Add a document signature to the LSH index."""
for band_idx in range(self.num_bands):
start = band_idx * self.rows_per_band
end = start + self.rows_per_band
band_values = tuple(signature[start:end])
# Hash the band tuple to a bucket key
bucket_key = hash(band_values)
self.buckets[band_idx][bucket_key].append(doc_id)
def candidate_pairs(self) -> set[tuple]:
"""Return all (doc_i, doc_j) pairs that share at least one bucket."""
candidates = set()
for band in self.buckets:
for bucket_docs in band.values():
if len(bucket_docs) > 1:
for pair in combinations(bucket_docs, 2):
candidates.add(tuple(sorted(pair)))
return candidatesThe add method computes band hashes for each document and inserts the document ID into the corresponding bucket in each band. The candidate_pairs method iterates over all buckets and emits all pairs of documents that share a bucket in any band.
Candidate pairs detected: {(0, 1)}
Approximate LSH threshold: 0.707
Pair verification:
Documents (0, 1): estimated similarity = 0.7734LSH correctly identifies documents A and B as candidates and correctly ignores the pairing with document C. The configuration of 16 bands times 8 rows gives a threshold near 0.72. Documents A and B, with similarity well above this threshold, are reliably detected as candidates. Document C, with near-zero similarity to the others, is correctly excluded.
Scaling to a Larger Corpus
Let's simulate the approach on a larger corpus to observe how MinHash LSH scales. We generate a collection of documents where some are near-duplicates, then measure the candidate reduction.
def generate_corpus(
num_docs: int = 1000, dup_fraction: float = 0.2, seed: int = 0
) -> list[str]:
"""Generate a corpus with a known fraction of near-duplicate pairs."""
rng = random.Random(seed)
base_texts = [
"machine learning models learn patterns from data through iterative optimization",
"natural language processing enables computers to understand human text",
"neural networks are computational models inspired by biological neurons",
"transformer architectures use self attention to process sequences efficiently",
"pretraining on large corpora gives models broad language understanding",
]
words_pool = [
"the",
"a",
"large",
"small",
"deep",
"modern",
"efficient",
"powerful",
"scalable",
"robust",
"accurate",
"fast",
"simple",
]
corpus = []
for i in range(num_docs):
base = rng.choice(base_texts)
words = base.split()
if i < int(num_docs * dup_fraction):
# Near-duplicate: swap one word
idx = rng.randint(0, len(words) - 1)
words[idx] = rng.choice(words_pool)
else:
# Unique: replace several words
for _ in range(rng.randint(3, 6)):
idx = rng.randint(0, len(words) - 1)
words[idx] = rng.choice(words_pool)
corpus.append(" ".join(words))
return corpus
corpus = generate_corpus(num_docs=1000)# Compute MinHash signatures for all documents
mh = MinHash(num_hashes=128, seed=42)
lsh_large = LSH(num_bands=16, rows_per_band=8)
t0 = time.time()
all_sigs = []
for doc_id, text in enumerate(corpus):
shingles = get_shingles(text, k=5)
sig = mh.signature(shingles)
all_sigs.append(sig)
lsh_large.add(doc_id, sig)
signature_time = time.time() - t0
# Find candidate pairs
t1 = time.time()
candidates_large = lsh_large.candidate_pairs()
lsh_time = time.time() - t1Corpus size: 1000 documents Total possible pairs: 499,500 Candidate pairs found: 2,260 Candidate reduction factor: 221.0x Timing: Signature computation: 1.556s LSH candidate search: 0.001s
LSH reduces the number of pairs to compare by orders of magnitude. Rather than checking all nearly 500,000 possible pairs, you only compare the small fraction that share at least one LSH bucket. This reduction factor grows rapidly with corpus size, making LSH the key ingredient that allows MinHash to scale to billions of documents.