pg_trgm — поддержка схожести текста с использованием триграмм#

Модуль pg_trgm предоставляет функции и операторы для определения схожести буквенно-цифрового текста на основе сопоставления триграмм, а также классы операторов индексации, которые поддерживают быстрый поиск похожих строк.

Этот модуль считается «надежным», то есть его могут устанавливать обычные пользователи, обладающие привилегией CREATE на текущей базе данных.

Концепции триграмм (или триграфа)#

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

Функции и операторы#

Функции, предоставляемые модулем, показаны в таблице «Функции pg_trgm», а операторы - в таблице «Операторы pg_trgm».

Функции pg_trgm:

Рассмотрим пример:

# 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:

Параметры GUC#

pg_trgm.similarity_threshold (real)

Устанавливает текущий порог подобия, который используется оператором %. Порог должен быть между 0 и 1 (по умолчанию 0,3).

pg_trgm.word_similarity_threshold (real)

Устанавливает текущий порог подобия слов, который используется операторами <% и %>. Порог должен быть между 0 и 1 (по умолчанию 0,6).

pg_trgm.strict_word_similarity_threshold (real)

Устанавливает текущий строгий порог подобия слов, который используется операторами <<% и %>>. Порог должен быть между 0 и 1 (по умолчанию 0,5).

Поддержка индексов#

Модуль 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;

Это вернет все значения в столбце text, которые достаточно похожи на 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, вместо использования специфичной для языка конфигурации, заключается в том, что хотим получить список исходных (необработанных) слов.

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

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

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