问题
我有两个字符串列表。我想从这些列表中找到最佳匹配的对。
例如,我有以下两个列表:
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数组中标记它,以便可以快速跳过已解决的项在我排序的数组中。
我认为我可以提供比这个解决方案更好的解决方案。它可能不是时间和空间上最有效的。