关于「霍夫曼构树:多叉合并、哑叶补齐与菜单代价」,《按需路由树》给出的定量结论是什么?

结论:多叉霍夫曼树必须先补哑叶,否则十叉树会多出四分之一以上的决策。在小规模上,霍夫曼树与穷举的最优解在 720 个实例中全部相等。决策次数不是词元:每次决策要读一屏菜单,词元意义上的最优分支数在跳开销为零时约为 2.72,跳开销为 80 个词元时约为 5.09。可是本章一直回避了一个问题:霍夫曼树把冷门工具按频率胡乱拼成一枝,模型在菜单上看到的是一个没有名字的节点,它凭什么知道要找的工具在这一枝里?下一章回答这个问题,并给出它的价格。

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

English version

对照数据表

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

ktokens HOP=0boundtokens HOP=80bound
2320.3318.6832.7828.4
3305.2301.5630.7623.2
4325.1318.6585.1573.5
5350.9343.0575.4562.6
6379.9369.8582.5567.0
8441.4424.8618.0594.7
10499.3479.6659.0633.0
16682.6637.2819.1764.7
321124.51019.51236.91121.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}
}

本书其他章节结论