根据相似度匹配 2 个字符串列表

Problem

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

例如，我有这两个列表：

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

我想得到以下结果：

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

附加信息

为了比较两个字符串，我想使用类似的东西编辑距离 http://en.wikipedia.org/wiki/Levenshtein_distance。例如，当我比较"a1" with "a2"，它给我的距离比"a1" with "b2", so "a1"+"a2"会被认为是更好的匹配。

当不同的配对获得相同的距离结果时，我会变得复杂。您不能仅采用特定项目的最小距离list1，因为其中的另一项list1可以获得相同的距离与相同的项目list2.

Question

您对此有算法建议吗？

我现在在哪里

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

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

• 该对（二维数组中的 i,j 索引）
• 距离

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

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

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

一旦您确定了要用来跟踪两个字符串之间的“距离”的度量（无论是编辑距离还是其他距离），您就可以使用匈牙利算法 http://en.wikipedia.org/wiki/Hungarian_algorithm来解决你的问题。

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