хабраиндекс
41,56
10 июня 2009 в 16:13

Мне кажется, я начал понимать, что ты имела в виду!

Опечататься дело нехитрое; опечататься в поисковом запросе так и вдвойне. Почитай все большие веб-поисковики сегодня умеют корректировать ошибки в ключевых словах во-1х и подсказывать запросы во-2х; вслед за ними того же хочется поискам поменьше. Обе штуки можно ловко реализовать при помощи открытого поисковика по кличке Sphinx; в этом посте расскажу, как конкретно.

Ну, за did you mean («что ты имела в виду») и прочий query completion («уж не Васю ли ты ищешь»).


Слушайте свою любимую песню «Валенки»!



Начнем с простого, те. query completion. Пользователь начинает вводить поисковую строчку, по мере набора хочется ему сразу показывать подсказки (это чтобы не искал неизвестно чего, а слушал «Валенки», как все). Возможно, даже и с числом результатов. Как делать, откуда хоть брать данные?

Вариантов примерно два: можно подсказывать прямо пользовательские запросы, а можно отдельные ключевые слова.

Ключевые слова подсказывать особенно несложно. У программы индексирования с неожиданным именем indexer есть два не менее внезапных ключика: --buildstops, который заставляет indexer вместо обычно индексирования строить список из N самых часто встречающихся слов (он же словарь), и к нему --buildfreqs, который заставляет еще и частоты при этом считать (он же частотный словарь). Берем indexer, строим тысяч 10 (можно 100) самых частых слов в нашей коллекции документов:

$ indexer myindex --buildstops dict.txt 10000 --buildfreqs


Получаем примерно такой файл:

i 9533843
and 5427048
to 5418872
the 5371581
a 4282225
you 2877338
...


Дальше дело техники. Создаем SQL табличку, пишем скрипт импорта на десяток строк, для подсказки используем обычный LIKE, результаты сортируем по частоте слова. LIKE по индексу получится вполне разумно быстрый, тк. ищем начало ключа. Для 1-буквенных запросов результаты неплохо бы сразу предрасчитать и закешировать, чтобы не лопатить тысячи строк на каждый чих. MySQL query cache, впрочем, по идее спасет, если включен.

CREATE TABLE keywords
(
   keyword VARCHAR(255) NOT NULL,
   freq INTEGER NOT NULL,
   INDEX(keyword,freq)
);

SELECT * FROM keywords WHERE keyword LIKE 'valen%' ORDER BY freq DESC LIMIT 10


Запросы подсказываются почти так же. Ни табличка, ни LIKE никуда не деваются; только вместо отдельных слов теперь хочется полноценные строки. Взять их можно и нужно в своем логе запросов, оттуда же и частоты посчитать. Лог придется чуть обработать напильником: строчка «vasya pupkin» с точки зрения поиска совпадает с «Vasya! Pupkin!», отчего считать их разными запросами не очень комильфо. Это забарывается методом Sphinx API BuildKeywords(): берем произвольную строчку запроса, строим по ней ключевые слова (с приведением регистра и всем таким), восстанавливаем нормализованную строчку запроса. Все это лучше делать, предварительно установив персистентное соединение методом Open(), иначе работать будет в немало раз медленнее. Ну, а дальше уже по накатанной; лог, напильник, sort, uniq -c, скрипт импорта, SQL табличка, LIKE, профит. Напильник должен выглядеть примерно так:

$cl = new SphinxClient();
$cl->Open();
foreach ( $log as $entry )
{
   $keywords = $cl->BuildKeywords ( $entry, "myindex", false );
   foreach ( $keywords as $keyword )
      print $keyword["tokenized"] . " ";
   print "\n";
}


Скрипт импорта из текстового файла о двух полях в SQL базу оставляем как домашнее задание для читателей.

Я понял, это намек.



