What does Compression Distance and Rewrite Detection conclude, in numbers, about “Hierarchical Clustering of Shared-Origin Script Families”?
Answer: Chapter 6 clusters scripts into families of shared origin by average linkage, with an adjusted Rand index of 0.9962 at a calibrated cut.
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.9962
| null NCD p01 h* = 0.7539, median 0.7935 | ||||
| cut h | clusters | ARI | singletons merged | members alone |
| 0.5500 | 23.2 | 0.2524 | 0.0 | 7.3 |
| 0.6500 | 15.6 | 0.5946 | 0.0 | 0.0 |
| 0.7500 | 11.7 | 0.9972 | 0.6 | 0.0 |
| 0.7539 | 11.6 | 0.9962 | 0.8 | 0.0 |
| 0.8000 | 5.2 | 0.6896 | 7.5 | 0.0 |
| 0.8500 | 1.0 | 0.0000 | 8.0 | 0.0 |
Show the full program
# Chapter 6. p63: where to cut the tree when the number of families is
# unknown. Corpus: 4 families of 6 (deep copying steps, g = 0.4, as in
# p62) plus 8 unrelated singleton scripts of the same genre. Average
# linkage on NCD, cut at a fixed height h. We report clusters found, ARI
# against the truth (each singleton its own family), singletons wrongly
# merged and family members left alone. Then a calibrated cut: h* = the
# 1st percentile of NCD over 300 independent same-genre pairs.
# Mean of 10 replicate corpora per row. Illustrative.
import bisect
import math
import random
import zlib
CONS, VOWS = "bdfgklmnprstvz", "aeiou"
def lexicon(seed, n_content=400, n_forms=3, n_func=30):
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])
elif out:
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 C(b):
return len(zlib.compress(b, 9))
def ncd(bx, by):
cx, cy, cxy = C(bx), C(by), C(bx + by)
return (cxy - min(cx, cy)) / max(cx, cy)
MOVES = "HPCRNOXK" # hook pain claim proof number offer objection close
NUMS = [3, 7, 9, 12, 15, 19, 24, 30, 49, 59, 99, 128, 199, 299, 399, 999]
NCUM = zipf_cum(len(NUMS))
mrng = random.Random(2930)
# two discourse markers per move, three forms each, four syllables long
MARK = [["".join(mrng.choice(CONS) + mrng.choice(VOWS) for _ in range(4))
for _ in range(3)] for _ in range(16)]
MARKER = {MARK[j][f]: MOVES[j // 2] for j in range(16) for f in range(3)}
def sales_script(rng, n_sent=12, p_num=0.35, conv=0.6):
# sentence = [move, marker, form, body tokens, number or None];
# with chance conv the next move follows the usual genre order
out, m = [], "H"
for _ in range(n_sent):
body = script(rng, 7)[:-1]
num = NUMS[draw(rng, NCUM)] if rng.random() < p_num else None
out.append([m, rng.randrange(2), 0, body, num])
if rng.random() < conv:
m = MOVES[min(MOVES.index(m) + 1, 7)]
else:
m = rng.choice(MOVES)
return out
def say(sents):
words = []
for m, k, form, body, num in sents:
if m != "?":
words.append(MARK[2 * MOVES.index(m) + k][form])
words.append(render(body))
if num is not None:
words.append(str(num))
words[-1] += "."
return " ".join(words)
def reword(rng, body, r, p_func):
out = []
for kind, i, form in body:
if kind == "c" and rng.random() < r:
form = rng.choice([x for x in range(3) if x != form])
elif kind == "f" and rng.random() < p_func:
i = rng.randrange(30)
out.append((kind, i, form))
return out
def light_rewrite(rng, sents, r=0.3):
return [[m, k, f, reword(rng, b, r, 0.0), n]
for m, k, f, b, n in sents]
def deep_rewrite(rng, sents, r=0.9):
# reword, rotate clauses, drop 10 %, insert 15 %, lose 20 % of
# markers, swap neighbours; the numbers and move order stay
out = []
for m, k, form, body, num in sents:
if rng.random() < 0.1:
continue
body = reword(rng, body, r, 0.5)
cut = rng.randrange(1, len(body))
mk = "?" if rng.random() < 0.2 else m
out.append([mk, k, rng.randrange(3), body[cut:] + body[:cut], num])
if rng.random() < 0.15:
out.append(["?", 0, 0, script(rng, 7)[:-1], None])
for i in range(len(out) - 1):
if rng.random() < 0.15:
out[i], out[i + 1] = out[i + 1], out[i]
return out
def fingerprint(text):
nums, moves = [], []
for sent in text.split(". "):
w = sent.rstrip(".").split()
moves.append(MARKER.get(w[0], "?") if w else "?")
nums += [x for x in w if x.isdigit()]
return nums, "".join(m for m in moves if m != "?")
def lcs(a, b):
prev = [0] * (len(b) + 1)
for x in a:
cur = [0]
for j, y in enumerate(b):
cur.append(prev[j] + 1 if x == y else max(prev[j + 1], cur[j]))
prev = cur
return prev[-1]
def lcs_sim(a, b):
return lcs(a, b) / max(len(a), len(b), 1)
def mutate(rng, sents, g, deep=False):
# one copying step: reword a share g of content words and swap each
# neighbouring pair of sentences with chance g / 2; numbers kept.
# deep: also swap function words (chance g / 2) and rotate clauses
# (chance g)
out = []
for m, k, f, b, n in sents:
b = reword(rng, b, g, g / 2.0 if deep else 0.0)
if deep and rng.random() < g:
c = rng.randrange(1, len(b))
b = b[c:] + b[:c]
out.append([m, k, f, b, n])
for i in range(len(out) - 1):
if rng.random() < g / 2.0:
out[i], out[i + 1] = out[i + 1], out[i]
return out
def family(rng, g, deep=False):
# ancestor -> 2 children -> 2 grandchildren each; members exclude
# the ancestor, as the true first draft is rarely found
root = sales_script(rng)
kids = [mutate(rng, root, g, deep) for _ in range(2)]
grand = [mutate(rng, k, g, deep) for k in kids for _ in range(2)]
return kids + grand
def linkage(d, n, how):
# agglomerative clustering; returns merges (height, members)
cl = {i: [i] for i in range(n)}
merges = []
while len(cl) > 1:
best = None
keys = sorted(cl)
for x in range(len(keys)):
for y in range(x + 1, len(keys)):
a, b = cl[keys[x]], cl[keys[y]]
ds = [d[i][j] for i in a for j in b]
if how == "single":
h = min(ds)
elif how == "complete":
h = max(ds)
else:
h = math.fsum(ds) / len(ds)
if best is None or h < best[0]:
best = (h, keys[x], keys[y])
h, p, q = best
cl[p] = cl[p] + cl.pop(q)
merges.append((h, sorted(cl[p])))
return merges
def cut(merges, n, k=None, height=None):
lab = list(range(n))
for i, (h, mem) in enumerate(merges):
if k is not None and n - i <= k:
break
if height is not None and h > height:
break
for j in mem:
lab[j] = mem[0]
return lab
def ari(a, b):
# adjusted Rand index (Hubert and Arabie 1985), integer counts
n = len(a)
pairs = {}
for x, y in zip(a, b):
pairs[(x, y)] = pairs.get((x, y), 0) + 1
def c2(v):
return v * (v - 1) // 2
ra = {}
rb = {}
for x, y in zip(a, b):
ra[x] = ra.get(x, 0) + 1
rb[y] = rb.get(y, 0) + 1
s = math.fsum(c2(v) for v in pairs.values())
sa = math.fsum(c2(v) for v in ra.values())
sb = math.fsum(c2(v) for v in rb.values())
exp = sa * sb / c2(n)
top = (sa + sb) / 2.0
return (s - exp) / (top - exp) if top != exp else 1.0
rng = random.Random(20261113)
null = []
for _ in range(300):
null.append(ncd(say(sales_script(rng)).encode(),
say(sales_script(rng)).encode()))
null.sort()
hstar = null[3]
corp = []
for _ in range(10):
docs, truth = [], []
for f in "ABCD":
for s in family(rng, 0.4, True):
docs.append(say(s).encode())
truth.append(f)
for i in range(8):
docs.append(say(sales_script(rng)).encode())
truth.append("S%d" % i)
n = len(docs)
d = [[0.0] * n for _ in range(n)]
for i in range(n):
for j in range(i + 1, n):
d[i][j] = d[j][i] = ncd(docs[i], docs[j])
corp.append((linkage(d, n, "average"), truth, n))
print("null NCD p01 h* = %.4f, median %.4f" % (hstar, null[150]))
print("cut h clusters ARI singletons merged members alone")
for h in (0.55, 0.65, 0.75, hstar, 0.80, 0.85):
k, a, sm, ma = [], [], [], []
for m, truth, n in corp:
lab = cut(m, n, height=h)
size = {}
for x in lab:
size[x] = size.get(x, 0) + 1
k.append(len(size))
a.append(ari(lab, truth))
sm.append(len([i for i in range(n) if truth[i][0] == "S"
and size[lab[i]] > 1]))
ma.append(len([i for i in range(n) if truth[i][0] != "S"
and size[lab[i]] == 1]))
print("%.4f %5.1f %.4f %5.1f %5.1f"
% (h, math.fsum(k) / 10, math.fsum(a) / 10,
math.fsum(sm) / 10, math.fsum(ma) / 10))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 6: Hierarchical Clustering of Shared-Origin Script Families. 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 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 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