与君共品代码: Spelling Corrector

标签: 代码 spelling corrector | 发表时间:2011-04-30 15:36 | 作者:(author unknown) kylexlau
出处:http://www.iteye.com

这是我在ITEYE发的第一个帖子:


1. 一段代码(很短,才21行)
2. 代码赏析(泡杯咖啡,慢慢品)

1. 一段代码

如果有人面试问我写过最棒的一段代码是什么,我可能真说不上什么。
但要是有人问我见过最棒的一段代码是什么?那非Peter NorvigSpelling Corrector莫属了。

好,大餐上来啦(python2.5, 21行):

 

import re, collections

def words(text): return re.findall('[a-z]+', text.lower()) 

def train(features):
    model = collections.defaultdict(lambda: 1)
    for f in features:
        model[f] += 1
    return model

NWORDS = train(words(file('big.txt').read()))

alphabet = 'abcdefghijklmnopqrstuvwxyz'

def edits1(word):
   splits     = [(word[:i], word[i:]) for i in range(len(word) + 1)]
   deletes    = [a + b[1:] for a, b in splits if b]
   transposes = [a + b[1] + b[0] + b[2:] for a, b in splits if len(b)>1]
   replaces   = [a + c + b[1:] for a, b in splits for c in alphabet if b]
   inserts    = [a + c + b     for a, b in splits for c in alphabet]
   return set(deletes + transposes + replaces + inserts)

def known_edits2(word):
    return set(e2 for e1 in edits1(word) for e2 in edits1(e1) if e2 in NWORDS)

def known(words): return set(w for w in words if w in NWORDS)

def correct(word):
    candidates = known([word]) or known(edits1(word)) or known_edits2(word) or [word]
    return max(candidates, key=NWORDS.get)



2. 代码赏析

这里只是简单介绍一下,强烈建议看原文,英文不好的可以看徐大哥的翻译(需fq)

大家一定都曾经在Google里输入错误的单词,比方说输入javaeya,Google会提示:
Showing results for javaeye. Search instead for javaeya
(其实我想举iteye为例子的,不幸的是Google还没把这词给当回事...)

是的,Peter的这段代码就是干这事的,输入为一个单词,输出为单词的纠正词:

>>> correct('speling')
'spelling'
>>> correct('korrecter')
'corrector'


好吧,简单分析一下:

第一个方法:

def words(text): return re.findall('[a-z]+', text.lower())

 

返回文本里所有单词,并使其字母变为小写(Google里搜索也是不分大小写的,因为如果分大小写的话太复杂了)

第二个方法:

def train(features):
    model = collections.defaultdict(lambda: 1)
    for f in features:
        model[f] += 1
    return model

 

返回一个'key=word', value='word出现个数'的字典(相当于java里的Hashtable)
用lambda:1(即没有出现的单词的个数记为1)的原因是,概率里用小概率而不是用0来替代不可能事件

于是:

NWORDS = train(words(file('big.txt').read()))

 

即把所有在big.txt里的单词按照出现的个数做了统计
(Peter在灰机上写的这段代码,big.txt是他自己电脑的一些文档)

再下来,Peter对输入错误的单词的情况做了几种分类:

def edits1(word):
    splits     = [(word[:i], word[i:]) for i in range(len(word) + 1)] #@IndentOk
    deletes    = [a + b[1:] for a, b in splits if b]
    transposes = [a + b[1] + b[0] + b[2:] for a, b in splits if len(b)>1]
    replaces   = [a + c + b[1:] for a, b in splits for c in alphabet if b]
    inserts    = [a + c + b     for a, b in splits for c in alphabet]
    return set(deletes + transposes + replaces + inserts)

 

即几下四种(这里以iteye做为例):
1. 漏输字母:iteye -> itye
2. 字母错位: iteye -> ityee
3. 输错字母: iteye -> iteya
4. 多输字母: iteye -> iteyee
可以看出edits1(word)这个方法即把所有可能字母出错个数为1的单词作了枚举
(注意这里字母出错个数为1的意思是不包括输漏,错,多超过两个字母的情况,比如iteyeee是不被包含的)

(从这个角度来看,iteye比javaeye这个域名好多了,我自己试了下javaeye输错的概率会比iteye大很多)

好,接着下一个方法:

def known_edits2(word):
    return set(e2 for e1 in edits1(word) for e2 in edits1(e1) if e2 in NWORDS)

 

这段代码返回的是出错字母个数为2且出现在培训样本里的单词,之所以这样做是因为:
假如不加判断if e2 in NWORDS的话,"something"这样一个单词的两个字母错误情况居然达到了 114,324 个.
Peter在做了些验证后决定只把那些正确的词作为候选词

好的,可以进行纠错了

def correct(word):
    candidates = known([word]) or known(edits1(word)) or known_edits2(word) or [word]
    return max(candidates, key=NWORDS.get)

 

在这里,Peter做了个直接了断的假设,即纠正词的选取优先级依次为 :库里的词,出错一个词,出错两个词


现在从三个方面来欣赏这段代码:

