字比較算法

我正在爲我正在處理的項目做一個CSV導入工具。客戶端需要能夠在Excel中輸入數據，將它們導出爲CSV並將其上傳到數據庫。例如，我有這個CSV記錄：字比較算法

1, John Doe,  ACME Comapny (the typo is on purpose)

當然，這兩家公司都保存在一個單獨的表，並與外鍵鏈接，所以我需要在插入之前發現正確的公司ID。我打算通過將數據庫中的公司名稱與CSV中的公司名稱進行比較來實現此目的。如果字符串完全相同，則比較應返回0，並且返回某些值隨着字符串變得更加不同而返回更大值，但strcmp不會在此處將其切換，因爲：

「Acme Company」和「Acme Comapny 「應該有一個非常小的差異指數，但」Acme公司「和」Cmea Mpnyaco「應該有非常大的差異指數或」Acme公司「和」Acme Comp。「。即使字符數不同，也應該有一個很小的差異指數。此外，「Acme公司」和「公司Acme」應返回0.

因此，如果客戶端在輸入數據時輸入類型，我可以提示他選擇他最想插入的名稱。

有沒有一個已知的算法來做到這一點，或者我們可以發明一個:) ？

來源

2009-01-23 disc0dancer

對於庫：http://stackoverflow.com/questions/83777/are-there-any-fuzzy-search-or-string-similarity-functions-libraries-written-for – nawfal 2013-06-06 05:25:11

您可能想查看Levenshtein Distance算法作爲起點。它會評估兩個單詞之間的「距離」。

This SO thread實施谷歌風格的「你的意思是......？」系統也可以提供一些想法。

來源

2009-01-23 16:25:23 MattK

你打我吧:) – 2009-01-23 16:27:03

這非常有用。我看到PHP甚至有一個levenshtein（）函數。謝謝。 – disc0dancer 2009-01-23 16:30:39

我發現了mySQL的levensthein函數，快速谷歌應該找到它。 – 2009-01-23 16:32:15

我用Levenshtein Distance算法取得了一些成功，也有Soundex。

你在使用哪種語言？我們可能會指出具體的例子

來源

2009-01-23 16:26:44

有多種算法可以做到這一點，大多數數據庫甚至默認包含一個算法。這實際上是一個相當普遍的問題。

如果它只是英文單詞，例如SQL Server就包含SOUNDEX，它可以用來比較單詞所產生的聲音。

http://msdn.microsoft.com/en-us/library/aa259235%28SQL.80%29.aspx

來源

2009-01-23 16:29:13 Loki

我不知道你在編碼的語言，但如果它是PHP，你應該考慮以下算法：

levenshtein()：返回字符的最小數必須更換，插入或刪除將一個字符串轉換爲另一個字符串。
soundex()：返回一個單詞的四個字符的soundex關鍵字，該關鍵字應與任何相似聽起來的單詞的關鍵字相同。
metaphone()：與soundex類似，可能對您更有效。它比soundex（）更準確，因爲它知道英語發音的基本規則。 metaphone生成的密鑰長度可變。
similar_text()：與levenshtein（）類似，但它可以返回百分比值。

來源

2009-01-23 16:32:06

我實際上實現了一個類似的系統。我使用Levenshtein距離（如其他海報已經建議），並進行了一些修改。未經修改的編輯距離（適用於整個字符串）的問題在於它對單詞重新排序很敏感，因此「Acme Digital Incorporated World Company」與「Digital Incorporated World Company Acme」的匹配很差，而且這種重新排序在我的數據中很常見。

我對它進行了修改，以便如果整個字符串的編輯距離過大，算法會回到匹配的單詞之間以找到一個好的單詞匹配匹配（二次成本，但是如果if有太多的話，所以它工作確定）。

來源

2009-01-23 16:35:33

我在PHP中實現它，現在我正在編寫一段代碼，它將分解單詞中的兩個字符串，並使用levenshtein將第一個字符串中的每個單詞與第二個字符串的單詞進行比較，並接受低可能的值。我完成後發佈它。

非常感謝。

更新：這是我想出來的：

function myLevenshtein($str1, $str2) 
{ 
    // prepare the words 
    $words1 = explode(" ", preg_replace("/\s+/", " ", trim($str1))); 
    $words2 = explode(" ", preg_replace("/\s+/", " ", trim($str2))); 

    $found = array(); // array that keeps the best matched words so we don't check them again 
    $score = 0;  // total score 
    // In my case, strings that have different amount of words can be good matches too 
    // For example, Acme Company and International Acme Company Ltd. are the same thing 
    // I will just add the wordcount differencre to the total score, and weigh it more later if needed 
    $wordDiff = count($words1) - count($words2); 
    foreach($words1 as $word1) 
    { 
    $minlevWord = ""; 
    $minlev = 1000; 
    $return = 0; 
    foreach($words2 as $word2) 
    { 
     $return = 1; 
     if(in_array($word2, $found)) 
     continue; 
     $lev = levenshtein($word1, $word2); 
     if($lev < $minlev) 
     { 
     $minlev = $lev; 
     $minlevWord = $word2; 
     } 
    } 
    if(!$return) 
     break; 
    $score += $minlev; 
    array_push($found, $minlevWord); 
    } 

    return $score + $wordDiff; 
}

來源

2009-01-23 16:48:53 disc0dancer

我已經採取的SoundEx，萊文斯坦，PHP相似，雙音位和一組對字符串擴展方法包裝起來的C＃。

Entire blog post here。

來源

2009-01-26 18:40:38 plinth