Особенности поведения Jaro Distance в JellyFish

Question

Я пытаюсь использовать медузы для работы с нечеткими строками. Я замечаю какое-то странное поведение алгоритма jaro_distance.

У меня были некоторые проблемы ранее с алгоритмом damerau_levenshtein_distance, который, как представляется, был ошибкой в ​​коде, который затем пользователь стек ставил как проблему в github.

Я не уверен, что я думаю о мерах неправильно или если это настоящая ошибка. Я посмотрел исходный код (http://goo.gl/YVMl8k), но я не знаком с C, поэтому мне трудно узнать, является ли это проблемой реализации, или я просто ошибаюсь.

Обратите внимание на следующее:

In [1]: S1 = Poverty 
In [2]: S2 = Poervty 
In [3]: jf.jaro_distance(S3, S4) 
Out[3]: 0.95238095 

Теперь, если мое понимание Jarrow измерения расстояния является правильным, я считаю, что результат должен быть 0.9285714285

Я определил, почему calcualtion происходит не так. Для того, чтобы вычислить меру я считаю, что followig правильно:

(7.0/7.0 + 7.0/7.0 + ((7.0 - (3.0/2.0))/7.0) * (1.0/3.0) = 0.9285714285

Критическое число в этом выражении является 3,0. Это число должно представлять «Число совпадений (но различный порядок последовательности)» (wikipedia). На мой взгляд, в S1 и S2 символы, которые совпадают, но находятся в порядке последовательности различий, это «e», «r», «v».

Однако JellyFish кажется только определить два транспозиции, как это вычисление:

(7.0/7.0 + 7.0/7.0 + ((7.0 - (2.0/2.0))/7.0) * (1.0/3.0) = 0.95238095

Я прав на это, или есть что-то плохое в функции?

Answer 1

Если вы посмотрите на Jellyfish source code jaro.c, вы увидите, что количество транспозиций хранится в переменной trans_count, которая имеет тип long. Это означает, что когда это делится на два: это использует целочисленное деление C, которое усекает результат. Таким образом, в вашем примере (POVERTY/POERVTY) количество транспозиций равно 3, но это становится равным 1 при делении на 2.

Это правильно? Ну, я попытался следующие направления исследований:

1. Wikipedia article не поможет, потому что все эти примеры имеют четное число транспозиций. (Это дает оценку Яро для MARTHA-MARHTA как 0,944, а показатель Яро-Винклера - 0,961.)

2. Документ Jaro 1989 года не является открытым.

3. Winkler's 1990 paper неоднозначно. Все, что он говорит, это:

   Количество несоответствующих символов делится на два, чтобы получить количество транспозиций.

   без указания того, следует ли за делением выполнить усечение.Хотя Винклер приводит несколько примеров, я не могу воспроизвести значения, используя алгоритм, который он описывает в статье. Например, он дает оценку J-W для MARTHA-MARHTA как 0,9667 (см. Таблицу 1), и я не вижу, как интерпретировать текст, чтобы сделать это правильно. Так что эта статья бесполезна. Может быть, стоило бы написать Винклеру объяснение?

4. Если вы посмотрите на код для «official string comparator to be used for matching during the 1995 Test Census» (который основан на коде, написанном «Билл Уинклер, Джордж McLaughlin и Мэтт Яро с модификациями Морин Lynch»), то вы увидите, что он считает транспозиции в переменная N_trans, которая имеет тип long, и поэтому усекает деление, соглашаясь с медузой.

   (Этот код дает оценку MARTHA-MARHTA как 0.9708 из-за дополнительной «подгонку длинной строки».)

Так он смотрит на меня, как будто поведение медуз, по крайней мере оправданы на основы исторических источников. Но это кажется ошибкой, потому что она теряет информацию о количестве транспозиций без принципиальной причины.