Jaro-Winkler和Levenshtein距离的差异？[关闭]
我想从多个文件做数百万条记录的模糊匹配。我为此确定了两种算法：Jaro-Winkler和Levenshtein编辑距离。
共有1个答案
Levenshtein计算将一个字符串转换为另一个字符串所需的编辑次数（插入、删除或替换）。Damerau-Levenshtein是一个修改版本，它也将换位视为单个编辑。虽然输出是整数次的编辑，但可以通过以下公式对其进行规范化以给出相似度值
1 - (edit distance / length of the larger of the two strings)
Jaro算法是一种公共字符的度量，在距离上不超过较长字符串长度的一半，并考虑了换位。Winkler修改了这个算法，以支持这样一个观点，即靠近字符串开头的差异比靠近字符串结尾的差异更显著。Jaro和Jaro-Winkler适合比较单词和名称等较小的字符串。
决定使用哪个不仅仅是性能问题。选择一个适合所比较字符串性质的方法是很重要的。但总的来说，您提到的两种算法都可能代价高昂，因为必须将每个字符串与其他字符串进行比较，而数据集中有数百万个字符串，这是一个巨大的比较数量。这比为每个字符串计算语音编码，然后简单地将共享相同编码的字符串分组要昂贵得多。
- Jaro
- Jaro-Winkler
- Levenshtein
- 达梅劳-莱文施泰因
最慢的要比最快的花2到3倍的时间。当然，这些时间取决于字符串的长度和实现，并且有一些方法可以优化这些算法，但这些算法可能还没有被使用过。
-
例子： 我在想，如果仅仅为了比较两个字符串并检测细微的变化，两个算法都满足了这个目的，那么除非是为了提高性能，否则选择一个而不是另一个就没有附加值了？
-
如何在C#中实现Jaro-Winkler距离字符串比较算法？
-
问题内容： 我一直想知道如何在Transact SQL中实现此算法，https：//en.wikipedia.org/wiki/Jaro%E2%80%93Winkler_distance 怎么做到呢？ 问题答案： 今天，我终于偶然发现了leebickmtu的这个Stack Overflow-answer，它显示了最初从Java移植的C＃实现。我自由地将其移植到Transact SQL函数，请尽情享
-
我使用Levenshtein距离算法将作为用户输入提供的公司名称与已知公司名称数据库进行比较，以找到最接近的匹配项。算法本身工作正常，但我想构建一个偏差，这样如果字符串的初始部分匹配，编辑距离就会被认为更低。 例如，如果搜索条件是“ABCD”，那么“ABCD Co.”和“XYX ABCD”具有相同的编辑距离。但是，我想增加一个事实，即第一个字符串的开头部分比第二个字符串更符合搜索条件。
-
我使用Levenshtein算法来查找两个字符串之间的相似性。这是我正在制作的程序的一个非常重要的部分，所以它需要有效。问题是算法没有发现以下示例相似： CONAIR AIRCON 编辑：我还研究了“Damerau-Levenshtein”算法，它增加了换位。问题是这种转换只针对相邻的字符（而不是多个字符）。
-
问题内容： 在Python + Sqlite中是否有可用的字符串相似性度量，例如与模块有关？ 用例示例： 此查询应匹配ID为1的行，但不匹配ID为2的行： 如何在Sqlite + Python中做到这一点？ 关于我到目前为止发现的注释： 该Levenshtein距离，即单字符编辑（插入，删除或替换）的最小数量需要改变一个字到另一个，可能是有用的，但我不知道是否SQLite中存在的正式实施（我看到一