What does Compression Distance and Rewrite Detection conclude, in numbers, about “Sweeping the Substitution Rate: Where Literal Matching Fails”?
Answer: Chapter 1 finds that the Jaccard index of word 3-grams falls most steeply at the start of substitution and has lost 0.641 of its range by thirty per cent, with a fixed alarm bar of 0.5 crossed at a rate of 0.211; calibrated on unrelated texts, literal fragments still detect 0.957 of rewrites with every content word replaced, while compression distance detects 0.000 and declines more slowly only in the share of signal kept (0.551 against 0.385).
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.000, 0.385, 0.5, 0.551, 0.957
| 150-word scripts, 300 rewrites per rate, 400 null pairs | ||||||
| null J3: mean 0.0012 | p99 0.0109 | null NCD: median 0.8140 | p01 0.7723 | ||||
| rate | J3 | NCD | J3 kept | NCD kept | det J3 | det NCD |
| 0.0 | 1.000 | 0.041 | 1.000 | 1.000 | 1.000 | 1.000 |
| 0.1 | 0.719 | 0.173 | 0.719 | 0.829 | 1.000 | 1.000 |
| 0.2 | 0.517 | 0.292 | 0.517 | 0.675 | 1.000 | 1.000 |
| 0.3 | 0.385 | 0.388 | 0.385 | 0.551 | 1.000 | 1.000 |
| 0.4 | 0.281 | 0.479 | 0.280 | 0.433 | 1.000 | 1.000 |
| 0.5 | 0.209 | 0.550 | 0.208 | 0.341 | 1.000 | 1.000 |
| 0.6 | 0.156 | 0.615 | 0.155 | 0.257 | 1.000 | 1.000 |
| 0.7 | 0.109 | 0.681 | 0.108 | 0.172 | 1.000 | 1.000 |
| 0.8 | 0.078 | 0.736 | 0.077 | 0.101 | 1.000 | 0.910 |
| 0.9 | 0.051 | 0.787 | 0.050 | 0.035 | 0.993 | 0.293 |
| 1.0 | 0.033 | 0.838 | 0.032 | -0.031 | 0.957 | 0.000 |
| fixed bar 0.5: J3 first below at r = 0.3, 1 - NCD at r = 0.5 |
Key formula
Show the full program
# Chapter 1. p11: substitution-rate sweep, word 3-gram Jaccard vs zlib NCD.
# Corpus (illustrative, self-made): pseudo-words built from syllables; 30
# function words with one form, 400 content concepts with 3 synonymous
# forms each, Zipf frequencies. A script is 150 words; a rewrite replaces
# a share r of content words by another synonym of the same concept.
# NCD(x, y) = (C(xy) - min(C(x), C(y))) / max(C(x), C(y)), C = zlib -9.
# Thresholds are calibrated on 400 unrelated pairs (null): J3 above the
# null 99th percentile, NCD below the null 1st percentile.
import bisect
import math
import random
import zlib
CONS, VOWS = "bdfgklmnprstvz", "aeiou"
def lexicon(seed, n_content=400, n_forms=3, n_func=30):
# pseudo-word lexicon (illustrative, self-made)
rng = random.Random(seed)
seen = set()
def word(k):
while True:
w = "".join(rng.choice(CONS) + rng.choice(VOWS)
for _ in range(k))
if w not in seen:
seen.add(w)
return w
func = [word(1) for _ in range(n_func)]
content = [[word(rng.randint(2, 3)) for _ in range(n_forms)]
for _ in range(n_content)]
return func, content
def zipf_cum(n):
w = [1.0 / (k + 1) for k in range(n)]
tot = math.fsum(w)
return [math.fsum(w[:k + 1]) / tot for k in range(n)]
FUNC, CONTENT = lexicon(293)
FCUM, CCUM = zipf_cum(len(FUNC)), zipf_cum(len(CONTENT))
def draw(rng, cum):
return min(bisect.bisect_left(cum, rng.random()), len(cum) - 1)
def script(rng, n_words, p_func=0.4):
toks = []
while len(toks) < n_words:
for _ in range(rng.randint(8, 14)):
if rng.random() < p_func:
toks.append(("f", draw(rng, FCUM), 0))
else:
toks.append(("c", draw(rng, CCUM), 0))
toks.append(("p", 0, 0))
return toks
def render(toks):
out = []
for kind, i, form in toks:
if kind == "f":
out.append(FUNC[i])
elif kind == "c":
out.append(CONTENT[i][form])
else:
out[-1] += "."
return " ".join(out)
def substitute(rng, toks, r):
out = []
for kind, i, form in toks:
if kind == "c" and rng.random() < r:
form = rng.choice([k for k in range(3) if k != form])
out.append((kind, i, form))
return out
def clen(b):
return len(zlib.compress(b, 9))
def ncd(x, y):
bx, by = x.encode(), y.encode()
cx, cy, cxy = clen(bx), clen(by), clen(bx + b" " + by)
return (cxy - min(cx, cy)) / max(cx, cy)
def shingles(text, n=3):
w = text.split()
return {" ".join(w[i:i + n]) for i in range(len(w) - n + 1)}
def jac(a, b):
return len(a & b) / len(a | b)
rng = random.Random(20261113)
NW, NULL, PAIRS = 150, 400, 300
nj, nn = [], []
for _ in range(NULL):
a, b = render(script(rng, NW)), render(script(rng, NW))
nj.append(jac(shingles(a), shingles(b)))
nn.append(ncd(a, b))
nj.sort()
nn.sort()
tj, tn = nj[int(0.99 * NULL)], nn[int(0.01 * NULL)]
mj, mn = math.fsum(nj) / NULL, nn[NULL // 2]
print("150-word scripts, %d rewrites per rate, %d null pairs"
% (PAIRS, NULL))
print("null J3: mean %.4f p99 %.4f | null NCD: median %.4f p01 %.4f"
% (mj, tj, mn, tn))
print("rate J3 NCD J3 kept NCD kept det J3 det NCD")
rows = []
for r10 in range(11):
r = r10 / 10.0
js, ns = [], []
for _ in range(PAIRS):
t = script(rng, NW)
a, b = render(t), render(substitute(rng, t, r))
js.append(jac(shingles(a), shingles(b)))
ns.append(ncd(a, b))
rows.append((r, math.fsum(js) / PAIRS, math.fsum(ns) / PAIRS,
len([x for x in js if x > tj]) / PAIRS,
len([x for x in ns if x < tn]) / PAIRS))
n0 = rows[0][2]
for r, j, n, dj, dn in rows:
kj = (j - mj) / (1.0 - mj)
kn = (mn - n) / (mn - n0)
print("%.1f %.3f %.3f %.3f %.3f %.3f %.3f"
% (r, j, n, kj, kn, dj, dn))
cj = [r for r, j, n, dj, dn in rows if j < 0.5][0]
cn = [r for r, j, n, dj, dn in rows if 1.0 - n < 0.5][0]
print("fixed bar 0.5: J3 first below at r = %.1f, 1 - NCD at r = %.1f"
% (cj, cn))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 1: Sweeping the Substitution Rate: Where Literal Matching Fails. 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 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 4 · N-grams, MinHash and Locality-Sensitive Hashing: a First Screen over Millions of Pages
- 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