关于「霍夫曼构树:多叉合并、哑叶补齐与菜单代价」,《按需路由树》给出的定量结论是什么?
结论:多叉霍夫曼树必须先补哑叶,否则十叉树会多出四分之一以上的决策。在小规模上,霍夫曼树与穷举的最优解在 720 个实例中全部相等。决策次数不是词元:每次决策要读一屏菜单,词元意义上的最优分支数在跳开销为零时约为 2.72,跳开销为 80 个词元时约为 5.09。可是本章一直回避了一个问题:霍夫曼树把冷门工具按频率胡乱拼成一枝,模型在菜单上看到的是一个没有名字的节点,它凭什么知道要找的工具在这一枝里?下一章回答这个问题,并给出它的价格。
数据口径:书中参数为示意;全部计算由书中程序生成;程序不读写任何文件;本书是非个人化经营建议,任何线上工具目录的改动须由主事者人工复核放行。 书中以标注框区分已发表的证据、可运行的 Python 计算(17 段程序)、原典与作者的假说。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 10, 2.72, 5.09, 80
| k | tokens HOP=0 | bound | tokens HOP=80 | bound |
| 2 | 320.3 | 318.6 | 832.7 | 828.4 |
| 3 | 305.2 | 301.5 | 630.7 | 623.2 |
| 4 | 325.1 | 318.6 | 585.1 | 573.5 |
| 5 | 350.9 | 343.0 | 575.4 | 562.6 |
| 6 | 379.9 | 369.8 | 582.5 | 567.0 |
| 8 | 441.4 | 424.8 | 618.0 | 594.7 |
| 10 | 499.3 | 479.6 | 659.0 | 633.0 |
| 16 | 682.6 | 637.2 | 819.1 | 764.7 |
| 32 | 1124.5 | 1019.5 | 1236.9 | 1121.5 |
| flat menu of all 300 one-line entries: 7500 tokens | ||||
| HOP= | 0: continuous optimum k* = 2.72 | |||
| HOP= 80: continuous optimum k* = 5.09 | ||||
| HOP=400: continuous optimum k* = 11.26 |
查看完整验算程序
# Chapter 2. p23: decisions are not tokens; the menu has to be read.
# Each routing decision reads a k-line menu (S tokens a line) and pays
# a fixed hop overhead HOP (call framing, reply envelope). Per lookup
# the router pays (HOP + k S) per decision, so the token bound is
# (HOP + k S) H / log2(k), not H. Shown for HOP = 0 and HOP = 80, with
# the padded k-ary Huffman tree on N = 300 Zipf(1) tools. The real
# optimum k solves k (ln k - 1) = HOP / S. S, HOP are illustrative.
import heapq
import math
N, S = 300, 25
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 entropy(p):
return -math.fsum(x * math.log2(x) for x in p if x > 0)
def huff_l(p, k):
items = [(x, i, (i,)) for i, x in enumerate(p)]
seq, pad = len(p), 0
while k > 2 and (len(items) + pad - 1) % (k - 1):
pad += 1
for _ in range(pad):
items.append((0.0, seq, ()))
seq += 1
heapq.heapify(items)
depth = [0] * len(p)
while len(items) > 1:
kids = [heapq.heappop(items) for _ in range(min(k, len(items)))]
leaves = ()
for c in kids:
for i in c[2]:
depth[i] += 1
leaves += c[2]
heapq.heappush(items, (math.fsum(c[0] for c in kids), seq, leaves))
seq += 1
return math.fsum(x * d for x, d in zip(p, depth))
def k_star(ratio):
lo, hi = 1.0001, 1000.0
for _ in range(200):
mid = (lo + hi) / 2
if mid * (math.log(mid) - 1) < ratio:
lo = mid
else:
hi = mid
return lo
p = zipf(N, 1.0)
h = entropy(p)
print(" k tokens HOP=0 bound tokens HOP=80 bound")
for k in (2, 3, 4, 5, 6, 8, 10, 16, 32):
lk = huff_l(p, k)
b = h / math.log2(k)
print("%3d %10.1f %8.1f %12.1f %8.1f"
% (k, lk * k * S, b * k * S, lk * (80 + k * S),
b * (80 + k * S)))
print("flat menu of all %d one-line entries: %d tokens" % (N, N * S))
for hop in (0, 80, 400):
print("HOP=%3d: continuous optimum k* = %.2f" % (hop, k_star(hop / S)))唯一数据源与引用
范雅福(Fan, Y.). (2026). 《延迟加载私有工具中枢、数百检查器零初始上下文开销与按需路由树母典》第 2 章「霍夫曼构树:多叉合并、哑叶补齐与菜单代价」(版本 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}
}