输错字了怎么办？

　　做输入法的时候，有一个很常见的问题，就是如果用户输错了拼音，怎么办？（嘉定用户用的是拼音输入法）

　　比如说，我要打北京，拼音就是beijing，结果达成了beijnig，或者bejing，怎么办？

　　首先，算法要做的就是区分到底是正确输入，还是错误输入。

　　比如beijin这个到底算是beijing的错误输入，还是一个正确输入呢？

　　这个的最好做法是做上下文判断，但这个算是高级要求，这里忽略。

　　在不做上下文判断的情况下（感觉谷歌输入法和苹果是有上下文判断的，虽然很不靠谱，苹果的输入法我感觉在不靠谱程度上更甚），面对一个用户输入，我们先去做匹配，看能否匹配到词组。

　　如果一个拼音输入可以匹配到一个存在的词组，那么就认为这是正确输入，不考虑错误输入的判定流程——当然，要走也可以，优先级调低（比如一页十个前6个是正确输入后4个做错误输入处理）。

　　而，如果一个拼音输入没有匹配到任何已经存在的词组，那么就可以当作是错误输入，来做纠正。

　　好了，重头戏来了——面对错误的输入，要怎么找到正确的输入？

　　比如说，面对bejing或者beijnig，我怎么知道它的正确拼写应该是什么样的？

　　这就是下一个问题——输入错误的种类。

　　输入错误的种类其实是有限的，可以归为四大类：

　　1，乱序，比如从beijing到beijnig

　　2，遗漏，比如从beijing到bejing

　　3，冗余，比如从beijing到beijiing

　　4，误入，比如从beijing到baijing

　　接下来的下一个问题，就是如何找到正确的拼写。

　　这里牵扯到这么一个概念：给定拼音A和拼音B之间的“距离”（这里有个专有名词，就不引用了）

　　比如说，同样是乱序，beijing到beijnig和到biejing的“距离”是一样的，都是乱序1。但beijing到biejnig的距离就为2，因为需要乱序两次。

　　我们当然不可能将所有乱序、遗漏和冗余的可能性都来一遍——一个字符数为n的字符串的乱序1的可能为n-1，但乱序2的可能就是(n-1)(n-2)，如果穷举所有乱序的可能，那就是(n-1)!的量级，碰到zhuangshangying这样的长词组直接嗝屁。

　　所以，我们只能去搜寻所有错符距为1的词组，并从中找到正确的单词。

　　这个做法在中文输入法（拼音是最常见的使用场景）和英文输入法（你不会不知道英文也有输入法吧？这个在手机上特别多）上都是最常用的做法。

　　可以算得上是业界标准。

　　但，我们的故事到此并没有结束。

　　就如前面所说，从错符距1到错符距2，工作量是几何级上升的，所以Google和苹果基本都只考虑错符距1，我们公司以前的产品也遵守这个业界统一标准。

　　但，这并不是我们不做错符距2的合理理由。

　　因为，事实上，错符距2一样可以在非几何级上升情况下被解决的，也就是说，不需要将工作量从n-1上升到(n-1)(n-2)也一样可以完成错符距2的纠正。

　　现在让我们以英语为例。

　　比如单词transformer，变压器，变形金刚，或者morphism，automorphism，endomorphism，transmorphism。

　　说这个不是在飚英语（话说GRE和雅思考完以后基本就不看英语了我擦……），而是在问你——发现没有，上面有什么规律？

　　答对了，词根。

　　英文单词的输入错误纠正目前和拼音一样，也是基于错符距1的，但这是将注意力放在“单词”这个整体上的，事实上却可以做进一步的拆分。

　　英文单词都有词根，要么是前缀，要么是后缀，组合在一起。于是一个单词可以分解为：prefix?+body*+postfix?，?表示有或者没有，*表示若干个（很少看到四个词根拼成一个单词的。。。不过生物化学医药等专业领域的新造词一个单词冒出十来个词根也是正常）。

　　比如说，transformer，就是trans + form + er（这个也算么？？），transmorphism就是trans + morphism，automorphism就是auto + morphism。

　　如果我们将单词以词根为单位做分解，然后对每个词根的部分做错符距1纠正，那么一个完整的单词就可以做到错符距2甚至错符距3的纠正，用户体验大增。

　　而词根分解本身的工作量是n的量级，三个词根构成的单词的错符距3纠正也不过是4n的量级，比原本n^2甚至n^3的量级小了很多。

　　在拼音输入中也是。

　　我们输入shanghai，结果输成了shanghia或者shnaghai，那么现在的输入法（谷歌或者苹果）都能自动纠正，但如果你输成了shnaghia，就直接无能为力了。

　　可，如果一个词组按照拼音来分解（这方面比英语词根分解要容易很多，因为中文一个单词的声母韵母及其组合比英语词根有规律太多了），那么上述shnaghia是可以被自动纠错的。

　　可见，业界标准的错符距1其实也不过是一个习惯性规定而已，并不存在技术上的绝对壁垒。

　　这点不单单输入法可以用，在搜索引擎上也可以用。

　　毕竟，输入法说到底，其核心功能就是对词库的搜索，所以也就是一种小型搜索引擎而已。