使用近似字符串匹配比較/匹配兩列（模糊字符串匹配，levenshtein）

首先讓我解釋我想實現的目標。我正在製作的應用程序應該能夠將兩個不同表格的兩列與彼此進行比較。因此，第一個表中列的每個單元格都應鏈接到第二個表中列的最佳匹配單元格。所以，你會得到這樣的事情：使用近似字符串匹配比較/匹配兩列（模糊字符串匹配，levenshtein）

example http://foto.modelbouwforum.nl/images/2014/11/03/Levenshtein_match.png

這可以很容易地通過使用萊文斯坦的算法來實現。所以我在c＃中編寫了一個測試程序，看看我是否可以像圖像顯示的那樣重新創建相同的結果。我做了兩個數組，一個包含圖像的第一列，另一個包含圖像的第二列。將第一列的每個單元格與第二列的每個單元格進行比較，這意味着我在每個單元格上總共進行4次迭代（總共16個單元格）。第二列的最高匹配（具有最低Levenshtein距離的匹配）然後鏈接到第一列的單元格。

問題：假設我們有兩個100K行的大列，這應該會導致一些嚴重的性能問題。因爲第一列中的每個單元格都需要與第二列中的每個單元格匹配以獲得最高可能的匹配，所以您必須迭代100K * 100K = 100億次。所以我必須創造一些東西來避免迭代100億次。

我做了一些研究levenshtein可以用在哪裏，並碰到這個：http://www.slideshare.net/fullscreen/VasileTopac/fuzzy-hash-map/4。我想知道我是否能夠創建類似鏈接中的人的內容？

有些事情要考慮：

在這樣的大柱有可能是在單個細胞上的多個匹配（根據用戶需要選擇正確的）。這意味着您不能從當前搜索中排除先前匹配的單元格，以便降低迭代次數。
在此示例中，匹配/比較僅在兩列上完成，但將來我希望將表1 中的單個列與表2中的所有列進行比較（用戶的工作量較少）。這會花費更多的時間，因爲你可以預期。

注：我只使用C＃4個月，現在，我希望有人能爲我提供一個很好的起點（我寧願沒有得到一個完全工作的答案，我寧願希望做一些研究我也從中學習）。感謝您的理解。英語不是我的母語，所以請隨時編輯我的文章。

來源

2014-11-03 WonderTiger

我假設「@us」前綴可以被簡單地刪除（或忽略符號），那麼我首先嚐試**在一個表中集羣**條目（例如「PUSH_BUTTON」，「PUSH-BUTTON」和「PUSH按鈕「將全部變爲」按鈕「，符號可以被刪除，數字將成爲分隔符（是的，迄今爲止非常天真！）現在你可以提取一個**指紋**（現在可能只是最長的單詞）。這將是你的散列鍵 – 2014-11-03 15:17:26

現在對於第二張桌子上的每個條目，你不必計算第一個表中每一個的距離：簡單地應用聚類，然後計算距離與指紋，設置將大大減少，然後您可以計算子集中每個項目的距離（例如FUSE 1A，FUSE 2A，FUSE 5A，FUSE 10A都將具有「FUSE」鍵） – 2014-11-03 15:18:09

總結：如果您的第一個表有100K個條目，並將它們減少到1000集羣（每個集羣有100個） s），那麼你將計算距離只有1000（每個羣集）+100（在選定羣集中的每個條目）。 1100 Levenshtein的計算（慢速部分）而不是100000（大約90％的增益，但你必須增加時間進行聚類計算）。當然，不要忘記所有這些東西都必須緩存，所以集羣是第一個表計算一次，並重新用於第二個表中的每個條目。最後（包括你的原始算法）這是很好的並行化！ – 2014-11-03 15:22:11

嘗試想出一些假設總是成立有關的匹配，可以細分成更小的塊，如：

表1中的第一個大寫字母字符必須在表中的第一個大寫字母字符匹配2

您可以找到一些有效的假設，讓你預先處理的值轉換成另一列：

FirstAlpha1 FirstAlpha2 
=========== =========== 
P    C 
S    F 
C    P 
F    S

然後，您可以對此額外值進行簡單排序並加入（精確匹配），以將解決方案分成更小的塊。

來源

2014-11-03 15:15:36 BlueMonkMN

使用近似字符串匹配比較/匹配兩列（模糊字符串匹配，levenshtein）

回答

相關問題