2.1. 数学之美

贝叶斯定理是这段代码的核心,做为人工智能领域的大牛,Peter对这种问题的数学建模能力确实非凡

设若单词c(correction)是输入单词w(word)的正确原型,那么P(c\w)即为给定的单词w, 单词c是w的正确原型的概率

通过贝叶斯做定理的变型,可得:
P(c|w)=P(c*w)/P(w)=(P(w|c)*P(c))/P(w)
因为w是用户输入给定的,故p(w)为1,得:P(c|w)=P(w|c)*P(c)


为什么要把p(c\w)转化为p(w\c)呢?Peter给出的解释是:

写道
The answer is that P(c|w) is already conflating two factors, and it is easier to separate the two out and deal with them explicitly.
Consider the misspelled word w="thew" and the two candidate corrections c="the" and c="thaw". Which has a higher P(c|w)? Well,
"thaw" seems good because the only change is "a" to "e", which is a small change. On the other hand,
"the" seems good because "the" is a very common word, and perhaps the typist's finger slipped off the "e" onto the "w".
The point is that to estimate P(c|w) we have to consider both the probability of c and the probability of the change from c to w anyway,
so it is cleaner to formally separate the two factors.

 

即要比较不同c的p(c|w)是件很难的事,因为我们是无法知道单词是如何被写错的
但把p(c|w)转化为P(w|c)*P(c)时,事情就变得简单了,因此我们的问题是找出max(p(w|c)*p(c))的c,
而如何找到最大的p(w|c)*p(c)呢?恩,在Peter的假设(纠正词的选取优先级依次为 :库里的词,出错一个词,出错两个词)下就是这行代码了:
return max(candidates, key=NWORDS.get). 按照优先级获得p(c)最大的c, Cool!

推荐大家看原文接下来的一些延伸。
刘未鹏在数学之美番外篇:《平凡而又神奇的贝叶斯方法》里也提到了这段程序,推荐大家读读。
恩,为什么有人说互联网公司拼的是数据?为什么当初李开复能把语音识别准确率提升了一个台阶?为什么贝叶斯定理在Google里有这么重要的地位?(Just Google it)

2.2. Python之美

老实说这段代码是我最初学Python的动力

看看这简单之美:

    splits     = [(word[:i], word[i:]) for i in range(len(word) + 1)]
    deletes    = [a + b[1:] for a, b in splits if b]
    transposes = [a + b[1] + b[0] + b[2:] for a, b in splits if len(b)>1]
    replaces   = [a + c + b[1:] for a, b in splits for c in alphabet if b]
    inserts    = [a + c + b     for a, b in splits for c in alphabet]
 


2.3. 程序之美

你一定看过乔丹跳投的视频吧?很美吧?持球,下蹲,发力,起跳,在最高点时移开左手,右手轻轻一拨,3 point,perfect.
Peter的'跳投'也很美,read,  train, edit, known, 最后: >>> correct('speling') 'spelling',pefect!

 

前段时间到上海博物馆里,看到那些巧夺天工的玉器,惊叹之余我竟然第一个想到的,是那些代码。
是的,几百年前Bayes提出了贝叶斯定理,几十年前Guido van Rossum整出了python,几年前Peter Norvig写出了这段代码。
若把spelling correct这个需求比作玉的话,Peter便是拿着这块玉,用Guido van Rossum作的工具,一行一行地在Bayes的思想下做出了这艺术品。
把编程喻为匠艺,挺确切,但不同的是,这份艺术不仅是大脑来雕砌更不止于欣赏,它不在博客馆里陈列着,而在计算机上运行着,它带来的是真实的价值。
倘若Google的一次corrector能为用户省下哪怕是1秒钟的时间,那以亿计的用户使用所省下的时间所创造的财富,足以给予Google和Googler们最丰厚的回报和自豪感。


3. 一个小活动

 

其实很早时我就想把酷代码印在T-shirt上了,夏天终于来啦,我决定把这段代码印在我的T-shirt上,Peter也同意啦:
 

 

 

 (这里面有个让我很囧的大笑话,希望你能发现)

我想一定有人会说,这样走在街上是不是太招摇了?是的,哥就是出来装AC的。


当有人拿很好的MPx,里面塞满一堆垃圾音乐,却在你面前装AC时。
当有人拿着xphone,里面塞着一堆美女的号码却不是朋友和亲人,却在你面前装AC时。
我希望你能和我一样,转过身去,让他看看这便宜的T-shirt背面印着的代码,当你转回身子看着他一脸茫然时,微笑着告诉他:"Well, what monkey can't buy!".

MPx, xphone, money, 美女这些东西终要腐烂的,唯有艺术与爱不朽于世。


"Smart is the new sexy",哥不穿黑丝,还不能性感了?

是的,一个夏天一件T-shirt是不够的,那就快点把你最喜欢的代码分享出来吧!如果它也很美,我一定会把它印在T-shirt上的。

 

想要印这段代码的同学也可以找我要印的图,哈哈,和大家一起分享,Habe a good summer, and happy programming!



