Здравствуйте
Не так давно я писал про правильный did you mean.
Несмотря на все мои улучшения, guess-инг всё равно часто ошибался, и выдавал странные результаты.
Однако недавно, мне удалось значительно улучшить качество guess-инга, и я решил, что было бы неплохо написать «патч» к моей предыдущей статье :)
Pre-Intro
Заранее предвидя обвинения в выполнении ненужной в наш век работы («а зачем это всё надо если есть aspell/lucene/подставить по вкусу»),
так же заранее отвечу, что:
- Lucene/SpellChecker далеко не идеален, и в некоторых случаях проигрывает моему решению
- Aspell хорош, но аспелловский suggest-инг, будучи написанным на php, тормозит безбожно
Ингридиенты
Всё рассчитано на PHP4/PHP5 + MySQL
Работа над ошибками
Проблема номер один — выборка начального массива слов. В прошлой версии я для этой цели использовал soundex, но результат меня совершенно не устраивал, ибо наряду со словами
имеющими шанс быть правильным результатом, выбирались слова совершенно далёкие от результата.
Вторая проблема — это сама функция определения расстояния между словами. Функция, используемая мною в прошлой версии, работает, конечно, получше расстояния редактирования (аки
расстояние Левенштейна), но всё равно для некоторых случаев работает прямо таки магическим образом.
Выборка начального массива слов
В отличие от первого раза, когда надо было быстро выдать что-нибудь рабочее, во второй раз времени было больше, по этому я решил покурить матчасть в виде вики и разных
опен-сорсовых программ имеющих в себе функцию suggesting-а. В результате, был выбран поиск на основе n-gram-ов.
Желающим обогатить себя знаниями, предлагаю проследовать в википедию, а я всё же очень кратко расскажу:
n-gram — это подстрока размером в n символов. Например, для строки stock можно выделить 2 x 4-gram-а: stoc и tock (а так же 3 x 3-gram-a и 4 x 2-gram-а).
В идеале, каждый n-gram надо представлять как вектор в n-мерном пространстве, и расстояние между ними рассчитывать используя скалярное произведение этих векторов,
но чтобы это сделать надо это сделать (готовых решений я не нашёл). А делать лень. В результате остановился на решении применяемом в SpellChecker (плагин к Lucene).
Создадим таблицу для индексов (пусть она называется guess_index), с нижеследующими полями:
id — а как же без него
word — само слово
gram1 — 1-gram-ы (n-gram-ы внутри поля разделяются пробелами)
gram2 — 2-gram-ы
gram3 — 3-gram-ы
gram4 — 4-gram-ы
Для поиска возможных вариантов, разделим искомое слово на n-gram-ы, и найдём все записи с совпадающими n-gram-ами в соответствующих полях.
Пример для слова bakc:
1-gram: b a k c
2-gram: ba ak kc
SQL: WHERE gram1 LIKE '%b%' OR gram1 LIKE '%a%' OR gram1 LIKE '%k%' OR gram1 LIKE '%c%' OR gram2 LIKE '%ba%' OR gram2 LIKE '%ak%' OR gram2 LIKE '%kc%'
Далее, для всех найденных слов вычисляем их рейтинг: каждое совпадение n-gram-a добавляет очко к результату, совпадение стартового n-gram-a — 3 очка, конечного — 2 очка.
Затем нормализуем результат, разделив его на минимум из количества n-gram-ов в искомом слове и количества n-gram-ов в слове из базы
(возможно, стоит делить на максимум, но для моего случая минимум даёт лучшие результаты).
Всё это можно рассмотреть в функции suggest из файла search_guess.php
Получаем результат
Для начала отсортируем полученный массив слов по рейтингу и, ничего не жалея, выкинем половину (слова с низким рейтингом наврядли будут искомыми, но могут попасть
в результат из-за магии в words_dist).
В идеале функция words_dist должна учитывать:
- Количество лишних / недостающих букв, причём нелинейно (чем из больше ошибок, тем больше вероятность того, что имелось в виду другое слово).
- Перемену букв местами. Опять же, чем больше расстояние между обменяными буквами, тем более вероятно что имелось в виду другое слово.
- Не путать описки (неправильные буквы на том же месте) с переменой букв местами.
- Для всех предыдущих пунктов учитывать возможность такой ошибки при наборе на клавиатуре (расстояние от набранной до нужной буквы на клавиатуре).
- Рейтинг слова полученный при n-gram поиске.
Но в результате я просто модифицировал предыдущий вариант :) (смотреть функцию words_dist из файла search_guess.php),
но он стал лучше, честно-честно :)
Исключения
Как бы это печально не звучало, но некоторые слова просто невозможно найти с помощью такой реализации n-gram поиска, напримен, magrin — margin.
На текущий момент лучшим выходом из ситуации (результат / количество времени потраченного на реализацию) я считаю таблицу исключений, в которой будут перечислены
пары неправильное слово / правильное слово.
Демо
Приглашаю опробовать работу «угадайки» :)
Заключение
На дворе скоро будет 2009 год, а на многих сайтах и форумах (особенно на форумах) до сих пор малопонятный поиск (или вообще отсутствует). Надеюсь, мои статьи
помогут немного приблизить качество поиска к поисковым гигантам :) (ну или если уж совсем лениво делать, Google Custom Search хороший выход)
Ссылка в тему: Яндекс-like поиск своими руками.
