0x00 前言
Premature optimization is the root of all evil（过早的优化是万恶之源）
学计算机的小伙伴们一定对Donald Knuth老先生的这句话不陌生，而且过去常常以此来为自己的懒惰开脱=。=但是请注意，Donald Knuth说的是过早的优化，而不指所有的优化都是没有必要的，一个完美的系统是在不断完善和优化的过程中成长起来的。
本人认为优化有三个层次：
-
顶层优化，这种类型的优化往往与程序本身无关，是思路和方法的革新与改进
-
代码优化，比如使用何种语言，使用何种数据结构，采用哪种排序算法等等
-
底层优化，底层涉及的包括编译器、指令集，还有Java虚拟机等等，比如在科学计算中就会涉及到较多的底层优化
一般来说，从效果上来看顶层优化>代码优化>底层优化，当然这也不是绝对的，与具体场景有关。本文将要介绍的就是一种顶层优化，而且效率比原来的方法高了1000多倍。有兴趣的小伙伴可以看看原文，1000x Faster Spelling Correction algorithm
0x01 拼写校正
关于拼写校正这里就不多解释了，用过Office的人肯定对人名和地名下面的红色波浪线恨之入骨=。=
这里需要解释的是编辑距离，来看看维基百科的解释
编辑距离，又称Levenshtein距离，是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。允许的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。
例如cat和car的编辑距离是1，因为只需将t→r即可，make和making的编辑距离是3，需要做的操作分别为e→i、插入n和g
朴素的拼写校正
朴素的拼写校正很好理解，将用户输入的单词与字典中的每一个词条计算编辑距离，并选出编辑距离最小的若干个词条作为拼写校正的备选选项。但是这个方法的缺点也非常明显——代价太高，即使在这个方法的基础上作优化（例如排除与用户输入单词长度相差3以上的词条），其计算量也是非常大的。
Peter Norvig拼写校正
对用户输入的单词进行编辑距离≤2的变换，包括插入、删除、修改以及它们的组合操作，这样我们就得到了若干个与原始输入编辑距离≤2的字符串，然后分别用它们在字典中进行查询。
这个方法虽然比朴素的拼写校正算法好了许多，但仍然有很高的复杂度，而且与具体的语言相关。例如在英语中只有26个字母，变换得到字符串个数还不是很多。而汉语有几千个常用字，这种方法就不可行了。
对称删除拼写校正(FAROO)
首先对字典进行处理，对每一个词条生成与其编辑距离≤2（只进行删除操作）的字符串，并添加到字典中。这是一个预处理过程，后面的操作都是基于这个全新的字典。
然后对用户输入进行处理，同样也是生成与其编辑距离≤2（只进行删除操作）的字符串，并在字典中查询这些字符串。
先不管有没有理解这个算法，仅仅看这个算法的描述就知道它比前面两个算法的复杂度低的多。首先预处理的过程可以不考虑，因为预处理只需要进行一次就可以了，我们所需要的仅仅是预处理得到的那个新字典。然后再看对用户输入处理的过程，没有插入和修改操作，只有删除操作，这样就保证了极高的效率和很好的语言无关性，无论是英语中4个字母的单词还是汉语中四个字的成语，最多只有\(4 + 4 \times 3=16\)种可能的结果。
0x02 对称思想的巧妙利用
也许你仍然对上面那个算法的正确性有所怀疑，为什么只考虑删除操作就可以了呢？插入和修改不考虑也可以吗？
我们用一个简单的例子来说明这个问题~
以单词simple为例，为了节省篇幅，这里就只考虑编辑距离为1的情况。先对其进行预处理，得到imple、smple、siple、simle、simpe、simpl，我们把它们添加到字典中。
考虑用户输入错误的3种情况
-
simpole多输入一个字符 -
simpe少输入一个字符 -
sinple输错一个字符
然后对用户输入进行处理。同样，我们只考虑编辑距离为1的情况
-
impole、smpole、sipole、simole、simple、simpoe、simpol -
impe、smpe、sipe、sime、simp -
inple、snple、siple、sinle、sinpe、simpl
第一种情况，用户输入生成的simple在字典中命中，第二种情况，用户的原始输入simpe在字典中命中，第三种情况，用户输入生成的siple在字典中命中。
这里虽然只考虑了编辑距离为1的情况，但是原理都是一样的。虽然我们只进行了删除操作，但是却可以囊括用户所有输入错误的情况。
看完这个例子，其实就很容易理解这个算法的精妙之处，对于用户的一个输入和字典中的一个潜在匹配，对其中一个进行插入和删除，与对另一个进行删除和插入是等价的。而对于拼写错误的情况只要两边同时删除不一致的字符同样可以匹配。
这就是对称思想在拼写校正算法优化中的应用~
0x03 总结
其实优化有的时候并非想像中那么复杂，一个好的优化一定是简单而优雅的。就像本文介绍的对称删除法，虽然本质上来说属于一种“用空间换时间”的方法，但这不是重点，它的核心思想就是两个字——对称
本文的最后再次说明，本文介绍的算法出自1000x Faster Spelling Correction algorithm，在GitHub有C#源码可供参考。
如果你觉得本文对你有帮助，欢迎打赏我一杯咖啡钱，支持我写出更多好文章~
