Введение

Поиск с использованием полного текста документов

В информационном поиске, полнотекстовый поиск относится к методам поиска одного документа, хранящегося на компьютере, или коллекции в полнотекстовой базе данных. Полнотекстовый поиск отличается от поиска на основе метаданных или частей оригинальных текстов, представленных в базах данных (таких как заголовки, аннотации, выбранные разделы или библиографические ссылки). При полнотекстовом поиске поисковая система анализирует все слова в каждом сохраненном документе, пытаясь сопоставить их с критериями поиска (например, с текстом, указанным пользователем). Методы полнотекстового поиска появились в 1960-х годах, например, IBM STAIRS в 1969 году, и стали широко распространены в онлайн-библиографических базах данных в 1990-х годах. Многие веб-сайты и прикладные программы (например, текстовые редакторы) предоставляют возможности полнотекстового поиска. Некоторые веб-поисковые системы, такие как прежняя AltaVista, используют методы полнотекстового поиска, в то время как другие индексируют лишь часть веб-страниц, проанализированных их системами индексации.

Индексирование

При работе с небольшим количеством документов поисковая система полного текста может напрямую сканировать содержимое документов с каждым запросом, стратегия, называемая "последовательным сканированием". Это делают некоторые инструменты, такие как grep, при поиске. Однако, когда количество документов для поиска потенциально велико, или количество поисковых запросов значительно, задача полнотекстового поиска часто разделяется на две составляющие: индексирование и поиск. На этапе индексирования текст всех документов сканируется и создается список поисковых терминов (часто называемый индексом, но более корректно – конкорданс). На этапе поиска, при выполнении конкретного запроса, обращаются только к индексу, а не к тексту исходных документов. Индексатор создает запись в индексе для каждого термина или слова, найденного в документе, и, возможно, указывает его относительную позицию в документе. Обычно индексатор игнорирует стоп-слова (например, "the" и "and"), которые часто встречаются и не несут достаточной смысловой нагрузки для поиска. Некоторые индексаторы также применяют языковую стемминг-обработку к индексируемым словам. Например, слова "drives", "drove" и "driven" будут занесены в индекс под общим понятием "drive".

Компромисс точности и отзывов

Полнота показывает количество релевантных результатов, возвращенных поиском, в то время как точность измеряет качество возвращенных результатов. Полнота – это отношение количества возвращенных релевантных результатов ко всему количеству релевантных результатов. Точность – это отношение количества релевантных результатов, возвращенных поиском, к общему количеству возвращенных результатов. Диаграмма справа иллюстрирует поиск с низкой точностью и низкой полнотой. На диаграмме красные и зеленые точки представляют общую совокупность потенциальных результатов поиска для данного запроса. Красные точки обозначают нерелевантные результаты, а зеленые – релевантные. Релевантность определяется близостью результатов поиска к центру внутреннего круга. Из всех возможных результатов, показанных на диаграмме, те, которые были фактически возвращены поиском, выделены светло-синим цветом. В примере был возвращен только 1 релевантный результат из 3 возможных, поэтому полнота составляет очень низкое соотношение – 1/3, или 33%. Точность в данном примере также очень низкая – 1/4, или 25%, поскольку только 1 из 4 возвращенных результатов оказался релевантным. В связи с неоднозначностью естественного языка, системы полнотекстового поиска обычно включают такие возможности, как стоп-слова для повышения точности и стемминг для повышения полноты. Поиск по контролируемому словарю также помогает снизить проблемы с низкой точностью, маркируя документы таким образом, чтобы устранить неоднозначность. Взаимосвязь между точностью и полнотой проста: повышение точности может снизить общую полноту, а повышение полноты – снизить точность.

Ложноположительная проблема

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

Улучшение производительности

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

Улучшенные алгоритмы поиска

Алгоритм PageRank, разработанный компанией Google, повышает значимость документов, на которые ссылаются другие веб-страницы. Подробнее смотрите в статье «Поисковая система».

Программное обеспечение

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