Поиск информации

Поиск информации – из чего он складывается? Как мы задаем документы? Как задаем запросы? Как вычисляем близость между запросом и документом?

Булевская модель Документ = множество слов Запрос = булевское выражение: (кошка OR собака) AND лебедь ANDNOT генерал 1 = true 0 = false Для больших собраний текстов такой поиск сложен.

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

Обработка запроса 1. Двигаемся одновременно по двум рядам указателей. 2. На каждом шаге сравниваем оба пойнтера. 3. Если они равны – то это искомое пересечение. 4. Если они не равны, то двигаем меньший.

В интернете Неконтролируемая коллекция документов Объемы Разные форматы Разнообразие (язык, темы) Ссылки (PageRank)

А теперь о лингвистической части происходящего…

Предварительная обработка Извлечь текст (PDF, HTML) Определить кодировки и язык Разбить на слова и предложения Удалить стоп-слова Привести слова к словарной форме

Разбиваем на слова и предложения Даты, числа: 23/03/2008; 3,1415… Наречия: без устали, в упор… Предлоги: в преддверии, несмотря на… Союзы: вроде как, вроде бы, к тому же, как будто… Союзы: в силу того что, несмотря на то что, тем более что… А также: Комсомольск-на-Амуре, Дмитрий Эммануилович, царская водка Определить границу предложения: « И.И. Соколов приехал в г. Хабаровск прошлой осенью».

Стоп-слова Текст = неструктурированный набор слов, «мешок со словами» Удаляем все служебные слова: предлоги, союзы, частицы… Близ, брысь, будто, бы, быть, в, вы, ваш…

Приводим к словарной форме – морфологический анализ Определяем только часть речи: (слушающий – что это за часть речи?) (а стекло?) Полная морфологическая информация (слушающий – прокомментируйте, пожалуйста =) )

Типы морфологического анализа Выделение основы: Лес, лесной, лесозаготовки -> лес Приведение к словарной форме: Лесному, лесным - > лесной Танцующая - > танцевать

Проблемы Предварительная обработка закончена. Что делаем дальше? Что ещё надо учитывать при поиске? Запрос: «печь пирог» Документ: «…кирпичная печь» Как сделать так, чтобы не находить по нашему запросу этот документ?

Проблемы Задать условие: если рядом с «печь» стоит существительное (печь пирожки), то «печь» с высокой вероятностью – глагол, а если прилагательное (каменная печь) – «печь» является существительным. А если глагол? («печь, стирать и гладить» и «растопить печь»)

Проблемы Запрос: «Красная площадь» Документ: «…красная баба кричала на всю площадь» Как сделать так, чтобы не находить по нашему запросу этот документ?

Проблемы Задать возможное расстояние между словами Какое?

Критерии соответствия запроса и документа: Количество вхождений слов (словосочетаний) в документ; Расположение слов запроса в документе (если слово присутствует в заголовке или названии документа); Формы слов запроса (преимущество – у слов, которые имеют тот же падеж, род, число, …);

Критерии соответствия запроса и документа: Расстояние между словами запроса; Посещаемость документа; Ссылочный вес документа; Относительная частота (отношение количества вхождений слов запроса в документ к общему количеству слов в документе)

Оценка качества поиска Документы: Точность P = a / (a+c) Полнота R = a / (a+b) Документывыданныеневыданные важныеac Не важныеbd

Поисковые системы и их основные особенности

Современные поисковые системы Поисковые каталоги Полнотекстовые поисковые системы Метапоисковые системы

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

Полнотекстовые поисковые системы Имеют специальные программы - пауки или роботы. Они ищут страницы, извлекают ссылки на страницах и индексируют информацию в базе данных. Роботы используют в качестве оценки полезности' ресурса глубину ссылок Недостатки: роботы не могут посещать все доступные интернет-ресурсы.

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

Yandex: Использует морфологический анализатор!

Google Совсем не использует морфологических анализаторов, вместо них – вероятности Очень хороший поисковик =)

Семантический поиск Что такое семантика? ~ наука о значениях и смыслах

Что такое семантический поиск? Попробуйте сформулировать =)

Как можно его осуществить? Нужно собрать знания о том, как слова связаны друг с другом по смыслу Существует специальный класс словарей, который описывает такую связь – тезаурусы

Тезаурус Традиционные словари – алфавит Тезаурус – семантическая сеть 1 понятие – много слов 1 слово – много понятий Моделирует память человека

Wordnet Базовая единица – синсет (synonym set), набор синонимов, взаимозаменяемых в различных контекстах Синсеты связаны между собой семантическими отношениями: Часть – целое Общее – частное Синонимия Род – вид