Все новое – это хорошо забытое старое.

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

Развитие индексирования в документных системах происходило от ручного заполнения списка ключевых слов в системах первого поколения до автоматического полнотекстового индексирования сегодня, подразумевающего сохранение всех слов текста. Несмотря на большой пройденный путь говорить о полном решении проблемы, наверное, пока рано. Безусловно, удалось решить вопрос автоматического ввода документов в систему, но оставшиеся весьма омрачают картину. Число получаемых при поиске нерелевантных документов подчас достигает 90%, а размер индекса составляет в среднем не менее 40-60% объема документа. С учетом быстрого роста количества электронных документов острота этих проблем усиливается.

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

При бинарном индексировании (контекстно-независимом по классификации [1]) поиск ведется на основе алгоритмов “нечеткого поиска”, т.е. поиска с ошибками. В этом случае допускается неполное (с заданным количеством ошибок в начале, середине и конце слова) совпадение слов с шаблоном. При втором методе индексации (контекстно-зависимом по классификации [1]) слова преобразуются в словоформы с отсечением суффиксов и окончаний, что позволяет искать склонения и спряжения шаблонов.

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

Заметим, что, несмотря на несомненные плюсы, полнотекстовое индексирование в любом своем виде имеет и ряд существенных минусов:

Эти недостатки обусловлены самой концепцией такого индексирования – сохранением всего текста за исключением “стоп-слов”, под которыми подразумеваются предлоги, союзы, местоимения и т.п. Действительно, с одной стороны наличие в индексе всех слов текста гарантирует его нахождение по любому из них, но с другой стороны встает вопрос: “А насколько это корректно?”. Предположим, мы имеем текст о компьютерных технологиях, в котором приведена пословица: “За двумя зайцами погонишься, ни одного не поймаешь”. При проведении поиска по слову “заяц” система выдаст этот документ, хотя он не будет иметь ни малейшего отношения к фауне. Безусловно, можно найти и сотни менее экзотичных примеров таких ситуаций. Наглядно иллюстрируют это приведенные чуть выше слова данного текста “предлог”, “союз” и “местоимение”.

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

С учетом вышесказанного в условную схему вариантов индексирования документа на рис. 1. включено “ключевое” индексирование, на предлагаемой концепции которого мы и остановимся в дальнейшем.

Итак, что же такое “ключевые” слова? С точки зрения человека, кажется, здесь все достаточно просто. Это слова определяющие содержание документа, характеризующие его смысл. Но вот проблема, одни и те же слова в разном контексте могут быть, а могут и не быть “ключевыми”. Как это объяснишь машине? Да и документ – документу рознь. Например, в договорах главное – кто, кому, как, когда, сколько и за что, а в тематических статьях по большому счету – только о чем. К тому же, определение “ключевых” слов человеком – процесс, в общем-то, весьма субъективный, т.е. зависящий от эксперта их выделяющего, что крайне плохо для дальнейшего осуществления поиска. Ясно, что при такой общей постановке вопроса алгоритмизация задачи весьма трудна. Попробуем найти объективное определение “ключевых” слов пригодное для машины, которое бы позволило уйти от недостатков полнотекстового индексирования.

Для начала разделим все многообразие документов на виды с точки зрения их организации:

Первый вид с точки зрения индексации и поиска самый приятный. В нем “ключевые” слова известны заранее – поля данных. Это хорошо структурированные документы, с обработкой которых нет проблем, поэтому данная группа документов в дальнейшем рассматриваться не будет.

Неструктурированные документы попробуем разделить на подвиды с точки зрения возможности выделения “ключевых” слов. В качестве предпосылки будем исходить из того, что метод определения характерных слов документа должен бы зависеть от типа его содержания, т.е. того, что в этом документе важно для возможности его контекстного поиска. На слово “контекстного” хотелось бы обратить особое внимание, т.к. речь идет именно о поиске по содержанию. Таким образом, разделим все неструктурированные документы на следующие группы (подвиды):

Рассмотрим данные подвиды документов по очереди.

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

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

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

Для начала была проделана следующая работа: входной документ преобразовывался в поток слов, из которых выделялись словоформы путем отсечения окончаний и суффиксов, далее словоформы группировались. В результате для документа получался список содержащихся в нем словоформ с количеством повторений оных – коэффициентом значимости словоформы (КЗСФ). Данный список сортировался по убыванию коэффициента КЗСФ. Результаты данной работы представлены на графике (рис. 2).

Обозначения:

Числовые соотношения:

Теперь можно обратиться и к смыслу полученных результатов. Дело в том, что анализ документов и соответствующих им упорядоченных по убыванию КЗСФ списков словоформ показал:

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

Слова со словоформами из зоны C2-C3 можно относить к “псевдоключевым” только для очень небольших документов (порядка 1-2 страниц). Для больших документов их становится целесообразно игнорировать. Вообще, здесь необходимо провести более детальную проработку зависимости точки игнорирования от числа словоформ документа, т.к. имеющейся пока статистики для этого не достаточно, но в качестве весьма неплохого приближения можно рассматривать отношение суммы КЗСФ всех словоформ списка к числу словоформ в списке, т.е. среднего арифметического. Все слова со словоформами левее точки игнорирования можно заносить в “ключевые” для данного документа.

Слова из начала списка, накопительной суммой своих КЗСФ покрывающие примерно 5-10% от суммы КЗСФ всех слов списка, позволяют однозначно классифицировать документ по теме в случае, если каждой теме будет сопоставлен список характерных слов. Причем данную операцию можно автоматизировать путем самообучения системы на 10-30 документах одной темы предложенных ей человеком. В этом случае 5-10% барьер в совокупном списке означает границу названия темы.

На базе полученных результатов можно предложить следующую технологию индексирования на основе выделения “ключевых” слов:

Преобразование документа в поток слов.

Преобразование слов в словоформы.

Создание списка словоформ документа упорядоченного по КЗСФ.

Удаление из списка словоформ от стоп-слов.

Выбор точки игнорирования по КЗСФ (ТИкзсф) в зависимости от Cmax.

Занесение в индекс словоформ расположенных левее ТИкзсф.

Таким образом, предложенный выше подход позволяет сократить объем индекса по крайней в два-четыре раза в зависимости от выбора точки игнорирования для КЗСФ без потери качества поиска по сравнению с полнотекстовым индексированием. Более того, число выдаваемых системой найденных нерелевантных документов значительно сократится за счет очистки индекса от мусора, а время поиска сократится за счет уменьшения индекса.

Марков А. Концепция построения электронного архива.// Открытые системы. – 1997.- №1