关于「可导航的树:字母序约束的价格与逐层误选的累积」,《按需路由树》给出的定量结论是什么?

结论:可导航的树必须保持语义次序。理论上这最多比霍夫曼树多花约一次决策;在齐普夫分布下,程序 p31 算出的实际代价只有十分之一次左右,随机次序下为 0.112。真正的不确定性在误选:路由树能否提高准确率,取决于误选随菜单长度变化的规律,而这个规律至今没有可靠的公开测量。下一章暂时把准确率放在一边,回到词元与往返,问一个更实际的问题:给定三百个工具,到底该分几层、每层多宽,哪些工具值得直接挂在根上?

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

English version

对照数据表

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

H = 6.372 bits; Huffman L = 6.406
orderalphabetic Lminus Huffmanminus H
sorted by share6.4060.0000.034
hot in the middle6.4160.0100.044
random order 16.5180.1120.146
random order 26.4660.0600.094
Gilbert-Moore bound: alphabetic L < H + 2 = 8.372
查看完整验算程序
# Chapter 3. p31: the price of a tree that can be navigated by meaning.
# A Huffman tree groups tools by frequency, so its inner nodes have no
# meaning a router could read. A navigable tree must keep tools in a
# fixed semantic order (adjacent tools share a parent): an alphabetic
# tree (Gilbert and Moore 1959; Hu and Tucker 1971). The optimal one is
# found here by interval dynamic programming. N = 300 tools; Zipf(1)
# shares placed in four orders (seeded shuffles are illustrative).
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 entropy(p):
    return -math.fsum(x * math.log2(x) for x in p if x > 0)


def huff_l(p):
    items = [(x, i) for i, x in enumerate(p)]
    heapq.heapify(items)
    seq, terms = len(p), []
    while len(items) > 1:
        a, b = heapq.heappop(items), heapq.heappop(items)
        w = a[0] + b[0]
        terms.append(w)
        heapq.heappush(items, (w, seq))
        seq += 1
    return math.fsum(terms)


def alpha_l(p):
    n = len(p)
    pre = [0.0]
    for i in range(n):
        pre.append(math.fsum(p[:i + 1]))
    cost = [[0.0] * n for _ in range(n)]
    root = [[i] * n for i in range(n)]
    for span in range(2, n + 1):
        for i in range(n - span + 1):
            j = i + span - 1
            lo = root[i][j - 1]
            hi = root[i + 1][j] if i + 1 <= j else j - 1
            best, arg = None, lo
            for m in range(lo, min(hi, j - 1) + 1):
                c = cost[i][m] + cost[m + 1][j]
                if best is None or c < best:
                    best, arg = c, m
            cost[i][j] = best + (pre[j + 1] - pre[i])
            root[i][j] = arg
    return cost[0][n - 1]


base = zipf(N, 1.0)
orders = [("sorted by share", list(base))]
mid = sorted(base)
orders.append(("hot in the middle", mid[0::2] + mid[1::2][::-1]))
for s in range(2):
    q = list(base)
    rng.shuffle(q)
    orders.append(("random order %d" % (s + 1), q))
h = entropy(base)
print("H = %.3f bits; Huffman L = %.3f" % (h, huff_l(base)))
print("order               alphabetic L  minus Huffman  minus H")
for name, q in orders:
    a = alpha_l(q)
    print("%-19s %12.3f %13.3f %9.3f"
          % (name, a, a - huff_l(base), a - h))
print("Gilbert-Moore bound: alphabetic L < H + 2 = %.3f" % (h + 2))

唯一数据源与引用

范雅福(Fan, Y.). (2026). 《延迟加载私有工具中枢、数百检查器零初始上下文开销与按需路由树母典》第 3 章「可导航的树:字母序约束的价格与逐层误选的累积」(版本 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}
}

本书其他章节结论