pg_trgm

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

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


Общее представление о триграммах (или триграфах)

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

Примечание
Извлекая триграммы из строки, pg_trgm игнорирует символы, не относящиеся к словам (не буквенно-цифровые). При определении набора триграмм, содержащихся в строке, считается, что перед каждым словом находятся два пробела, а после — один. Например, из строки «cat» выделяется набор триграмм: « c», « ca», «cat» и «at ». Набор триграмм из строки «foo|bar»: « f», « fo», «foo», «oo », « b», « ba», «bar» и «ar ».


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

Функции, предоставляемые модулем pg_trgm, перечислены в Таблице 25, а операторы — в Таблице 26.

Таблица 25. Функции pg_trgm

Функция
Описание
similarity ( text, text ) → real
Возвращает число, показывающее, насколько схожи два аргумента. Диапазон результата — от нуля (показывающего, что две строки полностью различны) до единицы (показывающей, что две строки идентичны).
show_trgm ( text ) → text[]
Возвращает массив всех триграмм в заданной строке. (На практике это редко бывает полезно, разве что для отладки.)
word_similarity ( text, text ) → real
Возвращает число, показывающее наибольшую степень схожести между набором триграмм в первой строке и любой непрерывной последовательностью упорядоченного набора триграмм во второй строке. Подробнее об этом рассказывается ниже.
strict_word_similarity ( text, text ) → real
Похожа на word_similarity, но подгоняет границы последовательности к границам слов. Поскольку триграммы не пересекают слова, эта функция фактически возвращает наибольшую степень схожести между первой строкой и любой непрерывной последовательностью слов во второй строке.
show_limit () → real
Возвращает текущий порог схожести, используемый оператором %. Это значение задает минимальную схожесть между двумя словами, при которой они считаются достаточно схожими, чтобы, к примеру, одно было ошибочным написанием другого. (Устаревшая функция; используйте вместо нее SHOW pg_trgm.similarity_threshold.)
set_limit ( real ) → real
Задает текущий порог схожести, используемый оператором %. Порог должен быть в диапазоне от 0 до 1 (по умолчанию 0.3). Возвращает то же значение, что было передано на вход. (Устаревшая функция; используйте вместо нее SET pg_trgm.similarity_threshold.)

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

# 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 больше подходит для выявления схожести частей слов.

Таблица 26. Операторы pg_trgm

Оператор
Описание
text % text → boolean
Возвращает true, если схожесть его аргументов выше текущего порога, заданного параметром pg_trgm.similarity_threshold.
text <% text → boolean
Возвращает true, если схожесть между набором триграмм в первом аргументе и непрерывной последовательностью упорядоченного набора триграмм во втором аргументе выше текущего порога схожести слов, заданного параметром pg_trgm.word_similarity_threshold.
text %> text → boolean
Коммутатор оператора <%.
text <<% text → boolean
Возвращает true, если в его втором аргументе имеется непрерывная последовательность упорядоченного набора триграмм, соответствующего границам слов, и его схожесть с набором триграмм первого аргумента выше текущего порога схожести строго слов, заданного параметром pg_trgm.strict_word_similarity_threshold.
text %>> text → boolean
Коммутатор оператора <<%.
text <-> text → real
Возвращает «расстояние» между аргументами, то есть один минус значение similarity().
text <<-> text → real
Возвращает «расстояние» между аргументами, то есть один минус значение word_similarity().
text <->> text → real
Коммутатор оператора <<->.
text <<<-> text → real
Возвращает «расстояние» между аргументами, то есть один минус значение strict_word_similarity().
text <->>> text → real
Коммутатор оператора <<<->.

Параметры 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, ~, ~* и =. Операторы неравенства не поддерживаются. Обратите внимание, что для операторов равенства эти индексы могут быть не так эффективны, как обычные индексы 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 gist_trgm_ops аппроксимирует набор триграмм в виде сигнатуры битовой карты. Его необязательный целочисленный параметр 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, 'слово') AS sml
  FROM test_trgm
  WHERE t % 'слово'
  ORDER BY sml DESC, t;

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

Другой вариант предыдущего запроса:

SELECT t, t <-> 'слово' AS dist
  FROM test_trgm
  ORDER BY dist LIMIT 10;

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

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

SELECT t, word_similarity('слово', t) AS sml
  FROM test_trgm
  WHERE 'слово' <% t
  ORDER BY sml DESC, t;

и

SELECT t, strict_word_similarity('слово', t) AS sml
  FROM test_trgm
  WHERE 'слово' <<% t
  ORDER BY sml DESC, t;

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

Другие возможные варианты предыдущих запросов:

SELECT t, 'слово' <<-> t AS dist
  FROM test_trgm
  ORDER BY dist LIMIT 10;

и

SELECT t, 'слово' <<<-> t AS dist
  FROM test_trgm
  ORDER BY dist LIMIT 10;

Они могут быть довольно эффективно выполнены с индексами GiST, но не GIN.

Эти типы индексов также поддерживают поиск с операторами LIKE и ILIKE, например:

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

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

Кроме того, эти типы индексов поддерживают индексный поиск по совпадению регулярных выражений (операторы ~ и ~*), например:

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

Затем создадим индекс триграмм по столбцу со словами:

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

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

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


Ссылки

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

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


Авторы

Олег Бартунов (oleg@sai.msu.su), Москва, Московский Государственный Университет им. М. В. Ломоносова, Россия

Федор Сигаев (teodor@sigaev.ru), Москва, ООО «Дельта-Софт», Россия

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

Документация: Кристофер Кингс-Линн (Christopher Kings-Lynne)

Разработку этого модуля спонсировало ООО «Дельта-Софт», г. Москва, Россия.