关于「线性账单:一次性加载的上下文开销与熵下界」,《按需路由树》给出的定量结论是什么?

结论:指数为零时,熵是 8.229 比特,霍夫曼树要 8.293 次决策,比平衡树只少 0.079 的份额:大家一样常用,按频率排也排不出什么。指数为一时,熵是 6.372,霍夫曼树是 6.406,差距 0.034,比平衡树少了 0.288。指数为二时,熵只有 2.324,霍夫曼树是 2.379,比平衡树少了 0.736。五行里霍夫曼树与熵的差距都不超过 0.065,远小于香农定理允许的一。最后两列是八叉树:以三次二选一折合一次八选一,指数为一时熵折合 2.124 次八选一,八叉霍夫曼树实际要 2.207 次。

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

English version

对照数据表

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

a H bits L Huff L-H balanced saved H/3 L8
0.08.2298.2930.06590.0792.743 2.900
0.67.7477.7770.03090.1362.582 2.651
1.06.3726.4060.03490.2882.124 2.207
1.44.4084.4680.06190.5041.469 1.597
2.02.3242.3790.05690.7360.775 1.139
查看完整验算程序
# Chapter 1. p12: how close a Huffman tree comes to the entropy bound.
# For N = 300 tools with Zipf call shares of exponent a, compare the
# entropy H (bits), the expected number of binary routing decisions L
# of the Huffman tree (Huffman 1952), and a balanced tree that ignores
# frequency (ceil(log2 N) decisions). Shannon's bound: H <= L < H + 1.
# The same for an 8-ary tree, measured in 8-way decisions (H / 3).
# Exponents are illustrative; a = 0 means every tool is equally used.
import heapq
import math

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 entropy(p):
    return -math.fsum(x * math.log2(x) for x in p if x > 0)


def huffman_depths(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 depth


bal = math.ceil(math.log2(N))
print("   a   H bits  L Huff  L-H    balanced  saved   H/3   L8")
for a in (0.0, 0.6, 1.0, 1.4, 2.0):
    p = zipf(N, a)
    h = entropy(p)
    d2 = huffman_depths(p, 2)
    d8 = huffman_depths(p, 8)
    l2 = math.fsum(x * d for x, d in zip(p, d2))
    l8 = math.fsum(x * d for x, d in zip(p, d8))
    print("%4.1f %8.3f %7.3f %6.3f %7d %8.3f %6.3f %5.3f"
          % (a, h, l2, l2 - h, bal, 1 - l2 / bal, h / 3, l8))

唯一数据源与引用

范雅福(Fan, Y.). (2026). 《延迟加载私有工具中枢、数百检查器零初始上下文开销与按需路由树母典》第 1 章「线性账单:一次性加载的上下文开销与熵下界」(版本 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}
}

本书其他章节结论