字符串比較算法，相關性，多少「相似」2個字符串

我有相同數據（公司）的2個信息來源，我可以通過唯一ID（合同編號）連接在一起。第二個不同來源的出現是由於這兩個來源是手動更新的，這是獨立的。所以我有一個ID和公司名稱在2個表中。字符串比較算法，相關性，多少「相似」2個字符串

我需要拿出一個算法會比較名稱 2分表爲同一ID中，並且爲了所有的公司由表示字符串是多麼的不同（要突出一個變量最不同的，將被放置在列表的頂部）。

我看着簡單的Levenshtein距離計算算法，但它在字母級別，所以我仍然在尋找更好的東西。

Levenshtein之所以沒有真正做好這項工作，是因爲公司有一個名稱，由組織形式（LTD，JSC，co。等）加上前綴或後綴。所以我們可能會有很多JSC "Foo"，它們與Foo JSC.的差別很大，但我真正在數據庫中尋找的是不同的字符串，如SomeLongCompanyName JSC和JSC OtherName。

有沒有什麼好的方法可以做到這一點？（我不太喜歡用正則表達式來分隔每個字符串中的單詞，然後使用Levenshtein距離查找另一個字符串中的每個單詞的匹配的想法，所以我正在尋找其他想法）

來源

2010-09-16 AlexanderMP

通過將組織表單移動到最後按字母順序排序來預處理每個字符串。然後使用Levenshtein距離。 – TonyK 2010-09-17 08:29:35

這裏也有困難。想象一下擁有'MeLTD'LTD'的公司。我在這裏實際上沒有'LTD'，這是另一種語言，所以我有很多像'IS''II''IM''SA''SRL'（有時用點分開），而2個字母是非常可能會出現在名字本身。你仍然應該寫這個答案，因爲這是一個新的想法，我會嘗試。至少會給你一個'上'。 – AlexanderMP 2010-09-17 08:48:36

在這種情況下，它會變得混亂。如何：1.用空格替換所有標點符號。 2.將字符串分解爲空白分隔的單詞。 3.將<= 4個字符的所有單詞移至末尾，按字母順序排序。萊文斯坦。你想要更多，我有一個代理:-) PS你也可以投票評論！ – TonyK 2010-09-17 15:34:40

如何：
1.用空格替換所有標點符號。
2.將字符串分解爲空白分隔的單詞。
3.將< = 4個字符的所有單詞移至末尾，按字母順序排序。
4. Levenshtein。

來源

2010-09-19 21:43:03 TonyK

您的幫助導致解決方案，不妨將其標記爲正確的答案。但是那些尋求全部細節和代碼的人，看看我的答案（我會稍微更新一下，以獲取全部細節）。謝謝。 – AlexanderMP 2010-09-20 08:13:26

您可以過濾（刪除）這些「常用詞」（類似於刪除全文索引的停用詞），然後搜索那個？如果不是，可以在比較之前按字母順序排列單詞嗎？

作爲Levenshtein距離的替代或補充，您可以使用Soundex。這不是非常好，但它可以用來索引數據（當使用Levenshtein時這是不可能的）。

來源

2010-09-16 12:20:08

常用字也很重要，'JSC'與'LTD'不同，組織形式可能會改變，儘管很少。至於Soundex - 它可以標記2個完全不同的單詞是平等的。對單詞進行排序雖然成本很高， – AlexanderMP 2010-09-16 12:47:01

謝謝你倆的想法。我用4個指數，其是通過（相對距離）的兩個詞的長度之和以下的劃分的Levenshtein距離：

就在2串
結果組成的串組分離的字之後序列，消除非單詞字符，按升序排序並與空格結合爲分隔符。
包含在引號之間的字符串（如果不存在此類字符串，則採用原始字符串）
字符串由每個單詞的按字母順序排列的第一個字符組成。

回報每個這些是1和1000得到的值之間的整數值是產物：
X1^E1 * X2^E2 * X3^E3 * X4^E4
凡X1..X4是指數，和E1..E4是用戶提供有價值（重要）的偏好是每個指標。爲了將結果保持在1..1000的合理值內，向量（E1..E4）被歸一化。

結果令人印象深刻。整個過程比我預期的要快得多（在C＃中爲Microsoft SQL Server 2008構建它作爲CLR程序集）。選擇E1後E4正確，整個數據庫中非空值的最大索引（最大差異）爲765.直到300，實際上沒有匹配的公司名稱。大約有200家公司有類似的名字，有些是相同的名字，但用非常不同的方式編寫，有縮寫，附加單詞等等。當它達到100或更少時 - 實際上所有記錄都包含名稱相同但是寫有細微差別，並且30，只有訂單或標點可能不同。
完全有效，結果比我預期的要好。

我寫了a post on my blog，分享這個庫，以防別人需要它。

來源

2010-09-18 12:48:45 AlexanderMP

字符串比較算法，相關性，多少「相似」2個字符串

回答

相關問題