Размявшись подсказками, переходим к исправлению ошибок. Как известно, имя Britney с опечатками можно ввести чуть менее, чем 600 различными способами. А ведь у нее еще и фамилия есть. А ведь искать могут и вообще не ее! Эдак запрос с ошибками точно ничего не найдет; страничка окажется пустой; Adsense/Ydirect/Unameit покажет плохую рекламу; никто не кликнет; ваш стартап прогорит; коммерческие сервисы про Sphinx окажется некому покупать и проект тоже помрет. Это недопустимо, нужно срочно исправлять ключевые слова!

Понятно, всегда есть вариант вкрутить ispell, aspell, hunspell, или любой-модный-сегодня-spell. Понятно, всегда упирается либо в кчество xxxspell-словаря, либо тупо в его отсутствие для нужного языка. Понятно, никак не помогает с неологизмами (превед), спецтерминами (ацидиум ацетилосалицилиум), географическими названиями, и т.д. Через это все равно хочется бОльшего. Да и блог не про ispell, нужно соответствовать.

Снова потребуется частотный словарь. Правда, побольше размером, чем 10K ключевых слов — «исправлять» редкое правильное слово в близкое частое слово таки не стоит. Словаря на 1 миллион слов обычно должно хватать, на 10 миллионов совсем должно, те. команда превращается в indexer --buildstops dict.txt 10000000 --buildfreqs MYINDEXNAME (работает со скоростью более 20 MB/sec на C2D E8500, кстати). В отличие от подсказок, SQL искать в таком словаре уже никак не поможет; и данных больше, и вид запросов совсе-ем не тот. Зато поможет Sphinx.

Основная идея следующая. Генерируем для каждого слова из словаря набор триграмм, те. 3 последовательно идущих символов. Индексируем триграммы Sphinx-ом. Для поиска вариантов замены, строим для слова-с-ошибкой триграммы тоже, ищем их в индексе. Кандидатов найдется несколько. Чем больше триграмм совпало, чем меньше отличается длина слова, и чем чаще встречается найденный вариант, тем лучше. А теперь разберем все это подробнее, на живом примере.

Созданный indexer --buildstops словарь все еще выглядит вот так (я выбрал другой кусок, чтобы слова были подлиннее, а пример нагляднее):

...
deal 32431
created 32429
light 32275
needed 32252
mood 32185
death 32140
behind 32136
usually 32113
action 32053
line 32052
pissed 32043
...


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

CREATE TABLE suggest (
   id       INTEGER PRIMARY KEY AUTO_INCREMENT NOT NULL,
   keyword  VARCHAR(255) NOT NULL,
   trigrams VARCHAR(255) NOT NULL,
   freq     INTEGER NOT NULL
);

INSERT INTO suggest VALUES
...
( 735, 'deal', '__d _de dea eal al_ l__ ', 32431 ),
( 736, 'created', '__c _cr cre rea eat ate ted ed_ d__ ', 32429 ),
( 737, 'light', '__l _li lig igh ght ht_ t__ ', 32275 ),
( 738, 'needed', '__n _ne nee eed ede ded ed_ d__ ', 32252 ),
( 739, 'mood', '__m _mo moo ood od_ d__ ', 32185 ),
( 740, 'death', '__d _de dea eat ath th_ h__ ', 32140 ),
( 741, 'behind', '__b _be beh ehi hin ind nd_ d__ ', 32136 ),
( 742, 'usually', '__u _us usu sua ual all lly ly_ y__ ', 32113 ),
( 743, 'action', '__a _ac act cti tio ion on_ n__ ', 32053 ),
( 744, 'line', '__l _li lin ine ne_ e__ ', 32052 ),
( 745, 'pissed', '__p _pi pis iss sse sed ed_ d__ ', 32043 ),
( 746, 'bye', '__b _by bye ye_ e__ ', 32012 ),
...


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

sql_query = SELECT id, trigrams, freq, LENGTH(keyword) AS len FROM suggest
sql_attr_uint = freq
sql_attr_uint = len


