前缀码

前缀码（prefix code）是一类具有特殊结构的变长码，其核心性质是：没有任何一个码字是另一个码字的前缀。这一性质保证了前缀码一定是唯一可译的，而且解码过程可以逐符号即时完成，无需向前搜索。因此前缀码也称为即时码（instantaneous code）。

前缀码的构造可以直观地通过与树结构的对应关系来理解。在 $D$ 进制前缀码中，每个码字对应一棵 $D$ 叉树的叶子节点，码字的长度即为从根到该叶子的路径长度。前缀条件恰好对应于”所有码字都是叶子节点”这一树结构性质——任何内部节点都不能被用作码字。

前缀码的存在性由 Kraft 不等式刻画。Kraft 不等式同时也是判断一组给定码长能否构造出前缀码的充要条件。常见的 Huffman 编码和 Shannon 编码都属于前缀码。前缀码在实际编码系统中得到广泛应用，其即时解码特性使得编码和解码过程都拥有较低的计算复杂度。