pg_trgm. Определение схожести алфавитно-цифровых строк на основе триграмм

В исходном дистрибутиве установлено по умолчанию: нет.

Связанные компоненты: отсутствуют.

Схема размещения: ext.

Модуль pg_trgm предоставляет:

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

Примечание:

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

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

Функции

Имя	Входные переменные функции	Выходные переменные функции	Описание
`similarity`	`text, text`	`real`	Возвращает число, показывающее, насколько близки два аргумента. Диапазон результатов — от `0` (две строки полностью различны) до `1` (две строки идентичны)
`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`

Операторы

Имя	Выходные переменные	Описание
`text % text`	`boolean`	Определяет схожесть аргументов относительно текущего порога, заданного параметром `pg_trgm.similarity_threshold`; `true` – схожесть аргументов выше уровня текущего порога
`text <% text`	`boolean`	Определяет схожесть набора триграмм в первом аргументе и непрерывного фрагмента упорядоченного набора триграмм во втором относительно уровня схожести, установленного в параметре `pg_trgm.word_similarity_threshold` `true` – если схожесть выше уровня порога
`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, позволяющие создавать индекс по текстовым столбцам для быстрого поиска по критерию схожести.

Типы индексов GiST и GIN поддерживают вышеописанные операторы схожести и дополнительно поддерживают поиск на основе триграмм для запросов с:

LIKE;
ILIKE;
~;
~*.

Индексы GiST и GIN не поддерживают простые операторы сравнения и равенства, поэтому может понадобиться индекс на основе B-дерева.

Пример:

CREATE TABLE test_trgm (t text);
CREATE INDEX trgm_idx ON test_trgm USING GIST (t gist_trgm_ops);

                                 Table "ext.test_trgm"
 Column | Type | Collation | Nullable | Default | Storage  | Stats target | Description 
--------+------+-----------+----------+---------+----------+--------------+-------------
 t      | text |           |          |         | extended |              | 
Indexes:
    "trgm_idx" gist (t gist_trgm_ops)
Access method: heap

Класс операторов GiST gist_trgm_ops аппроксимирует набор триграмм в виде сигнатуры битовой карты. В его необязательном целочисленном параметре siglen можно задать размер сигнатуры в байтах.

Параметр может принимать значения от 1 до 2024, по умолчанию равен 12.

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

Пример создания такого индекса с длиной сигнатуры 32 байта:

CREATE INDEX trgm_idxs ON test_trgm USING GIST (t gist_trgm_ops(siglen=32));

                                 Table "ext.test_trgm"
 Column | Type | Collation | Nullable | Default | Storage  | Stats target | Description 
--------+------+-----------+----------+---------+----------+--------------+-------------
 t      | text |           |          |         | extended |              | 
Indexes:
    "trgm_idx" gist (t gist_trgm_ops)
    "trgm_idxs" gist (t gist_trgm_ops (siglen='32'))
Access method: heap

Используя индекс по столбцу t, можно осуществлять поиск по схожести:

SELECT t, similarity (t, 'first') AS sml
  FROM test_trgm
  WHERE t % 'fir'
  ORDER BY sml DESC, t;

В текстовом столбце будут выданы все схожие с интересующим словом значения. Порядок сортировки – от наиболее к наименее схожим. С использованием индекса эта операция будет быстрой даже с очень большими наборами данных.

   t   |    sml     
-------+------------
 first |          1
 fire  |      0.375
 fires | 0.33333334
 fi    |  0.2857143
(4 rows)

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

SELECT t, t <-> 'fir' AS dist
  FROM test_trgm
  ORDER BY dist LIMIT 10;

Результат выполнения запроса:

   t    |    dist    
--------+------------
 fire   |        0.5
 first  | 0.57142854
 fires  | 0.57142854
 fi     |        0.6
 th     |          1
 third  |          1
 second |          1
 tyres  |          1
 second |          1
(9 rows)

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

Примеры типичных запросов:

SELECT t, word_similarity('fir', t) AS sml
  FROM test_trgm
  WHERE 'fir' <% t
  ORDER BY sml DESC, t;

Результат выполнения запроса:

   t   | sml  
-------+------
 fire  | 0.75
 fires | 0.75
 first | 0.75
 first | 0.75
(4 rows)

или

SELECT t, strict_word_similarity('fir', t) AS sml
  FROM test_trgm
  WHERE 'fir' <<% t
  ORDER BY sml DESC, t;

Результат выполнения запроса:

  t   | sml 
------+-----
 fire | 0.5
(1 row)

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

Типы индексов GiST и GIN также поддерживают поиск:

с операторами LIKE и ILIKE, например:
```
SELECT * FROM test_trgm WHERE t LIKE '%fir%tyr';
```
При таком поиске по индексу сначала из искомой строки извлекаются триграммы, а затем они ищутся в индексе. Чем больше триграмм оказывается в искомой строке, тем более эффективным будет поиск по индексу. В отличие от поиска по B-дереву, искомая строка не должна привязываться к левому краю.

Результат выполнения запроса:
```
 t 
