What does Compression Distance and Rewrite Detection conclude, in numbers, about “Kolmogorov Complexity and Real Compressors: Upper Bounds, Normality and the Window”?
Answer: Chapter 2 shows that compression only bounds Kolmogorov complexity from above, and that once a text exceeds zlib's window the compression distance of a complete copy jumps to 0.9330.
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.9330
| bytes | NCD(x,x) | NCD(x,y10) | blockwise NCD(x,y10) |
| 3557 | 0.0319 | 0.1788 | 0.1653 |
| 14146 | 0.0363 | 0.2269 | 0.2009 |
| 24537 | 0.0369 | 0.2203 | 0.1884 |
| 28177 | 0.0393 | 0.2326 | 0.1951 |
| 31708 | 0.0387 | 0.2351 | 0.1937 |
| 42252 | 0.9330 | 0.9378 | 0.2010 |
| 84761 | 0.9589 | 0.9605 | 0.1878 |
| deflate window: 32768 bytes |
Show the full program
# Chapter 2. p23: the 32 KB window of deflate breaks NCD on long texts.
# Deflate (zlib) can only point back 32,768 bytes. Once x is longer than
# that, the second copy in xx can no longer refer to the first, so
# NCD(x, x) jumps towards 1 (Cebrian, Alfonseca and Ortega 2005 report
# the same skew for real compressors). We test texts of growing length
# from the corpus of p11, an exact copy and a 10 % rewrite, and a repair:
# cut both texts at the same token positions into blocks of 600 words
# and average the block NCDs. Corpus 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)
rng = random.Random(20261113)
print("bytes NCD(x,x) NCD(x,y10) blockwise NCD(x,y10)")
for words in (800, 3200, 5600, 6400, 7200, 9600, 19200):
t = script(rng, words)
u = substitute(rng, t, 0.1)
x, y = render(t).encode(), render(u).encode()
blocks = []
for s in range(0, len(t), 600):
bx = render(t[s:s + 600]).encode()
by = render(u[s:s + 600]).encode()
blocks.append(ncd(bx, by))
print("%6d %.4f %.4f %.4f"
% (len(x), ncd(x, x), ncd(x, y), math.fsum(blocks) / len(blocks)))
print("deflate window: %d bytes" % (1 << 15))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 2: Kolmogorov Complexity and Real Compressors: Upper Bounds, Normality and the Window. 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 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