войти зарегистрироваться

PostgreSQL whois

индекс
95,14

Триграммный индекс или «Поиск с опечатками»

Как-то по долгу службы появилась необходимость добавить к поиску на сайте всем известную фичу, сервис «Возможно вы имели в виду…» или «Поиск с опечатками». Стали думать как реализовывать. Сторонние сервисы и api использовать не хотелось, ибо время до чужого сервера и назад, да и в целом не очень хорошо. Как раз кстати пришелся модуль pg_trgm, который ищет близкие к запросу слову на основе триграммного индекса.


Реализация


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

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: Вот еще пример поиска — с перестановкой букв.

_________
Текст подготовлен в ХабраРедакторе
+45
17 декабря 2009, 15:36
sel

комментарии (28)

  • Не знаю, на сколько это все очевидно и банальные весчи, но прочитал с удовольствием. Я хоть PostgreSQL не знаю, но наслышан ее мощью. Спасибо. Держите плюс.
  • Большой минус триграмм — на коротких словах (5 символов) они работают неадекватно при такой популярной опечатке, как перепутанные символы, например: 'table' % 'tbale' = 0.2.

    Обычно в словаре находятся совершенно посторонние слова с большей сходимостью.
    • Да, все верно. Результаты также бывают не очень, при пропущенной букве в маленьком слове.
      Поэтому используем проверку по целым фразам, а не отдельно по словам. Вероятность получить глупую подсказку гораздо меньше.

      Плюс значение имеет по какому принципу определяется верное слово. В нашем случае берем 5 самых схожих фраз — по какой из них нашлось больше упоминаний, там в большинстве случаев и оказывается верной.
  • Эх, вспоминаю давние времена, когда пытался при помощи триграмм определять язык на котором написан текст :-) Триграммы вообще полезная вещь.
  • суперска ,)
    /me записал в книжечку ещё один модуль пг
  • Да, триграммы вещь хорошая.
    Скажите у вас в какой кодировке база? windows-1251?
    Я когда-то давно пытался их использовать с UTF-8. Латиница обрабатывалась отлично, а вот с русскими символами были проблемы. Дело в том, что триграмма рубит слово не по буквам, а по байтам! Поэтому на выходе были обрубки букв:

    postgres=# SELECT show_trgm('Pushkin');
    show_trgm
    -----------------------------------------
    {" p"," pu",hki,"in ",kin,pus,shk,ush}
    (1 row)

    postgres=# SELECT show_trgm('Пушкин');
    show_trgm
    ------------------------------------------------------------------
    {0x8eb714,0x9092a3,0x922332,0xd19d23,0xfa46f0,0x38e3ee,0x5c1f41}
    (1 row)

    postgres=# SELECT show_trgm('Мушкин');
    show_trgm
    ------------------------------------------------------------------
    {0x9092a3,0x922332,0xd19d23,0xffb97c,0x34e61d,0x38e3ee,0x7c7c68}
    (1 row)

    Теретически, искать по такому можно — т.к. похожие байты все равно встречаются. Но качество такого поиска мне не понравилось.
    • Да, у нас win.

      megadb=# SELECT show_trgm('Пушкин');           
show_trgm              
-------------------------------------
 {"ин ",кин,пуш,ушк,шки," пу","  п"}
(1 row)
      • Я в итоге перешел на расстояние Левеншейна.
        Но опять же его реализация в PG оставляла желать лучшего. При работе с русскими буквами в UTF-8 он их считал за 2 буквы, поэтому расстояние иногда удваивалось, а иногда нет.
        Пришлось написать такую функцию на plpgsql — она корректно работала. Хотя и существенно медленнее.
    • acy
    • acy
    • 17 декабря 2009, 20:56
    • #
      • 0
    пушнин путин -> Возможно, Вы имели в виду «путин»

    Всё правильно! ;)
    • Ну да, такие веселости встречаются.
      Поиск основан на статистике, ничего не поделаешь, видимо пользователи не ищут «пушкин путин»)

      Вот ближайшие варианты, которые искали:

      phrase			similarity
