关于「n 元组、MinHash 与局部敏感哈希:百万篇里的第一轮初筛」,《压缩距离与洗稿识别》给出的定量结论是什么?
结论:第四章说明为近似拷贝设计的局部敏感哈希会漏掉改写,膝点 0.4204 时三成改写只有 0.5088 进入候选,须把膝点压到 0.1250。
数据口径:书中的语料、阈值与参数均为示意,所有样本文本由程序生成或作者自拟;全部计算由书中程序生成。 本书的用途是保护原创与发现抄袭,不讨论如何改写他人内容以逃避查重;本书是非个人化经营建议,不是法律意见,书中小工具的每一条标记都须人工复核。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 0.1250, 0.4204, 0.5088
| s | b=64 r= 2 | b=32 r= 4 | b=16 r= 8 | b= 8 r=16 |
| 0.900 | 1.0000 | 1.0000 | 0.9999 | 0.8059 |
| 0.700 | 1.0000 | 0.9998 | 0.6133 | 0.0263 |
| 0.500 | 1.0000 | 0.8732 | 0.0607 | 0.0001 |
| 0.385 | 1.0000 | 0.5088 | 0.0077 | 0.0000 |
| 0.300 | 0.9976 | 0.2291 | 0.0010 | 0.0000 |
| 0.156 | 0.7934 | 0.0188 | 0.0000 | 0.0000 |
| 0.100 | 0.4744 | 0.0032 | 0.0000 | 0.0000 |
| 0.033 | 0.0674 | 0.0000 | 0.0000 | 0.0000 |
| knee s* | 0.1250 | 0.4204 | 0.7071 | 0.8781 |
| simulation, b=32 r=4 (300 pairs per level, 100-gram sets) | ||||
| s = 0.385 (exact 0.3889): simulated 0.507, formula 0.523 | ||||
| s = 0.156 (exact 0.1561): simulated 0.003, formula 0.019 | ||||
| s = 0.033 (exact 0.0309): simulated 0.000, formula 0.000 |
查看完整验算程序
# Chapter 4. p42: banding MinHash signatures (locality-sensitive hashing).
# Split k = 128 MinHash values into b bands of r rows; two texts become a
# candidate pair if any band agrees in all r rows. For Jaccard s:
# P(candidate) = 1 - (1 - s^r)^b, steepest near s* = (1/b)^(1/r).
# We print the S-curve for four layouts, then check the formula by
# simulation on synthetic set pairs of exact Jaccard s (300 pairs each).
# The levels 0.385, 0.156 and 0.033 are the mean word 3-gram Jaccard of
# rewrites at rates 0.3, 0.6 and 1.0 in p11. Set elements are random
# 40-bit ids: linear hashes of consecutive integers are not min-wise
# independent and would bias the check.
import math
import random
PR = (1 << 61) - 1
hr = random.Random(97)
AB = [(hr.randrange(1, PR), hr.randrange(PR)) for _ in range(128)]
def p_cand(s, b, r):
return 1.0 - (1.0 - s ** r) ** b
LAYOUTS = ((64, 2), (32, 4), (16, 8), (8, 16))
LEVELS = (0.9, 0.7, 0.5, 0.385, 0.3, 0.156, 0.1, 0.033)
print("s " + " ".join("b=%2d r=%2d" % br for br in LAYOUTS))
for s in LEVELS:
print("%.3f " % s + " ".join("%.4f" % p_cand(s, b, r)
for b, r in LAYOUTS))
print("knee s* " + " ".join("%.4f" % (1.0 / b) ** (1.0 / r)
for b, r in LAYOUTS))
rng = random.Random(20261113)
print("simulation, b=32 r=4 (300 pairs per level, 100-gram sets)")
for s in (0.385, 0.156, 0.033):
hits = 0
both = round(200 * s / (1 + s))
for t in range(300):
ids = [rng.getrandbits(40) for _ in range(200 - both)]
A = set(ids[:100])
B = set(ids[:both] + ids[100:])
sa = [min((a * v + c) % PR for v in A) for a, c in AB]
sb = [min((a * v + c) % PR for v in B) for a, c in AB]
same = any(sa[i:i + 4] == sb[i:i + 4] for i in range(0, 128, 4))
hits += same # step
exact = (both / (200.0 - both))
print(" s = %.3f (exact %.4f): simulated %.3f, formula %.3f"
% (s, exact, hits / 300, p_cand(exact, 32, 4)))唯一数据源与引用
范雅福(Fan, Y.). (2026). 《归一化压缩距离与柯尔莫哥洛夫复杂度、洗稿伪原创识别与同源话术家族聚类母典》第 4 章「n 元组、MinHash 与局部敏感哈希:百万篇里的第一轮初筛」(版本 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}
}