What does Compression Distance and Rewrite Detection conclude, in numbers, about “N-grams, MinHash and Locality-Sensitive Hashing: a First Screen over Millions of Pages”?
Answer: Chapter 4 shows that locality-sensitive hashing designed for near copies misses rewrites, admitting only 0.5088 of thirty per cent rewrites at a knee of 0.4204, so the knee must come down to 0.1250.
Scope of the numbers: Its corpora, thresholds and parameters are illustrative, every sample text is generated by program or written by the author, and all calculations are generated by its programs. It is not individual business advice and not legal advice, and every flag raised by its small tool needs human review.
Data table
The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python onlyprinted values that match the answer: 0.1250, 0.4204, 0.5088
| s | b=64 r= 2 | b=32 r= 4 | b=16 r= 8 | b= 8 r=16 |
| 0.900 | 1.0000 | 1.0000 | 0.9999 | 0.8059 |
| 0.700 | 1.0000 | 0.9998 | 0.6133 | 0.0263 |
| 0.500 | 1.0000 | 0.8732 | 0.0607 | 0.0001 |
| 0.385 | 1.0000 | 0.5088 | 0.0077 | 0.0000 |
| 0.300 | 0.9976 | 0.2291 | 0.0010 | 0.0000 |
| 0.156 | 0.7934 | 0.0188 | 0.0000 | 0.0000 |
| 0.100 | 0.4744 | 0.0032 | 0.0000 | 0.0000 |
| 0.033 | 0.0674 | 0.0000 | 0.0000 | 0.0000 |
| knee s* | 0.1250 | 0.4204 | 0.7071 | 0.8781 |
| simulation, b=32 r=4 (300 pairs per level, 100-gram sets) | ||||
| s = 0.385 (exact 0.3889): simulated 0.507, formula 0.523 | ||||
| s = 0.156 (exact 0.1561): simulated 0.003, formula 0.019 | ||||
| s = 0.033 (exact 0.0309): simulated 0.000, formula 0.000 |
Show the full program
# Chapter 4. p42: banding MinHash signatures (locality-sensitive hashing).
# Split k = 128 MinHash values into b bands of r rows; two texts become a
# candidate pair if any band agrees in all r rows. For Jaccard s:
# P(candidate) = 1 - (1 - s^r)^b, steepest near s* = (1/b)^(1/r).
# We print the S-curve for four layouts, then check the formula by
# simulation on synthetic set pairs of exact Jaccard s (300 pairs each).
# The levels 0.385, 0.156 and 0.033 are the mean word 3-gram Jaccard of
# rewrites at rates 0.3, 0.6 and 1.0 in p11. Set elements are random
# 40-bit ids: linear hashes of consecutive integers are not min-wise
# independent and would bias the check.
import math
import random
PR = (1 << 61) - 1
hr = random.Random(97)
AB = [(hr.randrange(1, PR), hr.randrange(PR)) for _ in range(128)]
def p_cand(s, b, r):
return 1.0 - (1.0 - s ** r) ** b
LAYOUTS = ((64, 2), (32, 4), (16, 8), (8, 16))
LEVELS = (0.9, 0.7, 0.5, 0.385, 0.3, 0.156, 0.1, 0.033)
print("s " + " ".join("b=%2d r=%2d" % br for br in LAYOUTS))
for s in LEVELS:
print("%.3f " % s + " ".join("%.4f" % p_cand(s, b, r)
for b, r in LAYOUTS))
print("knee s* " + " ".join("%.4f" % (1.0 / b) ** (1.0 / r)
for b, r in LAYOUTS))
rng = random.Random(20261113)
print("simulation, b=32 r=4 (300 pairs per level, 100-gram sets)")
for s in (0.385, 0.156, 0.033):
hits = 0
both = round(200 * s / (1 + s))
for t in range(300):
ids = [rng.getrandbits(40) for _ in range(200 - both)]
A = set(ids[:100])
B = set(ids[:both] + ids[100:])
sa = [min((a * v + c) % PR for v in A) for a, c in AB]
sb = [min((a * v + c) % PR for v in B) for a, c in AB]
same = any(sa[i:i + 4] == sb[i:i + 4] for i in range(0, 128, 4))
hits += same # step
exact = (both / (200.0 - both))
print(" s = %.3f (exact %.4f): simulated %.3f, formula %.3f"
% (s, exact, hits / 300, p_cand(exact, 32, 4)))Single source and citation
Fan, Y. (2026). Normalised Compression Distance and Kolmogorov Complexity: Detecting Rewritten Copies and Clustering Families of Shared-Origin Sales Scripts (Version 1.0.0), Chapter 4: N-grams, MinHash and Locality-Sensitive Hashing: a First Screen over Millions of Pages. 5D Library. DOI pending
DOI pending · monograph page goes live after publication · 5DL-B-293 · v1.0.0 · CC-BY-NC-ND-4.0
BibTeX
@book{fan2026293,
author = {Fan, Yafu},
title = {Normalised Compression Distance and Kolmogorov Complexity: Detecting Rewritten Copies and Clustering Families of Shared-Origin Sales Scripts},
year = {2026},
publisher = {5D Library},
edition = {1.0.0},
note = {DOI pending}
}Other chapter answers in this book
- Chapter 1 · Sweeping the Substitution Rate: Where Literal Matching Fails
- Chapter 2 · Kolmogorov Complexity and Real Compressors: Upper Bounds, Normality and the Window
- Chapter 3 · Short-Text Bias and Threshold Sensitivity: One Line Cannot Rule Every Length
- Chapter 5 · Deep Paraphrase: Number Fingerprints and Argument-Sequence Fingerprints
- Chapter 6 · Hierarchical Clustering of Shared-Origin Script Families
- Chapter 7 · The Classics Examined: the Colophon of the Cheng House at Meishan and the Statute of Anne
- Chapter 8 · Closing the Loop: Weekly Monitoring for Rewritten Copies, De-duplicating Direct-Answer Pages and a Pre-registered Test