---
(0 rows)
```
по регулярным выражениям (операторы ~ и ~*), например:
```
SELECT * FROM test_trgm WHERE t ~ '(fir|tyr)';
```
При таком поиске из регулярного выражения извлекаются триграммы, а затем они ищутся в индексе. Чем больше триграмм удается извлечь из регулярного выражения, тем более эффективным будет поиск по индексу. В отличие от поиска по B-дереву, искомая строка не должна привязываться к левому краю.

Результат выполнения запроса:
```
 t   
-------
 first
 fire
 fires
 tyres
(4 rows)
```

При отсутствии триграмм в искомом шаблоне, поиск сводится к полному сканирования индекса.

Интеграция с текстовым поиском

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

Для возможности поиска нужно:

построить дополнительную таблицу, содержащую все уникальные слова в документе:
```
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, подобный показанному в предыдущем примере, и предлагать варианты исправлений слов, введенных пользователем с ошибками. Для улучшения результата можно дополнительно проверить, что выбранные слова имеют длину, примерно равную длинам ошибочных слов.

Доработка

Доработка не проводилась.

Ограничения

Ограничения отсутствуют.

Установка

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

CREATE EXTENSION pg_trgm SCHEMA ext;

Настройка

Настройка не требуется.

Использование модуля

Функция similarity:

SELECT similarity ('Pangolin','Postgres');

Пример результата запроса:

 similarity 
------------
 0.05882353
(1 row)

Другой пример:

SELECT similarity ('cat','cate');

Пример результата запроса:

 similarity 
------------
        0.5
(1 row)

Функция show_trgm:

SELECT show_trgm ('Pangolin');

Пример результата запроса:

                  show_trgm                  
---------------------------------------------
 {"  p"," pa",ang,gol,"in ",lin,ngo,oli,pan}
(1 row)

Функция word_similarity:

SELECT word_similarity ('Pangolin','Mango');

Пример результата запроса:

 word_similarity 
-----------------
      0.22222222
(1 row)

Функция strict_word_similarity:

SELECT strict_word_similarity ('Pangolin','Mango');

Пример результата запроса:

 strict_word_similarity 
------------------------
             0.15384616
(1 row)

Ссылки на документацию разработчика

Дополнительно поставляемый модуль pg_trgm: https://www.postgresql.org/docs/13/pgtrgm.html

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

Функции​

Операторы​

Параметры GUC​

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

Интеграция с текстовым поиском​

Доработка​

Ограничения​

Установка​

Настройка​

Использование модуля​

Ссылки на документацию разработчика​

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

Функции

Операторы

Параметры GUC

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

Интеграция с текстовым поиском

Доработка

Ограничения

Установка

Настройка

Использование модуля

Ссылки на документацию разработчика