从汉字输入到香农理论

作者: | 更新日期:

今天重读汉字输入问题,然后与香农扯上关系,发现香农好厉害。

大家好,这里是tiankonguse的公众号(tiankonguse-code)。
tiankonguse曾是一名ACMer,现在是鹅厂视频部门的后台开发。
这里主要记录算法,数学,计算机技术等好玩的东西。

这篇文章从公众号tiankonguse-code自动同步过来。
如果转载请加上署名:公众号tiankonguse-code,并附上公众号二维码,谢谢。

零、背景

今天看一个问题:比较好的输入法输入一个汉字平均需要敲多少次键盘?
有人提到香农,查了资料后把我带进信息论里面了,原来这是一个基础理论比较完善的领域。

一、汉字问题

对于这个问题在数学书显然是概率问题。
如果你听过哈夫曼编码的话,发现这个其实就是哈夫曼编码问题。
对于常用的汉字使用较短的编码,对于不常用的字使用较长的编码,这样平均下来每个汉字的编码就比较短了。

假定每一个汉字的频率是p1, p2, p3, ..., pn
它们编码的长度是L1, L2, L3, ..., Ln
那么,平均编码长度是p1×L1 + p2×L2 + ... + pn×Ln

在香农的信息理论中,有个词可以评估这个平均长度:信息熵。
可能有人会问信息熵是什么?
这篇文章不做深入解释这个概念了,简单几句话不容易说清楚。
下面是维基百科上摘的几句话:

在信息世界,熵越高,则能传输越多的信息,熵越低,则意味着传输的信息越少。
比如对于无损压缩,压缩后的消息可以通过较少的比特单位传递,因此压缩消息的每个比特单位能携带更多的信息,也就是说压缩信息的熵更加高。  

对于我们这个汉字输入,自然是熵越高越好了,熵越高储存的信息越多,我们可以敲的键盘字段就越少了。
那怎么衡量熵是多少呢?
有对应的公式:H = -p1 * log(p1) - ... - pn * log(pn)

常用汉字大概有6700个,带入这个熵公式可以得到汉字输入的熵大概为10。
然后输入需要使用26个字母,我们可以列出一个方程来H = -pv * log(26),于是算出平均敲键盘的次数就是H / log(26) = 2.1次

如果我们把一个汉字改成一个词语的话,就可以计算出词的熵了。
这样的好处是每个汉字的平均信息熵会减少一些,从而可以使得平均输入一个汉字需要敲更少的键盘。
现在的输入法大多都是基于词来做设计的,这样可以帮助用户减少敲更多的键盘。

当然,实际上没有输入法能到达理论上的最优,引入越优的输入法,进行编码的复杂度越高,这增加了用户的使用成本。
所以那些比较复杂的输入法,虽然有更高的输入法效率,但是一直不能被大家广为使用,比如王码输入法,五笔输入法。
而对于简单的拼音输入法,在稍微牺牲了一些东西后,可以让用户快速上手。

当然不从用户的角度看,从其他角度看,输入速度上更快时自然会在其他地方付出成本。
比如这个输入法需要更多的内存来储存模型数据,需要消耗更多的CPU来计算模型。

通信理论

上面的问题使用哈夫曼思想,大家都可以理解。
使用信息熵来解释,就有点抽象了,于是我去查阅了信息熵的资料,发现通信用于这个概念已经使用的很溜了。

当年香农就是为了通信建立数学理论时提出这些的。
看看香农的历史,人们对他的评价相当高。
物理界有牛顿,计算机界有图灵、冯诺依曼, 电子通信界就是香农。

香农当时发表的几篇论文,相当牛叉,奠定了通信界的基础理论知识。

比如下面两篇论文,可以看看,现在仍然不会过时。
公众号回复括号内内容可以得到这两篇论文。

1938年《保密系统的通信理论》(Communication Theory of Secrecy Systems)
1948年《通信的数学理论》(A mathematical theory of communication)

三、结论

熵是一个很有意思的话题,后面我看看能不能使用一些通俗易懂的话来解释一下。

对了现在开通了公众号和小密圈。
博客记录所有内容。
技术含量最高的文章放在公众号发布。
比较好玩的算法放在小密圈发布。
小密圈这周接受免费加入,欢迎大家加入看各种算法的思路。

长按图片关注公众号,接受最新文章消息。

点击查看评论

关注公众号,接收最新消息

关注小密圈,学习各种算法

tiankonguse +
穿越