关于「柯尔莫哥洛夫复杂度与压缩器:上界、正规性与窗口」,《压缩距离与洗稿识别》给出的定量结论是什么?

结论:第二章说明压缩只给柯尔莫哥洛夫复杂度的上界,并显示文本一旦超过 zlib 的窗口,完整拷贝的压缩距离会跳到 0.9330。

数据口径:书中的语料、阈值与参数均为示意,所有样本文本由程序生成或作者自拟;全部计算由书中程序生成。 本书的用途是保护原创与发现抄袭,不讨论如何改写他人内容以逃避查重;本书是非个人化经营建议,不是法律意见,书中小工具的每一条标记都须人工复核。

English version

对照数据表

下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 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
查看完整验算程序
# 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))

唯一数据源与引用

范雅福(Fan, Y.). (2026). 《归一化压缩距离与柯尔莫哥洛夫复杂度、洗稿伪原创识别与同源话术家族聚类母典》第 2 章「柯尔莫哥洛夫复杂度与压缩器:上界、正规性与窗口」(版本 1.0.0). 5D Library. DOI 待发布

DOI 待发布 · 专著页正式发布后上线(本站暂无专著页) · 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}
}

本书其他章节结论