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