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

Список функций, предоставляемых модулем pg_trgm, приведен в таблице Таблица F.27, операторы перечислены в таблице Таблица F.28.

Рассмотрим следующий пример:

# SELECT word_similarity('word', 'two words');
 word_similarity
-----------------
             0.8
(1 row)

В первой строке набор триграмм состоит из {" w"," wo","wor","ord","rd "}. Во второй строке упорядоченный набор триграмм состоит из {" t"," tw","two","wo "," w"," wo","wor","ord","rds","ds "}. Самый похожий набор триграмм второй строки это {" w"," wo","wor","ord"}, и сходство составляет 0.8.

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

В то же время, strict_word_similarity выбирает набор слов во второй строке. В приведенном выше примере, strict_word_similarity выбрал бы набор из одного слова 'words', чей набор триграмм состоит из {" w"," wo","wor","ord","rds","ds "}.

# SELECT strict_word_similarity('word', 'two words'), similarity('word', 'words');
 strict_word_similarity | similarity
------------------------+------------
               0.571429 |   0.571429
(1 row)

Таким образом, функция strict_word_similarity полезна для поиска сходства с целыми словами, в то время как функция word_similarity более подходит для поиска сходства для частей слов.

Модуль pg_trgm предоставляет классы операторов индексов GiST и GIN, которые позволяют создавать индекс по текстовому столбцу для очень быстрых поисков по схожести. Эти типы индексов поддерживают описанные выше операторы схожести, а также поддерживают поиск по индексу на основе триграмм для запросов LIKE, ILIKE, ~, ~* и =. Сравнения по схожести нечувствительны к регистру в стандартной сборке pg_trgm. Операторы неравенства не поддерживаются. Обратите внимание, что эти индексы могут быть не такими эффективными, как обычные B-деревья для оператора равенства.

Пример:

CREATE TABLE test_trgm (t text);
CREATE INDEX trgm_idx ON test_trgm USING GIST (t gist_trgm_ops);

или

CREATE INDEX trgm_idx ON test_trgm USING GIN (t gin_trgm_ops);

gist_trgm_ops Оператор GiST opclass приближает набор триграмм в виде битовой сигнатуры. Его необязательный целочисленный параметр siglen определяет длину сигнатуры в байтах. По умолчанию длина составляет 12 байт. Допустимые значения длины сигнатуры находятся в диапазоне от 1 до 2024 байт. Более длинные сигнатуры обеспечивают более точный поиск (сканирование меньшей доли индекса и меньшее количество страниц кучи), но требуют большего объема индекса.

Пример создания такого индекса с длиной сигнатуры 32 байта:

CREATE INDEX trgm_idx ON test_trgm USING GIST (t gist_trgm_ops(siglen=32));

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

SELECT t, similarity(t, 'word') AS sml
  FROM test_trgm
  WHERE t % 'word'
  ORDER BY sml DESC, t;

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

Вариант вышеприведенного запроса

SELECT t, t <-> 'word' AS dist
  FROM test_trgm
  ORDER BY dist LIMIT 10;

Это можно реализовать довольно эффективно с помощью индексов GiST, но не с помощью индексов GIN. Обычно это превосходит первую формулировку, когда требуется только небольшое количество ближайших совпадений.

Также вы можете использовать индекс на столбце t для сходства слов или строгого сходства слов. Типичные запросы:

SELECT t, word_similarity('word', t) AS sml
  FROM test_trgm
  WHERE 'word' <% t
  ORDER BY sml DESC, t;

и

SELECT t, strict_word_similarity('word', t) AS sml
  FROM test_trgm
  WHERE 'word' <<% t
  ORDER BY sml DESC, t;

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

Возможные варианты вышеприведенных запросов:

SELECT t, 'word' <<-> t AS dist
  FROM test_trgm
  ORDER BY dist LIMIT 10;

и

SELECT t, 'word' <<<-> t AS dist
  FROM test_trgm
  ORDER BY dist LIMIT 10;

Это можно реализовать довольно эффективно с помощью индексов GiST, но не с помощью индексов GIN.

Начиная с PostgreSQL 9.1, эти типы индексов также поддерживают поиск по индексу для LIKE и ILIKE, например

SELECT * FROM test_trgm WHERE t LIKE '%foo%bar';

Индексный поиск работает путем извлечения триграмм из поисковой строки и затем поиска их в индексе. Чем больше триграмм в поисковой строке, тем эффективнее индексный поиск. В отличие от поиска на основе B-дерева, поисковая строка не обязательно должна быть привязана к началу.

Начиная с PostgreSQL 9.3, эти типы индексов также поддерживают поиск по регулярным выражениям (операторы ~ и ~*), например

SELECT * FROM test_trgm WHERE t ~ '(foo|bar)';

Поиск по индексу работает путем извлечения триграмм из регулярного выражения и затем поиска их в индексе. Чем больше триграмм может быть извлечено из регулярного выражения, тем эффективнее будет поиск по индексу. В отличие от поиска на основе B-дерева, строка поиска не обязательно должна быть привязана к началу.

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

Выбор между индексированием GiST и GIN зависит от относительных характеристик производительности GiST и GIN, которые обсуждаются в другом месте.

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

Первый шаг - сгенерировать вспомогательную таблицу, содержащую все уникальные слова в документах:

CREATE TABLE words AS SELECT word FROM
        ts_stat('SELECT to_tsvector(''simple'', bodytext) FROM documents');

где documents - это таблица, которая имеет текстовое поле bodytext, которое мы хотим искать. Причина использования конфигурации simple с функцией to_tsvector, вместо использования языкоспецифичной конфигурации, заключается в том, что мы хотим получить список исходных (не стеммированных) слов.

Далее, создайте индекс триграмм на столбце word:

CREATE INDEX words_idx ON words USING GIN (word gin_trgm_ops);

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

Сайт разработки GiST http://www.sai.msu.su/~megera/postgres/gist/

Tsearch2 Development Site http://www.sai.msu.su/~megera/postgres/gist/tsearch/V2/

Олег Бартунов <oleg@sai.msu.su>, Москва, Московский университет, Россия

Teodor Sigaev <teodor@sigaev.ru>, Moscow, Delta-Soft Ltd.,Russia

Александр Коротков <a.korotkov@postgrespro.ru>, Москва, Postgres Professional, Россия

Документация: Christopher Kings-Lynne

Этот модуль спонсируется компанией Delta-Soft Ltd., Москва, Россия.