Необычное поведение Jaro Distance в JellyFish

Я пытаюсь использовать Jellyfish для работы с нечеткими строками. Я заметил странное поведение алгоритма 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

Я определил, почему расчет идет не так. Чтобы рассчитать меру, я считаю правильным следующее:

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

Критическое число в этом выражении — 3,0. Это число должно представлять собой «количество совпадений (но в другом порядке последовательности)» (википедия). На мой взгляд, в 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

Я ошибаюсь в этом, или что-то не так в функции?


python-2.7 string fuzzy-comparison
person Woody Pride    schedule 29.11.2013    source источник

Ответы (1)


arrow_upward
3
arrow_downward

Если вы посмотрите на исходный код Jellyfish jaro.c, вы увидите что количество транспозиций хранится в переменной trans_count, которая имеет тип long. Это означает, что при делении на два:

trans_count /= 2;

это использует целочисленное деление C, которое усекает результат. Итак, в вашем примере (БЕДНОСТЬ/ПОЕРВТИ) количество транспозиций равно 3, но при делении на 2 оно становится 1.

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

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

  2. статья Джаро 1989 года не находится в открытом доступе.

  3. #P6# <блочная цитата> #P7# #P8#

  4. Если вы посмотрите на код для "официальный компаратор строк, который будет использоваться для сопоставления во время тестовой переписи 1995 года» (который основан на коде, написанном «Биллом Винклером, Джорджем Маклафлином и Мэттом Джаро с модификациями Морин Линч»), тогда вы Я увижу, что он считает транспозиции в переменной N_trans, которая имеет тип long, и, таким образом, усекает деление, соглашаясь с Jellyfish.

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

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

person Gareth Rees    schedule 12.12.2013
comment
Очаровательный! Я написал разработчику об ошибке расстояния Левенштейна, и он ответил мне, я упомянул об этом, так что, возможно, он расскажет мне, почему они приняли такое решение. После того, как я обнаружил эту проблему, я просто предположил, что это ошибка. Похоже, источник тестовых ощущений должен быть довольно надежным. - person Woody Pride; 12.12.2013