Linguistic tools Лекция 5

ПОИСКОВЫЕ СИСТЕМЫ: предыстория Библейские индексы и конкордансы 1247 – Hugo de St. Caro – было задействовано 500 монахов для составления конкорданса ключевых слов к Библии Журнальные индексы (Королевское научное общество, 1600-е)

Orville James Nave ( )

Информационный поиск INFORMATION RETRIEVAL (IR) Поиск неструктурированных данных (обычно текстовых документов), в которых находится нужная информация в больших коллекциях/корпусах (обычно хранятся в компьютерах)

1950 – библиотечное дело 1952 г Кельвин Муерс: information retrieval WWW Google > 8 млрд страниц –Яндекс 6 млн страниц, 2,5 млн сайтов

Архитектура поисковой системы Робот ( краулер, спайдер, индексатор) Базы данных Клиент (обработка запроса)

ЗАПРОС Логический запрос 1=true 0= false Булевская модель поиска

Manning & Raghavan 2005

ЗАПРОС: Brutus AND Caesar NOT Calpurnia

Для больших коллекций матрица невозможна Инвертированный индекс ( запоминаем только вхождения, но не их отсутствия) Записи отсортированы по словам

Индексирование Документы Токенизация Лемматизация Индексатор

ИНДЕКСАТОР: шаг 1 Пара (слово, ID документа)

Индексатор: шаг 2 СОРТИРОВКА !

Индексатор: шаг 3 Вхождения в один и тот же документ объединяются Добавляются сведения о частоте

ОБРАБОТКА ЗАПРОСА POINTER

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

Оптимизация обработки запросов Начинай с наименее частотного (почему?) Частота двух терминов объединенных оператором OR может быть примерно оценена как сумма частот каждого

упражнение

Оценка качества поиска Релевантность –Полнота (recall) R –Точность (precision) P Точность P = a/a+c Полнота R = a/ a+b F мера = (p+r)/ 2pr документывыданныеневыданные релевантныеac нерелевантныеbd