вычисления отношения Python-Левенштейна

Question

у меня есть следующие две строки:

a = 'bjork gudmundsdottir' 
b = 'b. gudmundsson gunnar' 

Левенштейна расстояние между этими двумя 12. Когда я использую следующую формулу для расстояния Левенштейна, я получаю несоответствие 0.01 с python-Levenshtein библиотеки:

>>> Ldist/max(len(a), len(b)) 
>>> float(12)/21 
0.5714285714285714 
# python-Levenshtein 
Levenshtein.ratio(a,b) 
0.5853658536585366 
# difflib 
>>> seq=difflib.SequenceMatcher(a=a,b=b) 
>>> seq.ratio() 
0.5853658536585366 

Чем объясняется эта разница? Что я делаю неправильно в своих расчетах. Обратите внимание, что я рассмотрел этот вопрос How python-Levenshtein.ratio is computed, и он не совсем отвечает на то, что я прошу.

Может кто-нибудь объяснить формулу, которая используется для расчета приведенного выше отношения?

Answer 1

Из комментария Лукаса, в причина этого заключается в том, что ratio() использует стоимость для замены операций, а не нормальной стоимости на расстояние Левенштейна. Вот пример расчета:

a = 'bjork gudmundsdottir' 
b = 'b. gudmundsson gunnar' 

>>> Levenshtein.editops(a,b) 
[('delete', 1, 1), ('delete', 2, 1), ('delete', 3, 1), ('replace', 4, 1), ('replace', 14, 11), ('insert', 16, 13), ('insert', 16, 14), ('insert', 16, 15), ('insert', 16, 16), ('replace', 16, 17), ('replace', 17, 18), ('replace', 18, 19)] 

>>> ldist = sum([2 for item in Levenshtein.editops(a,b) if item[0] == 'replace']) 
      + sum([1 for item in Levenshtein.editops(a,b) if item[0] != 'replace']) # 17 
ln = len(a) + len(b) # 41 

>>> (41.0-17.0)/41.0 
0.5853658536585366 
>>> Levenshtein.ratio(a,b) 
0.5853658536585366