Блог → Краткий обзор методов поиска ключевого слова по словарю

В прошлой заметке я вкратце рассказал о проблематике поиска по нечёткому соответствия в базах данных, а сегодня настало время рассмотреть несколько наиболее распространенных методов поиска по словарю. Очень надеюсь, что эта информация будет полезной для широкого круга читателей, так как для специалистов я навряд ли открою что-то новое. Но всё же, приступим.

Сканирование словаря.

Под сканированием мы понимаем простой последовательный перебор терминов словаря, при котором ключевые слова запроса поочередно сравниваются с каждым из терминов в словаре. Если поиск идёт сразу по нескольким ключевым словам, их попарные сравнения с терминами словаря могут быть крайне неэффективными, так что для ускорения сравнения ключевые слова могут быть организованы в виде дерева, или специальной хэш-таблицы. Что интересно, хотя многие в это и не верят, но грамотно реализованное сканирование работает достаточно быстро. Так, к примеру, программа AGREP, запущенная на обычном "пентиуме" с поддержкой инструкций ММХ, просматривает словарь объёмом 300-800 тыс. записей за 0,01-0,3 секунды (при условии, что данные уже загружены в память), и за 0,5-2 секунды, если используется непосредственное чтения с диска. При работе в многопользовательском режиме запросы пользователей, пришедшие, скажем, за одну секунду, вполне можно объединять в пакеты по 10-1000 запросов и осуществлять последовательный поиск в словаре сразу по всем терминам пакета.

Частичный поиск с использованием хэширования.

Ещё один метод поиска, при котором используется специальная хэш-функция на множестве слов, инвариантная относительно определенного класса ошибок. Пожалуй, в качестве наиболее известного примера можно привести функцию soundex из СУБД Oracle. Обычно, для одинаково звучащих, но имеющих различное написание английских слов, значения функции soundex совпадают. Другим примером использования частичного поиска является хэширование по первым двум буквам слова. Поскольку вероятность сделать ошибку в начале слова не очень велика, этот подход вполне оправдывает себя в случае поиска на соответствие всей строке.

Метод spell-checker'а (метод расширения выборки).

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

Очевидно, что генерация всех возможных "ошибочных" форм поискового термина и проверка их наличия в словаре потребует некоторого времени, даже если термин модифицируется в пределах одной операции редактирования (вставки, удаления или замены). Поэтому большинство spell-checker'ов используют ограничение на количество созданных "ошибочных" форм. При этом сначала программа производит наиболее вероятные модификации. Так, например, бесплатно распространяемый spell-checker ISPELL сначала строит термины, полученные из исходного путем вставки одного символа, затем транспозиции (перестановки местами), удаления, и, наконец, замены.

Метод n-грамм, метод триад.

Это семейство методов основано на следующем наблюдении: модифицированное и исходное слова должны обладать общими подстроками. Пусть, к примеру, "полоса" в результате ошибки (скажем при оптическом распознавании) трансформировалась в слово "пороса". Тогда оба слова обладают общей подстрокой: оса. В общем случае, можно использовать следующее свойство: пусть слово и получено из слова V в результате к операций редактирования (типа удаление, замена или вставка), тогда, если представить слово и в виде последовательности (k+1) подстроки, то хотя бы одна из этих подстрок будет также являться подстрокой исходного слова V.

Организация списка ключевых слов в виде инвертированного файла, в котором роль терминов играют подстроки длины n (так называемые "n-граммы"), позволяет вести поиск по сходству и по подстроке, в большинстве случаев - без сканирования словаря. Предположим, нужно найти все термины, отличающиеся от n не более чем на k операций редактирования. Представим и в виде суммы k+1 подстрок, каждая из которых не короче n. Если такое разбиение невозможно - сканируем словарь. Если же возможно - то все подстроки разбиения обладают префиксом длины n. Для каждого префикса (являющегося как раз n-граммой) нужно считать соответствующий инвертированный список (где хранятся ссылки на слова, содержащие эту n-грамму), и для каждого слова из инвертированного списка непосредственно проверить, действительно ли оно отличается от поискового термина и не более чем на к операций редактирования.

Чтобы избежать сканирования словаря в случае коротких поисковых терминов - желательно также инвертировать и "синтетические" n-граммы, то есть подстроки вида $s и i$, где s и i, соответственно, начала и окончания слов длины n-1, а $ - специальный символ, не входящий в алфавит. Модификация метода n-грамм Вилбура-Ховайко, которую сами авторы называют методом триад (используются 3-граммы или "триады"), была разработана для минимизации числа обращений к словарю. Авторы метода предложили строить полное множество терминов, имеющих общие триады с ключевыми словами запроса, но затем - с помощью весового "коэффициента похожести" терминов словаря и запроса - на этапе чтения инвертированных списков "отсекать" малоперспективные варианты (для которых коэффициент похожести будет меньше заданного порогового значения). При этом какие-то термины могут быть пропущены; налицо компромисс между эффективностью поиска и его полнотой.

Trie-деревья.

В отличии от обычных сбалансированных деревьев, в trie-дереве все строки, имеющие общее начало, располагаются в одном поддереве. Каждое ребро помечено некоторой строкой. Терминальным вершинам ("листьям") соответствуют слова списка. Пусть список строк содержит термины: дерево, деревья, пол, половик. Чтобы ни одно из слов не было префиксом другого слова (как в случае слов пол и половик), в конец каждого слова добавляется специальный символ $, отсутствующий в алфавите. Словом w(x) , соответствующим вершине дерева x, будем называть строку, полученную в результате слияния строк, которыми помечены рёбра, ведущие из корня дерева в вершину х4. Как несложно видеть, все строки, соответствующие терминальным узлам поддерева с вершиной в x, обладают общим префиксом w(x).



Обычно trie-деревья используются для поиска по подстроке (в них заносятся все суффиксы или префиксы терминов). Тем не менее, trie-деревья можно использовать и для нечеткого поиска.

Собственное решение: хэширование по сигнатуре слова.

Несмотря на то, что разработано изрядное количество алгоритмов поиска по сходству, реализовать их гораздо сложнее, чем метод последовательного перебора терминов. При том, что выигрыш от их использования (например, для метода n-грамм) не слишком и велик. К тому же, индексы, необходимые для поиска по подстроке, имеют довольно большой объём.

В процессе тестирования и исследования уже существующих методик, был разработан собственный метод организации словарей: "хэширование по сигнатуре слова", который позволяет выполнять основные типы поисковых запросов - на соответствие термину целиком, по подстроке и простейшим регулярным выражениям - за более чем приемлемое время. Метод использует хэш-функцию, отображающую слово в битовый вектор, у которого i-ый компонент равен 1, если в слове есть буква, попадающая в i-ую группу. При этом алфавит разбивается на несколько подмножеств - групп с примерно одинаковыми вероятностями попадания символа алфавита в каждую из групп.

Используя хэширование по сигнатуре для индексирования словаря, реализуется макет поисковой системы, основанной на сжатых инвертированных файлах, и позволяющей осуществлять поиск по сходству. Как и ожидалось, инвертирование документов позволяет эффективно осуществлять как точный, так и нечёткий поиск на даже на обычном компьютере. Для текстовой базы данных, содержащей 100 тыс. документов суммарным объемом 220 Мб, поиск по сходству не превышает 1-3 секунд. Можно предположить, что даже для базы данных размером порядка 1 Гб - размер, практически недостижимый для пользовательской базы данных, время поиска на неточное равенство не превысит 5-10 секунд.

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