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

[xytop.livejournal.com]

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

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

спасибо!

Comments

[staryi-pioner.livejournal.com]

озвучить автоматически, звук фурье-анализировать до посинения? :)

[xytop.livejournal.com]

тогда уж лучше - чак норис.

[staryi-pioner.livejournal.com]

ну да.
в теме не рублю абсолютно, просто интересно - а что такое "нечеткое сравнение". что такое "похожесть", и как эти определения не сработают на конкретных примерах.

[xytop.livejournal.com]

вот две строки: "ALEXANDRE" и "ALEKSANDER" если их сравнивать при помощи алгоритма Jaro-Winkler, то их схожесть - 0.85. можно сказать, что это одно и тоже, просто оператор вбивая первую строку ошибся.
глазами такое определить - без проблем, а машина буксует. машины, обычно, сравнивают побуквенно и если хоть одна буква не совпадает, то строки разные. обычно этого хватает. но бывают ситуации, когда важно отловить такие ошибки ввода. стандартная ситуация - перепись населения. большинство алгоритмов придумали для этого. многие еще в позапрошлом веке.
типа того...

[staryi-pioner.livejournal.com]

а вот например олбанску мову олгаритм розлечид, али нет? или в основном именнно на ошибки ввода натравливается?

[xytop.livejournal.com]

может и сдюжит. только если "олбанску мову" со словарной базой сравнивать. и то будет много разночтений. "розлечид" - одинаково подходит к словам "различит" и "разлучит"

оффтоп

[staryi-pioner.livejournal.com]

ага. про розлечид пример хороший, ибо очевидно, что "у" там маловероятна. как раз таки по произношению, мне кажется. или это словарь нужен?

вот оно: может ли у вас буква быть "более похожа" на вторую букву, чем третья буква на вторую букву? или для опечаток это только мешать будет?

Re: оффтоп

[xytop.livejournal.com]

не... у меня все проще - мне фамилии надо сравнивать. а чтоб как вы пишите тут совсем много надо накручивать. и лингвистов (или как они там называются,кто в русском языке хорошо разбираются) привлекать.
мои задачи на порядок проще.

Re: оффтоп

[xytop.livejournal.com]

кстати, Jaro-Winkler говорит, что "разлучит" подходит больше, чем "различит"...
"розлечид" и "различит" - 60,4
"розлечид" и "разлучит" - 67.9

Re: оффтоп

[xytop.livejournal.com]

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

я проверил для всех вариантов выдает одно и тоже. но мой doublemetaphone рассчитан для европейских языков. и перед проверкой я их транслитерировал. результат - RSLX.

в своем деле я этот алгоритм использую для создания индекса по именам, что быстро выбирать похожие, а потом jaro-winkler проверяю схожесть. как-то так.