Нечеткий поиск: триграммыДостаточно часто на практике возникает задача организовать поиск слова по нечеткому совпадению, т.е. содержащего опечатки или имеющего близкое написание. В это статье я расскажу, как использовать триграммы для решения этой задачи. И так, пускай у нас есть слово
Оставим только уникальные тройки символов, в нашем случае они совпадут с исходными:
Таким же образом построим тройки символов для "програма" и получим:
Пересечением двух множеств троек символов будет:
в этом множестве у нас получилось l=8 элементов. Теперь взяв объединение множеств троек для исходных слов, мы получим:
число элементов в этом множестве L=12 Теперь введем коэффициент похожести двух множеств как результат деления
Его значение будет равно
Расстояние между двумя словами можно определить, как
Теперь мы можем сказать, что два слова похожи, если значения коэффициента R больше, некоторого порогового значения. На практике хорошие значения получаются, когда R >= 0.6 Основной недостаток метода заключается в том, что он плохо работает в случае коротких слов и не дает результатов. Поэтому лучше начинать его использование при размеров слов от 6 символов. Теперь когда принцип сравнения на основе триграмм стал ясен можно перейти к практическому применению. В базе данных PostgreSQL есть расширение pg_trgm, которое входит в стандартный contrib, которые позволяет организовать поиск на основе триграммных индексов. Для этого сначала подключаем расширение командой:
Индексируем поле таблицы одним из следующих способов:
или
Поле таблицы field должно быть текстовым. После чего можно выполнить поиск, следующим образом
Функция similarity возвращает значение коэффициента похожести двух слов. Пороговое значение коэффициента можно задать при помощи функции set_limit, а получить при помощи get_limit. Важно отметить, что GIN-индекс при поиске работает быстрее чем GiST, но медленнее обновляется и строится, поэтому выбор типа индекса зависит от того насколько статичны данные. Более того триграммные индексы не обеспечивают проверку на эквивалент и не учитывают порядок значений, поэтому, если нужно искать по полному соответствую или сортировать, то придется построить еще и обычный индекс. 04.08.2016 |
популярные тэги
наука
интересно
новости
технологии
история
go
golang
программирование
it
искусственный интеллект
путешествия
природа
космос
ai
базы данных
медицина
science
анализ текстов
ии
text mining
робототехника
авто
музыка
роботы
интернет
нейронные сети
robots
space
вокруг света
postgresql
алгоритмы
гитара
животные
оружие
google
nosql
авиация
здоровье
техника
auto
|