关于「韦尔霍夫算法拆解:位置、孪生、跳位与没有名字的错误」,《校验码代数与韦尔霍夫算法》给出的定量结论是什么?

结论:第五章补上无名错误:从 Luhn 换到韦尔霍夫,全谱漏检从 207.2 降到 107.1,约减半,两位 MOD 97-10 为 6.8。

数据口径:书中录入量、出错率与成本均为示意参数;全部计算由书中程序生成;本书是非个人化经营建议。 书中以标注框区分已发表的证据、可运行的 Python 计算(19 段程序)、原典与作者的假说。

English version

对照数据表

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

scheme named other total (misses per 10,000 errors)
Luhn117.489.8207.2
EAN 1,3204.689.7294.3
ISBN-10 mod 1111.679.390.8
Verhoeff18.388.8107.1
Damm17.089.0106.0
MOD 97-100.06.86.8
a single check digit lets about 1 in 10 random changes through;
two MOD 97-10 digits let about 1 in 97 through
查看完整验算程序
# Chapter 5. p52: the whole spectrum, including the errors with no name.
# The six named classes are scored exactly (as in p12). The other 1,041
# of Verhoeff's 12,112 errors (other adjacent, other jump, other two-
# digit, three to six digits) have no fixed pattern, so they are drawn
# at random: a random 10-digit string, the stated number of positions
# (inside a window of six, as in a six-digit number) each replaced by a
# different random digit; draws that fall into a named class are thrown
# back. A damaged string passes iff its final state equals the intact
# one, so validity of the random string does not matter. Fixed seed;
# 6,000 draws per class and scheme. Output: misses per 10,000 errors.
import math
import random

rng = random.Random(20261113)
L = 10
NAMED = {"single": 9574, "adj": 1237, "twin": 67, "phon": 59,
         "jump": 99, "jtwin": 35}
OTHER = [("other adjacent", 232, "adj2"), ("other jump", 43, "jmp2"),
         ("other two-digit", 98, "far2"), ("three digits", 169, 3),
         ("four digits", 118, 4), ("five digits", 219, 5),
         ("six digits", 162, 6)]
TOTAL = 12112
DAMM = ["0317598642", "7092154863", "4206871359", "1750983426",
        "6123045978", "3674209581", "5869720134", "8945362017",
        "9438617205", "2581436790"]
T = [[int(ch) for ch in row] for row in DAMM]
SIGMA = [1, 5, 7, 6, 2, 8, 3, 0, 9, 4]
P = [list(range(10))]
for _ in range(7):
    P.append([SIGMA[x] for x in P[-1]])


def d5(i, j):
    if i < 5 and j < 5:
        return (i + j) % 5
    if i < 5:
        return 5 + (i + j) % 5
    if j < 5:
        return 5 + (i - j) % 5
    return (i - j) % 5


def dbl(d):
    return 2 * d if d < 5 else 2 * d - 9


def st_lin(m, g):
    def f(digs):
        s = 0
        for k, d in enumerate(reversed(digs)):
            s = (s + g(k, d)) % m
        return s
    return f


def st_ver(digs):
    c = 0
    for k, d in enumerate(reversed(digs)):
        c = d5(c, P[k % 8][d])
    return c


def st_damm(digs):
    c = 0
    for d in digs:
        c = T[c][d]
    return c


SCHEMES = [
    ("Luhn", st_lin(10, lambda k, d: dbl(d) if k % 2 else d)),
    ("EAN 1,3", st_lin(10, lambda k, d: d * (3 if k % 2 else 1))),
    ("ISBN-10 mod 11", st_lin(11, lambda k, d: d * (k + 1))),
    ("Verhoeff", st_ver),
    ("Damm", st_damm),
    ("MOD 97-10", st_lin(97, lambda k, d: d * pow(10, k, 97))),
]


def named_pattern(o, e):
    # 两位改动是否落入已命名的类(换位、孪生、读音)
    (a, b), (c, d) = o, e
    if (c, d) == (b, a) or (a == b and c == d):
        return True
    return (a, b, c, d) in PHON


