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

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

Релевантность можно представить также как меру близости между реально полученными документами и тем, что следовало бы получить из системы. Возникают две взаимосвязанные задачи: представление информации в системе и её поиск в соответствии с информационными потребностями пользователя. Рассмотрим как решаются эти задачи в современных ИПС.

Подавляющие большинство поисковых алгоритмов основано на так называемой "Векторной модели текста", предложенной Дж. Солтоном (Salton G.) в 1975 году [18]. Работа Солтона представляет собой теоретическую основу современных ИПС в их классической реализации.

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

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

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

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

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

, где	(2.8)
tj – термин,
li – документ.

При таком рассмотрении можно сформулировать процедуру обращения к информационной системе следующим образом:

L x q = r, где	(2.9)
q – вектор запроса,
r – вектор отклика системы на запрос.

Это традиционное определение процедуры поиска документов в ИПС, которое используется Солтоном с 1977 года. Оно было введено для решения проблемы автоматического индексирования документов, но оказалось чрезвычайно полезным и для описания процедуры поиска.

Существуют и другие определения процедуры обращения пользователя к системе, но для описания работы распределенных ИПС Интернета больше подходит определение Солтона – в подавляющем большинстве этих систем применяются информационно-поисковые языки типа "Like This". Данный подход хорошо известен как вычисление мер близости "документ-запрос".

Начало применению запросов типа "Like This" положила система WAIS. Именно в ней был впервые сформулирован отказ от использования традиционных информационно-поисковых языков булевого типа, и было заявлено о переносе центра тяжести информационного поиска на языки, основанные на вычислении меры близости "документ-запрос". Основная причина такого подхода - желание снять с пользователей заботу по формулированию запросов на информационно- поисковых языках и дать им возможность использовать обычный естественный язык. Ради справедливости следует отметить, что от запросов на естественном языке практически сразу отказались. Система просто проводила нормализацию лексики и удаляла из списка терминов запроса общие и стоп-слова. Тем самым практически один в один выполнялись условия линейной модели индексирования и поиска. После этой процедуры система вычисляла меру близости по выражению и в соответствии с полученными значениями ранжировала информационный массив. Практически все ИПС Интернета устроены по этому принципу.

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

(2.10)

(2.11)

(2.12)

(2.13)

где

Ri,q – мера близости документа i и запроса q,

М – число терминов запроса,

N – число документов в индексе,

Pi – i-ый документ индекса,

Lii,k – {1, если из документа k есть ссылка на документ i; 0, иначе},

Loi,k – {1, если из документа i есть ссылка на документ k; 0, иначе},

Ci,j – {1, если документ i содержит термин j; 0, иначе}. [21]

Наиболее популярными из них являются:

• расширенный двоичный алгоритм поиска;
• алгоритм наибольшего цитирования;
• TFxIDF алгоритм (предложен и уточнён Солтоном в 1979 году);
• расширенный векторный алгоритм поиска.

Следует отметить, что наиболее эффективным из этих алгоритмов является TFxIDF, который и используется в большинстве ИПС (RBSE, WAIS, WebCrawler, Lycos, OpenText, Lycos и Altavista).

Одним из компонентов меры близости TFxIDF является частота встречаемости терминов в массиве документов.

Обычно плотность функции распределения частоты встречаемости терминов описывают гиперболическим распределением, известным как закон Зипфа (см. п. 2.2).

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

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

С точки зрения экспериментальных результатов можно сделать два вывода:

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

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

Но и Lycos, и OpenText, и Altavista, и другие системы Интернета применяют линейную модель индексирования и поиска, используя различительную силу термина в алгоритмах автоматического индексирования и поиска. Следовательно, применяемые алгоритмы ограничивают словарь, допуская его незначительный рост.

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

В итоге выполняется второе предположение из приведенного списка. Следовательно, использование различительной силы терминов в качестве веса терминов позволяет выбирать термины из окрестности максимума частотного распределения. [22, 23]