Spell Checking算法
给定一个可能拼写错误的单词(word)，跟字典里的单词进行比对，找出可能的正确拼写。
参见维基百科上的Spell Checker条目。
数学理论
- 要检查的单词 w
- 字典里的单词 c
- 贝叶斯概率
P(c|w) = P(w|c)*P(c)/P(w) - 简化为
P(c|w) = P(w|c)*P(c)# 考虑到对所有c来说P(w)为常数
求解 P(w|c)
Editing Distance
比较两个字符串s和t，对源字符串s进行d步操作（插入、删除、替换等）可以得到目标字符串t的话，我们可以说两个字符串之间的编辑距离（Editing Distance）是d。这里的操作指的是针对字符的操作。
| 可以认为，d越小，s和t越接近。实际上是近似认为：`P(w | c) ~ d` |
|---|
每一步允许的操作的不同，是几种不同的编辑距离的主要区别。
- 只允许字符替换，是 Hamming Distance
- 只允许相邻字符交换，是 Jaro Distance
- 只允许插入和删除，是 Longest Common Subsequence
- 允许插入、删除、替换，是 Levenshtein Distance
- 允许插入、删除、替换和相邻字符交换，是 Damerau–Levenshtein Distance
Soundex
根据读音来判断两个单词的相似程度也是一个思路。
比如根据单词的 Soundex 来判断。
相关资源
- Spell checker at Wikipedia
- How to Write a Spelling Corrector by Peter Norvig
- Blog of Peter Norvig - Director of Research at Google
- Spelling Correction in PHP by Ian Barber
- PHP/ir - Information Retrieval and other interesting topics
- Spelling correction with Soundex
- Spellchecking by computer