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

bytesNCD(x,x)NCD(x,y10)blockwise NCD(x,y10)
35570.03190.17880.1653
141460.03630.22690.2009
245370.03690.22030.1884
281770.03930.23260.1951
317080.03870.23510.1937
422520.93300.93780.2010
847610.95890.96050.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