有比Levenshtein距离更好的字符串比较算法吗？

Question

我一直在使用它来完成一个项目，但其中一些结果不是我想要的。例如：

当“日期”与

1. “州”比较时，它的lev距离为2
2. “今天的日期”比较时，它的lev距离为9

这当然是我们从算法中预期的，但我想知道是否有任何东西可以给出更接近于源字符串（"日期"）的任何比较字符串的匹配。意思是，“今天的日期”会因为它包含“日期”而具有更高的排名。

如果您能找到一个实现此功能的.NET库，则可获得额外奖励分数。

- Abe Miessler

---

我们在谈论什么类型的奖励积分？ - The Scrum Meister

@Scrum，我会来洗你的车。 - Abe Miessler

@Lie，我以为我做了。你是只看了问题的标题还是阅读了整个问题？请看倒数第二段对我所说的“better”进行解释。 - Abe Miessler

你可以简单地对字符串进行单词匹配，并根据结果修改它的排名吗？ 还可以查看这个问题：https://dev59.com/x0nSa4cB1Zd3GeqPPp4L - Jaroslav Jandek

@Abe Miessler：举一个例子是不够的，你应该清楚地定义为什么一个字符串应该被认为比另一个更接近；或者如果你不知道，你能解释一下你试图解决什么问题吗？Levenshtein编辑距离给出了将一个字符串转换为另一个字符串所需的最小单字符转换次数（插入、删除和更改）。从某种意义上说，它是“最佳”的，但显然不是你要寻找的。 - Lie Ryan

例如，您可以取多个同义词与您的单词之间Levenshtein距离的最小值。例如 {"日期"，“今天的日期”，“今天的日期”，...}。如果您需要匹配许多不同的单词，定义同义词可能需要大量工作。 - Anonym Mus

Answer 1

你可能想找的是最长公共子序列？

- Lie Ryan

Answer 2

我认为在使用Levenshtein之前，你应该对单词进行分词。另外，还有Jaro-Winker距离可以作为替代。

有一个.NET库SimMetrics似乎涵盖了几个替代方案。

- Johan Sjöberg

---

有趣的是，您是在说比较所比较的每个单词吗？那么我是否应该使用所比较值中任何单词的最低分数？ - Abe Miessler

@Abe - 这取决于问题本身，是否适合比较每个标记并选择最低匹配。实质上，这相当于进行模糊的“包含”搜索。在比较校园建筑物的建筑名称时，我会这样做，因为人们可能只输入名称的主要部分，但我希望能基于完整的名称进行匹配。我所做的是对源字符串和目标字符串进行标记化，找到每个源标记与每个目标标记之间的最小距离，并将它们求和。 - tvanfosson

根据您的应用程序而定，如果您想要使用它为一个或多个单词提供拼写建议，我认为您应该逐个进行比较；如果您希望查看单词 a 在句子 b 中出现的可能性也是一样的。但正如我所说，这取决于您需要距离的目的。 - Johan Sjöberg

Answer 3

要做好它，您需要了解使用上下文。

如果您正在尝试进行地址查找，那么“Nosuch STREET”可能与“Nosuch ROAD”的完美匹配，或者在禁飞名单中，您想要所有20个Gadaffi的拼写相匹配。

如果您试图分析一段历史文本在复制过程中发生了多少变化，那么您需要不同的算法。

- Martin Beckett