微信号:tiankonguse-code

介绍:这里是tiankonguse在代码世界里学习时的记录

从汉字输入到香农理论

2017-05-22 08:50 袁小康

(朋友独自一人去三亚一周,拍于三亚)


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

这里一般一周更新两篇文章。
今天记录一下信息熵,没有说清楚。

作为回馈,送大家一个电影《非凡任务》,文章末尾点击原文免费观看,名额有限先到先得。

零、背景

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

一、汉字输入最优问题

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

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

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

 
           
  1. 在信息世界,熵越高,则能传输越多的信息,熵越低,则意味着传输的信息越少。

  2. 比如对于无损压缩,压缩后的消息可以通过较少的比特单位传递,因此压缩消息的每个比特单位能携带更多的信息,也就是说压缩信息的熵更加高。  

对于我们这个汉字输入,自然是熵越高越好了,熵越高单位比特储存的信息越多,我们可以敲的键盘字段就越少了。
那怎么衡量熵是多少呢?
有对应的公式: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)

三、结论

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

对了现在开通了公众号和小密圈。
博客记录所有内容。
技术含量最高的文章放在公众号发布。
比较好玩的算法放在小密圈发布。
PS:想免费进去圈子的同学可以加我微信,我可以免费要求进入圈子。

其他文章

每秒千万级系统架构篇  每秒千万级系统诞生篇  谈谈cache  排名算法 hash算法 Bloom Filter GDB CPU与内存 协议 JPEG


关于作者

曾是一名ACMer,现在是鹅厂视频部门的后台开发。

这里主要记录工作中的技术架构与经验、计算机相关的技术、数学、算法、生活上好玩的东西。

长按二维码支持作者,了解作者发布的最新好玩的东西。


 
天空的代码世界 更多文章 mysql中一个索引与FROM_UNIXTIME的问题 AES对称加密 聊聊WannaCry电脑勒索病毒 今天得到一个不幸的消息 2017 ACM女生专场比赛记录
猜您喜欢 [译]如何给变量取个简短且无歧义的名字 基于Mesos和Docker的分布式计算平台 为小程序而生的小(jiao)手架 IC卡破解 高校水卡 日本,让我感触的那些细节