两个列表中字符串的模糊配对算法

Question

假设您有两个包含相似项目的字符串列表，但有更改（例如，列表 1：Apples,fruits_b,orange；列表 2：Fruit,apples,banana,orange_juice）。

给定距离度量，例如 Levenshtein 距离，找到最佳配对的好算法是什么，即最小化所有配对的距离总和的配对？

与我的示例相对应的结果是：

Apples    - apples
fruits_b  - Fruit
orange    - orange_juice
          - banana

附属问题：是否有一些工具已经实现了这个或类似的东西？

Answer 1

好的，这是我使用 Levenshtein 距离和匈牙利算法（均由外部包提供）的 python 解决方案：

from munkres import Munkres
from Levenshtein import distance
from sys import argv

if __name__ == '__main__':
    if len(argv) < 3:
        print("Usage: fuzzy_match.py file file")
        print("Finds the best pairing of lines from the two input files")
        print("using the Levenshtein distance and the Hungarian algorithm")
    w1 = [l.strip() for l in open(argv[1]).readlines()]
    w2 = [l.strip() for l in open(argv[2]).readlines()]
    if len(w1) != len(w2):
        if len(w2) > len(w1):
            w1, w2 = w2, w1
        w2.extend([""]*(len(w1)-len(w2)))
    matrix = []
    for i in w1: 
        row = []
        for j in w2:
            row.append(distance(i.lower(), j.lower()))
        matrix.append(row)
    m = Munkres()
    max_length = max(len(w) for w in w1)
    for i, j in m.compute(matrix):
        print(("{:<%d}{}" % (max_length+10)).format(w1[i], w2[j]))

它工作得很好。不过，我仍然很好奇是否有人可以提出更好的算法！