关于「n 元组、MinHash 与局部敏感哈希:百万篇里的第一轮初筛」,《压缩距离与洗稿识别》给出的定量结论是什么?

结论:第四章说明为近似拷贝设计的局部敏感哈希会漏掉改写,膝点 0.4204 时三成改写只有 0.5088 进入候选,须把膝点压到 0.1250。

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

English version

对照数据表

下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 0.1250, 0.4204, 0.5088

sb=64 r= 2b=32 r= 4b=16 r= 8b= 8 r=16
0.9001.00001.00000.99990.8059
0.7001.00000.99980.61330.0263
0.5001.00000.87320.06070.0001
0.3851.00000.50880.00770.0000
0.3000.99760.22910.00100.0000
0.1560.79340.01880.00000.0000
0.1000.47440.00320.00000.0000
0.0330.06740.00000.00000.0000
knee s*0.12500.42040.70710.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}
}

本书其他章节结论