Levenshtein短語的距離/字符串匹配算法

Question

我有兩個電子表格，每個電子表格都提供有關在我的工作網絡上運行的一組應用程序的信息。他們是由兩個獨立的人創造的，他們從來沒有見過這樣的人。

因此，它們給予應用程序的名稱在表單之間並不固定。但是，它們是相似的。例如，可以調用應用程序「Office 2010」，其他「MS Office 10」或其他。

我查了Levenshtein算法，但是這似乎只適用於單詞順序不變的單個單詞或短語，而只有拼寫不同。 （我不是計算機科學家，請隨時糾正我）。

因此，我正在尋找一種算法，對於一張表中的每個名稱，可以循環顯示另一張表中的每個名稱並查找最接近的匹配項。不一定要完美，任何事情都會有所幫助。

任何想法？感謝所有能夠幫助的人。

Answer 1

Levenshtein距離是編輯距離的一種通用形式，用於統計編輯的次數 - 插入，刪除和替換 - 將一個字符串轉換爲另一個字符串。你說得對，它不能很好地處理換位，但根據你的需要，它仍然可以完成這項工作。

模糊字符串匹配是一個啓發式區域，所以最好的辦法是四處遊玩以嘗試滿足您的特定目標。例如，您可以嘗試通過對文本進行大小寫摺疊來對文本進行預處理，然後在採用編輯距離之前按照字典順序對令牌進行排序，這在很多情況下有助於進行換位。如果一個字符串是另一個字符串的近似子字符串，則還可以減去兩個字符串之間的絕對長度差異，以便獲得較低的距離 - 但要小心，因爲如果這樣做，空字符串將匹配所有內容。

總的來說，你總是會在特異性和靈敏度之間進行權衡，所以訣竅就是簡單地調整啓發式，使其以你熟悉的方式執行。