Содержание к диссертации
Введение
1 Введение 4
1.1 Задачи информационного поиска 4
1.2 Оценка качества информационного поиска 6
1.3 Основные вопросы, рассмотренные в данной работе . 9
2 Модели и методы информационного поиска 11
2.1 Описание моделей представления документа 14
2.2 Модель „множество слов" (bag-of-words) 14
2.2.1 Бинарная модель 14
2.2.2 Модель с „весами" слов 20
2.3 Учет взаимного положения слов 24
2.3.1 Формирование многословных терминов 26
2.3.2 Разбиение документа на фрагменты 28
2.4 Гипертекстовые ссылки между документами 32
2.5 Перспективы 38
2.6 Выводы 38
3 Реализация модели документа 39
3.1 Использование пар слов 40
3.1.1 Обоснование выбора 40
3.1.2 Особенности реализации 41
3.2 „Скользящее" по тексту окно 42
3.2.1 Обоснование выбора 42
3.2.2 Реализация информационного поиска с использованием данной модели 43
3.2.3 Выбор и обоснование функции взвешивания документа 43
3.2.4 Использование индексной информации 46
3.3 Выводы
4 Индексные структуры 50
4.1 Организация инвертированного файла 51
4.2 Сжатие инвертированного файла 53
4.2.1 Алгоритмы сжатия инвертированных файлов 54
4.2.2 Сжатие пост-листов редко встречающихся слов . 56
4.2.3 Сжатие инвертированного файла, построенного на базе В+дерева 57
4.3 Эффективность операций с индексными структурами 58
4.3.1 Эффективность поиска 59
4.3.2 Изменение индекса 61
4.4 Индексирование многоверсионных документов 62
4.4.1 Постановка задачи 62
4.4.2 Реализация 63
4.5 Выводы 66
5 Экспериментальная часть 67
5.1 Использование пар 67
5.1.1 Используемые коллекции 67
5.1.2 Описание эксперимента 68
5.1.3 Результаты эксперимента 68
5.2 Использование „скользящего окна" 70
5.2.1 Данные для эксперимента 71
5.2.2 Результаты 72
5.3 Сжатие инвертированного файла 74
5.3.1 Характеристики коллекций 74
5.3.2 Методика исследования статистики слов и пар слов 75
5.3.3 Размеры словарей 76
5.3.4 Исследование характеристик пост-листов 78
5.3.5 Исследование алгоритма сжатия 81
5.4 Индексирование изменяющихся документов 84
5.4.1 Использованные коллекции 84
5.4.2 Описание эксперимента 84
5.5 Выводы по экспериментальной части 85
Заключение
- Оценка качества информационного поиска
- Модель „множество слов" (bag-of-words)
- Особенности реализации
- Алгоритмы сжатия инвертированных файлов
Введение к работе
В течение последних десятилетий наблюдается постоянно ускоряющийся рост объемов текстовой информации, хранящейся в виде электронных документов. Для эффективной работы с ними требуются современные инструменты, важную роль среди которых играют различные средства информационного поиска. Основная цель информационного поиска -помочь пользователю найти информацию, в которой он заинтересован. Система отбирает из всего имеющегося множества информации подмножество, удовлетворяющее пользователя.
Оценка качества информационного поиска
При сравнении качества информационного поиска необходимо опираться на определенные характеристики исследуемой системы и их изменение [5, 67].
В данной работе мы рассматриваем оценку качества только для классической задачи информационного поиска. В основе всех методов оценки лежит понятие релевантности, то есть соответствия документа запросу. Факт соответствия имеет субъективный характер, так как может быть установлен только человеком. Для получения более объективных характеристик оценку соответствия делают несколько человек и результат усредняется.
Исторически первыми и до сих пор общепринятыми критериями оценки являются полнота (recall) и точность (precision). Полнота определяется как отношение количества выбранных при поиске документов к общему количеству документов, соответствующих запросу. Точность определяется как отношение количества попавших в результат документов, не соответствующих запросу, к общему количеству выбранных документов. RECALL = 1 1 \Щ PRECISION = 51 , где R - множество всех документов, которые релевантны запросу S - множество документов, которые выданы системой на запрос.
Данные характеристики зависят друг от друга. Увеличение точности, как правило, приводит к снижению полноты и наоборот. Система, которая демонстрирует более высокое качество поиска, в идеальном случае, должна показывать более высокие значения для обеих характеристик. Для сравнительного анализа оценивают значение точности для разных значений полноты. В большинстве современных исследований, при оценке качества поиска используют методику, согласно которой точность оценивают при 11 значениях полноты - от 0 до 100% с шагом 10%. По данным точкам строят так называемый 11-точечный график полноты/точности. Чем выше проходит данный график, тем выше качество информационного поиска, который демонстрирует система.
Данные характеристики информационного поиска не являются наилучшими для всех случаев, имеется ряд проблем с их оценкой и тем, насколько хорошо они отражают качество работы системы с точки зрения пользователя. Например, в больших коллекциях для пользователя становится важным не то, что система отобрала все документы по запросу (часто этот массив физически невозможно просмотреть) а то насколько полно освещают интересующий его вопрос первые документы в полученном списке. Однако точность и полнота - это стандартные характеристики, которые приводятся практически во всех исследованиях информационного поиска, поэтому они используются и в данной работе.
Помимо выбора характеристик оценки поиска, можно выделить еще ряд проблем, которые усложняют объективное сравнение влияния различных моделей и методов информационного поиска на его качество: влияние тестового набора данных. Оценка получается в результате эксперимента на некотором наборе документов и запросов. Результаты, полученные для этих данных, не обязательно повторятся на других. Кроме этого, различные наборы содержат разные представления документа, тем самым предопределяя выбор возможных методов реализации информационного поиска. Для решения этой проблемы используются стандартные наборы данных, так называемые коллекции. Сейчас существует ряд стандартных наборов данных (TREC, LREC, РОМИП), которые позволяют проводить более объективное сравнение для некоторых видов информационного поиска, но они, конечно, не представляют всего возможного разнообразия документов и запросов; различия в реализации компонентов системы информационного поиска. Любая система реализует достаточно сложный алгоритм, часто многошаговый, содержащий множество параметров. Поэтому, если мы имеем две системы, использующие два метода, мы не можем напрямую сравнивать их результаты, ведь другие особенности реализации и выбор алгоритма также могут оказывать влияние. Идеальным был бы эксперимент, когда в одной и той же системе при неизменных других параметрах обработки менялось только представление документа и методика его использования, но таких данных зачастую нет;
высокая вычислительная стоимость. Некоторые алгоритмы информационного поиска могут требовать значительных вычислительных ресурсов или объемов занимаемой памяти. В результате при современном уровне развития техники, их невозможно применять на практике либо они применимы только на небольших коллекциях, что не позволяет объективно оценить их влияние на качество для больших наборов данных.
Сравнивая результаты применения различных методов, описанные в литературе, мы сталкиваемся с описанными выше проблемами. Различные исследователи используют разные коллекции и сопутствующие методики. Поэтому объективное сравнение, основанное на точных количественных характеристиках, невозможно сделать на основании этих данных. Возможно только качественное сравнение, основанное на полученных при данных исследованиях результатах.
Еще более сложным является анализ методов, применяемых в коммерческих системах, в силу неполной информации об используемых алгоритмах и отсутствия достоверных данных о количественных показателях качества поиска. Поэтому, в данном случае, мы можем говорить только о том, что информация о применении той или иной модели означает, что с точки зрения разработчиков она улучшила качество поиска и ее реализация достаточно технологична, чтобы быть примененной в коммерческом решении.
Модель „множество слов" (bag-of-words)
Основной гипотезой информационного поиска является то, что релевантный документ содержит те же термины, что и запрос [20].
Под термином обычно понимают отдельное слово естественного языка, на котором создан документ. Все известные современные языки, используемые человеком, основываются на слове как минимальной единице, которая имеет самостоятельное значение. Информационная система должна выделить слова из хранящегося в ней представления документа.
Проблемы выделения слов.
Особенности алфавитов и языков. Данная задача достаточно тривиальна для большинства языков, письменность которых основана на латинском алфавите, кириллице и им подобных. Все множество символов разбивается на два множества: символы, которые могут входить в слово (буквы и цифры) и символы-разделители (пробелы, знаки препинания). Подпрограмма выделения слов просто сканирует текст, выбирая последовательности символов, ограниченных символами-разделителями.
Однако такой алгоритм имеет ряд погрешностей при работе с естественными текстами. Такие особенности написания, как переносы слов, написание слов через дефис, аббревиатуры, пишущиеся через точки, номера, даты и числа, содержащие кроме цифр различные символы препинания и т.д. В системах информационного поиска для обработки таких ситуаций применяется усложнение описанного алгоритма, когда в качестве слова формируется множество возможных вариантов, как соединенных символами-разделителями, так и слова целиком. Так, например, встретив в тексте последовательность ,Д10-1551 алгоритм формирует следующие слова - ,Д10-1551", ,Д10" и „1551". Такое формирование слов особенно полезно для выполнения поиска в некоторых видах документов, таких как поиск цифровая информация и цены [17]. Большинство современных коммерческих систем формируют слова подобным образом. Такой алгоритм реализован в модуле выделения слов поисковой системы Microsoft Index Server. Поисковая система Google пошла в этом направлении несколько дальше, выделяя с помощью шаблонов некоторые типовые буквенно-цифровые последовательности, такие как номера телефонов или кредитных карт.
Многие современные языки, например, китайский и японский, имеют значительно более сложную систему выделения слов из письменного текста. В этих языках при написании не существует определенного разделения между словами. Слово обозначается одним или несколькими символами - иероглифами, например, для китайского языка средняя длина слова составляет 3 иероглифа [33]. В информационных системах, обрабатывающих эти языки, применяется более сложный подход [46], когда применяется ряд алгоритмов, которые формируют возможные слова-кандидаты, анализируя несколько предыдущих иероглифов. В простейшем случае, просто формируются все возможные получаемые из текста последовательности из 3 иероглифов [25].
Кодировки текстов. Другой проблемой при выделении слов является наличие большого количества ", различных кодировок. Одним и тем же печатным символам в электронном представлении соответствуют различные коды. В настоящее время существует набор стандартов кодирования Unicode [9], однако имеется большое количество унаследованных и специальных кодировок. Зачастую перед информационной системой стоит задача определения кодировки по тексту документа, когда эту информацию нельзя получить из других источников. Эта задача особенно важна для поисковых машин по русскоязычной области интернета, где русские тексты могут быть представлены в одной из 5-ти широко распространенных кодировок -DOS, Mac, Koi8-r,Win-1251, Unicode. При этом применяются следующие алгоритмы автоматического определения кодировки:
1 статистический. Кодировка определяется по статистике распределения букв или сочетаний букв. Данный подход даег очень хорошие результаты на длинных текстах, но може г плохо работать на коротких сообщениях [53, 4];
2 словарный. Так как во всех кодировках символы-разделители кодируются одинаково, то можно выделить слова-кандидаты и сравнить их с известными в разных кодировках. Данный подход требует наличия большого словаря слов.
Различные форматы представления документов. Большинство документов готовятся не столько с целью последующего поиска, но чаще для печати или интерактивного представления пользователям. При этом используются разнообразные компьютерные системы подготовки документов. Это создает дополнительные трудности при выделении слов. Их можно разделить на 3 группы, связанные с особенностями используемого представления документа:
1 устаревшие и закрытые коммерческие форматы. Многие офисные документы готовятся в таких системах, как MS Word и хранятся в собственном формате этих систем, который недостаточно документирован и является собственностью фирмы-разработчика. Другие документы могут быть подготовлены в устаревших на настоящий момент текстовых процессорах, таких как Lexicon, WordStar и других, описание форматов которых полностью не доступно. Разработчики при этом используют упрощенные методы анализа, которые могут неправильно интерпретировать отдельные элементы структуры документа. Таким образом, основной проблемой данных форматов является отсутствие достаточной информации о них;
2 форматы, ориентированные на графическое представление документа. Ряд таких распространенных форматов как PostScript, PDF (Portable Document Format) [16] и ряд форматов систем верстки для печати представляют текст как набор графических областей. При этом возникает проблема определения взаимного положения символов для алгоритма выделения слов. Практически перед работой стандартного выделения слов модулю поисковой системы приходится выполнять моделирование отображения документа, определяя взаимное положение букв. При определении последовательности букв и наличия между ними разделителей приходится применять ряд эвристик, которые могут вносить искажения;
Особенности реализации
При первой реализации этой модели предполагалось, что при поиске будут учитываться все пары слов, которые можно выделить из запроса. Однако первые же эксперименты показали (см. 5.1), что в этом случае качество поиска очень сильно ухудшается, вплоть до отсутствия релевантных документов в результатах большинства запросов. Было сделано предположение, что ограничение числа обрабатываемых пар должно улучшить качество, увеличив точность без уменьшения полноты. Для этого был добавлен алгоритм выделения „настоящих" словосочетаний. Данный алгоритм основывается на идее, что, если данная пара слов является устойчивым словосочетанием, то в большом количестве документов, которые содержат оба слова, должна встречаться и данная пара. Следовательно, если это устойчивое словосочетание, то вероятность того, что документ, содержащий оба этих слова, содержит и пару, выше, чем в случае, если совместное появление данных слов случайно. Использовался следующий алгоритм: 1 для каждой пары получается список документов, которые содержат эту пару Spair. Для каждого входящего в пару слова также формируются списки вхождения 5ші И SW2] 2 формируется пересечение списков документов, содержащих пару, и списков для слов - Sc = Swi П 5 ,2 П SW2\ 3 если Размер \Spair\ К \SC\, то данная пара считается словосочетанием и оставляется, иначе отбрасывается. Параметр К определяется экспериментально.
Данный алгоритм отбора пар, как показали эксперименты, заметно улучшил качество поиска. Также возросла скорость обработки запросов с большим количеством слов, так как уменьшилось количество обрабатываемых пар. Общий алгоритм обработки запроса системой выглядел следующим образом:
1 из запроса выделяются все возможные пары слов. То есть при обработке запроса не учитывалось расстояние между словами, а формировался полный набор сочетаний по два слова из слов запроса; из сформированного массива пар с помощью описанного выше алгоритма отбираются „настоящие" словосочетания, которые добавляются к массиву слов запроса в виде отдельных терминов.
3 осуществляется поиск и взвешивание документов. Алгоритм поиска является вариантом классического TF IDF [61]. Пары слов учитывались при обработке запроса точно так же, как и отдельные термины;
4 результаты поиска выводились в виде списка документов, упорядоченных по убыванию веса.
Эффективность модели с парами слов была проверена экспериментально, описание результатов приведено в главе 5.
Данный подход является вариантом использования модели документа, при которой он разбивается на фрагменты (см. 2.3.2). Практически в системе документ представляется как массив терминов, упорядоченных по своим позициям в тексте. Информация о позициях слов используется для вычисления функции оценки веса документа, который используется для сортировки документов в выдаче системы. При описываемом подходе функция вычисляется с помощью „скользящего окна", то есть учитывается группа слов, встречающихся подряд в некотором фрагменте документа (окне). „Скользящим окном" оно названо потому, что последовательно берутся перекрывающиеся фрагменты документа, полученные выборкой со сдвигом на одно слово.
По сравнению с рассмотренной моделью, основанной на парах слов, а также другими моделями, основанными на разбиении документа, интуитивно этот подход предпочтительнее, поскольку:
1 он не накладывает столь жестких ограничений, как пары слов, на близкое положение слов в документе, что должно сделать систему более устойчивой к ситуации, когда термины запроса не появляются в тексте на малом расстоянии; подходы, использующие статическое разбиение документа на фрагменты, часто оказываются зависимыми от выбора разбиения документа. Использование скользящего окна не имеет этого недостатка;
3 можно легко комбинировать этот метод с алгоритмами, не учитывающими взаимное положение слов;
4 данный подход может быть достаточно эффективно реализован с использованием инвертированного файла хранящего положения слов в документе.
Мы использовали следующую реализацию поиска с использованием данной модели: 1 производился отбор документов, которые содержат термины запроса; 2 отобранные документы обрабатывались с помощью функции взвешивания. При вычислении веса использовалась функция от „скользящего окна". Выбор функции взвешивания описан в следующем разделе; 3 документы, отсортированные в порядке убывания значения функции взвешивания, выводились пользователю.
Подобная реализация, как показал практический опыт, относительно легко может быть разработана на базе существующей системы, использующей модель „множество терминов" и, как показали эксперименты, продемонстрировала неплохие результаты поиска.
В данной модели важную роль играет выбор функции взвешивания. В связи с невозможностью формального обоснования, выбор основывался на ряде предположений: данная функция должна возрастать с увеличением веса отдельных фрагментов документа;
2 предполагается, что введение учета взаимного положения слов должно улучшить качество поиска по сравнению с использованием отдельных терминов. Поэтому данная функция выбирается как комбинация функции взвешивания для отдельных терминов и для „скользящего окна";
3 выбранная зависимость должна достаточно просто вычисляться и позволять контролировать влияние учитываемых параметров.
Алгоритмы сжатия инвертированных файлов
Неиараметрические коды с переменным числом бит не требуют при кодировании и декодировании никаких дополнительных параметров. При гамма-кодировании Элиса число X представляется как 1+Lbg J нулевых битов, вслед за которым идет 1 ненулевой бит, далее само число без старшего бита. Например, число 1 представляется одним единичным битом, а число 7 последовательностью 00111. Это кодирование обеспечивает более компактное кодирование чисел по сравнению с байт-ориентированным кодированием для чисел меньших 16, таким образом, его имеет смысл применять для очень маленьких чисел.
Дельта-кодирование Элиса представляет число X, в котором 1 + [log-Xj кодируется с помощью гамма-кодирования, вслед за чем записывается само число без старшего бита. Так, число 1 представляется опять 1, а число 7 последовательностью 01111. Дельта-кодирование обеспечивает более эффективное представление больших чисел. Можно показать, что оно требует меньше бит, чем гамма кодирования для всех чисел, больших 64. Оно так же более компактно по сравнению с байтовым кодированием для всех чисел, меньших 15 и имеет диапазоны, где оно компактнее при других значениях целых чисел.
Недостатком этих алгоритмов сжатия является отсутствие параметров, которые позволили бы адаптировать их для конкретных характеристик сжимаемой последовательности. Например, пост-лист для часто встречающегося слова содержит в среднем меньшие значение кодируемой дельты, чем для редкого. Соответственно, такая кодируемая последовательность имеет меньшее среднее значение кодируемого числа и дисперсию. Схемой кодирования, которая имеет такой параметр, является кодирование Голомба. При таком кодировании число X, закодированное с параметром к представляется опять же из двух частей: первой частью является частное q = [{X — l)/k\ + 1, которое сохраняется в виде последовательности нулевых бит, вслед за которым идет единичный бит. Вторая часть - бинарное представление остатка г = X — (q к) — 1. Подбирая параметр к, можно получать более компактное кодирование чисел в различных диапазонах. Можно показать, что минимальное число бит при кодировании случайной последовательности чисел при равномерном их распределении достигается при к = 0.69теап(Х), где теап(Х) - медиана кодируемой последовательности.
Описанные битовые коды достаточно требовательны к быстродействию компьютера. Современные компьютеры в силу своей архитектуры значительно быстрее обрабатывают данные, выровненные по границам байта. Ряд проведенных исследований [52] показал, что несмотря на то, что байтовое кодирование дает незначительное увеличение требуемого дискового пространства, оно при этом значительно выигрывает по скорости обработки. Эксперименты но исследованию сжатия пост-листов некоторыми алгоритмами приведены в главе 5 данной работы.
По нашему мнению, общим недостатком всех описанных схем сжатия является то, что они предполагают, что идентификаторы расположены достаточно „кучно", то есть разность идентификаторов значительно меньше их значений. Это соответствует истине в случае с часто встречающимися словами, однако 80% слов коллекции как правило составляют редко встречающиеся. Для таких слов пост-листов сжатие описанными алгоритмами дает неудовлетворительный результат.
Для улучшения коэффициента сжатия коротких пост-листов нами было предложено объединять в один лист списки вхождения для нескольких слов. При этом обеспечивалось значительное увеличение коэффициента сжатия при незначительном увеличении времени поиска. Предложенный алгоритм сжатия пост-листов можно представить следующим образом:
1. длинные пост-листы сжимались традиционными способами, например, с применением кодирования переменным числом байт;
2. короткие пост-листы объединялись в „корзины", по несколько посг листов в каждом. Для каждой „корзины" сохранялся объединенный массив идентификаторов документов, сжатый, как и длинные листы. Далее сохранялись представленные кодом Хаффмана номера слов, соответствующие позиции в пост-листе. Если одному идентификатору документа соответствовало несколько слов, то использовался специальный зарезервированный для этого код.
Описание экспериментов по исследованию данного алгоритма приведено в разделе 5.3 данной работы.
Высокий коэффициент сжатия коротких пост-листов особенно важен при реализации модели с парами слов. Такой индекс содержит достаточно короткие пост-листы и при использовании традиционных алгоритмов сжатия получается неприемлемо большим.
Особенностью организации инвертированного файла на базе В+дерева является то, что на размер одной записи в дереве накладываются ограничения реализации. Теоретически запись не может быть больше половины размера одного листа, а на практике, из разных соображений, это ограничение еще строже. При сжатии с помощью обычных методов кодирования пост-листов эффективность сжатия увеличивается с их длиной, так как каждый новый пост-лист имеет не сжатое первое число. Для того, чтобы разместигь длинные ност-листы в индексе применяется два метода:
1 разбиение пост-листа. Один пост-лист размещается в нескольких записях. В этом случае ключом дерева является не только слово, но и первое значение в пост-листе.
2 вынесение длинных пост листов. При таком подходе пост-листы, которые не помещаются в запись дерева выносятся во внешнюю, по отношению к дереву, структуру.
