蟒蛇-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

通過仔細查看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的整個長度上。

這就解釋了「如何」，我想剩下的唯一方面就是「爲什麼」，但是現在我對這種理解感到滿意。

Answer 2

的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的長度）。

Answer 3

雖然沒有絕對的標準，但歸一化的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))。

Answer 4

(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 

更多信息：python-Levenshtein ratio calculation

又如：

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