如何计算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不考虑gap。距离=编辑次数（插入+删除+替换），而Needleman–Wunsch algorithm这是标准的全局对齐方式，请考虑间隙。这是Neederman–Wunsch和Levenshtein之间的（间隙）差异，因此很多论文使用两个序列之间的最大距离（但这是我自己的理解，我不确定100%）}

下面是关于PAITERN分析的IEEE事务：Computation of Normalized Edit Distance and Applications在本文中，规范化编辑距离如下：

Given two strings X and Y over a finite alphabet, the normalized edit distance between X and Y, d( X , Y ) is defined as the minimum of W( P ) / L ( P )w, here P is an editing path between X and Y , W ( P ) is the sum of the weights of the elementary edit operations of P, and L(P) is the number of these operations (length of P).

Answer 2

虽然没有绝对的标准，但是规范化的levensinide距离是最常用的定义。这两个例子都是0.5。

由于max是Levenshtein距离的最低上限，因此它是有意义的：要从b中获得a，在len(a) > len(b)中，您始终可以用a中的相应元素替换len(b)中的第一个b元素，然后插入缺少的部分a[len(b):]，总共进行len(a)编辑操作。

这个参数显然扩展到了len(a) <= len(b)的情况。要将规范化距离转换为相似性度量，请将其从1中减去：1 - ldist / max(len(a), len(b))。

Answer 3

通过更仔细地研究C代码，我发现这种明显的矛盾是由于ratio对待“替换”编辑操作与对待其他操作不同（即代价为2），而distance对待它们都一样，代价为1。

这可以在ratio_py函数中对内部levenshtein_common函数的调用中看到：

---

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。

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