用码字集合确定符号边界
变长编码给不同符号分配不同长度的比特串。若某码字也是另一码字的开头,读到它时就可能还不知道该结束当前符号,还是继续读取更长码字;前缀无歧义条件排除了这种等待。
例如0、10、11可作为三个符号的码字,解码者读到0便可立即输出第一个符号,读到1则再读一位决定后两者。反之,0与01同时作码字就不满足前缀条件,尽管“非前缀码”也不必然等于整体不能唯一解码。
参考:[1]
树的叶子代表完整码字
二元前缀码可以画成一棵树,左右边分别代表0和1,完整符号只放在叶子。若一个符号放在另一个符号的祖先节点,祖先路径就成为后者码字的前缀,违反条件;叶子安排让这种情况不会发生。
解码时从根沿输入比特前进,到叶子输出一个符号,再回根处理下一段。Huffman编码用频率构造这样的树,但前缀性质本身并不要求必须使用Huffman算法,也不保证当前树已经最节省平均长度。
符号可解码仍需要消息边界
接收端必须知道相同码表。静态格式可以预先约定,文件也可以携带树或其他足够重建码表的信息;只发送压缩位串,却让解码者猜测每个叶子代表什么,不能保证恢复原消息。
前缀条件解决的是相邻码字怎样拆开,不单独说明整个消息何时结束。文件可记录符号数量或结束标记,并规定末尾字节填充位怎样处理。它也不会让错误比特自动恢复,或替代外层完整性检查。