Индексация массивов документов

А. В. Аграновский, Р. Э. Арутюнян

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

Сотрудникам крупных, средних и даже небольших компаний, в частности, работающих в сфере информационных технологий, приходится сталкиваться с проблемой навигации по значительному объему документации, хранящейся на сервере локальной сети или на их рабочих станциях. Программные продукты, разработанные для решения подобной проблемы, не всегда исчерпывающим образом удовлетворяют потенциальных пользователей таких информационных систем, поэтому возникает задача разработки собственного механизма навигации, учитывающего особенности конкретного массива документов.

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

Извлечение текстового содержания

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

• Текстовые файлы (txt). Извлечь текстовое содержание из таких файлов достаточно просто. Это самый удобный для индексации формат, но на сегодняшний день он используется относительно редко. Кроме того, в файлах текстового формата затруднено определение названия документа и практически невозможно выделение его авторов.
• HTML-страницы (htm, html). Будучи одним из самых распространенных форматов хранения текстовой информации, формат HTML относительно легко подвергается обработке для выделения текста. Простейший алгоритм состоит в удалении всех тегов. Однако в заголовке HTML-файла может храниться информация, которую следует обрабатывать отдельно: название документа (тег TITLE), сведения об авторах, ключевые слова и др. (тег META).
• Документы Adobe Acrobat (pdf). Данный формат получил в последнее время широкое распространение отчасти благодаря своей межплатформности. Несмотря на то что pdf-файлы, как правило, содержат текст, для получения его в явном виде обычно требуются значительные усилия. Для этого существует ряд программных продуктов, реализующих полный разбор pdf-файла. Возможно также использование средств automation Adobe Acrobat, но вследствие больших затрат на межпроцессные вызовы (COM-сервер Adobe Acrobat реализован в виде локального, т. е. exe-файла) процедура получения текста даже для одного pdf-файла требует значительных затрат времени и, на взгляд авторов, практически неприемлема.
• Файлы PostScript (ps). Файлы этого формата также приобрели большую популярность и используются, в частности, для хранения научных статей, чему способствует возможность легкого преобразования в этот формат dvi-файлов. Формат ps сложен, однако существуют программы для выделения текста из таких файлов, причем некоторые из них, как и в случае с pdf-файлами, доступны в виде открытых кодов.
• Документы MS Word (doc). Фирма Microsoft официально не открыла формат doc и не предоставила удобных автоматических средств получения содержимого doc-файлов. Тем не менее с помощью имеющихся автоматических средств данная задача может быть решена, хотя и со значительным ущербом для надежности и скорости работы приложений. Во всяком случае, в Интернете есть неофициальные описания формата doc и исходные коды программ, выделяющих текст из doc-файлов.
• Файлы RTF (rtf). Этот формат был также разработан Microsoft, его описание можно найти на официальном сайте корпорации.
• Файлы мультимедиа (mp3, ogg, avi, mpeg и др.). Они могут быть проиндексированы по названию песни, фильма, альбома и имени исполнителя, если эти данные в них присутствуют.
• Исполняемые файлы (exe). Иногда такие файлы можно подвергнуть индексации. Хотя текстовое содержание из exe-файлов получить невозможно, но этот формат позволяет определить название программы и ее авторов из ресурсов. Правда, соответствующие данные присутствуют не во всех exe-файлах.

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

Алгоритмы поиска и индексации

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

Булев поиск опирается на использование инвертированного индекса ключевых слов, т. е. таблицы, в которой для каждого ключевого слова перечисляются все документы, где оно встречается. Главным достоинством этого алгоритма является возможность связывания слов запроса логическими операциями, например, он позволяет осуществить поиск по запросу «кофе или чай» и получить в результате объединение множеств документов, содержащих слова «кофе» и «чай». К недостаткам этого алгоритма следует отнести невозможность определения релевантности запросу полученной выборки документов и, как следствие, невозможность ее сортировки.

В векторной модели поиска каждому документу ставится в соответствие вектор

