关于「柯尔莫哥洛夫复杂度与压缩器:上界、正规性与窗口」,《压缩距离与洗稿识别》给出的定量结论是什么?
结论:第二章说明压缩只给柯尔莫哥洛夫复杂度的上界,并显示文本一旦超过 zlib 的窗口,完整拷贝的压缩距离会跳到 0.9330。
数据口径:书中的语料、阈值与参数均为示意,所有样本文本由程序生成或作者自拟;全部计算由书中程序生成。 本书的用途是保护原创与发现抄袭,不讨论如何改写他人内容以逃避查重;本书是非个人化经营建议,不是法律意见,书中小工具的每一条标记都须人工复核。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 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 |
查看完整验算程序
# 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}
}