[PYTHON] 어떻게 파이썬 - Levenshtein.ratio 계산됩니다

어떻게 파이썬 - Levenshtein.ratio 계산됩니다

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는 왜 안되는가?

해결법

1. ==============================

   1.다음과 같이 'ab'와 'ac'에 대한 Levenshtein 거리 :

   다음과 같이 'ab'와 'ac'에 대한 Levenshtein 거리 :

   정렬은 다음과 같습니다.

     a c
     a b 
   

   정렬 길이 = 2 불일치 수 = 1

   Levenshtein Distance는 1을 나타냅니다. 왜냐하면 ac를 ab (또는 reverse)

   거리 비 = (Levenshtein 거리) / (정렬 길이) = 0.5

   편집하다

   글 쓰고 있구나

   (lens - ldist) / lensum = (1 - ldist / lens) = 1 - 0.5 = 0.5이다.

   그러나 이것은 매칭 (거리가 아님) 진눈깨비, 당신은 그것의 서면을 볼 수 있습니다

   일치하는 %

   p = (1 - l/m) × 100
   

   여기서 l은 levenshtein 거리이고 m은 두 단어 중 가장 긴 길이입니다.

   (주의 : 일부 저자는 둘 중 가장 긴 것을 사용하고, 정렬 길이를 사용했습니다)

   (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 ANALYSIS에 대한 TRANSACTIONS입니다. 정규화 된 편집 거리 및 응용 프로그램 계산이 백서에서는 표준화 된 편집 거리를 다음과 같이 설명합니다.

2. ==============================

   2.C 코드를 더 자세히 살펴보면,이 명백한 모순은 비율이 "바꾸기"편집 작업을 다른 작업 (즉, 비용이 2 인)과 다르게 처리하는 반면, 거리는 모든 작업을 동일하게 처리한다는 사실에 기인합니다 비용은 1입니다.

   C 코드를 더 자세히 살펴보면,이 명백한 모순은 비율이 "바꾸기"편집 작업을 다른 작업 (즉, 비용이 2 인)과 다르게 처리하는 반면, 거리는 모든 작업을 동일하게 처리한다는 사실에 기인합니다 비용은 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;
   

   [대답]

   그래서 나의 예에서,

   비율 ( 'ab', 'ac')은 문자열 (4)의 전체 길이에 대한 대체 작업 (비용 2)을 의미하므로 2/4 = 0.5입니다.

   그것은 "방법"을 설명합니다, 나는 유일한 나머지 부분이 "왜"라고 생각하지만, 잠시 동안 나는이 이해에 만족합니다.

3. ==============================

   3.절대 표준은 없지만 표준화 된 Levensthein 거리는 가장 일반적으로 정의되는 ldist / max (len (a), len (b))입니다. 두 예제 모두 0.5를 얻을 것입니다.

   절대 표준은 없지만 표준화 된 Levensthein 거리는 가장 일반적으로 정의되는 ldist / max (len (a), len (b))입니다. 두 예제 모두 0.5를 얻을 것입니다.

   최대 값은 Levenshtein distance에서 가장 낮은 상한이기 때문에 의미가 있습니다. len (a)> len (b) 인 곳에서 a를 얻으려면 b의 첫 번째 len (b) 원소를 항상 a의 해당 원소로 대체하면됩니다. 누락 된 부분을 [len (b) :]로 삽입하여 총 len (a) 편집 작업을 수행하십시오.

   이 인수는 명백한 방법으로 len (a) <= len (b) 인 경우까지 확장됩니다. 정규화 된 거리를 유사성 측정으로 변환하려면 1 - ldist / max (len (a), len (b))에서 빼십시오.

4. ==============================

   4.(lens - ldist) / lensum

   (lens - 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 비율 계산을 참조하십시오.

   다른 예시:

   비용은 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
   

from https://stackoverflow.com/questions/14260126/how-python-levenshtein-ratio-is-computed by cc-by-sa and MIT license