信息论与编码篇---Kraft不等式
如果你觉得它听起来像某个德国物理学家的名字，不用担心，它其实是一个非常简单的判断工具——就像一个"码尺"。
1. Kraft不等式是用来干什么的？
想象你要设计一套不等长编码（比如给汉字编二进制码，有的用2位，有的用3位，有的用4位）。
你的问题是：我想用的这些码字长度（比如 2, 3, 3, 4, 4, 4...），到底存不存在一套即时码（前缀码）？
Kraft不等式就是用来回答这个问题的：给定一组码字长度，如果不满足这个不等式，那肯定不存在即时码；如果满足，则至少存在一种即时码。
2. 公式长什么样？
对于二进制编码，Kraft不等式是：
其中：
n 是码字的个数
li 是第 i 个码字的长度（比特数）
2−li 可以理解为这个码字在码树中占用的"空间"或"权重"
3. 一个通俗的类比：酒店房间分配
想象你开了一家奇怪的酒店，房间都是用二进制编号的：
酒店结构：这栋楼是一棵二叉树。从根出发，向左拐是0，向右拐是1。每层对应码字长度。
房间规则：如果你分配了一个房间给客人，那么这个房间下面的所有子房间（即以此为前缀的更长的码）就不能再住人了（因为是前缀码，不能有冲突）。
Kraft不等式：其实就是房间容量的检查。
举个例子：
你想分配一个长度为1的房间：
0。这占了整棵树的一半（因为以0开头的所有房间都不能用了）。你还想分配三个长度为2的房间：
10、110（不对，110是长度3，我们举例子要一致）。我们换一个例子：
具体算一下：
假设你想用码字长度：1, 2, 2（即一个1位码，两个2位码）。
长度1的码字：占用 1/21/2 的树空间
两个长度2的码字：每个占用 1/41/4 空间，共 1/21/2 空间
合计：1/2+1/2=1
结果：正好等于1，说明树被占满了，存在即时码（比如0、10、11）。
4. 三种情况解读
| 计算结果 | 含义 | 能不能编出即时码？ |
|---|---|---|
| 和 < 1 | 树还有空房间 | 能，而且还有剩余空间 |
| 和 = 1 | 树刚好占满 | 能，空间利用最充分 |
| 和 > 1 | 树装不下了 | 绝对不能 |
5. 生活中的直观理解
Kraft不等式就像装修预算：你手里有1万元（总空间=1）。
每个码字就像一件家具：长度1的家具（比如沙发）占5000元（2−1=0.52−1=0.5），长度2的家具占2500元（2−2=0.252−2=0.25）。
如果你选的所有家具总价超过1万元，那肯定买不起（编不出即时码）。
如果正好1万或不到1万，那就能买（可以编出即时码）。
6. Mermaid总结框图
框图解读：
输入：你手头有一组想要的码字长度。
计算：把每个长度 li代入 2−li，然后求和。
判断：
绿色：如果和 ≤ 1，恭喜！至少存在一种即时码（前缀码）可以实现这些长度。
红色：如果和 > 1，别想了，任何即时码都编不出来，必须改短一些码字。
补充：K=1 时树被完美填满（比如所有叶子节点都被用了）；K<1 时还有空位，可以再加码字。