通过相似性匹配两个字符串列表

Question

问题

我有两个字符串列表。我想从这些列表中找到最佳匹配的对。

例如，我有以下两个列表：

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

我想要获得以下结果：

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

附加信息

为了比较两个字符串，我想使用类似于Levenshtein距离的算法。例如，当我将"a1"与"a2"进行比较时，它给出的距离比"a1"与"b2"的距离短，因此"a1"+"a2"将被视为更好的匹配。

当不同的字符串对得到相同的距离结果时，问题就变得复杂了。你不能仅仅拿一个特定的list1中的最小距离，因为list1中的另一个项可能会与list2中的同一项获得相同的距离。

问题

你有相关的算法建议吗？

目前进展

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

我计算每对字符串的Levenshtein距离，并将结果存储在二维数组中。然后我构建了一个单维数组，其中每个元素都具有以下内容：

• 相对的一对（我的二维数组中的i，j索引）
• 距离

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

最后，我遍历排序后的数组，并将具有共同距离的项一起解决（首先所有distance==0的项，然后所有distance==1的项，等等...）。每次解析一个元素时，我都会在我的2D数组中标记它，以便可以快速跳过已解决的项在我排序的数组中。

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

- decasteljau

---

请定义最佳匹配。是距离之和吗？还是距离平方的和？ - biziclop

如果你想要最小化距离的总和，你的问题似乎是一个最大权二分图匹配，如果这有帮助的话。 - biziclop

@biziclop 非常有趣的问题。我没有看到过这样的问题。我不确定哪一个是最好的：距离总和还是平方总和。我将调查这些途径。谢谢。 - decasteljau

Answer 1

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

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

- abeln

---

注意：匈牙利算法正在工作并返回良好的结果，但它显示出严重的性能问题。该算法是O（N ^ 3），当用于数百个条目时，处理时间会变得非常长。 - decasteljau

我发现性能取决于内容而有很大的差异。当匹配很容易（完全匹配或者模糊匹配但是歧义度低）时，性能非常好。但是当你传入完全不相关的列表，即使只有100个条目，性能也会非常糟糕（超过30秒）。希望对我来说，正常情况下列表之间匹配得很好。 - decasteljau

嗯...O(n^3)在100个元素的情况下需要30秒以上。肯定有一个相当大的常数隐藏在O符号里面。 - abeln

我发现性能问题与在Debug模式下使用STL相关。同一场景在Debug模式下需要30秒，在Release版本中却不到100毫秒。 - decasteljau

很高兴听到您能够加速这个过程！ - abeln

Answer 2

我对此可能进行优化的建议是：

I calculate the Levenshtein distance for each possible pair of string and store the results in a 2-dimension array.

你可以通过考虑字符串的长度来避免计算每对字符串的距离。因为假设：

1. if the pair is e.g. "ab", and "cdefg"
2. and you know that there's another string that has similar length with "ab" e.g. "xy"

那么你不需要计算“ab”和“cdefg”之间的距离。因为这些长度的字符串之间可以得到的最小距离是3，而相等长度的两个字符串之间的最大距离（例如示例中的“ab”和“xy”）将为2。

您可以通过使用更智能的数据结构来实现此目的，该数据结构可以跟踪字符串的长度，例如在C++0x或tr1 C++中使用unordered_map<int, vector<string> >。

- ryaner