Принципы работы ИПС Тема 1. Обратные индекы для поиска документов

Запрос В каких из русских сказок есть слово волк, но нет упоминания медведя и поросенка?

Вектор слово-документной встречаемости Три поро- сенка Красная ШапочкаКолобокТеремок медведь0011 волк1111 поросенок1000 мышь0001 бабушка0110 0,если слова нет в документе,1 если есть

Векторы инциденции Итак мы имеем 0/1 вектор для каждого слова размерности равной количеству документов. Ответ на запрос: возьмем вектора для медведя (дополнение), волка и поросенка(дополнение) и выполним между ними побитное умножение 1100&1111&0111 = 0100

Ответы на запрос Ответом на запрос будет сказка Красная Шапочка

Большая энциклопедия сказок Рассмотрим n=1 миллион документов, по 1К слов/ терминов в каждом В среднем 6 байт/термин, включая пробелы, знаки пунктуации - 6 ГБ данных. Будем предполагать, что среди них m=500 К разных терминов.

Не можем построить матрицу 500 К x 1 млн. - матрица имеет полтриллиона 0 и 1. Но она имеет не больше единиц –матрица крайне разреженная. Какое представление лучше? Почему?

Обратные индексы Документы разбираются на слова, сохраняемые вместе с номером (идентификатором) документа. документ 1 документ 2 Милый, милый Бармалей, Смилуйся над нами, Отпусти нас поскорей К нашей милой маме! Милый, милый людоед, Смилуйся над нами. Мы дадим тебе конфет, Чаю с сухарями! Милый1 милый 1 Бармалей 1 смилуйся 1 над 1 нами 1 отпусти 1 нас 1 поскорей 1 к 1 нашей 1 милой 1 маме 1 милый 2 2 людоед 2 смилуйся 2 над 2 нами 2 мы 2 дадим 2 тебе 2 конфет 2 Чаю2 с2 сухарями 2

Затем для всех документов формируется общий обратный файл, термины в котором сортированы по алфавиту. Бармалей1 дадим2 К1 конфет2 Людоед2 маме 1 Милой1 милый1 Милый1 милый 2 Милый2 Мы2 над1 Над2 Нами1 2 Нас1 Нашей1 Отпусти1 Поскорей1 с2 смилуйся 1 Смилуйся2 Сухарями2 тебе2 чаю1 милый1 1 Бармалей 1 смилуйся 1 над 1 нами 1 отпусти 1 нас 1 поскорей 1 к 1 нашей 1 милой 1 маме 1 милый 2 2 людоед 2 смилуйся 2 над 2 нами 2 мы 2 дадим 2 тебе 2 конфет 2 Чаю2 с2 сухарями 2

Термины, которые несколько раз повторяются в документе соединяются, добавляем информацию о повторении, заменяем большие буквы на маленькие, нормализуем: имен.падеж, ед. число, муж.род, инфинитив. Бармалей1 дадим2 К1 конфет2 Людоед2 маме 1 Милой1 милый1 Милый1 милый 2 Милый2 Мы2 Над1 2 Нами1 2 Нас1 Нашей1 Отпусти1 Поскорей1 с2 смилуйся 1 Смилуйся2 Сухарями2 тебе2 чаю1 Терминповтор бармалей11 давать21 к11 конфета21 людоед 21 мама11 милый13 22 мы12 22 над11 наш11 отпустить11 поскорей11 с11 смиловаться11 21 сухарь21 чай21

Файл разделяется на словарь и собственно индекс. докповторов Термин число докум. общее число повторов бармалей11 давать11 к11 конфета11 людоед 11 мама11 милый25 мы24 над22 наш11 отпустить11 поскорей11 с11 смиловаться22 сухарь11 чай11

Что наиболее дорого при хранении? термины указатели докповторов Термин число докум. общее число повторов бармалей11 давать11 к11 конфета11 людоед 11 мама11 милый25 мы24 над22 наш11 отпустить11 поскорей11 с11 смиловаться22 сухарь11 чай11

