如何计算python-Levenshtein.ratio

Question

根据python-Levenshtein.ratio消息来源:

https://github.com/miohtama/python-Levenshtein/blob/master/Levenshtein.c#L722

它被计算为(lensum - ldist) / lensum.这适用于

distance('ab', 'a') = 1
ratio('ab', 'a') = 0.666666

但是,它似乎打破了

distance('ab', 'ac') = 1
ratio('ab', 'ac') = 0.5

我觉得我必须遗漏一些非常简单的事情......但为什么不0.75呢？

Answer 1

Levenshtein距离为'ab'与'ac'如下:

对齐是:

  a c
  a b 

对齐长度= 2
个不匹配数= 1

Levenshtein Distance是1因为只有一个取代需要转移ac到ab(或反向)

距离比=(Levenshtein距离)/(对准长度)= 0.5

编辑

你在写作

(lensum - ldist) / lensum= (1 - ldist/lensum)= 1 - 0.5 = 0.5.

但这是匹配(而非距离)
REFFRENCE,你可能会注意到它的写作

Matching %

p = (1 - l/m) × 100

哪里l是levenshtein distance和m是length of the longest of the two的话:

_{(注意:有些作者使用了两个中最长的,我使用了对齐长度)}

(1 - 3/7) × 100 = 57.14...  

  (Word 1    Word 2    RATIO   Mis-Match   Match%
   AB         AB         0       0        (1 - 0/2 )*100  = 100%  
   CD         AB         1       2        (1 - 2/2 )*100  = 0%   
   AB         AC        .5       1        (1 - 1/2 )*100  = 50%      

_{为什么有些作者除以对齐长度,除了两者之一的最大长度？...,因为Levenshtein不考虑差距.距离=编辑次数(插入+删除+替换),而标准全局对齐的Needleman-Wunsch算法考虑间隙.这是Needleman-Wunsch和Levenshtein之间的(差距)差异,因此大量的纸张使用两个序列之间的最大距离(但这是我自己的理解,而IAM不确定100%)}

这是IEEE交易的PAITERN分析:规范化编辑距离和应用的计算在本文中,标准化编辑距离如下:

给定有限字母表上的两个字符串X和Y,X和Y之间的归一化编辑距离,d(X,Y)被定义为W(P)/ L(P)w的最小值,这里P是两者之间的编辑路径. X和Y,W(P)是P的基本编辑操作的权重之和,L(P)是这些操作的数量(P的长度).

Answer 2

通过更仔细地查看C代码,我发现这个明显的矛盾是由于ratio将"替换"编辑操作与其他操作(即成本为2)区别对待的事实,而distance对待它们都是相同的成本为1.

这可以levenshtein_common在ratio_py函数内部函数 调用中看到:

https://github.com/miohtama/python-Levenshtein/blob/master/Levenshtein.c#L727

static PyObject*
ratio_py(PyObject *self, PyObject *args)
{
  size_t lensum;
  long int ldist;

  if ((ldist = levenshtein_common(args, "ratio", 1, &lensum)) < 0) //Call
    return NULL;

  if (lensum == 0)
    return PyFloat_FromDouble(1.0);

  return PyFloat_FromDouble((double)(lensum - ldist)/(lensum));
}

并按distance_py功能:

https://github.com/miohtama/python-Levenshtein/blob/master/Levenshtein.c#L715

static PyObject*
distance_py(PyObject *self, PyObject *args)
{
  size_t lensum;
  long int ldist;

  if ((ldist = levenshtein_common(args, "distance", 0, &lensum)) < 0)
    return NULL;

  return PyInt_FromLong((long)ldist);
}

最终导致不同的成本参数被发送到另一个内部函数lev_edit_distance,其中包含以下文档片段:

@xcost: If nonzero, the replace operation has weight 2, otherwise all
        edit operations have equal weights of 1.

代码lev_edit_distance():

/**
 * lev_edit_distance:
 * @len1: The length of @string1.
 * @string1: A sequence of bytes of length @len1, may contain NUL characters.
 * @len2: The length of @string2.
 * @string2: A sequence of bytes of length @len2, may contain NUL characters.
 * @xcost: If nonzero, the replace operation has weight 2, otherwise all
 *         edit operations have equal weights of 1.
 *
 * Computes Levenshtein edit distance of two strings.
 *
 * Returns: The edit distance.
 **/
_LEV_STATIC_PY size_t
lev_edit_distance(size_t len1, const lev_byte *string1,
                  size_t len2, const lev_byte *string2,
                  int xcost)
{
  size_t i;

[回答]

所以在我的例子中,

ratio('ab', 'ac')因此,暗示了在弦(4)的总长度上的替换操作(成本为2)2/4 = 0.5.

这解释了"如何",我想唯一剩下的方面就是"为什么",但目前我对这种理解感到满意.

Answer 3

(lensum - ldist) / lensum

ldist 不是距离，是成本总和

不匹配的数组的每个数字来自上方、左侧或对角线

如果数字来自左边他是一个插入，它来自上面它是一个删除，它来自对角线它是一个替换

插入和删除的成本为 1，替换的成本为 2。替换成本为 2，因为它是删除和插入

ab ac cost 是 2 因为它是一个替代品

>>> import Levenshtein as lev
>>> lev.distance("ab","ac")
1
>>> lev.ratio("ab","ac")
0.5
>>> (4.0-1.0)/4.0    #Erro, the distance is 1 but the cost is 2 to be a replacement
0.75
>>> lev.ratio("ab","a")
0.6666666666666666
>>> lev.distance("ab","a")
1
>>> (3.0-1.0)/3.0    #Coincidence, the distance equal to the cost of insertion that is 1
0.6666666666666666
>>> x="ab"
>>> y="ac"
>>> lev.editops(x,y)
[('replace', 1, 1)]
>>> ldist = sum([2 for item in lev.editops(x,y) if item[0] == 'replace'])+ sum([1 for item in lev.editops(x,y) if item[0] != 'replace'])
>>> ldist
2
>>> ln=len(x)+len(y)
>>> ln
4
>>> (4.0-2.0)/4.0
0.5

更多信息：python-Levenshtein 比率计算

另一个例子：

成本为 9（4 次替换 => 4*2=8 和 1 次删除 1*1=1, 8+1=9）

str1=len("google") #6
str2=len("look-at") #7
str1 + str2 #13

距离 = 5（根据矩阵的向量 (7, 6) = 5）

比率为 (13-9)/13 = 0.3076923076923077

>>> c="look-at"
>>> d="google"
>>> lev.editops(c,d)
[('replace', 0, 0), ('delete', 3, 3), ('replace', 4, 3), ('replace', 5, 4), ('replace', 6, 5)]
>>> lev.ratio(c,d)
0.3076923076923077
>>> lev.distance(c,d)
5

Answer 4

尽管没有绝对的标准，但最常见的定义是归一化莱文斯特距离ldist / max(len(a), len(b))。这两个例子的结果都是 0.5。

这max是有道理的，因为它是 Levenshtein 距离的最低上限：要从 where 获取a，b您始终可以用 中的相应元素替换的len(a) > len(b)第一个元素，然后插入缺失的部分，完成总共编辑操作。len(b)baa[len(b):]len(a)

这个论点以明显的方式延伸到 的情况len(a) <= len(b)。要将归一化距离转换为相似性度量，请从 1 中减去它1 - ldist / max(len(a), len(b))。