Levenshtein短语的距离/字符串匹配算法

Question

我有两个电子表格，每个电子表格都提供有关在我的工作网络上运行的一组应用程序的信息。他们是由两个独立的人创造的，他们从来没有见过这样的人。

因此，它们给予应用程序的名称在表单之间并不固定。但是，它们是相似的。例如，可以调用应用程序“Office 2010”，其他“MS Office 10”或其他。

我查了Levenshtein算法，但是这似乎只适用于单词顺序不变的单个单词或短语，而只有拼写不同。 （我不是计算机科学家，请随时纠正我）。

因此，我正在寻找一种算法，对于一张表中的每个名称，可以循环显示另一张表中的每个名称并查找最接近的匹配项。不一定要完美，任何事情都会有所帮助。

任何想法？感谢所有能够帮助的人。

Answer 1

Levenshtein距离是编辑距离的一种通用形式，用于统计编辑的次数 - 插入，删除和替换 - 将一个字符串转换为另一个字符串。你说得对，它不能很好地处理换位，但根据你的需要，它仍然可以完成这项工作。

模糊字符串匹配是一个启发式区域，所以最好的办法是四处游玩以尝试满足您的特定目标。例如，您可以尝试通过对文本进行大小写折叠来对文本进行预处理，然后在采用编辑距离之前按照字典顺序对令牌进行排序，这在很多情况下有助于进行换位。如果一个字符串是另一个字符串的近似子字符串，则还可以减去两个字符串之间的绝对长度差异，以便获得较低的距离 - 但要小心，因为如果这样做，空字符串将匹配所有内容。

总的来说，你总是会在特异性和灵敏度之间进行权衡，所以诀窍就是简单地调整启发式，使其以你熟悉的方式执行。