Как-то по долгу службы появилась необходимость добавить к поиску на сайте всем известную фичу, сервис «Возможно вы имели в виду…» или «Поиск с опечатками». Стали думать как реализовывать. Сторонние сервисы и api использовать не хотелось, ибо время до чужого сервера и назад, да и в целом не очень хорошо. Как раз кстати пришелся модуль pg_trgm, который ищет близкие к запросу слову на основе триграммного индекса.
Для начала – как это используется.
Чтобы искать похожие слова, нужно создать список правильных вариантов. Создаем таблицу с текстовым полем, на которое позже повесим триграммный индекс.
Заполнить таблицу можно различными способами, для себя мы решили этот вопрос так:
— Грамматический словарь Зализняка (~90 тысяч слов), словарь Русской литературы (~160 тысяч слов), либо любой другой или все вместе. Словари легко находятся в сети, обычно представляют собой построчный список слов, распарсить такой в БД труда не составляет.
— У нас книжный интернет магазин, около 200 тысяч товаров в базе, у каждого есть название, автор, краткая аннотация и прочее. Так как люди, вполне вероятно, будут искать, используя слова из этих данных, собираем все в кучу, делим по пробельным символам, уникальные слова также заливаем в таблицу.
Далее добавляем индекс.
Вот в таком виде схему уже можно использовать.
Подобный запрос выдаст нам похожие слова и rate, который показывает на сколько слово схоже с предложенным. Сортируя по рейтингу «похожести» в обратном порядке, получим самые похожие слова.
Далее предстоит определить, когда же все-таки человек ошибся и ему надо предложить правильный вариант. Самый очевидный вариант – если пользователь по своему запросу ничего не нашел, или, к примеру, нашел мало результатов, проверяем похожие варианты. Если поиск по похожим вариантам выдал какое-то количество результатов, показываем подсказку пользователю.
На данном этапе, чтобы добиться правильного результата, можно подкручивать значения выдавать/не выдавать, сколько выдал поиск по похожим словам и прочие свойства. Стоит установить пороговое значение «рейтинга похожести», до которого слова даже не нужно рассматривать как похожие.
У этого способа, однако, есть несколько больших минусов:
1) Словарь у нас состоит из отдельных слов, в то время как поисковые запросы обычно бывают многосложными. Поиск похожих фраз приходится осуществлять отдельно по словам, потом их комбинировать. То есть, например, имея поисковую фразу «рагняя поэзия Пушкина», которая не выдаст результатов, приходится искать похожие слова, соответственно, для «рагняя», «поэзия», «пушкина». Если взять по 2 похожих слова, количество вариаций будет равно 8. Это создает неплохую нагрузку на базу, что обычно не радует.
2) Даже при установке всех нужных параметров, случаются веселые курьезы, когда поиск по не имеющему отношения к запросу слову, выдаст больше результатов, чем оригинальный запрос. Таким образом, получаются довольно веселые подсказки, например при поиске слова «Тина», появится предложение, «возможно вы имели в виду Путина», или, не дай бог, наоборот)
Итого:
Плюсы – легкая реализация, большое количество вариантов подсказок.
Минусы – загрузка базы при больших запросах, периодически неверные подсказки.
Если вы ведете статистику поисковых запросов, то можно использовать другой вариант.
Создается таблица с уникальными поисковыми запросами, на поле с запросами по тому же принципу добавляется триграммный индекс. И соответствие ищется не отдельно по словам, а по полной поисковой фразе в сохраненных запросах.
Итого:
Плюсы – фразы в подсказках составлены пользователями, меньшая вероятность «глупых» подсказок.
Минусы – полнота базы зависит только от вашей статистики запросов.
После неоднократного тестирования, мы решили отказаться от первого метода в пользу второго, уж больно непредсказуемыми были его результаты) Результаты работы второго способа можно посмотреть здесь.
Чтобы до конца стало все ясно, расскажу как это работает. Все довольно просто.
Каждое слово делится на трехбуквенные сочетания – триграммы.
Например:
При поиске похожей фразы, ищутся одинаковые триграммы. Чем больше равных триграмм, тем больше фраза схожа с исходной.
Триграммный индекс пригодился еще в одном случае. На странице товара у нас есть различные блоки предложений: «Товары этого автора», «Товары этого издательства» и так далее. Один из них – «Похожие товары».
На многих сайтах встречается подобная функция, но по опыту, обычно это либо товары из той же категории, что и основной товар, либо список, назначаемый вручную. Еще встречалась реализация, в которой выводились товары, найденные с помощью полнотекстового поиска, например, по двум или по одному слову из названия основного товара. Но это тоже дает, зачастую, не очень предсказуемые результаты. К примеру к книге «Архитектура приложений на С++» выдавались книги по архитектуре и строительству.
Триграммный индекс, установленный на названия товаров, дал неплохие «релевантные» результаты) Пример тут, либо на любой странице товара на сайте.
Если кому-то будет интересно, в следующий раз выложу тесты производительности и исходники.
UPD: Вот еще пример поиска — с перестановкой букв.
Реализация
Для начала – как это используется.
Чтобы искать похожие слова, нужно создать список правильных вариантов. Создаем таблицу с текстовым полем, на которое позже повесим триграммный индекс.
CREATE TABLE "public"."tbl_words" (
"word" VARCHAR(255) NOT NULL
) WITHOUT OIDS;
* This source code was highlighted with Source Code Highlighter.Заполнить таблицу можно различными способами, для себя мы решили этот вопрос так:
— Грамматический словарь Зализняка (~90 тысяч слов), словарь Русской литературы (~160 тысяч слов), либо любой другой или все вместе. Словари легко находятся в сети, обычно представляют собой построчный список слов, распарсить такой в БД труда не составляет.
— У нас книжный интернет магазин, около 200 тысяч товаров в базе, у каждого есть название, автор, краткая аннотация и прочее. Так как люди, вполне вероятно, будут искать, используя слова из этих данных, собираем все в кучу, делим по пробельным символам, уникальные слова также заливаем в таблицу.
Далее добавляем индекс.
CREATE INDEX "tbl_words_trgm_idx" ON "public"."tbl_words"
USING gist ("word" "public"."gist_trgm_ops");
* This source code was highlighted with Source Code Highlighter.Вот в таком виде схему уже можно использовать.
select word, similarity(word, 'Пужкин') from tbl_words
* This source code was highlighted with Source Code Highlighter.Подобный запрос выдаст нам похожие слова и rate, который показывает на сколько слово схоже с предложенным. Сортируя по рейтингу «похожести» в обратном порядке, получим самые похожие слова.
select word from tbl_words where word % 'Пужкин' order by similarity(word, 'Пужкин') desc, word limit 5
* This source code was highlighted with Source Code Highlighter.Далее предстоит определить, когда же все-таки человек ошибся и ему надо предложить правильный вариант. Самый очевидный вариант – если пользователь по своему запросу ничего не нашел, или, к примеру, нашел мало результатов, проверяем похожие варианты. Если поиск по похожим вариантам выдал какое-то количество результатов, показываем подсказку пользователю.
На данном этапе, чтобы добиться правильного результата, можно подкручивать значения выдавать/не выдавать, сколько выдал поиск по похожим словам и прочие свойства. Стоит установить пороговое значение «рейтинга похожести», до которого слова даже не нужно рассматривать как похожие.
У этого способа, однако, есть несколько больших минусов:
1) Словарь у нас состоит из отдельных слов, в то время как поисковые запросы обычно бывают многосложными. Поиск похожих фраз приходится осуществлять отдельно по словам, потом их комбинировать. То есть, например, имея поисковую фразу «рагняя поэзия Пушкина», которая не выдаст результатов, приходится искать похожие слова, соответственно, для «рагняя», «поэзия», «пушкина». Если взять по 2 похожих слова, количество вариаций будет равно 8. Это создает неплохую нагрузку на базу, что обычно не радует.
2) Даже при установке всех нужных параметров, случаются веселые курьезы, когда поиск по не имеющему отношения к запросу слову, выдаст больше результатов, чем оригинальный запрос. Таким образом, получаются довольно веселые подсказки, например при поиске слова «Тина», появится предложение, «возможно вы имели в виду Путина», или, не дай бог, наоборот)
Итого:
Плюсы – легкая реализация, большое количество вариантов подсказок.
Минусы – загрузка базы при больших запросах, периодически неверные подсказки.
Вариант 2.
Если вы ведете статистику поисковых запросов, то можно использовать другой вариант.
Создается таблица с уникальными поисковыми запросами, на поле с запросами по тому же принципу добавляется триграммный индекс. И соответствие ищется не отдельно по словам, а по полной поисковой фразе в сохраненных запросах.
Итого:
Плюсы – фразы в подсказках составлены пользователями, меньшая вероятность «глупых» подсказок.
Минусы – полнота базы зависит только от вашей статистики запросов.
После неоднократного тестирования, мы решили отказаться от первого метода в пользу второго, уж больно непредсказуемыми были его результаты) Результаты работы второго способа можно посмотреть здесь.
Как это работает.
Чтобы до конца стало все ясно, расскажу как это работает. Все довольно просто.
Каждое слово делится на трехбуквенные сочетания – триграммы.
Например:
При поиске похожей фразы, ищутся одинаковые триграммы. Чем больше равных триграмм, тем больше фраза схожа с исходной.
Похожие товары.
Триграммный индекс пригодился еще в одном случае. На странице товара у нас есть различные блоки предложений: «Товары этого автора», «Товары этого издательства» и так далее. Один из них – «Похожие товары».
На многих сайтах встречается подобная функция, но по опыту, обычно это либо товары из той же категории, что и основной товар, либо список, назначаемый вручную. Еще встречалась реализация, в которой выводились товары, найденные с помощью полнотекстового поиска, например, по двум или по одному слову из названия основного товара. Но это тоже дает, зачастую, не очень предсказуемые результаты. К примеру к книге «Архитектура приложений на С++» выдавались книги по архитектуре и строительству.
Триграммный индекс, установленный на названия товаров, дал неплохие «релевантные» результаты) Пример тут, либо на любой странице товара на сайте.
Если кому-то будет интересно, в следующий раз выложу тесты производительности и исходники.
UPD: Вот еще пример поиска — с перестановкой букв.