путин			0,6
путилин			0,384615
плакат путин		0,375
владимир путин		0,315789
без путина		0,3125
  • >>>ибо время до чужого сервера и назад, да и в целом не очень хорошо.

    Тяга к техническому творчеству это хорошо, но на пользу ли это вашему проекту?
    Не знаю какое получится время до чужого сервера, а вот пользователю сайта больше понравится результат сильного алгоритма автоисправления, например если вы воспользуетесь гугловским (или еще чьим проверенным) поиском внутри сайта, нежели результат от сделанного по-быстрому для «чтобы было своё».
    • Это вопрос целесообразности. Никто не спорит о громадном преимуществе текстового поиска гугла, но искать товары в каталоге лучше по определенным параметрам, и те вещи, которые у нас есть в расширенном поиске, например, при всем желании не прикрутить к поиску гугла.

      К тому же полнотекстовый поиск в базах данных — абсолютно нормальная вещь и используется повсеместно. Вас же не смущает что в углу страницы хабра есть поле поиска по сайту и реализован он не с помощью стороннего api, а с использованием sphinx))

      А уж по поводу «сделанного по-быстрому» вообще нечего сказать. Если статья читается за 5 минут, это не значит, что придумывается и реализовывается все за то же время)
  • почему по ссылке _тут_(read.ru/id/442820/) «ушкин» не нашел «пушкин»?
    • read.ru/search/ушкин/

      Тут уже нашлась книга, поэтому подсказок не выдаем. Пробовали разные значения, меньше 5-ти, меньше 10-ти найденных. Часто люди ищут по полному названию с автором, подсказки в этом случае бывают лишними.
  • Когда то пытался решить похожую проблему через soundex функции. Смысл заключался в следующем: брался словарь русских слов и отдельной колонкой записывался SOUNDEX слов.
    Далее если ispell говорил что слово неверно написано я сравнивал слово с похожими по произношению и пытался найти слова схожие по произношению.
    Увы метод тоже оказался с весьма большой погрешностью.
  • Когда-то писала бакалаврскую по сравнению методов нечеткого поиска, и у меня получилось, что как раз триграммный метод для русского и украинского языков дает далеко не лучшие результаты, да и SoundEx тоже — лучшими были «максимальная общая подстрока» и «расстояние Левенштейна». Приятно видеть, что где-то он все-таки используется.
    • Я в конечном итоге перешел на расстояние Левеншейна.
    • 13i
    • 13i
    • 19 декабря 2009, 12:17
    • #
      • 0
    А к MySQL это всё применимо? Или хотя бы второй вариант???
    • Вполне вероятно, что для MySql есть подобные модули, но я не встречал. Поверхностный поиск в сети тоже ничего не дал, хотя может нужно поискать тщательней.
      • а что мешает использовать второй способ — с триграммами?
        разбить слово при помощи PHP на трехбуквенные кусочки и поискать их в мускуле…

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

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

            Составим индекс. Если составлять его из триграмм — получится довольно большой индекс, т.к. кол-во вариаций с тремя символами в любом случае больше, чем с двумя. Поэтому решено сделать «стереограммы». Каждая статья разбивается на слова (за счет пробелов), а каждое слово — на стереограммы, которые прописываются в таблицу стереограмм в базе данных. Каждая статья имеет свой номер.

            Пример таблицы:
            _а — 234, 567, 234
            _б — 432, 322, 234
            пи — 324, 343, 244

            Очевидные условия:
            — при заполнении индекса — если стереограмма слова со страницы уже присутствует в таблице стереограмм — повторно не заносить, не дублировать

            Далее — сам поиск.
            Возьмем слово «Пужкин», разобъем его на стереограммы:
            _п, пу, уж, жк, ки, ин, н_
            ищем каждую стереограмму в таблице по отдельности, получая список номеров страниц, где она встречается.
            На основании сравнения общих совпадений выдаем список страниц по рейтингу двух типов совпадений: полное и частичное (без одной стереограммы).

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

            Надеюсь, что изложил доступно.
            • Ну здесь несколько моментов:
              1. Комбинаций по 2 буквы вообще не много, собственно примерно 33^2, можно и сразу заполнить.
              2. Все-таки искать сразу в тексте ничего не даст. В любом случае надо сначала искать слова/фразы. То есть набор «стереограмм» или «триграмм» надо искать в пределах одного слова/фразы, а потом ссылать на статью. Во-первых, надо же показать правильное слово, а второе — уверен, что любой набор из 2-х букв будет встречаться практически в любом тексте. Если не все стереограммы, то большая часть из набора.
              3. 3 буквы, а не 2, используются для того, чтобы была большая определенность, больший процент вероятности совпадения. Мне кажется, лучше пробовать с 3-мя.

              Интересно, что получилось в результате? Или это еще пока идея?
              • 1. Точнее 34^2…

                2. Проверил. Действительно почти в любом мало-мальски нормальном тексте (1-2 «страницы»).

                3. Пришлось нехотя согласиться с тремя буквами, хоть это и получается 34 в третьей степени (добавляется символ «пробел» или заменяющее его «подчеркивание»). В общем около 40 тысяч строк получится в таблице. Первая ячейка — varchar (3), вторая — text.

                4. Для экономии места стоит ли автоматически сокращать запись во второй ячейке при перечислении номеров страниц типа «34,35,36,37,38,39» до «34-39»?

                5. Для ускорения работы поиска можно сначала поискать обычным методом (полнотекстовый поиск) и если результат будет равен 0 — искать с опечатками, а если результат будет положительным — предложить пользователю также возможность поискать с опечатками… Это спорный вопрос, готов выслушать ваше мнение.
                • Предположим, на сайте 1000 страниц.
                  Номера в основном трехзначные, т.е. 3 байта.
                  В среднем предположим, что под запись во вторую ячейку будут попадать 65% страниц, т.е. 650.
                  Умножим 650 на 3 = 1950, округлим до 2000 байт.
                  Умножим кол-во строк 40 тысяч на размер одной строки 2000 байт = 80 000 000 байт = 78125 Кбайт ≈ 76 Мбайт.

                  Округлим до максимума — 100 Мбайт с каждой тысячи страниц ради поиска с опечатками.
                  Стоит ли это результата? Думаю, стоит!
                  • Несмотря на быстродопущенные ляпы (например 650 надо умножать на 4, т.к. еще разделитель нужен), результат примерно остается таким же — 100 Мбайт, а если применить описанное выше сжатие — около 60 Мбайт.
  • Это конечно всё хорошо, но, думаю, надо еще отдать приоритет согласным и первым-последним буквам, т.к. их расположение является определяющим. Еще стоит учитывать раскладку клавиатуры и учитывать в первую очередь наиболее вероятные опечатки, ну и переводить в другую раскладку автоматически при необходимости, a-la Punto Switcher. Это решается более продвинутым индексом, который складывает очки для каждого варианта. То есть, для каждого слова генерируется набор условий и очки, а затем выполняется поиск и вычисление наиболее подходящих вариантов. Надо еще подумать о фразах, поскольку наиболее подходящий вариант можно подобрать по контексту.
    Кстати говоря, зачем использовать толстые словари? Можно в качестве словаря использовать множество слов в собственной базе
    • Перевод в другую раскладку используем.
      read.ru/search/geirby/

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