нечеткое сравнение строк

[xytop.livejournal.com]

господа, кто в теме, подскажите,

а есть что-нибудь круче и быстрее алгоритма Jaro-Winkler для нечеткого сравнения строк?

спасибо!

Comments

о! про шингл я и не знал. почитаю...

[xytop.livejournal.com]

Джаро-Винклер

Сходство Джаро-Винклера (Jaro-Winkler similarity) было применено в переписи США и использовано в последующей обработке.

Для данных строк string1 и string2, их сходство задаётся формулой:

s = m/3a + m/3b + (m-t)/3m.

Здесь:

m - число соответствующих символов
a - длина string1
b - длина string2
t - число перестановок

Два символа считаются соответствующими, только если они находятся не дальше чем (max(a,b)/2 - 1). Первый соответствующий символ в string1 сравнивается с первым соответствующим символом в string2; второй соответствующий символ в string1 сравнивается со вторым соответствующим символом в string2, и так далее. Число соответствующих символов делённое на 2 даёт число перестановок.

Улучшенный метод Джаро-Винклера использует веса отличные от 1/3. Он также даёт меньший вес некоторым типам ошибок: визуального сканирования, клавишного ввода и в конце строки.
Примеры

1. Сходство ALEXANDRE и ALEKSANDER: (8/9 + 8/10 + (8-1)/8) / 3 = 0.85 (соответствуют A, L, E, A, N, D, R, E; 1 перестановка).

Re: о! про шингл я и не знал. почитаю...

[gudguy.livejournal.com]

ага, спасибо=)