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.0012p99 0.0109 | null NCD: median 0.8140p01 0.7723
rateJ3NCDJ3 keptNCD keptdet J3det NCD
0.01.0000.0411.0001.0001.0001.000
0.10.7190.1730.7190.8291.0001.000
0.20.5170.2920.5170.6751.0001.000
0.30.3850.3880.3850.5511.0001.000
0.40.2810.4790.2800.4331.0001.000
0.50.2090.5500.2080.3411.0001.000
0.60.1560.6150.1550.2571.0001.000
0.70.1090.6810.1080.1721.0001.000
0.80.0780.7360.0770.1011.0000.910
0.90.0510.7870.0500.0350.9930.293
1.00.0330.8380.032-0.0310.9570.000
fixed bar 0.5: J3 first below at r = 0.3, 1 - NCD at r = 0.5

Key formula

\[\mathrm{NCD}(x,y)=\frac{C(xy)-\min\{C(x),C(y)\}}{\max\{C(x),C(y)\}}.\]
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