python - 字符加扰的Levenshtein距离？

Question

我正在寻找一个字符串比较度量 ala Levenshtein，当字符串中的字符被打乱时，它也可以工作。有谁知道这样的指标？如果有一个 Python 模块可以计算这样的指标，那就太好了。谢谢！

Answer 1

您可以尝试该difflib库，或者还有一个名为pylevenshtein的外部库。

Answer 2

计算每种类型字符的数量（使用 HashMap 或等效项），然后减去结果值并取每个减法的绝对值。将所有这些加在一起，然后除以 2（因为您已经重复计算了每个差异）。

例子：

banana
batman

a - 3 , 2 -> |1| -> 1
b - 1 , 1 -> |0| -> 0
m - 0 , 1 -> |-1| -> 1
n - 2 , 1 -> |1| -> 1
t - 0 , 1 -> |-1| -> 1

因此你有1+1+1+1 = 4 -> 4/2 = 2

检查：在banana中，将一个更改n为 a t，将一个更改a为一个m（2 个更改），您的字母在batman

如果字符串的长度不同，请计算字符串长度的差异，然后从差异计数中减去该数字（上图）。然后除以 2，然后将该数字加回去。

例子：

nab
banana

total difference count: 3
3 - 3 = 0 -> 0 / 2 = 0 -> 0 + 3 = 3

此外，我根本不会在这里使用 Levenshtein，因为该问题的很多困难在于定位，而您并不关心。

Answer 3

可以简单地编辑 levenstien 距离的动态规划解决方案，以捕获例如德里、德里的成对加扰，并且与相应的替换或添加或删除相比，赋予这个较小的权重。

编辑：这个算法已经存在并被命名为Damerau–Levenshtein distance。搜索这个算法会给你一个Python 包，你可以直接使用它。