做輸入法的時候，有一個很常見的問題，就是如果用戶輸錯了拼音钧唐，怎么辦诱建？（嘉定用戶用的是拼音輸入法）

　　比如說，我要打北京灾炭，拼音就是beijing，結(jié)果達成了beijnig，或者bejing逗扒，怎么辦？

　　首先欠橘，算法要做的就是區(qū)分到底是正確輸入矩肩，還是錯誤輸入。

　　比如beijin這個到底算是beijing的錯誤輸入肃续，還是一個正確輸入呢黍檩？

　　這個的最好做法是做上下文判斷，但這個算是高級要求始锚，這里忽略刽酱。

　　在不做上下文判斷的情況下（感覺谷歌輸入法和蘋果是有上下文判斷的，雖然很不靠譜瞧捌，蘋果的輸入法我感覺在不靠譜程度上更甚）棵里，面對一個用戶輸入，我們先去做匹配察郁，看能否匹配到詞組衍慎。

　　如果一個拼音輸入可以匹配到一個存在的詞組，那么就認為這是正確輸入皮钠，不考慮錯誤輸入的判定流程——當然稳捆，要走也可以，優(yōu)先級調(diào)低（比如一頁十個前6個是正確輸入后4個做錯誤輸入處理）麦轰。

　　而乔夯，如果一個拼音輸入沒有匹配到任何已經(jīng)存在的詞組砖织，那么就可以當作是錯誤輸入，來做糾正末荐。

　　好了侧纯，重頭戲來了——面對錯誤的輸入，要怎么找到正確的輸入甲脏？

　　比如說眶熬，面對bejing或者beijnig，我怎么知道它的正確拼寫應該是什么樣的块请？

　　這就是下一個問題——輸入錯誤的種類娜氏。

　　輸入錯誤的種類其實是有限的，可以歸為四大類：

　　1墩新，亂序贸弥，比如從beijing到beijnig

　　2，遺漏海渊，比如從beijing到bejing

　　3绵疲，冗余，比如從beijing到beijiing

　　4臣疑，誤入盔憨，比如從beijing到baijing

　　接下來的下一個問題，就是如何找到正確的拼寫朝捆。

　　這里牽扯到這么一個概念：給定拼音A和拼音B之間的“距離”（這里有個專有名詞般渡，就不引用了）

　　比如說，同樣是亂序芙盘，beijing到beijnig和到biejing的“距離”是一樣的驯用，都是亂序1。但beijing到biejnig的距離就為2儒老，因為需要亂序兩次蝴乔。

　　我們當然不可能將所有亂序、遺漏和冗余的可能性都來一遍——一個字符數(shù)為n的字符串的亂序1的可能為n-1驮樊，但亂序2的可能就是(n-1)(n-2)薇正，如果窮舉所有亂序的可能，那就是(n-1)!的量級囚衔，碰到zhuangshangying這樣的長詞組直接嗝屁挖腰。

　　所以，我們只能去搜尋所有錯符距為1的詞組练湿，并從中找到正確的單詞猴仑。

　　這個做法在中文輸入法（拼音是最常見的使用場景）和英文輸入法（你不會不知道英文也有輸入法吧？這個在手機上特別多）上都是最常用的做法肥哎。

　　可以算得上是業(yè)界標準辽俗。

　　但疾渣，我們的故事到此并沒有結(jié)束。

　　就如前面所說崖飘，從錯符距1到錯符距2榴捡，工作量是幾何級上升的，所以Google和蘋果基本都只考慮錯符距1朱浴，我們公司以前的產(chǎn)品也遵守這個業(yè)界統(tǒng)一標準吊圾。

　　但，這并不是我們不做錯符距2的合理理由赊琳。

　　因為街夭，事實上，錯符距2一樣可以在非幾何級上升情況下被解決的躏筏，也就是說，不需要將工作量從n-1上升到(n-1)(n-2)也一樣可以完成錯符距2的糾正呈枉。

　　現(xiàn)在讓我們以英語為例趁尼。

　　比如單詞transformer，變壓器猖辫，變形金剛酥泞，或者morphism，automorphism啃憎，endomorphism芝囤，transmorphism。

　　說這個不是在飚英語（話說GRE和雅思考完以后基本就不看英語了我擦……）辛萍，而是在問你——發(fā)現(xiàn)沒有悯姊，上面有什么規(guī)律？

　　答對了贩毕，詞根悯许。

　　英文單詞的輸入錯誤糾正目前和拼音一樣，也是基于錯符距1的辉阶，但這是將注意力放在“單詞”這個整體上的先壕，事實上卻可以做進一步的拆分。

　　英文單詞都有詞根谆甜，要么是前綴垃僚，要么是后綴，組合在一起规辱。于是一個單詞可以分解為：prefix?+body*+postfix?谆棺，?表示有或者沒有，*表示若干個（很少看到四個詞根拼成一個單詞的按摘。包券。纫谅。不過生物化學醫(yī)藥等專業(yè)領(lǐng)域的新造詞一個單詞冒出十來個詞根也是正常）。

　　比如說溅固，transformer付秕，就是trans + form + er（這個也算么？侍郭？）询吴，transmorphism就是trans + morphism，automorphism就是auto + morphism亮元。

　　如果我們將單詞以詞根為單位做分解猛计，然后對每個詞根的部分做錯符距1糾正，那么一個完整的單詞就可以做到錯符距2甚至錯符距3的糾正爆捞，用戶體驗大增奉瘤。

　　而詞根分解本身的工作量是n的量級，三個詞根構(gòu)成的單詞的錯符距3糾正也不過是4n的量級煮甥，比原本n^2甚至n^3的量級小了很多盗温。

　　在拼音輸入中也是。

　　我們輸入shanghai成肘，結(jié)果輸成了shanghia或者shnaghai卖局，那么現(xiàn)在的輸入法（谷歌或者蘋果）都能自動糾正，但如果你輸成了shnaghia双霍，就直接無能為力了砚偶。

　　可，如果一個詞組按照拼音來分解（這方面比英語詞根分解要容易很多洒闸，因為中文一個單詞的聲母韻母及其組合比英語詞根有規(guī)律太多了）染坯，那么上述shnaghia是可以被自動糾錯的。

　　可見顷蟀，業(yè)界標準的錯符距1其實也不過是一個習慣性規(guī)定而已酒请，并不存在技術(shù)上的絕對壁壘。

　　這點不單單輸入法可以用鸣个，在搜索引擎上也可以用羞反。

　　畢竟，輸入法說到底囤萤，其核心功能就是對詞庫的搜索昼窗，所以也就是一種小型搜索引擎而已。