关于「考刻决策树:平均问答次数的熵下界与哈夫曼最优」,《铁板神数的比特账》给出的定量结论是什么?
结论:第二章把考刻写成决策树:十二选一的问题确定 120 分,哈夫曼树平均只要 1.9833 问。
数据口径:书中参数为示意;全部计算由书中程序生成;本书分析结构与概率,不对任何个人作任何占断,也不构成法律或理财建议。 第五章说明一句条文的期望信息量至多 0.5307 比特,按示意规模每分钟有 19.01 人出生。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 1.9833, 120
| prior | k | H bits | bound | Huffman | max |
|---|---|---|---|---|---|
| 8 ke, uniform | 2 | 3.0000 | 3.0000 | 3.0000 | 3 |
| 8 ke, tent 1234 4321 | 2 | 2.8464 | 2.8464 | 2.9000 | 4 |
| 8 ke, tent, 3-way | 3 | 2.8464 | 1.7959 | 1.9000 | 3 |
| 120 fen, uniform | 2 | 6.9069 | 6.9069 | 6.9333 | 7 |
| 120 fen, uniform | 3 | 6.9069 | 4.3578 | 4.4917 | 5 |
| 120 fen, uniform | 12 | 6.9069 | 1.9266 | 1.9833 | 2 |
| double-hour x fen | 12 | 10.4919 | 2.9266 | 2.9819 | 3 |
查看完整验算程序
# 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}
}