这是我在ITEYE发的第一个帖子：
1. 一段代码(很短，才21行)
2. 代码赏析(泡杯咖啡，慢慢品)
1. 一段代码
如果有人面试问我写过最棒的一段代码是什么，我可能真说不上什么。
但要是有人问我见过最棒的一段代码是什么？那非Peter Norvig的Spelling 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给出的解释是：
即要比较不同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！