Блог → О проблемах поиска в базах данных по нечёткому соответствию

Как всем нам хорошо известно, за последние 50 лет объём информации, представленной в электронном виде, вырос до поистине космических величин, а с появлением Интернета он продолжает расти буквально по экспоненте. Причин, по которым этот рост может вдруг остановиться, я не нахожу - да и вряд ли они вообще есть. Человечество не сможет существовать без информации, так что нам остаётся лишь - что-то с этим безобразием делать! Именно поэтому задача поиска в документальных базах данных не только до сих пор актуальна, но и стоит как никогда, остро.

Давайте обратимся к истории - первые информационно-поисковые системы (сокращённо ИПС) появились лет 30-40 назад, и за это время сильно изменилось как техническое оснащение, так и алгоритмы поиска по базам данных. Нынешние ИПС (например, тот же самый Google или Яндекс) "обучились" автоматически обращаться к Интернету, чтобы собирать информацию, хорошо учитывать языковые особенности и производить оценку значимости найденных документов (речь о релевантности поиска, который современные поисковики уделяют большое значение). В то же время поиску с учетом изменяемости слов в языке (морфологии) и синонимов, а также ранжированию выборки для соответствию запросу посвящено множество интересных статей - как у нас, в России, так и за рубежом. На этом фоне выглядит довольно странным, что такая проблема, как поиск по сходству, до сих пор остается слабо изученной.

Поиск по сходству или как его ещё называют, нечёткий поиск, в отличии от поиска на точное соответствие, предполагает, что и в тексте запроса, и тем более, в документах могут присутствовать ошибки. Поэтому, чтобы достичь удовлетворительного результата, нужно кроме точно заданных терминов, искать и "достаточно похожие". Насколько это нужно? Представьте сами, какое количество ошибок содержится в электронных документах (да хотя бы в этой небольшой заметке, которую вы читаете), в том числе, и доступных в Интернете. Также учитывайте, что всё чаще используются программы распознавания текста (OCR), для которых процент ошибочно считанных данных варьируется в пределах от одного до пяти процентов. Эти документы также попадают в Сеть, и далеко не каждый их них выверяется с помощью программ проверки орфографии!

Мало того, существуют словари спецтерминов (например, медицинских или химических), содержащие миллионы сложнейших "многоэтажных" слов - ясно, что все эти термины помнить невозможно, и вероятность ошибки в задании ключевого слова будет, по определению, очень высока. Ещё один пример, где очень полезен поиск по сходству - поиск необходимой программы по FTP ресурсам в Интернете - кто же знает заранее, как именно будет называться архив с конкретной программой, которая нам нужна?

Но, несмотря на актуальность проблемы, на сегодняшний день очень немногие ИПС предоставляют возможность нечеткого поиска. Этому мешают, в частности, такие факторы, как сложность реализации подобного поиска, большие (по сравнению с поиском на равенство) временные и вычислительные затраты, отсутствие эффективных сублинейных (то есть таких, которые не требуют полного перебора словаря) алгоритмов поиска "похожих" терминов, и наконец, просто сложность в ранжировании найденных документов. Хороший списочек, да?

Как правило, текстовые базы данных структурированы иерархически: тематические каталоги - документы - параграфы - предложения - слова. Суммарный размер текстовых данных может легко превышать терабайт (1012 байт), поэтому для эффективного поиска все поисковые системы используют индексацию данных. Как именно это делается? Самый популярный на сегодня метод организации индекса - так называемое "инвертирование документов" (а полученный в результате индекс называют, соответственно, "инвертированным файлом"). Логически инвертированный файл устроен наподобие предметного указателя в конце книги: для каждого термина словаря W в индексе хранится список ссылок на документы (называемый также инвертированным списком), в которых встречается термин W.

Как правило, поиск в таком "инвертированном файле" ведётся по ключевым словам (хотя, безусловно, возможно и задание точного контекста). Также понятно, что инвертированный файл можно использовать и для точного, и для нечеткого поиска - при этом задача поиска в массиве документов сводится к поиску термина в словаре и обработке инвертированных списков найденных терминов. В случае же поиска по контексту уже понадобятся более сложные алгоритмы, ведь при модификации поискового запроса вполне может измениться порядок разбиения строки на термины (например, если пользователь по невнимательности пропустил разделитель). До сих пор считалось, что размер инвертированного файла может в два-три раза превышать размер массива документов, что, разумеется, неприемлемо для обычного компьютера с ограниченным объёмом винчестера. Но в последнее время разработаны методы кодирования списков вхождения терминов, которые позволяют "ужать" инвертированный файл до 7-30% от суммарного размера документов. При этом скорость поиска в сжатом инвертированном файле может быть больше, нежели в неупакованном. Такая методика позволяет использовать инвертированные файлы как на персональных компьютерах, и на серверах.



Как я уже говорил, поиск по сходству в большинстве случаев сводится к поиску в словаре. Но если в случае точного поиска широко используются древовидные структуры и хэш-индексы, а учёт грамматических форм и синонимов осуществляется с помощью расширения выборки, то уже для "поиска по подстроке" приходится использовать суффиксные деревья (то есть деревья, в которых хранятся суффиксы терминов). А поиск на неточное равенство - ещё более сложная задача, ведь индексирование словаря приводит к избыточности хранения данных, а выигрыш по сравнению со сканированием (прямым перебором) словаря не так уж и велик: далеко не всегда удается добиться хотя бы десятикратного сокращения времени поиска. Ну и, поскольку словарь может быть очень и очень большим, актуальна задача эффективной индексации списка терминов. Но об этом - в следующей заметке. Заходите в мой блог, читайте и комментируйте!