pg_trgm — поддержка схожести текста с использованием триграмм
Эта страница переведена при помощи нейросети GigaChat.
Модуль pg_trgm предоставляет функции и операторы для определения схожести буквенно-цифрового текста на основе сопоставления триграмм, а также классы операторов индексации, которые поддерживают быстрый поиск похожих строк.
Этот модуль считается «надежным», то есть его могут устанавливать обычные пользователи, обладающие привилегией CREATE на текущей базе данных.
Концепции триграмм (или триграфа)
Триграмма - это группа из трех последовательных символов, взятых из строки. Можно измерить сходство двух строк, подсчитав количество триграмм, которые есть в обеих. Эта простая идея оказывается очень эффективной для измерения сходства слов во многих естественных языках.
pg_trgm игнорирует неразборчивые символы (неалфавитные) при извлечении триграмм из строки. Каждое слово считается имеющим два пробела перед ним и один пробел после него при определении набора триграмм, содержащихся в строке. Например, набор триграмм в строке "cat" - это " c", " ca", "cat" и "at ". Набор триграмм в строке "foo|bar" - это " f", " fo", "foo", "oo ", " b", " ba", "bar" и "ar ".
Функции и операторы
Функции, предоставляемые модулем, показаны в таблице «Функции pg_trgm», а операторы - в таблице «Операторы pg_trgm».
Функции 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 больше подходит для поиска схожести частей слов.
Операторы 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, ~, ~* и =. В стандартной сборке 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, аналогичный предыдущему примеру, может быть использован для предложения правописания для неправильно написанных слов в поисковых запросах пользователя. Полезным дополнительным тестом будет требование, чтобы выбранные слова также были аналогичной длины с неправильным словом.
Поскольку таблица words была создана как отдельная статическая таблица, ее необходимо периодически регенерировать, чтобы она оставалась достаточно актуальной с коллекцией документов. Обычно нет необходимости поддерживать его в точности актуальным.