algorithm - 通过相似性匹配 2 个字符串列表

Question

问题

我有 2 个字符串列表。我想从我的列表中找到最匹配的配对。

例如，我有这两个列表:

list1 = {"a1","b1","c1"}
list2 = {"a2","b2","c2"}

我想得到以下结果:

results = {{"a1,"a2"}, {"b1,"b2"}, {"c1,"c2"}}

附加信息

要将 2 个字符串放在一起比较，我想使用类似于 Levenshtein distance 的东西.例如，当我比较 "a1"与 "a2" ，它给我的距离比 "a1" 更短与 "b2" , 所以 "a1" + "a2"将被认为是更好的匹配。

当不同的对得到相同的距离结果时，我会变得复杂。您不能只为 list1 中的特定项目取最小距离，因为 list1 中的另一项list2中的相同元素可以获得相同的距离.

问题

您对此有什么算法建议吗？

我现在在哪里

你最好不要先看我的发现，这样你就不会受到我工作的影响。

我计算每对可能的字符串的 Levenshtein 距离，并将结果存储在二维数组中。然后我构建一个单维数组，其中每个元素都有:

• 这对(我的二维数组中的 i,j 索引)
• 距离

然后我使用距离元素对这个数组进行排序。

最后，我遍历排序数组并一起解析具有共同距离的项目(首先所有距离==0，然后所有距离==1，等等)。每次解析一个元素时，我都会在我的二维数组中标记它，这样我就可以快速跳过已排序数组中已解析的项目。

我认为我可以比这个解决方案更好。它在时间和空间上可能不是最有效的。

Answer 1

一旦您确定了要用于跟踪两个字符串之间“距离”的指标，无论是 Levenshtein 距离还是其他距离，您都可以使用 Hungarian algorithm解决您的问题。

我个人从未实现过它，但维基百科包含几个可能有帮助的链接。