Два крайних случая. Термин луноход встречаются, возможно, в одном документе из миллиона - храним этот указатель, используя log ~ 20 бит. Термин и встречается в каждом документе, поэтому 20 бит на указатель - это много. –Предпочитают 0/1 вектор в этом случае

Элементы индекса Хранить список документов с содержащимися терминами в возрастающем порядке ID документов. -Волк - 33,47,154,159,202… Следствие достаточно хранить промежутки между ID Надежда: большинство пробелов может хранится с помощью значительно меньшего количества битов, чем 20.

Переменное кодирование Для лунохода используется ~ 20 битов/промежуток. Для и используется ~ 1 бит/промежуток. Если средний промежуток для термина равен G, хотим использовать ~log 2 G бит/промежуток.

Гамма - код для кодирования промежутков Представим промежуток G как пару Длина – в унарном коде и использует ceil(log 2 G)+1 бит для двоичного кодирования длины остатка=G-2 ceil(log 2 G). Например, 9 = , 3 в унарном коде 1110; 1 в двоичном коде 001, таким образом, 9 -> Кодируем G, используя 2*ceil(log 2 G)+1 бит.

Что мы уже сделали? Закодировали промежутки так плотно, как возможно, сточностью до множителя - двойки. Для лучшей настройки и простого анализа нужна информация о возможном распределении значений промежутков.

Закон Зипфа. к наиболее повторяющихся терминов имеют повторение пропорциональное 1/к. Используем это для грубого анализа объема памяти, требуемой для хранения указателей файла обратного индекса.

Грубый анализ, основанный на законе Зипфа. Наиболее частое слово встречается в n документах. –n промежутков равных единице. Второе по частоте слово встречается в n/2 документах. -n/2 промежутков величины два. К-ое по частоте слово встречается в n/k документах. - n/k промежутков - используем 2*ceil(log 2 G)+1 бит для каждого промежутка. - итак, ~(2n/k)log 2 k бит для к-го наиболее встречающегося термина.

Суммируем к от 1 до 500К. Делаем это, разбивая к в группы: - i группа состоит из таких номеров к, что 2 i- 1 < к

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

Вопросы по построенному индексу Как обрабатывать запрос? Какие термины в документе индексировать? –все слова или только важные? Список стоп-слов: термины, которые повторяются так часто, что мы игнорируем их индексирование. -союзы, -специфические элементы языка. Упражнение: повторить расчет размера индекса, если не включать 100 наиболее частых терминов

Вопрос, что индексировать волк или волка или волку. ЗАмок или заМОК. ( ударение) Пунктуация. -C.Ш. А. или США (сокращение, аббревиатура). Числа (в каком формате?) –3/12/91 –Март 12,1991 –55 В.С. –В-55 –

Большие/маленькие буквы Что произойдет, если все большие буквы сделать маленькими Теряем имена собственные –Например, General Motors –Верховный Совет

Понятия и созвучия Как обрататывать синонимы и омонимы, индексировать эквивалентность или расширять/уточнять запрос? –Классы эквивалентности: автомашина и автомобиль –опушка – край леса или меховая обшивка одежды? подробнее далее…

Орфографическое корректирование Рассмотрим все близкие по написанию слова, в пределах 3-х простых операций редактирования (вставка, удаление, замена), в момент запроса. значительно замедляет обработку запроса (до 100 раз). - используется только в случае, когда незультат запроса пуст, - что, если документы сами содержат орфографические ошибки?

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

Алгоритм Портера Обычный алгоритм для выделения корня в англолязычных текстах Соглашения + 5-фазное сокращение –фазы применяют последовательно –каждая фаза состоит из набора команд –пример соглашения: из правил в составной команде, выбираем одно применимый к самому длинному суффиксу. Типичные правила Портера –Прилагательное существительное –Множественное число един.число

Накопление свидетельств Обычно рассматривается случай поиска термина 1/0 (присутствует/не присутствует) -2 vs. 3 случай -3 vs. 2 и т.д. Необходимо частота повторения термина в документе.

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

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

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

Ресурсы для сегодняшней лекции Managing Gigabytes, Глава 3. Modern Information Retrieval, Глава 7.2. Алгоритм Портера: http//