Пример информационного поиска

В библиотеках многих людей есть толстый том собрания произведений Шекспира Допустим, вы хотите определить, в какой пьесе используются слова Brutus AND Caesar AND NOT Calpumia. Для этого можно, например, прочитать текст от начала до конца, отмечая пьесы, содержащие слова Brutus и Caesar, и исключая из рассмотрения пьесы, в которых встречается слово Calpumia. Простейший компьютерный метод решения этой задачи сводится к последовательному просмотру (linear scanning) всех документов. Этот процесс часто называют прямым поиском или, на английском, grepping (от названия ко­манды grep, которая в операционной системе Unix выполняет этот процесс). Прямой по­иск по тексту может быть очень эффективным, особенно на современных компьютерах. Довольно часто такая обработка допускает поиск по шаблону с джокерами (wildcard pattern matching). На современных компьютерах выполнения простых запросов на коллек­циях данных среднего размера (общий объем тома собрания избранных произведений Шекспира составляет чуть меньше одного миллиона слов) вполне достаточно для рядо­вого пользователя.

Тем не менее во многих случаях необходимо нечто большее.

1. Иногда нужно быстро обработать большую коллекцию документов. Объем дан­ных, доступных онлайн, растет по меньшей мере с той же скоростью, с которой увеличивается скорость работы компьютеров. Теперь мы хотели бы выполнять поиск информации в массивах данных, содержащих миллиарды и триллионы слов.
2. Иногда требуется большая гибкость при выполнении операции сравнения. Например, было бы непрактично выполнять запрос Romans NEAR countrymen с помощью команды grep, где слово NEAR может означать "не далее 5 слов" или "в пределах одного предложения".
3. Иногда необходимо выполнить ранжированный поиск. Во многих ситуациях нам нужен не просто ответ, а наилучший ответ на запрос относительно документов, содержащих определенное слово.

Для того чтобы избежать последовательного просмотра текстов при выполнении ка­ждого запроса, заранее составляется индекс документов. Вернемся к тому Шекспира и опишем на его примере основы модели булева поиска. Допустим, что для каждого доку­мента (в данном примере - для каждой пьесы Шекспира) мы создали запись, в которой указано, содержит ли он конкретное слово из лексикона Шекспира (состоящего из 32 тысяч слов). В результате возникнет бинарная матрица инцидентности "термин- документ" (term-document incidence matrix), представленная на рис. 1.1. Термины (terms) — это единицы индексирования (это понятие обсуждается в разделе 2.2). Как правило, это обычные слова, но в литературе по информационному поиску употребляет­ся название термин, поскольку некоторые выражения могут быть непохожими на "обычные слова", например 1—9 или Hong Kong. Теперь в зависимости от порядка про­смотра матрицы (по строкам или по столбцам) мы можем получить либо вектор термина, в котором указано, в каких документах он встречается, либо вектор документа, в кото­ром указано, какие термины в нем употребляются.

Для обработки запроса Brutus AND Caesar AND NOT Calpurnia мы берем вектор для терминов Brutus, Caesar и Calpumia, вычисляем двоичное дополнение к последне­му вектору и выполняем поразрядную операцию AND

110100 AND 110111 AND 101111 =100100

Ответ на запрос выглядит так: Antony and Cleopatra и Hamlet (рис. 1.2).

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

Рассмотрим теперь более реалистичный сценарий, на примере которого удобно вве­сти несколько понятий и обозначений. Допустим, что в нашем распоряжении есть N = 1 миллион документов. Под документами (documents) подразумеваются любые объек­ты, на основе которых решено строить систему информационного поиска. Документами могут быть личные заметки или главы книги. Группу документов, по которой осуществляется поиск, мы будем называть коллекцией (collection). Ее также иногда называют корпусом (corpus) или массивом текстов (body of texts). Допустим, что каждый документ состоит примерно из 1 000 слов (2-3 книжные страницы). Если пред­положить, что в среднем на хранение слова с учетом пробелов и знаков препинания от­водится 6 байт, то такая коллекция документов займет около 6 Гбайт (GB). Как правило, в подобных документах может оказаться около М = 500 ООО разных терминов. В выбран­ных числах нет ничего особенного, и они могут варьироваться в ту или другую сторону, но они все же дают представление о размерности рассматриваемых задач.

находится в документе, а также (довольно часто) о координате термина в чтом документе, называ­ется словопозицией (posting). Соответствующий список называется списком словопозиций (postings list) или инвертированным списком. Словарь, представленный на рис. 1.3, упорядочен в алфавитном порядке, а каждый список словопозиций упорядочен по иден­тификаторам документов.

Наша цель — разработать систему, выполняющую поиск по произвольному запросу (ad hoc retrieval). Это самая распространенная задача информационного поиска. Цель системы - найти в коллекции документы, которые являются наиболее релевантными по отношению к произвольным информационным потребностям, сообщаемых системе при помощи однократных, инициированных пользователем запросов. Информационная по­требность (information need) — это тема, о которой пользователь хочет знать больше. Ее следует отличать от запроса, т.е. от того, что пользователь вводит в компьютер, пытаясь выразить свою информационную потребность. Документ называется релевантным (relevant), если, с точки зрения пользователя, он содержит ценную информацию, удовле­творяющую его информационную потребность. Приведенный выше пример был доволь­но искусственным, поскольку информационная потребность была сведена к поиску кон­кретных слов, в то время как обычно пользователи интересуются более неопределенны­ми темами, такими как "pipeline leaks" ("утечки из трубопроводов"), и хотят получать документы независимо от того, употребляются в них именно эти слова или идея выража­ется другими словами, например pipeline rupture ("прорыв трубопровода"). Для того чтобы оценить эффективность системы информационного поиска (качество результа­тов ее работы), пользователь обычно желает знать два основных статистических показа­теля, характеризующих результаты, возвращаемые системой.

Точность (precision). Какая доля результатов является релевантной по отношению к информационной потребности?

Полнота (recall). Какая доля релевантных документов из коллекции возвращена сис­темой?

Теперь мы уже не можем создать матрицу "термин-документ" наивным способом. Матрица размером 500 К х 1 М содержит полтриллиона нулей и единиц — слишком много, чтобы поместиться в памяти компьютера. Тем не менее следует подчеркнуть, что эта матрица является чрезвычайно разреженной, т.е. содержит лишь небольшое количе­ство ненулевых элементов. Поскольку каждый документ состоит из 1 ООО слов, матрица будет содержать не более одного миллиарда единиц, поэтому как минимум <59,8% ячеек будут содержать нули. Намного целесообразнее хранить в памяти только единицы.

Эта идея является основной по отношению к первой важной концепции информаци­онного поиска — инвертированному индексу. Это название на самом деле является из­быточным: индекс всегда ставит в соответствие терминам те части документа, в которых они встречаются. Тем не менее выражения инвертированный индекс, и иногда — инвер­тированный файл — стали стандартными в области информационного поиска. Основ­ная идея инвертированного индекса проиллюстрирована на рис. 1.3. Сначала мы записы- ваем в память словарь (dictionary) терминов (иногда его также называют словником (vocabulary) или лексиконом (lexicon); в этой книге мы называем словарем структуру данных, а лексиконом — множество терминов той или иной коллекции). Затем для каж­дого термина мы создаем список, в котором указаны документы, содержащие данный термин. Каждый элемент списка, содержащий информацию о том, что термин