代码之家 › 专栏 › 技术社区 › Lerner Zhang

SequenceMatcher在编辑距离和difflib中的应用有什么不同?

longest-substring edit-distance algorithm python

1

Lerner Zhang · 技术社区 · 3 年前

我知道编辑距离算法的实现。通过动态规划,我们首先填充第一列和第一行,然后通过比较左上方和左上方的三条路径,填充条目的右下方。而对于Ratcliff/Obershelp算法,我们首先从两个字符串中提取出最长的公共子字符串,然后对左侧两个子字符串和右侧两个子字符串进行递归操作,直到没有剩余字符。

它们都可以用来计算两个字符串之间的相似性,并使用四个操作将一个字符串转换为另一个:删除、替换、复制和插入。

但我不知道什么时候在两者之间使用 SequenceMatcher in edit distance 和 that in difflib ?

以下是我在互联网上的发现,这让我认为这个问题也会让其他人受益:

与difflib SequenceMatcher类似,但使用Levenshtein/edit距离。

据我所知,我有以下想法:

我发现 edit distance 还有 Ratcliff/Obershelp algorithm 两者都可以用于拼写检查。但是什么时候用哪一个呢?
我认为编辑距离是用来寻找最小编辑序列的,而Ratcliff/Obershelp算法 在人们看来“看起来不错”的匹配结果 然而,“look right”这个词似乎太模糊了,尤其是在现实应用中。更重要的是,什么时候是必须/首选的最小编辑顺序?

如有任何建议,我们将不胜感激,并提前表示感谢。

1 回复 | 直到 3 年前

1

Tim Peters 3 年前

“在人们看来是对的”不一定就是全部那个模糊的在网上搜索原因的讨论,例如,使用非常广泛的 git 源代码控制系统增加了“耐心”和“直方图”差分算法作为选项。“最小编辑距离”的变化通常会产生差异,这对人类来说是不和谐的,我不会在这里重复通过搜索很容易找到的例子。

从形式上看,Levenshtein更符合数学家所说的“距离”。主要是, difflib 是的 .ratio() 可以取决于传递给它的参数的顺序,但Levenshtein对顺序不敏感:

>>> import difflib
>>> difflib.SequenceMatcher(None, "tide", "diet").ratio()
0.25
>>> difflib.SequenceMatcher(None, "diet", "tide").ratio()
0.5

至于剩下的,我认为你不会得到明确的答案。“相似性”有很多概念,不仅仅是你提到的两个,而且它们都有自己的粉丝。在磁盘空间和带宽稀缺且昂贵的年代,“最小”可能被认为更重要。

限制基因突变的物理现实使得考虑空间位置的措施在该领域变得更加重要——如果它是“最小的”,如果它在物理上也是不可信的,这一点无关紧要;——要搜索的术语:Smith–Waterman和Neederman–Wunsch。