Как вычисляется python-Levenshtein.ratio




levenshtein-distance (3)

Посмотрев внимательнее на код 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') подразумевает операцию замены (стоимость 2) по всей длине строк (4), следовательно, 2/4 = 0.5 .

Это объясняет «как», я думаю, единственным оставшимся аспектом будет «почему», но на данный момент я удовлетворен этим пониманием.

По словам источника 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 ?


Хотя абсолютного стандарта не существует, нормализованное расстояние Левенштейна чаще всего определяется как ldist / max(len(a), len(b)) . Это дало бы .5 для обоих примеров.

max имеет смысл, поскольку он является самой нижней верхней границей расстояния Левенштейна: чтобы получить a из b где len(a) > len(b) , вы всегда можете заменить первые элементы len(b) элемента b соответствующими элементами из a , затем вставьте недостающую часть a[len(b):] , чтобы получить в общей сложности len(a) операций редактирования.

Этот аргумент очевидным образом распространяется на случай, когда len(a) <= len(b) . Чтобы превратить нормированное расстояние в меру сходства, 1 - ldist / max(len(a), len(b)) его из единицы: 1 - ldist / max(len(a), len(b)) .


Расстояние Левенштейна для 'ab' и 'ac' как 'ac' ниже:

так выравнивание это:

  a c
  a b 

Длина выравнивания = 2
количество несовпадений = 1

Levenshtein Distance равно 1 потому что для перевода ac в ab (или наоборот) требуется только одна замена

Отношение расстояний = (Расстояние Левенштейна) / (Длина выравнивания) = 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%      

Почему некоторые авторы делят на длину выравнивания, а другие - на максимальную длину одного из обоих? .., потому что Левенштейн не учитывает разрыв. Расстояние = количество правок (вставка + удаление + замена), в то время как алгоритм Нидлмана-Вунша, который является стандартным глобальным выравниванием, учитывает разрыв. Это разница (разрыва) между Нидлманом-Вуншем и Левенштейном, поэтому большая часть бумаги использует максимальное расстояние между двумя последовательностями ( НО ЭТО МОЕ СОБСТВЕННОЕ ПОНИМАНИЕ, И Я НЕ УВЕРЕН 100% )

Вот транзакции IEEE по анализу PAITERN: Вычисление нормализованного расстояния редактирования и приложений В этой статье нормализованное расстояние редактирования следующим образом:

Для двух строк X и Y над конечным алфавитом нормализованное расстояние редактирования между X и Y, d (X, Y) определяется как минимум W (P) / L (P) w, где P - путь редактирования между X и Y, W (P) - сумма весов элементарных операций редактирования P, а L (P) - количество этих операций (длина P).





levenshtein-distance