如果你觉得它听起来像某个德国物理学家的名字不用担心它其实是一个非常简单的判断工具——就像一个码尺。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/21/21结果正好等于1说明树被占满了存在即时码比如0、10、11。4. 三种情况解读计算结果含义能不能编出即时码和 1树还有空房间能而且还有剩余空间和 1树刚好占满能空间利用最充分和 1树装不下了绝对不能5. 生活中的直观理解Kraft不等式就像装修预算你手里有1万元总空间1。每个码字就像一件家具长度1的家具比如沙发占5000元2−10.52−10.5长度2的家具占2500元2−20.252−20.25。如果你选的所有家具总价超过1万元那肯定买不起编不出即时码。如果正好1万或不到1万那就能买可以编出即时码。6. Mermaid总结框图框图解读输入你手头有一组想要的码字长度。计算把每个长度 li代入 2−li然后求和。判断绿色如果和 ≤ 1恭喜至少存在一种即时码前缀码可以实现这些长度。红色如果和 1别想了任何即时码都编不出来必须改短一些码字。补充K1 时树被完美填满比如所有叶子节点都被用了K1 时还有空位可以再加码字。