Я наконец-таки начал переходить к нормальному режиму: работать по будним дням и отдыхать по выходным. Но отдых в моем понимании это не бесцельное лежание на диване, а чаще всего получение новых знаний. Часто такой отдых приводит к появлению новых экспанатов в моей «Веб-лаборатории». Но в этот раз мне так понравилось, что я решил поделиться с вами своим небольшим исследованием на одну из тем информационного поиска — поиск по сходству, как стало понятно из заголовка, в контексте опечаток.

Исправление опечатки проходит в три этапа:
1. Определение что произошла опечатка
2. Поиск возможных вариантов
3. Выбор подходящего варианта

Я расскажу о втором этапе, и постараюсь это сделать как можно проще.

Расстояние редактирования

Для начала нужно рассказать о расстоянии редактирования или, как его ещё называют, расстоянии Левенштейна. В общем случае оно сообщает количество минимальных элементарных операций редактирования (замены, вставки, удаления), необходимых для преобразования одной строки в другую, а в нашем случае, оно говорит нам о том, на сколько символов отличаются слова. Например для слов «превед» и «привет» растояние будет 2, а для слов «хлеб» и «пиво» — 4. Расстояние Левенштейна-Дамерау к операциям преобразования добавляется перестановка соседних символов. Дамерау доказал, что 80% ошибок при наборе текста человеком являются перестановками, поэтому для опечаток это расстояние является самым оптимальным.

Очевидны трудности при вычислении расстояния простым перебором, и для ускорения сравнения стоит использовать алгоритм Вагнера-Фишера, в его реализацию я углубляться не буду, графически это выглядит как-то так:


Теперь, умея вычислять расстояние редактирования, мы можем определить какие слова мог иметь в виду пользователь. Сначала нам нужно выбрать максимальное расстояние при котором мы будем относить слово к возможной опечатке, если взять за эталон поисковые системы, то возьмем 3 возможных ошибки. Теперь нужно сравнить наше слово с возможными вариантами. Для этого нам понадобится словарь, который содержит как можно больше словоформ.

Самый простой способ — это простой перебор слов из словаря и вычисление расстояния редактирования между ним и введенным словом. Например в моем словаре 1361765 словоформ, очевидно, что полный перебор и вычисление расстояния для такого количества слов не самый оптимальный вариант.

Для уменьшения количества сравнений, можно использовать специальные фильтры по любой из метрик, самая очевидная — длина слова. Если пользователь ввел 6 букв, он врядли имел в виду двух или двенадцати буквенное слово, но стоит помнить, что алгоритм Левенштейна предусматривает возможность пропуска и добавления символов, поэтому промежуток длин слов стоит расчитывать по формуле: длина слова ± максимальное расстояние. Такой фильтр позволит сократить количество сравнений больше чем в половину!

В результате мы получим список слов, которые возможно имел в виду пользователь и дальше, в зависимости от контекста запроса, выбираем наиболее подходящее.

Рабочий пример ищущий опечатки на единичном растоянии Левенштэйна можно посмотреть в моей веб-лаборатории.

N-грамм

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

Для определения схожести, текст разделяют на подстроки размером в три буквы, например «пингвины» будет выглядеть так: {пин инг нгв гви вин ины}, а неправильно написанное «пинкгвины» будет {пин инк нкг кгв гви вин ины}. Чтобы вычислить сходство мы делим число совпадающих триграмм (считаем парами) на число всех отличающихся триграмм. В нашем примере это означает деление 4 / 9 в результате похожесть равна 0,44.

Фонетические алгоритмы

Но это не единственный способ определения похожих слов, существует несколько фонетических алгоритмов позволяющих находить похожие слова по их звучанию. Наиболее известные это Soundex и Metahpone. Они разработаны для английского языка, но ничего не мешает доработать их для русской фонетики или просто использовать транслитерацию. Алгоритмы сами по себе довольно просты, поэтому я кратко их опишу, а на примере слов Sontan и Santana докажу их актуальность.

Ключ Soundex состоит из буквы за которой стоят три числа. В качестве буквы используется первая буква слова, а в цифры кодируются оставшиеся согласные. Похожие по звучанию согласные имеют один и тот же код:

Дальше избавляемся от повторов цифр заменяя их одной. Удаляем все гласные, после чего возвращаем букву и три следующие за ней цифры, если цифр меньше, то можно добавить нулей. Итак, Soundex-ключ для Sontan будет S535, а для Santana будет S535!

Metaphone, в свою очередь, реализует более сложный алгоритм, используя правила английского языка, приводит согласные к похоже звучащим и удаляет гласные. В результате получется ключ переменной длины, очевидно, что чем больше согласных, тем длиннее ключ. Итак, Metaphone-ключ для Sontan будет SNTN, Santana будет SNTN!

Оба этих алгоритма весьма популярны и поэтому уже реализованы во многих продуктах, например Soundex есть во многих СУБД таких как MySQL и PostgreSQL. Оба алгоритма реализованы в PHP, да и для любого другого языка найти их реализацию не составит труда.

лингвистика, исследование, информационный поиск

2121 просмотр

нет комментариев