D_i ={w_i1 ,..., w_in},

где w_ij — вес j-го ключевого слова в i-м документе, обычно вычисляемый по формуле

где a_ij — частота появления j-го ключевого слова в i-м документе; d_j — количество документов, в которых встречается j-е ключевое слово; N — общее количество рассматриваемых документов.

Аналогично для запроса Q вводится одноименный вектор

Q = {q₁ ,..., q_n},

где q_j =1, если j-е ключевое слово присутствует в запросе Q, и q_j = 0, если нет.

Мера схожести документа D_j и запроса Q в этом случае вычисляется как косинус угла между соответствующими векторами:

где (D_i ,Q) — скалярное произведение векторов D_i и Q; ||D_i||, ||Q|| — их нормы.

Вероятностная модель поиска основана на вычислении условной вероятности события, что документ соответствует данному запросу, т. е. величины P(документ D релевантен| запрос Q).

Используя теорему Байеса и тот факт, что вероятность P(запрос Q) постоянна на протяжении всего поиска, получаем: мерой релевантности документа D является величина

P(документ D релевантен) P(запрос Q | документ D релевантен).

В качестве факторов, влияющих на безусловную релевантность документа, можно рассматривать его размер, источник, дату публикации и т. д. Вероятность запроса Q при условии релевантности документа D зависит главным образом от веса ключевых слов запроса в документе D.

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

Таблицы индекса

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

• Таблица документов Documents. В ней хранится информация обо всех документах, проиндексированных системой, а именно название документа, его авторы, тип файла, путь к файлу/URL и т. д. При этом каждому документу необходимо присвоить уникальный идентификатор Doc_id.
• Таблица ключевых слов/словарь Words. Здесь хранятся все ключевые слова системы и соответствующие им номера Word_id.
• Инвертированный индекс Inverse, используемый для поиска. В этой таблице хранится идентификатор слова Word_id и соответствующий ему список документов, содержащих это слово.

При добавлении в индекс очередного документа заносится соответствующая запись в таблицу Documents, после чего необходимо провести обновление таблицы инвертированного индекса. Для этого идентификатор вновь созданного документа добавляется ко всем записям таблицы Inverse, соответствующим ключевым словам нового текста.

Эффективная организация словаря

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

Для выделения базовых словоформ существует ряд алгоритмов. Простейшим из них является метод отсечения всех знакомых системе приставок и суффиксов/окончаний. Из более продвинутых методов стоит упомянуть прием, называемый «квадратом Джозефа Гринберга», который предложил в графическом представлении размещать по двум противоположным сторонам квадрата (или ромба) английские слова, например sleeps и eats, по двум другим противоположным сторонам — слова sleeping и eating. То же можно записать в виде пропорции sleeps:eats = sleeping:eating. Анализ этой конструкции позволяет выделить две базовые словоформы sleep и eat и окончания s и ing.

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

Другим часто используемым алгоритмом выделения базовых словоформ является метод Портера, разработанный специально для поисковых систем и изначально применявшийся для английского языка. Идея алгоритма состоит в создании для каждого используемого языка правил отсечения окончаний (в широком смысле) слов. Каждое из них имеет вид:

(условие) S1->S2, где S1 — окончание слова, которое необходимо удалить, S2 — новое окончание слова. Условия, при которых применяется данное правило, являются логическими функциями следующих событий:
*S — базовая словоформа заканчивается на S (здесь S — любая буква);
*v* — базовая словоформа содержит гласную;
*d — базовая словоформа заканчивается на двойную согласную и т. д.

В качестве примера приведем следующие правила, построенные по этой схеме:

SSES->ES # caresses->caress
IES->I # ponies->poni
(*v*) ED-> # plastered->plaster
(*v*) ING-> # sing->sing

