关于「频率漂移:用错频率的代价与重建路由树的时机」,《按需路由树》给出的定量结论是什么?
结论:用错频率的代价约等于相对熵:小漂移几乎无害,漂移 1.0 时每次查找多做 0.678 次决策,大漂移会让频率树比平衡树还差。重建的触发信号不能用样本内的差距,它每个月都会触发;应当用留出检验,让重建只在频率真的变化时发生。到这里,我们已经把路由树的数学讲完了。下一章暂时离开计算机,回到两千多年前的官制与一百五十年前的图书馆,看古人怎样给成百上千的职事与书籍分层,他们说对了什么,又漏掉了什么。
数据口径:书中参数为示意;全部计算由书中程序生成;程序不读写任何文件;本书是非个人化经营建议,任何线上工具目录的改动须由主事者人工复核放行。 书中以标注框区分已发表的证据、可运行的 Python 计算(17 段程序)、原典与作者的假说。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 0.678
| delta | D(p||q) | H+D | Shannon L | in bound | Huffman(q) | excess |
|---|---|---|---|---|---|---|
| 0.00 | 0.000 | 6.372 | 6.824 | yes | 6.406 | 0.000 |
| 0.25 | 0.040 | 6.412 | 6.880 | yes | 6.430 | 0.025 |
| 0.50 | 0.136 | 6.508 | 6.972 | yes | 6.517 | 0.112 |
| 1.00 | 0.758 | 7.130 | 7.614 | yes | 7.083 | 0.678 |
| 2.00 | 2.016 | 8.388 | 8.932 | yes | 8.295 | 1.889 |
| 4.00 | 2.876 | 9.248 | 9.724 | yes | 9.061 | 2.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}
}