PHON = {(a, 0, 1, a) for a in range(2, 10)}
PHON |= {(1, a, a, 0) for a in range(2, 10)}


def damage(body, kind):
    b = body[:]
    w = rng.randrange(L - 5)
    if kind == "adj2":
        pos = [w, w + 1]
    elif kind == "jmp2":
        pos = [w, w + 2]
    elif kind == "far2":
        i = rng.randrange(3)
        pos = [w + i, w + i + rng.randrange(3, 6 - i)]
    else:
        pos = rng.sample(range(w, w + 6), kind)
    for p in pos:
        b[p] = (b[p] + rng.randrange(1, 10)) % 10
    if kind in ("adj2", "jmp2"):
        o = (body[pos[0]], body[pos[1]])
        e = (b[pos[0]], b[pos[1]])
        if named_pattern(o, e) and not (kind == "jmp2" and o + e in PHON):
            return None
    return b


def exact(state):
    r = range(10)
    pats = {"single": [((a,), (b,)) for a in r for b in r if a != b],
            "adj": [((a, b), (b, a)) for a in r for b in r if a != b],
            "twin": [((a, a), (b, b)) for a in r for b in r if a != b],
            "phon": [((a, 0), (1, a)) for a in range(2, 10)]
            + [((1, a), (a, 0)) for a in range(2, 10)],
            "jump": [((a, c, b), (b, c, a)) for a in r for c in r
                     for b in r if a != b],
            "jtwin": [((a, c, a), (b, c, b)) for a in r for c in r
                      for b in r if a != b]}
    out = []
    for name, pairs in pats.items():
        n = len(pairs[0][0])
        miss = tot = 0
        for k0 in range(L - n + 1):
            for pre in range(10):
                for o, e in pairs:
                    tot += 1
                    head = [0] * (L - n - k0 - 1) + [pre]
                    if k0 == L - n:
                        head = []
                    x = head + list(o) + [0] * k0
                    y = head + list(e) + [0] * k0
                    if state(x) == state(y):
                        miss += 1
        out.append(NAMED[name] * miss / tot)
    return math.fsum(out)


print("scheme          named  other  total  (misses per 10,000 errors)")
for name, state in SCHEMES:
    named = exact(state)
    other = []
    for _, cnt, kind in OTHER:
        miss = tot = 0
        while tot < 6000:
            body = [rng.randrange(10) for _ in range(L)]
            bad = damage(body, kind)
            if bad is None:
                continue
            tot += 1
            if state(bad) == state(body):
                miss += 1
        other.append(cnt * miss / tot)
    o = math.fsum(other)
    print("%-15s %6.1f %6.1f %6.1f" % (name, named / TOTAL * 1e4,
                                         o / TOTAL * 1e4,
                                         (named + o) / TOTAL * 1e4))
print("a single check digit lets about 1 in 10 random changes through;")
print("two MOD 97-10 digits let about 1 in 97 through")

唯一数据源与引用

范雅福(Fan, Y.). (2026). 《校验码代数与二面体群韦尔霍夫算法、订单号汇款码书号单字误抄与相邻换位检出率母典》第 5 章「韦尔霍夫算法拆解:位置、孪生、跳位与没有名字的错误」(版本 1.0.0). 5D Library. DOI 待发布

DOI 待发布 · 专著页正式发布后上线(本站暂无专著页) · 5DL-B-297 · v1.0.0 · CC-BY-NC-ND-4.0

BibTeX
@book{fan2026297,
  author    = {Fan, Yafu},
  title     = {The Algebra of Check Digits and Verhoeff's Dihedral-Group Code: Detection Rates for Single-Digit Slips and Adjacent Transpositions in Order, Remittance and Book Numbers},
  year      = {2026},
  publisher = {5D Library},
  edition   = {1.0.0},
  note      = {DOI pending}
}

本书其他章节结论