关于「考刻决策树:平均问答次数的熵下界与哈夫曼最优」,《铁板神数的比特账》给出的定量结论是什么?

结论:第二章把考刻写成决策树:十二选一的问题确定 120 分,哈夫曼树平均只要 1.9833 问。

数据口径:书中参数为示意;全部计算由书中程序生成;本书分析结构与概率,不对任何个人作任何占断,也不构成法律或理财建议。 第五章说明一句条文的期望信息量至多 0.5307 比特,按示意规模每分钟有 19.01 人出生。

English version

对照数据表

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

priorkH bitsboundHuffmanmax
8 ke, uniform23.00003.00003.00003
8 ke, tent 1234 432122.84642.84642.90004
8 ke, tent, 3-way32.84641.79591.90003
120 fen, uniform26.90696.90696.93337
120 fen, uniform36.90694.35784.49175
120 fen, uniform126.90691.92661.98332
double-hour x fen1210.49192.92662.98193
查看完整验算程序
# Chapter 2. p21: Ke-checking as a decision tree. For a target with
# prior p, any tree of k-way questions needs on average at least
# H(p) / log2 k questions (Shannon), and Huffman's construction reaches
# the best average (within one question of the bound). Priors are
# illustrative: uniform over 8 ke or 120 fen, and a "tent" prior over 8
# ke (weights 1 2 3 4 4 3 2 1) for a client who says "about the middle
# of the double-hour".
import heapq
import math


def entropy(p):
    return -math.fsum(x * math.log2(x) for x in p if x > 0)


def huffman_depths(p, k):
    # k-ary Huffman; pad with zero-weight leaves so (n - 1) % (k - 1) == 0
    n = len(p)
    pad = 0
    while (n + pad - 1) % (k - 1):
        pad += 1
    heap = [(w, i, (i,)) for i, w in enumerate(list(p) + [0.0] * pad)]
    heapq.heapify(heap)
    depth = [0] * (n + pad)
    tick = n + pad
    while len(heap) > 1:
        group = [heapq.heappop(heap) for _ in range(k)]
        leaves = ()
        for _, _, lv in group:
            for j in lv:
                depth[j] += 1
            leaves += lv
        w = math.fsum(g[0] for g in group)
        heapq.heappush(heap, (w, tick, leaves))
        tick += 1
    return depth[:n]


def report(name, w, k):
    tot = math.fsum(w)
    p = [x / tot for x in w]
    h = entropy(p)
    d = huffman_depths(p, k)
    avg = math.fsum(pi * di for pi, di in zip(p, d))
    print("  {:<22}{:>3}  {:7.4f}  {:7.4f}  {:7.4f}  {:>3}".format(
        name, k, h, h / math.log2(k), avg, max(d)))


print("  prior                  k  H bits   bound    Huffman  max")
report("8 ke, uniform", [1] * 8, 2)
report("8 ke, tent 1234 4321", [1, 2, 3, 4, 4, 3, 2, 1], 2)
report("8 ke, tent, 3-way", [1, 2, 3, 4, 4, 3, 2, 1], 3)
report("120 fen, uniform", [1] * 120, 2)
report("120 fen, uniform", [1] * 120, 3)
report("120 fen, uniform", [1] * 120, 12)
report("double-hour x fen", [1] * 1440, 12)

唯一数据源与引用

范雅福(Fan, Y.). (2026). 《铁板神数考刻分决策树、条文库仿射编码与信息熵套取下界》第 2 章「考刻决策树:平均问答次数的熵下界与哈夫曼最优」(版本 1.0.0). 5D Library. DOI 待发布

DOI 待发布 · 专著页正式发布后上线(本站暂无专著页) · 5DL-B-157 · v1.0.0 · CC-BY-NC-ND-4.0

BibTeX
@book{fan2026157,
  author    = {Fan, Yafu},
  title     = {Tieban Shenshu Ke-Fen Decision Trees, Affine Coding of the Verse Bank and Entropy Lower Bounds on Elicitation},
  year      = {2026},
  publisher = {5D Library},
  edition   = {1.0.0},
  note      = {DOI pending}
}

本书其他章节结论