Нечеткий поиск: триграммы

Достаточно часто на практике возникает задача организовать поиск слова по нечеткому совпадению, т.е. содержащего опечатки или имеющего близкое написание.  В это статье я расскажу, как использовать триграммы для решения этой задачи.

И так, пускай у нас есть слово программа и оно же с опечаткой - програма.  Добавим в начало слова два символа _ (подчеркивание) и два в коней, слово запишется следующим образом: __программа__. Распишем последовательно все тройки символов и получим:

__п, _пр, про, рог, огр, гра, рам, амм, мма, ма_, а__

Оставим только уникальные тройки символов, в нашем случае они совпадут с исходными:

__п, _пр, про, рог, огр, гра, рам, амм, мма, ма_, а__

Таким же образом построим тройки символов для "програма" и получим:

__п, _пр, про, рог, огр, гра, рам, ама, ма_, а__

Пересечением двух множеств троек символов будет:

__п, _пр, про, рог, огр, гра, ма_, а__

в этом множестве у нас получилось l=8 элементов.

Теперь взяв объединение множеств троек для исходных слов, мы получим:

__п, _пр, про, рог, огр, гра, рам, амм, ама, мма, ма_, а__

число элементов в этом множестве L=12

Теперь введем коэффициент похожести двух множеств как результат деления

R=l/L.

Его значение будет равно

R=8/12 = 0.6667

Расстояние между двумя словами можно определить, как

D=1-R

Теперь мы можем сказать, что два слова похожи, если значения коэффициента R больше, некоторого порогового значения. На практике хорошие значения получаются, когда R >= 0.6

Основной недостаток метода заключается в том, что он плохо работает в случае коротких слов и не дает результатов. Поэтому лучше начинать его использование при размеров слов от 6 символов.

Теперь когда принцип сравнения на основе триграмм стал ясен можно перейти к практическому применению.  В базе данных PostgreSQL есть расширение pg_trgm, которое входит в стандартный contrib, которые позволяет организовать поиск на основе триграммных индексов. Для этого сначала подключаем расширение командой:

create extension pg_trgm;

Индексируем поле таблицы одним из следующих способов:

CREATE INDEX trgm_idx ON our_table USING gist (field gist_trgm_ops);

или

CREATE INDEX trgm_idx ON out_table USING gin (field gin_trgm_ops);

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

SELECT field, similarity(field, 'keyword') AS sml
FROM our_table
WHERE field % 'keyword'
ORDER BY sml DESC, t;

Функция similarity возвращает значение коэффициента похожести двух слов. Пороговое значение коэффициента можно задать при помощи функции set_limit, а получить при помощи get_limit.

Важно отметить, что GIN-индекс при поиске работает быстрее чем GiST, но медленнее обновляется и строится, поэтому выбор типа индекса зависит от того насколько статичны данные.

Более того триграммные индексы не обеспечивают проверку на эквивалент и не учитывают порядок значений, поэтому, если нужно искать по полному соответствую или сортировать, то придется построить еще и обычный индекс.

04.08.2016