Baidu, google 等搜索引擎如何識別搜索詞的typo?

01-08

例如，在google上搜索Apple stre，會顯示apple store的搜索結果
這跟machine learning有關么？

這個問題如果不局限於搜索引擎的typo的話，屬於normalization的問題。而normalization則屬於自然語言處理(NLP)的一個topic，NLP本身是機器學習(ML)的一個分支。

normalization本身是用來解決在文本尤其是當前社交媒體如twitter，fb上的縮寫問題。比如我們常見的"ppl/people"這類縮寫，"yeeeeaaaah"這類重複，"u r rite"這類發音替換，和「appology/apology」這類的typo。

在一般的做法中，常用的模型是「雜訊信道模型」：

雜訊信道模型假設原始的正規詞語(t)因為雜訊而變成了不正規的詞語(s)，這個模型的基本公式是

$P(t|s)=frac{p(s|t)*p(t)}{p(s)}propto p(s|t)*p(t)$

於是由stre轉移回store的概率就由（1）從store轉移到stre的概率（2）store本身出現的概率決定。第二個因素大家都沒有什麼可以改進的，就是去一堆語料里查詞頻就好了，而第一個因素則比較主觀，也是業界探討的重點。有人採用編輯距離(edit distance，衡量字元串的相似度)來體現「看著像」，用這個來進行一些處理加權獲得一個概率值，少部分人使用一些發音的模型去體現「聽著像」，這個用的人不多，因為如何去衡量發音也是一個複雜的問題。

假設對於apple stre這個搜索請求，我們發現stre不是一個單詞，那麼通過信道模型發現stre可以變成street和store，比較一下概率大小就好了。

但是假設street在語料中出現的概率可能會大於store，那麼如何去考慮呢？

如果有上下文的話，就可以考慮加入上下文的因素進行考量。比如apple stre的話，與stre看著像或是聽著像的有store，street，那麼除了store，street本身這兩個單詞出現的頻率以外，和apple共現的可能性也要加入其中。當然apple store出現的可能性要比apple street的可能性要高一些，那麼就選擇apple store就好了。

是跟machine learning有關的。

在GOOGLE上搜「spelling correction search query」, 你應該能搜到一些相關的資源。

最簡單的方法是計算edit distance，就是找最相近的字元串（面試常考題目）。當然實際上會比這個複雜得多，一般會用到（所有）用戶搜索過的歷史記錄來推薦最合適的字元串。

.... 給前面的回答跪了 p（ store| stre）這東西你都算的出來.

Apple stre是做拼寫檢查, 然後糾正後的結果, 不用機器學習, 在可能的詞裡面找個頻率最大的就行了.

p（ store| stre）正比 p（ store）* p（stre|store），結合apple，再乘以p（xx|apple）就ok了