蟒蛇-Levenshtein.ratio是如何计算

按照python-Levenshtein.ratio来源：蟒蛇-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？

来源

2013-01-10 cjauvin

我查库（在链接给你），我也搞不清他为什么使用'sum'.Also '（1-1/3）= .666..'这是正确的根据代码，但也（'1 - 1/4）= 0.75'它如何.5？即使在文档中也不清楚......但是计算Levenshtein距离的实际公式是在我的答案中。 –

通过仔细查看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;

[ANSWER]

所以在我的例子，

ratio('ab', 'ac')意味着更换操作（2成本），琴弦（4），因此2/4 = 0.5的整个长度上。

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

来源

2013-01-12 18:46:02 cjauvin

的Levenshtein如下面在'ab'距离和'ac'：

所以取向是：

a c 
    a b

对齐长度= 2
号不匹配的= 1

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

距离比=（Levenshtein距离）/（比长度）= 0.5

EDIT

你书写

(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%

_{为什么一些作者的排列长度划分，通过二者的一个最大长度等..，？因为莱文斯坦不考虑差距。距离=编辑次数（插入+删除+替换），而标准全球对齐Needleman–Wunsch algorithm考虑差距。这是（间隙）的Needleman-Wunsch的和的Levenshtein之间使用最大距离的两个序列之间的差异，因此多的纸（但是这是我自己的理解，与IAM不能确定100％）}

这里是IEEE交易ON PAITERN分析：Computation of Normalized Edit Distance and Applications本文归一化编辑距离如下：

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

来源

2013-01-10 15:00:04

感谢您的回答，它是有道理的，但它没有解决真正困扰我的方面：两个结果（用相同的代码获得）似乎彼此不一致（即它们表明两个不同计算比率的方式）。怎么会这样？ – cjauvin

@cjauvin您是否阅读了我对您问题的评论......我已经检查过，并且我有同样的印象，根据文档它应该是'.75'，但在您的示例中有两个结果是矛盾的。 –

是的，我看到了你的评论，这就是为什么，虽然是好的和有趣的，我不能接受你的答案作为解决方案，因为我真正追求的是这段代码中矛盾的原因。也许我应该问问PL维护者。 – cjauvin

虽然没有绝对的标准，但归一化的Levensthe距离最常见的是ldist/max(len(a), len(b))。这两个例子都会产生0.5。

的max有道理的，因为它是Levenshtein距离最低上界：获得来自ba其中len(a) > len(b)，可以始终与相应的一些从a取代的b第一len(b)元素，然后插入缺失部分a[len(b):] ，总计len(a)编辑操作。

此参数以明显的方式扩展到len(a) <= len(b)的情况。要将标准化距离转换为相似性度量，请从一个中减去它：1 - ldist/max(len(a), len(b))。

来源

2013-01-10 15:30:21

嗨拉斯曼！你是正确的'最常用的定义ldist/max（len（a），len（b））'，考虑gap是[Needleman-Wunsch算法]（http://en.wikipedia.org/wiki/Needleman%E2% 80％93Wunsch_algorithm） –

(lensum - ldist)/lensum

ldist不是距离，是成本

所述阵列的每个数字是不匹配来自以上，从左侧或对角线

总和如果数字来自左侧，他是一个插入，它来自上面它是一个删除，它来自对角线它是一个替代品

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

AB AC成本是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

又如：

成本是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

来源

2015-09-10 14:25:55 rafaelcb21

蟒蛇-Levenshtein.ratio是如何计算

回答

相关问题