Существуют другие подходы к решению проблемы словаря. Например, создается фиксированный набор слов языка с указанием для каждого слова его базовой словоформы. Существенным недостатком данного метода является большой объем словаря, в котором приходится хранить не только базовые словоформы, а все используемые слова. Однако это позволяет построить более точное соответствие между словами и их базовыми словоформами. Кроме того, появляется возможность ограничить словарь некоторым набором базовых слов, созданным при его инициализации. Во время индексации можно игнорировать неизвестные слова (в случае, если исходный словарь уже велик). Это позволит отсечь большое количество «мусора» — ошибочных и служебных слов, появление которых неизбежно. Наряду с этим могут быть пропущены слова, важные для индексации, преимущественно специальные выражения и термины предметных областей. Чтобы избежать этого, предлагается добавлять новые слова, но без учета образования от них словоформ. Такой подход дает особенно хорошие результаты при добавлении в словарь аббревиатур, не требующих образования от них дополнительных словоформ.

Еще одна проблема индексирования связана с выявлением и удалением из текста так называемых стоп-слов. Они не несут смысловой нагрузки в текущей предметной области, и для эффективной работы системы их следует удалять при индексировании. Как правило, стоп-словами являются предлоги, союзы, артикли, вводные слова и т. п. Они очень часто встречаются в документах, но малоинформативны. Для их удаления можно либо использовать отдельный словарь стоп-слов, либо считать все слова с высокими частотами встречаемости в базе данных текстов стоп-словами и удалять их при индексировании.

Интерфейс поисковой системы

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

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

Отдельного внимания в данном случае требует объем информации, выводимой поисковой системой по запросу. Большинство поисковых Интернет-систем ограничивается следующим.

• Заголовок документа.
• Тип документа. В случае, если поисковая система поддерживает несколько типов документов (html, doc, pdf, ps и т. д.), информация о типе каждого из них может оказаться полезной для пользователя. Система Google выводит тип документа (если документ не является html-страницей) перед его названием в квадратных скобках.
• Выдержки из текста документа. Обычно приводятся предложения или части предложений документа, содержащие ключевые слова запроса. Сами ключевые слова при этом выделяются жирным начертанием. Выдержки из текста документа оказываются крайне полезными для определения контекста, в котором встретились ключевые слова, и позволяют, как правило, сразу отсечь значительное количество ненужных и ошибочных документов.
• Помимо приведения вышеперечисленной стандартной информации, поисковые Интернет-системы предоставляют разнообразные дополнительные возможности, облегчающие нахождение нужных документов. Большинство из них, например, имеют функцию "Похожие документы", позволяющую произвести поиск в базе данных на предмет нахождения документов, имеющих максимальное сходство с данным.

Смежные вопросы обработки текстов

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

• рубрикация текстов (text categorization);
• кластеризация текстов (text clustering);
• автоматическое аннотирование текстов (text summarizing);

Задача рубрикации текстов состоит в определении принадлежности входного текста одной из имеющихся рубрик. Ее решение основано также на механизме ключевых слов и в самом простом случае сводится к вычислению меры близости между вектором признаков документа и некоторым средним вектором, представляющим категорию текстов. Текущий текст считается принадлежащим той категории, для которой эта мера минимальна. Задача рубрикации имеет много важных и востребованных в современном мире приложений. Одним из них является механизм фильтрации сообщений электронной почты от спама. При этом все почтовые сообщения разбиваются на две рубрики: «спам» и «нужные сообщения». После соответствующего обучения системы становится возможной автоматическая фильтрация.

Кластеризация текстов также имеет большое число приложений. Задача кластеризации состоит в автоматическом разбиении массива текстов на категории. От рубрикации ее отличает то, что категории заранее не определены; известно лишь их число. Для решения задачи кластеризации документов обычно используются традиционные алгоритмы кластеризации, такие как алгоритм k средних, EM-алгоритм для моделей гауссовых смесей (GMM), иерархическая кластеризация и т. д. С помощью кластеризации может быть повышена точность работы поисковых систем (при этом используется принцип, согласно которому документы, близкие по содержанию, обычно релевантны одним и тем же запросам), а также облегчен просмотр больших объемов документов и работа с ними.

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