Интеллектуальный поиск с pg_trgm и расстоянием Левенштейна в Postgres

Существует три распространенных сценария поиска в базе данных, которые выходят за рамки возможностей традиционных запросов с подстановочными знаками.

Во-первых, когда пользователи ищут «корм для домашних животных», но в вашей базе данных нет продуктов с названием «корм для домашних животных», будет ли база данных достаточно умной, чтобы вместо этого вернуть «корм для кошек» или «корм для собак»?

Во-вторых, если пользователи неправильно написали «шоколад» как «шоколад», может ли база данных попытаться угадать, чего хотят пользователи, и вернуть наиболее близкие совпадения?

В-третьих, слова в другом порядке могут по-прежнему относиться к одному и тому же предмету, например, «торт с манго» и «торт с манго». Сможет ли база данных сопоставить строку поиска с названием продукта, если порядок слов отличается?

В традиционных базах данных подстановочный поиск «кофеварка» не даст вам «кофемашина», поиск «круассана» (с ошибкой) не найдет «круассан», а запрос «моющее средство для рук» не даст t вернуть «моющее средство для мытья посуды». Но с нечетким сопоставлением в Postgres модуль pg_trgm поддерживает быстрый поиск похожих строк и обеспечивает гибкую и интеллектуальную производительность поиска. Сравнение некоторых результатов запроса можно найти на следующих изображениях.

Схема

  • Что такое pg_trgm и триграммы
  • Нечеткий поиск с pg_trgm
  • Расстояние Левенштейна в Postgres
  • Каковы ограничения нечеткого поиска в Postgres

Что такое pg_trgm

Модуль pg_trgm из Postgres ищет похожие строки на основе совпадения триграмм. Триграммы в pg_trgm — это группы из трех символов, которые игнорируют несловесные символы. Сходство двух заданных строк можно определить по количеству общих триграмм.

Триграммы в заданной строке

Всегда легче понять концепцию на примерах. Набор триграмм в строке «манго» равен

m, ma, man, ang, ngo, go

Функция show_trgm возвращает все триграммы в заданной строке и на практике часто используется для отладки.

В другом примере, «the|bay», мы видим, что учитывается только буквенно-цифровой текст, который

t, th, the, he, b, ba, bay, ay

Оценка Similairty от pg_trgm

Оценка сходства двух заданных строк может быть измерена количеством триграмм, которые они разделяют. Например, оценка similarity между «торт с манго» и строкой в ​​другом порядке «торт с манго» – 0,68, "корм для кошек" и "корм для домашних животных" – 0,38, "coconuts”, а слово с ошибкой “ciconuts” равно 0,5.

Нечеткий поиск с pg_gram

Сначала создайте расширение для pg_trgm, если оно еще не загружено. Затем найдите цели, похожие на «кофемашину», и отсортируйте результаты в порядке убывания показателей сходства. Как показано на скриншоте ниже, «кофеварка» больше всего похожа на «кофеварку».

CREATE EXTENSION IF NOT EXISTS pg_trgm; 
select distinct product_sub_species, 
similarity(product_sub_species, 'coffee machine') as score from 
ct where product_sub_species % 'coffee machine'
order by score desc;

Давайте рассмотрим еще один пример с опечаткой в ​​цели запроса. Пользователь хотел найти «разделочную доску», но вместо этого ввел «разделочная доска». Мы видим, что поиск pg_trgm может вернуть «разделочные доски» как наиболее близкое совпадение, и это именно то, что нужно пользователю.

Расстояние Левенштейна в Postgres

В отличие от pg_trgm, расстояние Левенштейна измеряет сходство, анализируя, насколько различны две строки. Как определено в Википедии, неформально расстояние Левенштейна между двумя словами — это минимальное количество односимвольных правок (вставок, удалений или замен), необходимых для замены одного слова другим.

Чем меньше расстояние Левенштейна, тем более похожи две строки. В следующем примере показано, что расстояние Левенштейна между «игрушками для кошек» и «игрушками для домашних животных» равно 4, что указывает на то, что «игрушки для кошек» более близки, чем «игрушки для собак».

CREATE EXTENSION IF NOT EXISTS fuzzystrmatch;
SELECT distinct
 product_sub_species,
    LEVENSHTEIN(product_sub_species, 'pet toy')
FROM ct
ORDER BY LEVENSHTEIN(product_sub_species, 'pet toy') ASC

Каковы ограничения нечеткого поиска в Postgres

В методах нечеткого поиска Postgres есть два основных ограничения. Во-первых, сопоставление строк в Postgres не основано на семантике. И pg_trgm, и расстояние Левенштейна, или soundex, метафон являются сравнениями на уровне символов. Например, поисковый запрос SQL для «Dog Chews» не найдет «Pet Treat» из-за отсутствия общих триграмм.

Во-вторых, нечеткое совпадение в Postgres нельзя применять в сценарии обучения с учителем. Например, есть 2 набора данных с некоторыми общими столбцами: «employee_name», «email» и «address». И нам нужно объединить сотрудников из этих наборов данных, чтобы объединить информацию об одном и том же человеке. Типичное решение состоит в том, чтобы вычислить показатель сходства для каждого столбца, а затем запустить случайный лес или другие классификаторы, чтобы изучить базовые правила для обнаружения одного и того же человека в разных наборах данных. Это выходит за рамки Postgres.

Заключение

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

В этой статье мы рассмотрели методы pg_trgm и расстояния Левенштейна с примерами поиска в базе данных с использованием похожих строк, строк в разном порядке и строк с ошибками. Также мы обсудили ограничения нечеткого сопоставления в Postgres. Пожалуйста, примените эту технологию к своим проектам и не стесняйтесь обращаться, если у вас есть какие-либо вопросы. 🐸 🐣 🐼

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

Отдельное спасибо Файзану Кази за вычитку. 🔆 ✔️ 🐳