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

sb=64 r= 2b=32 r= 4b=16 r= 8b= 8 r=16
0.9001.00001.00000.99990.8059
0.7001.00000.99980.61330.0263
0.5001.00000.87320.06070.0001
0.3851.00000.50880.00770.0000
0.3000.99760.22910.00100.0000
0.1560.79340.01880.00000.0000
0.1000.47440.00320.00000.0000
0.0330.06740.00000.00000.0000
knee s*0.12500.42040.70710.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