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

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

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

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

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

• функции и операторы для определения схожести алфавитно-цифровых строк на основе триграмм;

• классы операторов индексов, поддерживающие быстрый поиск схожих строк.

Примечание:

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

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

Функции#

Операторы#

Параметры GUC#

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

Модуль 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;

Настройка#

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

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

1. Функция similarity:

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

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

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

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

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

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

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

2. Функция show_trgm:

   SELECT show_trgm ('Pangolin');
   

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

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

3. Функция word_similarity:

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

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

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

4. Функция strict_word_similarity:

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

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

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

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

Исходная документация PosgreSQL по модулю pg_trgm: https://www.postgresql.org/docs/15/pgtrgm.html