Знаменитый советский и российский математик Владимир Иосифович Левенштейн (кстати, ушедший из жизни два с небольшим месяца назад) в начале второй половины прошлого века ввёл понятие дистанции редактирования, которым мы пользуемся по сей день в различных сферах — от поисковых систем до биоинформатики. В этой статье мы применим его принцип для нечёткого поиска в MySQL (поскольку MySQL на данный момент пока не предлагает встроенного решения), вычислив самый эффективный (т.е. быстрый) способ из нескольких найденных в интернете, построим алгоритм такого поиска и реализуем его на PHP.
Рубрика «metaphone»
Расстояние Левенштейна в MySQL и алгоритмы нечёткого поиска средствами PHP
2017-11-15 в 8:41, admin, рубрики: levenshtein, metaphone, mysql, php, similar_text, алгоритм Оливера, Алгоритмы, метафон, нечеткий поиск, поисковые технологии, расстояние дамерау-левенштейна, расстояние ЛевенштейнаИщем имена с опечатками в PostgreSQL
2017-10-28 в 14:38, admin, рубрики: metaphone, postgresql, postrgresql, trigram, АлгоритмыВсе началось с того, что мне нужно было разработать поиск пациентов для одной внутренней медицинской системы. Логика работы была в том, что если мы не нашли человека в системе, то его нужно создать (а дубли пациентов плодить нельзя). В связи с этим одной из подзадач стала реализация поиска людей с учетом опечаток в их именах. Ну а поскольку я люблю PostgreSQL (а когда в руках у тебя молоток, то все похоже на гвозди), не сложно угадать, на чем я решил реализовать поиск с опечатками…
Читать полностью »
Делаем спеллчекер на фонетических алгоритмах своими руками
2017-04-02 в 16:01, admin, рубрики: metaphone, nlp, soundex, spell checker, spell correction, Алгоритмы, фонетические алгоритмы, фонетический поиск, метки: soundex, фонетические алгоритмы, фонетический поискЗапустив в продакшене супер-мега-навороченную систему нечёткого поиска с поддержкой морфологии, которая показывала на тестовый кейсах блестящие результаты, разработчик сталкивается с суровой реальностью. Пользователи, избалованные автокоррекцией Яндекса и Гугла, делают ошибки и опечатки. И вместо аккуратной страницы с результатами поиска получают грустный смайлик — машина не поняла запроса.
Машинный спеллчекинг — это целое искусство и не зря поисковые гиганты нанимают талантливых математиков работать над этой задачей. Но существуют и простые механизмы автокоррекции, основанные на фонетических принципах, которые уже способны давать результат и улучшать пользовательский опыт. О них и поговорим в статье. Тем более, что они так или иначе являются фундаментом для более сложных решений.
В конце статьи приводится ссылка на открытый датасет с ошибками и опечатками. Можно собрать по нему ценную статистику и потестировать свои алгоритмы спеллчекинга.Читать полностью »