Математическое моделирование. 
Автоматизация документооборота

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

Наряду с организацией хранения документов, их необходимо также быстро и эффективно искать. Со скоростью поиска все относительно понятно — чем быстрее вы найдете необходимые документы, тем лучше. А вот с эффективностью поиска документа ситуация не так проста. Что считать эффективным поиском? Для того чтобы понять это, рассмотрим модели поиска. Здесь существует два подхода.

Первый состоит в том, что в процессе поиска вы ищете документ, который точно существует в системе, и ваша задача — свести процесс к его нахождению. Этот метод применяется в 90% всех случаев. Второй подход состоит в том, что вы ищете все документы, которые могут относиться к интересующему вас вопросу.

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

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

К атрибутам документа можно отнести имя документа, время создания, автора, машинистку, имя подразделения, тип документа (факс, письмо, контракт, спецификация).

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

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

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

Зависимость от языка выражается в следующих факторах…

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

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

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

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

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

• — бинарное индексирование — не зависит от языка документа по причине бинарной или словарной индексации;
• — морфологическое индексирование — производится с учетом морфологии и семантики языка.

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

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

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

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

Ниже приведен разработанный алгоритм процесса индексирования документа…

Присвоение документу уникального идентификатора, внесение в файл идентификаторов:

• — Определение формата документа;
• — Определение кодировки документа;
• — Перевод текста в «плоский» формат;
• — Определение единицы поиска;
• — Выделение отдельных слов;
• — Выделение отдельных предложений;
• — Исключение из запроса шумовых слов;
• — Составление (пополнение) индекса определенного формата (рис. 4).

Рис. 4. — Формат индекса:

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

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

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

Под словарем понимают упорядоченное множество терминов, мощность которого обозначают как D.

Документ — это двоичный вектор размерности D. Если термин входит в документ, то в соответствующем разряде этого двоичного вектора проставляется 1, в противном же случае — 0. Обычно все операции в линейной модели индексирования и поиска документов выполняются над поисковыми образами документов, но при этом их как правило называют просто документами.

Информационный поток или массив L представляют в виде матрицы размерности NxD, где в качестве строк выступают поисковые образы N документов. При таком рассмотрении можно сформулировать процедуру обращения к информационной системе следующим образом:

L x q = r (1).

Где:

q — вектор запроса;

r — отклик системы на запрос.

Это традиционное определение процедуры поиска документов в информационно-поисковой системе, которое ввел Солтон в 1977 году. Оно было введено для решения проблемы автоматического индексирования документов, но оказалось чрезвычайно полезным и для описания процедуры поиска. Существуют и другие определения процедуры обращения пользователя к системе, но для описания работы распределенных информационно-поисковых систем в интернете больше подходит определение Солтона — в подавляющем большинстве этих систем применяются информационно-поисковые языки типа «Like This». Данный подход хорошо известен как вычисление мер близости «документ-запрос» .

В современных распределенных информационно-поисковых системах Internet реально используются только 6 мер близости. При этом наиболее часто в качестве меры близости рассматривают определение Солтона, например, системы RBSE и WAIS, и его же улучшенную меру близости — системы WebCrawler и Lycos.

Начало применению запросов типа «Like This» положила система WAIS. Именно в ней был впервые сформулирован отказ от использования традиционных информационно-поисковых языков булевого типа и было заявлено о переносе центра тяжести информационного поиска на языки, основанные на вычислении меры близости «документ-запрос». Основная причина такого подхода — желание снять с пользователей заботу по формулированию запросов на информационно-поисковых языках и дать им возможность использовать обычный естественный язык.

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

Коррекция запросов по релевантности.

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

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

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

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

LT x r0 = q1 (2).

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

LT x Fk-1 x rk-1 = qk (3).

L x qk = rk.

Как видно из (3) матрицы Fk-1 составляют систему фильтров пользователя, при помощи которых он корректирует свой запрос. Эти фильтры имеют в реальных системах конкретную интерпретацию. Так в WAIS и Lycos пользователь просто помечает релевантные документы. В этом случае фильтры превращаются в диагональные матрицы, которые в релевантных документах имеют главную диагональ с единицами, а в нерелевантных — нули. Но, в общем случае, на диагонали можно размещать и веса релевантности. Эти фильтры могут быть и недиагональными.

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

F0 = F1 = F2 =… = Fk — 1 = Fk = F (4).

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

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

• (L x LT x F) x rk-1 = rk (5)
• (A x F) x r = lr: rk = lrk-1

Из (5) следует, что процесс коррекции запросов по релевантности должен сходиться к собственному вектору матрицы:

L x LT x F.

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

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

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

Приведенная трактовка процедуры коррекции запроса и профиля информационной системы имеет аналоги в других методах анализа информационных потоков.

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