Dec 03
From Google黑板报 by 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/，半年后再看看我们有没有提高。
Jun 22
再探史上最强验证码
在 蓝色理想 的 会员叫喊 里看到了 网上流传已久的 史上最强验证码 的讨论，于是再次到那个 卡维注册页面 参观了一下，发现了这个传说中 最强 验证码 的一些纰漏
右键点击验证码图片 属性，发现链接到
http://www.kawise.com/Reg/Reg_Code.asp
用Maxthon打开这个链接，发现居然是客户端跳转～～那么图片的地址为：
http://www.kawise.com/images/YzCode/1.gif
http://www.kawise.com/images/YzCode/2.gif
http://www.kawise.com/images/YzCode/3.gif
http://www.kawise.com/images/YzCode/5.gif
http://www.kawise.com/images/YzCode/6.gif
其实这样的验证码只能用来取笑，并不能用来防止恶意注册，很简单，因为验证码的数量是有限的，可以人工知道每个验证码的答案。真正的验证码应该程序随机生成内容，并且有一个固定的URL使用Response.BinaryWrite()来输出图片二进制留，取消客户端缓存，并且刷新一次变一次，多次验证码错误还要强行禁止注册一段时间～～
May 31
一直比较关心RFID技术及其应用，没想到微软这家伙居然偷偷出了个如此了得的新概念计算机。
Channel 10放出了微软Surface计算机的视频，这是一台全触摸式的令人惊叹的创新计算机。微软称Surface计算机将最先作为公共服务出现在Las Vegas。随着产量的提升，价格也会慢慢降下来。建议大家都下载此视频观看一下，Surace意图将自身打造成服务终端，将各项服务整合在这个平台之下，实现的功能令人十分振奋。
在这段视频中，Surface电脑的市场营销主任Mark Bolger向我们解释了什么是Surface计算机。“这是一台什么计算机呢？这是一台将在每个宾馆、每个小卖部、每个娱乐场所都将出现的计算机。”
看了视频，大为震撼。这种计算机形状如同平时的茶几，看似一个平放的传统触摸屏电脑，特殊之处在于：
- 多重触控（MultiTouch）
- 基于RFID的图章
- 和掌上移动设备的无缝连接、同步
- 甚至可以感知你放到屏幕上的香槟是哪一年出产的
附：
什么是RFID：
RFID，射频识别技术，Radio Frequency Identification的缩写
RFID first appeared in tracking and access applications during the 1980s. These wireless AIDC systems allow for non-contact reading and are effective in manufacturing and other hostile environments where bar code labels could not survive. RFID has established itself in a wide range of markets including livestock identification and automated vehicle identification (AVI) systems because of its ability to track moving objects.
RFID射频识别是一种非接触式的自动识别技术，它通过射频信号自动识别目标对象并获取相关数据，识别工作无须人工干预，可工作于各种恶劣环境。RFID技术可识别高速运动物体并可同时识别多个标签， 操作快捷方便。
RFID的基本组成部分：
标签(Tag)：由耦合元件及芯片组成，每个标签具有唯一的电子编码，附着在物体上标识目标对象；
阅读器(Reader)：读取(有时还可以写入)标签信息的设备，可设计为手持式或固定式；
天线(Antenna)：在标签和读取器间传递射频信号。
RFID技术的基本工作原理：
标签进入磁场后，接收解读器发出的射频信号，凭借感应电流所获得的能量发送出存储在芯片中的产品信息（Passive Tag，无源标签或被动标签），或者主动发送某一频率的信号（Active Tag，有源标签或主动标签）；解读器读取信息并解码后，送至中央信息系统进行有关数据处理。
一个RFID标签十分微小（甚至比盐粒还小），例如，办公室桌面上要快速找到一份文件在哪个位置比较困难，如果每个订书针上都可以放置一个RFID标记（Tag），然后我们要找一份文件只需要用个扫描器（Reader）就可以定位了。读写设备（Reader）可通过无线电讯号以一定的数据传输率与标签交换信息，作用距离可根据采用的技术从若干厘米到1千米不等。
将射频类别技术与条形码（Barcode）技术相互比较，射频类别拥有许多优点，如：可容纳较多容量、通讯距离长、难以复制、对环境变化有较高的忍受能力、可同时读取多个标签。相对地有缺点，就是建置成本较高。不过目前透过该技术的大量使用，生产成本就可大幅降低。
2005年初每标签的价格仍在30欧分左右，大批量（十亿个以上）生产的射频识别标签的价格可望在2008年降至10欧分以下。
在Baidu上搜索了下RFID，文章寥寥数片，不成气候，看来大陆还没有“热”起来。想必5年之后，RFID一定如同商品条形码一样被人们普篇认识。射频识别技术可应用的领域十分广泛，主要决定因素是该项技术在相应领域中的经济效益。经常提到的具体应用包括：钞票及产品防伪技术、 身份证、通行证(包括门票) 、电子收费系统，如香港的八达通与台湾的悠游卡 、家畜或野生动物识别 、病人识别及电子病历、物流管理等等。许多人把射频识别技术看作为继互联网和移动通信两大技术大潮后的又一次大潮。但是目前RFID在中国大陆，香港，台湾的发展远远落后于美国及欧洲，需要非常的努力方能赶上这次“新的浪潮”。
