关于「频率漂移:用错频率的代价与重建路由树的时机」,《按需路由树》给出的定量结论是什么?

结论:用错频率的代价约等于相对熵:小漂移几乎无害,漂移 1.0 时每次查找多做 0.678 次决策,大漂移会让频率树比平衡树还差。重建的触发信号不能用样本内的差距,它每个月都会触发;应当用留出检验,让重建只在频率真的变化时发生。到这里,我们已经把路由树的数学讲完了。下一章暂时离开计算机,回到两千多年前的官制与一百五十年前的图书馆,看古人怎样给成百上千的职事与书籍分层,他们说对了什么,又漏掉了什么。

数据口径:书中参数为示意;全部计算由书中程序生成;程序不读写任何文件;本书是非个人化经营建议,任何线上工具目录的改动须由主事者人工复核放行。 书中以标注框区分已发表的证据、可运行的 Python 计算(17 段程序)、原典与作者的假说。

English version

对照数据表

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

deltaD(p||q)H+DShannon Lin boundHuffman(q)excess
0.000.0006.3726.824yes6.4060.000
0.250.0406.4126.880yes6.4300.025
0.500.1366.5086.972yes6.5170.112
1.000.7587.1307.614yes7.0830.678
2.002.0168.3888.932yes8.2951.889
4.002.8769.2489.724yes9.0612.656
H(p) = 6.372 bits, Huffman on p = 6.406 decisions
查看完整验算程序
# Chapter 6. p61: a tree built for last month's shares costs H + D.
# True shares p: Zipf(1) over N = 300 tools. Stale shares q: the same
# Zipf weights over a ranking perturbed by noise of size delta (seeded,
# illustrative). With code lengths ceil(-log2 q) the expected path is
# bounded by H(p) + D(p||q) <= L < H(p) + D(p||q) + 1 (the wrong-code
# theorem in Cover and Thomas). The Huffman tree built on q is shown
# too, with its excess over the Huffman tree built on the true p.
import heapq
import math
import random

rng = random.Random(20261113)
N = 300


def zipf(n, a):
    w = [1.0 / (i ** a) for i in range(1, n + 1)]
    t = math.fsum(w)
    return [x / t for x in w]


def depths(p):
    items = [(x, i, (i,)) for i, x in enumerate(p)]
    heapq.heapify(items)
    seq, depth = len(p), [0] * len(p)
    while len(items) > 1:
        a, b = heapq.heappop(items), heapq.heappop(items)
        for i in a[2] + b[2]:
            depth[i] += 1
        heapq.heappush(items, (a[0] + b[0], seq, a[2] + b[2]))
        seq += 1
    return depth


p = zipf(N, 1.0)
h = -math.fsum(x * math.log2(x) for x in p)
opt = math.fsum(x * d for x, d in zip(p, depths(p)))
w = zipf(N, 1.0)
noise = [rng.gauss(0.0, 1.0) for _ in range(N)]
print("delta  D(p||q)   H+D    Shannon L  in bound  Huffman(q)  excess")
for delta in (0.0, 0.25, 0.5, 1.0, 2.0, 4.0):
    score = [math.log(i + 1) + delta * noise[i] for i in range(N)]
    order = sorted(range(N), key=lambda i: (score[i], i))
    q = [0.0] * N
    for r, i in enumerate(order):
        q[i] = w[r]
    d = math.fsum(x * math.log2(x / y) for x, y in zip(p, q))
    ls = math.fsum(x * math.ceil(-math.log2(y)) for x, y in zip(p, q))
    lh = math.fsum(x * dd for x, dd in zip(p, depths(q)))
    ok = h + d <= ls < h + d + 1
    print("%5.2f %8.3f %7.3f %10.3f %8s %11.3f %7.3f"
          % (delta, d, h + d, ls, "yes" if ok else "NO", lh, lh - opt))
print("H(p) = %.3f bits, Huffman on p = %.3f decisions" % (h, opt))

唯一数据源与引用

范雅福(Fan, Y.). (2026). 《延迟加载私有工具中枢、数百检查器零初始上下文开销与按需路由树母典》第 6 章「频率漂移:用错频率的代价与重建路由树的时机」(版本 1.0.0). 5D Library. DOI 待发布

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

BibTeX
@book{fan2026257,
  author    = {Fan, Yafu},
  title     = {A Lazy-Loading Private Tool Hub: Near-Zero Opening Context for Hundreds of Checkers and On-Demand Routing Trees},
  year      = {2026},
  publisher = {5D Library},
  edition   = {1.0.0},
  note      = {DOI pending}
}

本书其他章节结论