我們最近在工作中遇到了一個有趣的問題，我們在數據庫中發現了重複的用戶提交的數據。我們意識到大部分數據之間的Levenshtein距離僅僅是兩個字符串之間的差異。這表明如果我們只是將一個字符串中的字符添加到另一個字符串中，那麼我們最終會得到相同的字符串，並且對於大多數情況來說，這似乎是我們解釋重複項目的最佳方式。如何使用Levenshtein距離創建類似字符串的閾值並解釋拼寫錯誤？
我們也想解釋拼寫錯誤。所以我們開始平均考慮人們每個字每次在網上打字錯誤的次數，並嘗試在這個距離內使用這些數據。我們找不到這樣的統計數據。
當創建這種數據匹配閾值時，是否有任何方法來解決拼寫錯誤？
讓我知道我是否可以澄清！
首先，Levenshtein距離被定義爲edi的最小數量將字符串A轉換爲字符串B所需的ts，其中編輯是插入或刪除單個字符，或用另一個字符替換字符。因此，對於距離的某個定義來說，這非常「兩個字符串之間的差別」。 =）
聽起來好像你正在尋找一個給出字符串A和B之間距離的距離函數F（A，B）和一個閾值N，其中距離小於N的字符串是錯別字的候選字符。除Levenshtein距離外，您還可以考慮Needleman–Wunsch。它基本上是一樣的東西，但它可以讓你提供一個函數，讓一個給定的角色與另一個角色有多接近。您可以將該算法與一組反映QWERTY鍵盤上按鍵位置的權重結合使用，以發現拼寫錯誤。儘管如此，這對於國際鍵盤會有問題。
如果您有k個字符串，並且想要查找潛在的拼寫錯誤，則需要進行的比較次數爲O（k^2）。另外，每個比較是O（len（A）* len（B））。所以，如果你有一百萬條琴絃，如果你天真地做事，你會發現自己陷入麻煩。下面是關於如何加快速度了幾點建議：
您可能遇到的一個問題是「1st St.」與「第一街」距離相當遠，儘管您可能想要將它們視爲相同。處理這個問題的最簡單方法可能是在比較之前將字符串轉換爲規範形式。因此，您可以將所有字符串設置爲小寫字母，使用映射「1st」到「first」等的字典。該字典可能會變得很大，但我不知道處理這些問題的更好方法。
既然你用php標記了這個問題，我假設你想用這個php。 PHP有一個內置的levenshtein（）函數，但兩個字符串必須不超過255個字符。如果這還不夠長，你必須自己做。或者，您可以使用Python的difflib進行調查。
你應該看看這本書：
http://nlp.stanford.edu/IR-book/pdf/irbookonlinereading.pdf
對法術的好章（3.3）檢查
在本章列出了一些論文是討論概率模型
結束時引用祝你好運