Подозрительные слова выявляем из результатов поискового запроса: если результатов поиска слишком мало (или вообще нету), анализируем секцию ответа $result[«words»], смотрим на число документов для каждого слова. Если документов мало, пробуем корректировать такое слово. Например, для запроса «green liight» в моем тестовом индексе число вхождений для «green» равно 34421, для «liight» только 2. Кого из них этапировать на исправительные работы, ясно немедленно. Конкретные пороги для «мало» очень индивидуальны для разных коллекций документов и запросов. Смотрите в свой словарь и лог запросов, подбирайте магические константы.

Строим триграммы, запускаем запрос по специндексу триграмм. Поскольку слово набрано с ошибками, то все триграммы вряд ли совпадут. С другой стороны, если совпадает только одна триграмма, такой кандидат тоже малоинтересен: такое может случится, только если совпали три буквы в середине слова (и больше ничего), либо одна буква в начале (и больше ничего). Хорошо, используем оператор кворума, он именно так и ищет: выдает все документы, где совпало не менее 2х триграмм. Еще вводим ограничение на длину: предполагаем, что длина правильного варианта отличается не более, чем на 2 символа.

$len = strlen ( "liight" );
$cl->SetFilterRange ( "len", $len-2, $len+2 );
$cl->Query ( ' "__l _li iig igh ght ht_ ht__"/2 ', 'suggest' );


Кучу найденных кандидатов необходимо отсортировать, и выбрать из нее лучшего. Вспоминаем, какие у нас есть факторы:
  1. чем больше триграмм совпало, тем лучше;
  2. чем меньше отличается длина слова, тем лучше;
  3. чем чаще встречается найденный вариант, тем лучше.


Все эти факторы свежая версия Sphinx способна посчитать и посортировать полностью на стороне сервера. Количество совпавших триграмм можно рассчитать ранкером SPH_RANK_WORDCOUNT (тк. в ходе нашего спецпоиска каждая триграмма и выступает отдельным ключевым словом). Разница в длине слова равна abs(len-$len), а частота хранится в атрибуте freq. Рассчитываем факторы, собираем некоторые вместе, и выбираем лучший:

$cl->SetMatchMode ( SPH_MATCH_EXTENDED2 );
$cl->SetRankingMode ( SPH_RANK_WORDCOUNT );
$cl->SetSelect ( "*, @weight+2-abs(len-$len) AS myrank" );
$cl->SetSortMode ( SPH_SORT_EXTENDED, "myrank DESC, freq DESC" );


Ура, работает! Для слова liight успешно находится исправление light. (Точнее, Sphinx находит ID, по которому затем из базы достается строчка «light»).

Именно так устроена приложенная к Sphinx 0.9.9-rc2 демка (см. директорию misc/suggest внутри архива), которую можно немедленно опробовать на своих данных совсем без написания дополнительного кода :-)

Демка, сразу понятно, неидеальная и подлежит доводке напильником. (Извините, удержаться не смог.) Есть опасность, что из коробки PHP часть не заработает с русским языком, потому что ожидается UTF-8, используется substr, и соотв-но без mbstring.overload=7 никуда. Почти наверняка придется покрутить FREQ_THRESHOLD, те. минимальное количество вхождений, ниже которого слово считается опечаткой и в специндекс не попадает; для маленьких коллекций данных понизить, для больших повысить. Из тех же соображений (чтобы не ранжировало редкий мусор выше частого немусора) может случиться необходимость покрутить формулу для расчета myrank. Например, добавить по лишней единичке к числу совпавших триграмм для отличающихся в 1000 раз частот:

$cl->SetSelect ( "*, @weight+2-abs(len-$len)+ln(freq)/ln(1000) AS myrank" );


Кроме того, фокус с триграммами действенный, но очень простой, и многое не учитывает. Не учитывается порядок следования триграмм, хотя для слов разумной длины это в общем-то не проблема. Что интереснее, не учитывается как люди ошибаются: перестановка 2х соседних букв по числу триграмм неотличима от замены этих букв на любые (!) другие (например light/lihgt/limit); никак не учитывается близость букв на клавиатуре; никак не учитывается фонетическая близость (actually/akshully). Довольно очевидная идея для улучшения качества исправлений малой кровью: вместо 1 лучшего варианта вытаскиваем штук 10-20, считаем на клиенте дистанцию Левенштейна, корректируем результаты расчетов. Большой кровью можно точно так же «досчитать» десяток-другой кандидатов любым другим самописным алгоритмом.

