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

Question

假设您有两个包含类似项目的字符串列表，其中包含更改（例如List 1：Apples，fruits_b，orange; List2：Fruit，apples，banana，orange_juice）。

给定距离度量，如Levenshtein距离，有哪些好的算法可用于查找最佳配对，即最小化所有配对的距离总和的配对？

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

Apples    - apples
fruits_b  - Fruit
orange    - orange_juice
          - banana

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

- static_rtti

---

所以你已经有了所有的距离，想要一个能够计算出最低总匹配的算法？匈牙利算法对你是否适用？ - svinja

@svinja：是的，我想那样应该可以。不过避免计算所有距离会更好。 - static_rtti

有趣的事实： "orange" 和 "banana" 之间的Levenshtein距离为5，而 "orange" 和 "orange juice" 之间的距离为6。（我认为Levenshtein距离只有在具有小值时才有意义，至少比单词长度小。） - M Oehm

@svinja：实际上，匈牙利算法的维基页面似乎暗示这两个列表具有相同数量的项目。不确定这是否是算法的基本限制。 - static_rtti

如果列表的大小不相同，对于每个“缺失”的单词，您只需向矩阵添加一列或一行，并将所有距离设置为相等（假设为0）。因此，您可以假装在第一个列表中有一个额外的单词，该单词与第二个列表中的所有单词的距离都相等。 - svinja

既然“编辑距离”已经是空间隐喻：你能否使用某种最近邻搜索，其中“坐标”是单词度量？（这些度量必须在单词本身上工作，以便您可以将单词放置在单词“空间”中，但我除了单词长度之外无法想出任何明智的东西。） - M Oehm

Answer 1

好的，下面是我的Python解决方案，使用了Levenshtein距离和匈牙利算法（都是外部包提供的）：

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]))

它的表现相当不错。但我仍然很好奇是否有人能提出更好的算法！

- static_rtti

---

定义“更好”。匈牙利/蒙克雷斯算法是一种高效的精确方法，用于解决分配（匹配）问题。它根据您的度量找到最优匹配。如果得到的匹配不够好，那是因为您的度量有问题，而不是方法的错。 - Gaminic

@Gaminic：我以为可能可以避免计算所有的指标。但它已经运行得非常好了。 - static_rtti