中文 Huffman 编码及其对中文输入方案的启发

Huffman 编码简介

给定一个消息集合 $S=\{s_1,\cdots,s_n\}$，他们有各自的频率 $p_1,\cdots,p_n$。现在使用含有 $k$ 个符号的字母表 $\Sigma=\{\sigma_1,\cdots,\sigma_k\}$ 对其进行编码。

Huffman 编码的构造方式是：

• 把消息放入一个优先队列，按频率从低到高排列；
• 从队列中取出 $k$ 个最低频的消息，指定他们编码的最后一位分别为 $\sigma_1,\cdots,\sigma_k$，然后把他们合并为一组，再放入队列；
• 重复上述操作直至所有消息被合并为 1 组，此时每个消息陆续获得的编码组合起来就是他们最终的编码。
• 经过编码后，各个消息的编码记为 $C_{\mathrm H}=\{c_1,\cdots,c_n\}$

用这种方式构造出来的编码为前缀码，也即不存在任何一个编码是另一个编码的前缀。可以从理论上证明，这种方法构造出来的编码码长是最短的，其中码长定义为

$$l[C]=\sum_ip_i\operatorname{len}c_i;\quad C_{\mathrm H}=\arg\min_C l[C]$$

对于中文输入来说，编码当然需要符合一定的规律，而且也不宜采用前缀码，而是更多地采用顶功的方式来取得较高的编码效率。但是，如果观察 Huffman 编码这个最优前缀码对不同长度编码空间的利用情况，也许可以启发顶功方案的设计，来尽可能贴近 Huffman 编码所给出的理论极限。

下面我们在以字为单位的编码和以词为单位的编码两种情况下来计算出 Huffman 编码，并讨论什么样的顶功方案能接近 Huffman 编码给出的极限。所使用的语料为综合各个社交媒体平台的语料，分词算法为 jieba 库的默认分词。

为了尽可能接近实际输入的情况，分词后去除了非汉字（定义为 0x4E00 ~ 0x9FFF 的符号），编码采用 26 个字母和空格，不使用标点符号和数字。

另注：在词编码的情况下，上述码长定义与通常中文编码所讨论的码长有所不同：中文编码的码长是除以总汉字数而不是总词数，因此实际上的码长应该为

$$l_{\mathrm{zh}}[C]=\frac{l[C]}{\sum_ip_i\operatorname{len}s_i}$$

不过，这个值和 Huffman 编码的码长成正比关系，所以 Huffman 编码仍然是中文编码意义上的最优编码。

Huffman 词编码与词顶功方案

为便于讨论，我们对一字词和多字词分别统计。分词得到一字词 9551 个，多字词 882461 个。在下表中，我们用 a : b 的格式表示该码长对应的一字词和多字词数量。我们还将两个实际的顶功方案（声笔四拼、声笔简码三顶和星空键道）放在一起，计算他们按照编码规则理论上可以具有的编码空间，与 Huffman 编码比较。

这几个顶功方案的最长码都是 6 码，而 Huffman 词编码的最长码也是 6 码，不过下面我们仅对比前 4 码的数据：

码长	Huffman	声笔四拼	声笔简码三顶	星空键道
1	5 : 0	1 : 0	1 : 0	1 : 0
2	129 : 155	126 : 0	126 : 0	21 : 105
3	1011 : 4874	525 : 2646	525 : 11907	2646 : 525
4	2178 : 54733	2625 : 251811	2625 : 57330	11025 : 240786

注：不考虑标点顶屏的情况下，声笔四拼和星空键道都没有一键字或词，但是我们假定「空格」本身是一个一键字，因此数量记作 1.

可见声笔四拼、声笔简码三顶、星空键道这三个方案和 Huffman 编码给出的分布均有一定的差异。主要问题似乎在于二键字或二键词的数量相对偏少，而更多的空间分配给了长码。

Huffman 字编码与字顶功方案

字共 10453 个。我们将实际的顶功方案声笔飞单和一个假想的一二码混顶方案（16 大集合、5 小集合、5 一码顶小集合）与该 Huffman 编码比较。声笔飞单最长码是 4 码，但是 Huffman 字编码最长码是 6 码。

码长	Huffman	声笔飞单	一二码混顶
1	8	1	6
2	435	567	457
3	2008	2730	2205
4	2540	13650	11025

可见二码顶本身就和 Huffman 编码极为相似，刻意拟合后的一二码混顶更加相似。