人在德国社区 - Powered by Discuz! Board

标题: 数学之美系列二十三输入一个汉字需要敲多少个键 — 谈谈香农第一定律 [打印本页]

作者: qquchn 时间: 2007-12-4 16:09 标题: 数学之美系列二十三输入一个汉字需要敲多少个键 — 谈谈香农第一定律

从 Google 黑板报 -- Google 中国的博客网志作者：joydandan
发表者：Google（谷歌）研究员吴军

今天各种汉字输入法已经很成熟了，随便挑出一种主要的输入法比十几年前最好的输入法都要快、要准。现在抛开具体的输入法，从理论上分析一下，输入汉字到底能有多快。

我们假定常用的汉字在二级国标里面，一共有 6700 个作用的汉字。如果不考虑汉字频率的分布，用键盘上的 26个字母对汉字编码，两个字母的组合只能对 676 个汉字编码，对 6700个汉字编码需要用三个字母的组合，即编码长度为三。当然，聪明的读者马上发现了我们可以对常见的字用较短的编码对不常见的字用较长的编码，这样平均起来每个汉字的编码长度可以缩短。我们假定每一个汉字的频率是
p1, p2, p3, ..., p6700
它们编码的长度是
L1, L2, L3, ..., L6700
那么，平均编码长度是
p1×L1 + p2×L2 + ... + p6700×L6700

香农第一定理指出：这个编码的长度的最小值是汉字的信息熵，也就是说任何输入方面不可能突破信息熵给定的极限。当然，香农第一定理是针对所有编码的，不但是汉字输入编码的。这里需要指出的是，如果我们将输入法的字库从二级国标扩展到更大的字库GBK，由于后面不常见的字频率较短，平均编码长度比针对国标的大不了多少。让我们回忆一下汉字的信息熵（见 http://www.googlechinablog.com/2006/04/4.html），
H = -p1 * log p1 - ... - p6700 log p6700。
我们如果对每一个字进行统计，而且不考虑上下文相关性，大致可以估算出它的值在十比特以内，当然这取决于用什么语料库来做估计。如果我们假定输入法只能用 26 个字母输入，那么每个字母可以代表 log26=
4.7 比特的信息，也就是说，输入一个汉字平均需要敲 10/4.7= 2.1 次键。

聪明的读者也许一经发现，如果我们把汉字组成词，再以词为单位统计信息熵，那么，每个汉字的平均信息熵将会减少。这样，平均输入一个字可以少敲零点几次键盘。不考虑词的上下文相关性，以词为单位统计，汉字的信息熵大约是8比特作用，也就是说，以词为单位输入一个汉字平均只需要敲 8/4.7=1.7次键。这就是现在所有输入法都是基于词输入的内在原因。当然，如果我们再考虑上下文的相关性，对汉语建立一个基于词的统计语言模型（见http://www.googlechinablog.com/2006/04/blog-post.html），我们可以将每个汉字的信息熵降到 6 比特作用，这时，输入一个汉字只要敲 6/4.7=1.3 次键。如果一种输入方法能做到这一点，那么汉字的输入已经比英文快的多了。

但是，事实上没有一种输入方法接近这个效率。这里面主要有两个原因。首先，要接近信息论给的这个极限，就要对汉字的词组根据其词频进行特殊编码。事实上像王码这类的输入方法就是这么做到，只不过它们第一没有对词组统一编码，第二没有有效的语言模型。这种编码方法理论上讲有效，实际上不实用。原因有两个，第一，很难学；第二，从认知科学的角度上讲，人一心无二用，人们在没有稿子边想边写的情况下不太可能在回忆每个词复杂的编码的同时又不中断思维。我们过去在研究语言识别时做过很多用户测试，发现使用各种复杂编码输入法的人在脱稿打字时的速度只有他在看稿打字时的一半到四分之一。因此，虽然每个字平均敲键次数少，但是打键盘的速度也慢了很多，总的并不快。这也就是为什么基于拼音的简单输入法占统治地位的原因。事实上，汉语全拼的平均长度为2.98，只要基于拼音的输入法能利用上下文彻底解决一音多字的问题，平均每个汉字输入的敲键次数应该在三次左右，每分钟输入 100个字完全有可能达到。

另外一个不容易达到信息论极限的输入速度的原因在于，这个理论值是根据一个很多的语言模型计算出来的。在产品中，我们不可能占有用户太多的内存空间，因此各种输入方法提供给用户的是一个压缩的很厉害的语音模型，而有的输入方法为了减小内存占用，根本没有语言模型。拼音输入法的好坏关键在准确而有效的语言模型。

另一方面，由于现有输入方法离信息论给的极限还有很大的差距，汉语输入方法可提升的空间很大，会有越来越好用的输入方法不断涌现。当然，输入速度只是输入法的一项而不是唯一的衡量标准。我们也会努力把谷歌的输入法做的越来越好。大家不妨先试试现在的版本，http://tools.google.com/pinyin/，半年后再看看我们有没有提高。

欢迎光临人在德国社区 (http://csuchen.de/bbs/)