F.47. pg_trgm — поддержка определения схожести текста на основе триграмм #

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

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

F.47.1. Понятия, связанные с триграммами (или триграфами) #

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

Примечание

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

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

Реализованные в модуле pg_trgm функции перечислены в Таблице F.31, а операторы — в Таблице F.32.

Таблица F.31. Функции 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 больше подходит для определения схожести частей слов.

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

Оператор

Описание

text % textboolean

Возвращает true, если схожесть аргументов выше текущего порога, заданного параметром pg_trgm.similarity_threshold.

text <% textboolean

Возвращает true, если схожесть между набором триграмм в первом аргументе и непрерывным фрагментом упорядоченного набора триграмм во втором превышает уровень схожести, устанавливаемый параметром pg_trgm.word_similarity_threshold.

text %> textboolean

Коммутирующий оператор для <%.

text <<% textboolean

Возвращает true, если во втором аргументе имеется непрерывный фрагмент упорядоченного набора триграмм, соответствующего границам слов, и его схожесть с набором триграмм первого аргумента превышает уровень схожести, устанавливаемый параметром pg_trgm.strict_word_similarity_threshold.

text %>> textboolean

Коммутирующий оператор для <<%.

text <-> textreal

Возвращает «расстояние» между аргументами, то есть один минус значение similarity().

text <<-> textreal

Возвращает «расстояние» между аргументами, то есть один минус значение word_similarity().

text <->> textreal

Коммутирующий оператор для <<->.

text <<<-> textreal

Возвращает «расстояние» между аргументами, то есть один минус значение strict_word_similarity().

text <->>> textreal

Коммутирующий оператор для <<<->.


F.47.3. Параметры 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).

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

Модуль 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 gist_trgm_ops аппроксимирует набор триграмм в виде сигнатуры битовой карты. В его необязательном целочисленном параметре siglen можно задать размер сигнатуры в байтах. Параметр может принимать значения от 1 до 2024, по умолчанию он равен 12. При увеличении размера сигнатуры поиск работает точнее (сканируется меньшая область в индексе и меньше страниц кучи), но сам индекс становится больше.

Пример создания такого индекса с длиной сигнатуры 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;

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

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

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.

Начиная с 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, которые здесь не рассматриваются.

F.47.6. Ссылки #

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

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

F.47.7. Авторы #

Олег Бартунов , Москва, Московский Государственный Университет, Россия

Фёдор Сигаев , Москва, ООО «Дельта-Софт», Россия

Александр Коротков , Москва, Postgres Professional, Россия

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

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