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

Ответ 1

Более внимательно рассмотрев код 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.

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

Ответ 2

Расстояние Левенштейна для '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 по 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%      

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

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

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

Ответ 3

Хотя абсолютного стандарта нет, нормализованное расстояние Левенштейна обычно определяется 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)).

Ответ 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

Другой пример:

Стоимость составляет 9 (4 replace => 4 * 2 = 8 и 1 delete 1 * 1 = 1, 8 + 1 = 9)

str1=len("google") #6
str2=len("look-at") #7
str1 + str2 #13

distance = 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