нечеткое сравнение строк
Oct. 22nd, 2009 01:22 pm![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
xytop.livejournal.com posting in ![[community profile]](https://www.dreamwidth.org/img/silk/identity/community.png){kind=small}
useful_faqгоспода, кто в теме, подскажите,
а есть что-нибудь круче и быстрее алгоритма Jaro-Winkler для нечеткого сравнения строк?
спасибо!
а есть что-нибудь круче и быстрее алгоритма Jaro-Winkler для нечеткого сравнения строк?
спасибо!
no subject
Date: 2009-10-22 11:25 am (UTC)извините. =)
no subject
Date: 2009-10-22 11:28 am (UTC)no subject
Date: 2009-10-22 03:09 pm (UTC)no subject
Date: 2009-10-22 11:58 am (UTC)no subject
Date: 2009-10-22 12:00 pm (UTC)no subject
Date: 2009-10-22 12:39 pm (UTC)мы не мудурствуя лукава юзаем шингы =)
о! про шингл я и не знал. почитаю...
Date: 2009-10-22 12:44 pm (UTC)Сходство Джаро-Винклера (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: о! про шингл я и не знал. почитаю...
Date: 2009-10-22 01:11 pm (UTC)no subject
Date: 2009-10-22 12:46 pm (UTC)no subject
Date: 2009-10-22 01:10 pm (UTC)может это тогда?
no subject
Date: 2009-10-22 01:20 pm (UTC)хотя, пожалуй, еще раз посмотрю...
хотя и в статье это пишут: "Расстояния между абсолютно разными короткими словами оказываются небольшими, в то время как расстояние между сильно похожими длинными словами оказываются значительными."
no subject
Date: 2009-10-22 03:53 pm (UTC)no subject
Date: 2009-10-22 03:55 pm (UTC)no subject
Date: 2009-10-22 05:05 pm (UTC)в теме не рублю абсолютно, просто интересно - а что такое "нечеткое сравнение". что такое "похожесть", и как эти определения не сработают на конкретных примерах.
no subject
Date: 2009-10-22 06:08 pm (UTC)глазами такое определить - без проблем, а машина буксует. машины, обычно, сравнивают побуквенно и если хоть одна буква не совпадает, то строки разные. обычно этого хватает. но бывают ситуации, когда важно отловить такие ошибки ввода. стандартная ситуация - перепись населения. большинство алгоритмов придумали для этого. многие еще в позапрошлом веке.
типа того...
no subject
Date: 2009-10-22 06:32 pm (UTC)no subject
Date: 2009-10-22 07:03 pm (UTC)оффтоп
Date: 2009-10-23 10:34 am (UTC)вот оно: может ли у вас буква быть "более похожа" на вторую букву, чем третья буква на вторую букву? или для опечаток это только мешать будет?
Re: оффтоп
Date: 2009-10-23 10:37 am (UTC)мои задачи на порядок проще.
Re: оффтоп
Date: 2009-10-23 10:44 am (UTC)"розлечид" и "различит" - 60,4
"розлечид" и "разлучит" - 67.9
Re: оффтоп
Date: 2009-10-23 10:47 am (UTC)я проверил для всех вариантов выдает одно и тоже. но мой doublemetaphone рассчитан для европейских языков. и перед проверкой я их транслитерировал. результат - RSLX.
в своем деле я этот алгоритм использую для создания индекса по именам, что быстро выбирать похожие, а потом jaro-winkler проверяю схожесть. как-то так.