Хабр Курсы для всех
РЕКЛАМА
Большая витрина: от крупнейших школ до частных авторов. Сравнивайте по цене, длительности, формату и выбирайте самый подходящий курс!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 35
Отличная статья!
Юзал Soundex правда не помню какой именно.
Но реально очень удобно.
Но реально очень удобно.
Раньше не встречала таких алгоритмов, очень интересно было почитать, спасибо.
В логике этих алгоритмов нет ничего сложного, и они легко реализуются в виде хранимых подпрограмм (или каких-либо других расширений) для большинства СУБД.
Вообще, не совсем понятно, почему во многих системах используется именно Soundex, ведь он по многим параметрам уступает остальным алгоритмом, тому же Metaphone, например. Да, его реализация немного проще, но это — ничто по сравнению с качеством результатов.
Вообще, не совсем понятно, почему во многих системах используется именно Soundex, ведь он по многим параметрам уступает остальным алгоритмом, тому же Metaphone, например. Да, его реализация немного проще, но это — ничто по сравнению с качеством результатов.
Что же вы забыли n-grams! В отличие от всех рассмотренных алгоритмов, n-граммы поддерживают индексный поиск. Мы написали для постгреса такой модуль, который доступен в дистрибутиве, а совсем недавно, этот же индекс ускоряет *pattern*!
Вы немного путаете области — метод n-грамм (если говорить о подстроках фиксированной длины n) относится к нечеткому поиску, который обычно не затрагивает фонетических аспектов, и больше основывается на понятиях метрик (Левенштейна, например).
Кроме того, все представленные алгоритмы позволяют проводить индексирование по значению кода как по обычным словам, а индексирование в методе n-грамм — совершенной иной процесс.
Кроме того, все представленные алгоритмы позволяют проводить индексирование по значению кода как по обычным словам, а индексирование в методе n-грамм — совершенной иной процесс.
На первом курсе писал курсовую работу, в которой реализовывал компьютера-собеседника. Использовал Soundex для сравнения слов со словарем. Русский текст просто транслитерировал латиницей и применял алгоритм. Результат получался довольно неплохим.
Занятно, что ни один из алгоритмов не учитывает ударения. В результате русские фамилии на -ин от армянских отличит только русский Metaphone. Интересно, этого сознательно добивались?
обоже!
это вот именно то, что генерит «Возможно, вы имели в виду: Шварценеггер»?
это вот именно то, что генерит «Возможно, вы имели в виду: Шварценеггер»?
Любопытные алгоритмы.
А вот ещё более интересная реализация (алгоритм вряд ли имеет название ибо самопальный).
Например:
nanohertz.net/?word=%D1%85%D1%80%D0%BE%D0%BD%D0%BE%D1%84%D0%B0%D0%B7%D0%B8%D1%82%D1%80%D0%BE%D0%BD
Если будете играться, то примите во внимание, что система обучена русским и английским словам, но не знает ни имён ни ругательств.
Если система выдаёт казалось бы бредовый результат, перед тем как писать «автор — козёл, код не работает» проверьте наличие искомого слова в БД путём ввода корректного написания этого слова.
А вот ещё более интересная реализация (алгоритм вряд ли имеет название ибо самопальный).
Например:
nanohertz.net/?word=%D1%85%D1%80%D0%BE%D0%BD%D0%BE%D1%84%D0%B0%D0%B7%D0%B8%D1%82%D1%80%D0%BE%D0%BD
Если будете играться, то примите во внимание, что система обучена русским и английским словам, но не знает ни имён ни ругательств.
Если система выдаёт казалось бы бредовый результат, перед тем как писать «автор — козёл, код не работает» проверьте наличие искомого слова в БД путём ввода корректного написания этого слова.
На Хабре публиковалась реализация daitch-mokotoff на php
Использую в своих проектах, по сравнению с soundex просто небо и земля.
Использую в своих проектах, по сравнению с soundex просто небо и земля.
Подумал, что может быть интересно для чего :)
Я использую daitch-mokotoff для исправления опечаток в поисковых запросах.
Вкратце реализовано это так: есть таблица, в которой хранятся слова в базовой форме (используется словарь морфологии) и их фонетический вид по daitch-mokotoff
При поиске для каждого слова пытаемся словарем найти базовую форму. Если такой нет, предполагаем, что человек ошибся, получаем фонетический вид поискового слова и выбираем из таблицы все слова с таким же видом. После чего для поискового слова и слова из запроса вычисляется расстояние по Левенштайну (минимальное количество вставок, замен и удалений символов, необходимое для преобразования str1 в str2) и находим самое близкое слово.
Плохо работает для имен собственных, но на общеупотреблительных фразах — весьма, весьма.
Я использую daitch-mokotoff для исправления опечаток в поисковых запросах.
Вкратце реализовано это так: есть таблица, в которой хранятся слова в базовой форме (используется словарь морфологии) и их фонетический вид по daitch-mokotoff
При поиске для каждого слова пытаемся словарем найти базовую форму. Если такой нет, предполагаем, что человек ошибся, получаем фонетический вид поискового слова и выбираем из таблицы все слова с таким же видом. После чего для поискового слова и слова из запроса вычисляется расстояние по Левенштайну (минимальное количество вставок, замен и удалений символов, необходимое для преобразования str1 в str2) и находим самое близкое слово.
Плохо работает для имен собственных, но на общеупотреблительных фразах — весьма, весьма.
Теперь эта же реализация на javascript :-)
А нет ли ошибки в примерах для Daitch-Mokotoff Soundex?
095747 → Архипцев, Архипцов, Архипычев, Арцыбасов, Арцыбашев, Арчибасов
095757 → Архипков, Архипцев, Архипцов, Архипычев
Одна фамилия (например. Архипцев) соответствует двум кодам.
095747 → Архипцев, Архипцов, Архипычев, Арцыбасов, Арцыбашев, Арчибасов
095757 → Архипков, Архипцев, Архипцов, Архипычев
Одна фамилия (например. Архипцев) соответствует двум кодам.
Однако если захочется найти именно «Швардсенеггера», придется попотеть. Гугл со своими фонетизмами некоторые фразы (даже с кавычками) отказывается искать. Например: «operator+ C++» (пример из головы).
Такой вопрос:
Существуют ли какие-то фонетические алгоритмы (или реализации описанных), которые могут измерять расстояние между словами? Иногда хотелось бы проводить ранжирование слов по схожести произношения…
Существуют ли какие-то фонетические алгоритмы (или реализации описанных), которые могут измерять расстояние между словами? Иногда хотелось бы проводить ранжирование слов по схожести произношения…
Если я не ошибаюсь, специализированных алгоритмов для этого нет. Однако, можно попытаться приспособить уже существующие алгоритмы к подсчету количества преобразований, необходимых для приведения одного слова ко второму, правда я не очень хорошо себе представляю, как это возможно за оптимальное время сделать.
Исходя из вашего текста наиболее точно (в случае англоязычных фамилий) попадает NYSIIS — не смотря на то, что он не самый новый. Или я не правильно оцениваю результаты?
Сложно сказать. Нужно проводить тестирование, сравнение, и, опять же, без участия человека сложно выяснить, насколько точным является результат. По примерам также нельзя объективно оценить качество.
Кроме того, меньше слов с одинаковым кодом — еще не значит лучше, так как в результат могут не попасть действительно похожие слова.
Одно ясно точно — будь NYSIIS наилучшим вариантом, не стали бы изобретать новые алгоритмы.
Кроме того, меньше слов с одинаковым кодом — еще не значит лучше, так как в результат могут не попасть действительно похожие слова.
Одно ясно точно — будь NYSIIS наилучшим вариантом, не стали бы изобретать новые алгоритмы.
Если вдруг захочется дополнить реализациями на разных языках
https://github.com/Betawolf/Phonetics.jl
Это библиотека на Julia
Soundex
— Fuzzy Soundex
— Phonex
— Phonix
— The New York State Identification and Intelligence System (NYSIIS)
— The Census Modified Statistics Canada procedure
— The Match Rating Approach
— Lein
— Caverphone
— Roger Root
— Metaphone
— Double Metaphone
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Фонетические алгоритмы