5D Library › 百卷知识超图拓扑、多模态个人先验编译与自主知识帝国标度律 · English
第三章 压缩与覆盖:十五个原语究竟解释了多少?
描述长度
「十五个核心数学原语覆盖一百个应用领域」是一个关于压缩的说法:一个把每个原语只定义一次、由各卷引用的书库,应当比一百卷各自从头写起要短得多。柯尔莫哥洛夫复杂度,即生成一段文本的最短程序的长度,是理想的度量,但不可计算 (Kolmogorov 1965);最小描述长度原则以明确编码下的长度代替它 (Rissanen 1978),而任何实际的压缩器都只给出上界。p06 用不可压缩的定义构建一个 100 卷的合成书库。
推导
# Chapter 3. p06: How much does a shared library of primitives compress
# a hundred-volume description? Synthetic incidence (shared with p07 and
# p08): 100 volumes each use 2 to 5 of 15 core primitives (popularity
# falling as 1 / rank^0.8) and, with chance 0.25, one of 30 rare ones.
# Each primitive has a random definition of 300 to 580 letters from a
# 32-letter alphabet (5 bits a letter, incompressible by design); each
# use carries 24 letters of parameters. "Separate": every volume spells
# out each definition it uses. "Library": each used definition once,
# then a reference per use. Kolmogorov complexity cannot be computed; bz2
# and lzma sizes are upper bounds on it. (bz2 rather than zlib: zlib's
# output size varies between zlib builds.) Seed 100.
import bz2
import lzma
import random
ALPHA = "abcdefghijklmnopqrstuvwxyz012345"
def incidence(rng):
w = [1 / (j + 1) ** 0.8 for j in range(15)]
vols = []
for _ in range(100):
k = rng.choice((2, 2, 3, 3, 3, 4, 4, 5))
use = set()
while len(use) < k:
use.add(rng.choices(range(15), weights=w)[0])
use = sorted(use)
if rng.random() < 0.25:
use.append(15 + rng.randrange(30))
vols.append(use)
return vols
if __name__ == "__main__":
rng = random.Random(100)
vols = incidence(rng)
defs = ["".join(rng.choice(ALPHA) for _ in range(300 + 7 * j % 281))
for j in range(45)]
used = sorted({j for v in vols for j in v})
sep, ref = [], ["".join("{}:{};".format(j, defs[j]) for j in used)]
for v in vols:
for j in v:
par = "".join(rng.choice(ALPHA) for _ in range(24))
sep.append(defs[j] + par)
ref.append("#{}{}".format(j, par))
a, b = "".join(sep).encode(), "".join(ref).encode()
print(" description raw bytes bz2 bytes lzma bytes")
for name, s in (("separate", a), ("library", b)):
print(" {:<14} {:10,d} {:11,d} {:11,d}".format(
name, len(s), len(bz2.compress(s, 9)),
len(lzma.compress(s, preset=9))))
print(" primitives used: {} ({} core, {} rare)".format(
len(used), sum(j < 15 for j in used), sum(j >= 15 for j in used)))
print(" raw ratio separate / library: {:.2f}".format(len(a) / len(b)))
print(" lzma ratio separate / library: {:.2f}".format(
len(lzma.compress(a, preset=9)) / len(lzma.compress(b, preset=9))))
print(" ideal bits (5 per letter): separate {:,}, library {:,}".format(
5 * sum(len(x) for x in sep), 5 * sum(len(x) for x in ref)))
# description raw bytes bz2 bytes lzma bytes
# separate 124,389 20,291 13,864
# library 20,387 13,167 13,376
# primitives used: 28 (15 core, 13 rare)
# raw ratio separate / library: 6.10
# lzma ratio separate / library: 1.04
# ideal bits (5 per letter): separate 621,945, library 101,935各自写出时,描述共 124,389 字节;使用共享书库时是 20,387 字节,比值 6.10。但一个对原语一无所知的通用压缩器,用 lzma 就能把各自写出的文本压到 13,864 字节,几乎与压缩后的书库(13,376)相同,比值只有 1.04。重复的定义从来就不是信息;任何好的压缩器都会去掉重复。所以原语库的压缩比只有相对于朴素基准才显得很大。它真正的价值不在于更少的比特,而在于有名字、经过核对、可以重复使用的部件。
覆盖
p07 用同一个合成关联结构,问需要多少个原语才能完整覆盖各卷:只有当一卷用到的每个原语都在集合之中时,这一卷才算被覆盖。
推导
# Chapter 3. p07: How many primitives cover how many volumes? The
# synthetic incidence of p06 (same seed, same generator). A volume is
# covered when every primitive it uses is in the chosen set. Greedy
# choice: at each step add the primitive that completes the most
# volumes (ties: the most uses). Seed 100.
import random
NAMES = ("markov", "phase-lock", "weibull", "bregman", "bayes", "kelly",
"power-law", "queue", "entropy", "equilibrium", "stopping",
"diffusion", "least-squares", "fourier", "centrality")
def incidence(rng):
w = [1 / (j + 1) ** 0.8 for j in range(15)]
vols = []
for _ in range(100):
k = rng.choice((2, 2, 3, 3, 3, 4, 4, 5))
use = set()
while len(use) < k:
use.add(rng.choices(range(15), weights=w)[0])
use = sorted(use)
if rng.random() < 0.25:
use.append(15 + rng.randrange(30))
vols.append(use)
return vols
if __name__ == "__main__":
vols = incidence(random.Random(100))
chosen, curve = set(), []
allp = sorted({j for v in vols for j in v})
while len(chosen) < len(allp):
def score(j):
s = chosen | {j}
return (sum(set(v) <= s for v in vols),
sum(j in v for v in vols))
j = max((j for j in allp if j not in chosen), key=score)
chosen.add(j)
curve.append((len(chosen), sum(set(v) <= chosen for v in vols)))
for n, c in curve:
if n in (3, 5, 8, 10, 12, 15) or c == 100:
print(" {:2d} primitives cover {:3d} volumes".format(n, c))
if c == 100:
break
top = sorted(range(15), key=lambda j: -sum(j in v for v in vols))[:4]
print(" most used: " + ", ".join("{} ({})".format(
NAMES[j], sum(j in v for v in vols)) for j in top))
print(" volumes needing a rare primitive: {}".format(
sum(max(v) >= 15 for v in vols)))
# 3 primitives cover 6 volumes
# 5 primitives cover 18 volumes
# 8 primitives cover 36 volumes
# 10 primitives cover 49 volumes
# 12 primitives cover 65 volumes
# 15 primitives cover 82 volumes
# 28 primitives cover 100 volumes
# most used: markov (65), phase-lock (41), bregman (34), weibull (30)
# volumes needing a rare primitive: 18覆盖起初增长得很慢,因为一卷需要它所有的原语:5 个原语覆盖 18 卷,10 个覆盖 49 卷。十五个核心原语覆盖 82 卷。其余 18 卷各需要一个罕见的领域专用算子,覆盖全部 100 卷需要 28 个原语。最常用的原语,即马尔可夫链,出现在 65 卷中。「十五个原语覆盖一百个领域」说的是长尾分布的头部;尾部才是每个领域保留自身特色的地方。
假说 · 尚未验证
作者的诠释(尚未验证): 若按本书库各卷实际程序所用的原语进行标注,最常用的十五个原语能完整覆盖至少四分之三的卷,而完整覆盖全部所需的原语少于其两倍。什么会证明它错: 由两位独立读者标注全部程序并调和后,最常用的十五个原语覆盖的卷少于四分之三,或完整覆盖需要三十个以上的原语。
小结
共享原语库能把朴素的描述缩短六倍,但一个好的压缩器自己就能得到几乎相同的结果,所以原语库所谓的「柯尔莫哥洛夫缩减」主要是相对于重复的缩减。在合成书库中,十五个核心原语覆盖了 100 卷中的 82 卷;完整覆盖需要 28 个。
参考文献
Fan, Y. (2026). Hundred-Volume Knowledge Hypergraphs, Multimodal Personal Prior Compilation and Autonomous Empire Scaling: Cross-Disciplinary Isomorphisms, Zero-Marginal-Cost Replication and Century-Scale Knowledge Preservation [百卷知识超图拓扑、多模态个人先验编译与自主知识帝国标度律] (Version 1.0.0). 5D Library. https://doi.org/10.5281/zenodo.24090260 · Licensed under Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0).