`
liuxinglanyue
  • 浏览: 565178 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

数学之美系列 二十三 输入一个汉字需要敲多少个键 — 谈谈香农第一定律

阅读更多

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

我们假定常用的汉字在二级国标里面,一共有 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/,半年后再看看我们有没有提高。

分享到:
评论

相关推荐

    通信的数学理论_香农_中文版1参考.pdf

    二进制是指信息用0和1来表示,十进制是指信息用0到9来表示,自然对数是指信息用自然对数来表示。 香农熵 香农熵是指信息的不确定性。香农熵是指信息的随机性和不确定性。香农熵可以用来衡量信息的可靠性和安全性。...

    通信的数学理论-香农-中文版1.doc

    通信的数学理论-香农-中文版 1 通信的数学理论是现代通信领域的基础理论之一,该理论研究的是如何在通信系统中accurately传输信息。该理论的基础包括在重要的报纸和中关于此学科的内容。在当今的报纸中,我们将延伸...

    《通信的数学理论》(1948) 中英文版 香农

    《通信的数学理论》是1948年由美国数学家兼电气工程师克劳德·香农(Claude Shannon)发表的开创性论文,这是一部里程碑式的作品,奠定了现代信息论的基础。这篇论文不仅对信息技术的发展产生了深远影响,还对整个...

    通信的数学理论 香农

    ### 通信的数学理论——香农 #### 引言与背景 香农(C.E. Shannon)在其开创性的论文《通信的数学理论》中提出了一个关于通信系统的全面理论框架。这篇论文不仅为现代通信工程奠定了基础,而且对于理解信息如何在...

    数学之美系列完整版.doc

    【数学之美系列】是由Google研究员吴军撰写的一系列文章,主要探讨了数学在信息处理、自然语言处理(NLP)和搜索引擎技术中的应用。该系列文章涵盖了多个关键知识点,包括统计语言模型、中文分词、隐含马尔可夫模型...

    信息论基础 香农 通信的数学理论

    1. **通信的数学理论**:1948年,香农在《贝尔系统技术杂志》上发表了论文《通信的数学理论》,这篇论文被认为是信息论的开山之作。在论文中,香农首次提出了信息熵的概念,它是衡量信息不确定性的指标,也是信息论...

    通信的数学理论[英]香农

    香农信息论的开山之作, 《通信的数学理论》,并非网上流传的 A Symbolic Analysis of Relay and Switching Circuits, 《继电器与开关回路的符号分析方法》

    香农信息论中译版(pdf)

    1. **香农第一编码定理**:任何信息都可以被编码为一组符号序列,使得该序列的平均长度接近其信息熵。 2. **香农第二编码定理**:对于任何给定的信息源,存在一种编码方式,使得解码后的错误概率可忽略不计,且编码...

    香农1948通信中的数学理论

    《香农1948通信中的数学理论》是信息论领域的开山之作,由美国数学家、信息论之父克劳德·艾尔伍德·香农(Claude Elwood Shannon)于1948年发表。这篇论文不仅奠定了现代信息论的基础,还对通信系统的设计产生了...

    香农公式的C++程序实现

    1. 香农公式的基本概念:香农公式是信息论中一个重要的概念,它描述了信息的熵和信息的编码方式。香农公式的基本概念是信息的熵,它是指信息的不确定性或随机性。 2.C++语言的使用:在这个程序中,作者使用了C++...

    Shannon_Python香农编码_python_shannon_香农编码_

    在Python中实现香农编码,首先需要统计字符的出现频率,这可以通过构建一个字典来完成。例如,遍历文本文件,对每个字符进行计数,得到一个键为字符、值为频率的字典。接着,可以使用哈夫曼树(也称为最优二叉树)来...

    香农三大定理

    香农三大定理

    通信的数学理论(中文版带书签)

    1. **引言**:香农在引言部分提到了通信的基本目标——在一个地点准确或近似地复现另一个地点的消息。此外,他还指出了早期研究者如奈奎斯特和哈特莱的工作为通信理论奠定了基础。本文将在此基础上进一步探讨噪声的...

    信息的数学理论 香农

    《信息的数学理论》是克劳德·香农在1948年发表的一篇具有里程碑意义的论文,这篇论文标志着信息论这一科学领域的诞生,香农也因此被誉为信息论的开山鼻祖。在这篇论文中,香农提出了许多基础且深远的概念,对通信、...

    香农代码的matlab实现_香农编码_

    例如,第一个符号(最高概率)分配码字00,第二个符号分配01,依此类推。如果码字长度不一致,可以使用前导零填充,确保所有码字都具有相同的长度。 4. **编码**:有了符号与码字的映射关系,我们就可以对原始数据...

    香农编码 Java 代码

    香农编码是信息论中的一个重要概念,由美国数学家克劳德·香农提出,用于无损数据压缩。它的核心思想是为每个可能的输入符号分配一个唯一的二进制码,使得频繁出现的符号拥有较短的编码,不常出现的符号则有较长的...

    香农编码的matlab语言实现

    无噪信道编码定理(又称香农第一定理)指出,码字的平均长度只能大于或等于信源的熵。有噪信道编码定理(又称香农第二定理)则是编码存在定理。它指出只要信息传输速率小于信道容量,就存在一类编码,使信息传输的...

    C++程序实现香农编码

    在信息论领域,香农编码是一种无损数据压缩方法,由美国数学家克劳德·香农提出。它主要基于信源符号出现的概率来分配不同的二进制码字,使得频繁出现的符号对应较短的码字,而罕见的符号对应较长的码字。这种编码...

    香农理论,通信的数学理论

    一个二进制数字可以表示两种状态之一(0或1),因此可以存储1比特的信息。 - 当底数为10时,单位被称为十进制数位(decimal digit)。一个十进制数位约等于3.32比特。 - 当底数为e时,单位被称为自然单位。这种...

    香农编码之C++实现2

    香农编码是信息论中的一个重要概念,由美国数学家克劳德·香农提出,主要用于数据压缩和通信领域。在信息论中,香农编码是一种无损数据压缩方法,其核心思想是为出现频率较高的字符分配较短的编码,而出现频率较低的...

Global site tag (gtag.js) - Google Analytics