В общем, демка будет работать и из коробки. Но это таки демка, и массу пространства для дальнейшего креатива никто не отменял. Творите, выдумывайте, пишите блоги, засылайте патчи!
+66
10046
272
shodan 171,3

Комментарии (24)

НЛО прилетело и опубликовало эту надпись здесь
+3
shodan, #
Одну отдельную таблицу.
И можно ее хоть на отдельный сервер загнать, кстати.
0
MichaelMonashev, #
Спасибо за подробную статью, Андрей. Будем пробовать, ибо вещь полезная и юзерам приятная…
0
Joka, #
habrahabr.ru/blogs/php/28752/ — вот описана альтернатива того как можно исправлять ошибки. тоже интересный метод
+1
shodan, #
Я сам пробовал живьем soundex, metaphone.
Очень много мусора, даже на родном английском :(
0
Programmer, #
Весьма интересно. Все раздумываю над применением Sphinx для большой базы с mp3шками. Никак не решусь, надо оно мне и будет от этого толк.
0
shodan, #
Если есть раздумья, значит не особо надо :)
Ну те. мне более привычна ситуация «тормоза жуткие от поиска, надо срочно менять»
Такое вот профессиональное искажение.
НЛО прилетело и опубликовало эту надпись здесь
0
shodan, #
Плохо как-то понятно.

«По большому количеству слов» со Сфинксом осмысленно запрос гонять НЕ в режиме «найди все» дефолтном.
А с тем же кворумом, например (как тот Яндекс и делает).

Морфология русского у Яндекса, разумеется, много лучше.
Ужо я надеюсь, 15 лет люди работают :)
НЛО прилетело и опубликовало эту надпись здесь
0
grey_kristy, #
А что такое кворум?

Кстати о морфологии.
По запросу «девушки» находятся

девушки
девушка
девушке

но не находится

девушек

Это как-то лечится, или в морг?

0
shodan, #
Про кворум — это оператор, который матчит документы с не менее, чем N словами из указанных (например «мама мыла раму»/2)

Про девушек — видимо стеммер не осиливает, можно пробовать добавить правило в словоформы, мапить форму «девушек» в стем (!) вручную.
0
SlamJam, #
Афигенская статья.
0
bullgare, #
спасибо за статью.
а эти ключики указанные работают давно или только в новой версии?
0
shodan, #
Ключики давно, очень давно.
А вот нужные для исправлений плюшки типа SetSelect только в 0.9.9 появились.
0
coldFlame, #
О! Таки вы меня опередили со стетьей. :) Ну, придется написать про реализацию всего этого на Rails.
+1
shodan, #
На следующей неделе собираюсь опередить со статьей про ранжирование.
Разве что в комментах МНОГО народу вдруг захочет про что-то другое.
:)
0
Aldekein, #
Я не верю, что никто не опечатался в слове spears!
Мне кажется, что где-то там зарыта гугловская собака.
0
Aldekein, #
Так… я прочитал начало и понял — это статистика только по имени, извиняюсь.
0
dbykov, #
Пока запускал did you mean, узнал некоторые возможности PHP, в том числе о настройке mbstring, о директиве mbstring.overload
в итоге всё таки запустил, работает на отлично
пишите еще, очень интересно и полезно в обиходе :)
0
ruFog, #
Огромное спасибо за хорошую статью! Очень актуально.
0
ruFog, #
Супер работает. Самое сложное как оказалось — определиться с пороговыми значениями для формирования сугестов.
0
poimtsev, #
Скажите, а не приходилось ли вам реализовывать контекстный поиск? То есть у меня есть некий документ, а есть необходимость для него подобрать схожие документы.
0
coool, #
Благодарю Вас! Статья очень помогла мне в реализации поставленной задачи. Написано доступно и просто. А главное, работает!:)

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.