作者: codeincoffee 
声明: 本文系ITeye网站发布的原创文章,未经作者书面许可,严禁任何网站转载本文,否则必将追究法律责任!

已有 22 人发表回复,猛击->>这里<<-参与讨论


ITeye推荐



相关 [代码 spelling corrector] 推荐:

与君共品代码: Spelling Corrector

- kylexlau - ITeye论坛最新精华讨论帖
这是我在ITEYE发的第一个帖子:. 如果有人面试问我写过最棒的一段代码是什么,我可能真说不上什么. 但要是有人问我见过最棒的一段代码是什么. 那非Peter Norvig的Spelling Corrector莫属了. 好,大餐上来啦(python2.5, 21行):. return set(e2 for e1 in edits1(word) for e2 in edits1(e1) if e2 in NWORDS) def known(words): return set(w for w in words if w in NWORDS) def correct(word):.

代码重构

- - ITeye博客
随着程序的演化,我们有必要重新思考早先的决策,并重写部分代码. 代码需要演化;它不是静态的事物. 重写、重做和重新架构代码合起来,称为重构.    当你遇到绊脚石  ---  代码不在合适,你注意到有两样东西其实应该合并或是其他任何对你来说是"错误"的东西  -------- . 如果代码具备以下特征,你都应该考虑重构代码:.

代码小比较

- Tim - 斯巴达第二季
判断上百万个4k的buffer是否为全0,我最先想到的办法是:zero_buffer = malloc(4096);. /* 循环百万次读取buffer */.         /* 全0 */. 由于好奇,看看shell工具cp的代码,它的解决办法是:. /* 循环百万次读取buffer */.         /* 全0 */.

两行 JavaScript 代码

- MessyCS - Dreamer&#39;s Blog
最近看到了两行 JavaScript 代码,很受启发. 在 JavaScript 中,我们可以获取HTML元素的属性值,例如 element.id. 但是,因为 for 和 class 是 JavaScript 中的关键字,所以在 JavaScript 中这两个属性名称分别用 htmlFor 和 className 代替,于是在封装的时候需要先对这两个属性进行特殊判断.

Netty代码分析

- LightingMan - 淘宝JAVA中间件团队博客
Netty提供异步的、事件驱动的网络应用程序框架和工具,用以快速开发高性能、高可靠性的网络服务器和客户端程序[官方定义],整体来看其包含了以下内容:1.提供了丰富的协议编解码支持,2.实现自有的buffer系统,减少复制所带来的消耗,3.整套channel的实现,4.基于事件的过程流转以及完整的网络事件响应与扩展,5.丰富的example.

python代码调试

- - 阿里古古
【转自: http://blog.csdn.net/luckeryin/article/details/4477233】. 本文讨论在没有方便的IDE工具可用的情况下,使用pdb调试python程序. 例如,有模拟税收计算的程序:. debug_demo函数计算4500的入账所需的税收. 在需要插入断点的地方,加入红色部分代码:如果_DEBUG值为True,则在该处开始调试(加入_DEBUG的原因是为了方便打开/关闭调试).

ios代码开源

- - CSDN博客移动开发推荐文章
本人从10年开始搞ios开发,从菜鸟到现在的入门,期间遇到了许多困难,也总结了一些东西,本着开源精神,希望大家共同成长的目的把这个工程开源出来.. 这个工程是从11年到13年之前完成的.主要是我平时用到的一些基础功能模块.其中有其他开源的代码和我自己写的一些.代码结构基本乱,12年以后的代码结构还可以,不是很乱,之前水平有限,如果不怎么样就别喷我了.

Oracle错误代码

- - 数据库 - ITeye博客
ORA-00001: 违反唯一约束条件 (.). ORA-00017: 请求会话以设置跟踪事件. ORA-00018: 超出最大会话数. ORA-00019: 超出最大会话许可数. ORA-00020: 超出最大进程数 (). ORA-00021: 会话附属于其它某些进程;无法转换会话. ORA-00022: 无效的会话 ID;访问被拒绝.

Java代码优化

- - ImportNew
2016年3月修改,结合自己的工作和平时学习的体验重新谈一下为什么要进行代码优化. 在修改之前,我的说法是这样的:. 就像鲸鱼吃虾米一样,也许吃一个两个虾米对于鲸鱼来说作用不大,但是吃的虾米多了,鲸鱼自然饱了. 代码优化一样,也许一个两个的优化,对于提升代码的运行效率意义不大,但是只要处处都能注意代码优化,总体来说对于提升代码的运行效率就很有用了.

用 pylint, 写好代码

- Nickcheng - 赖勇浩的编程私伙局
赖勇浩(http://laiyonghao.com). Pylint 是一个 Python 代码分析工具,它分析 Python 代码中的错误,查找不符合代码风格标准(Pylint 默认使用的代码风格是 PEP 8)和有潜在问题的代码. Pylint 是一个 Python 工具,除了平常代码分析工具的作用之外,它提供了更多的功能:如检查一行代码的长度,变量名是否符合命名标准,一个声明过的接口是否被真正实现等等.