Поиск, 01 лекция (от 13 октября)

Материал из eSyr's wiki.

Версия 11:12, 17 октября 2010

Введение в информационный поиск

Матспецкурс. Полугодовой спецкурс. В конце экзамен, две попытки. Минимальное требование — быть хотя бы на одной лекции.

Леонид Дмитриев, leozub@cs.msu.su

Информационный поиск - прежде всего, поиск, прежде всего, информации.

Это поиск в массиве каких бы то ни было документов.

Само понятие информационного поиска появилось до интернета, но сейчас оно ассоциируется в первую очередь с ним. Действительно, в этом курсе будет упор сделан на поиск в интернете, но будут затронуты и вопросы классического информационного поиска.

Это не с/к о том, как искать, и не с/к по поисковой оптимизации.

В с/к будут рассмотрены базовые структуры данных поиска, будут некоторые примеры из поисковых систем, но не будет подробно рассказано о внутреннем устройстве гугла или яндекса, поскольку не всё известно, а то, что известно, представляет коммерческую тайну, но некоторые вещи затронуты будут. Далее будут затронуты такие вещи, как лингвистические технологии в поиске. Будет рассказано о том, как устроена машинная морфология, и какие технологии применяются в поиске. Будет рассказано о мультимедийном поиске (поиск картинок). Про seo будет в контексте поискового спама. Будет рассказано в том числе про особенности поиска в вебе и в больших объёмах данных.

Также принимаются пожелания, о чём же хотелось послушать. Для тех, кто ходил на этот же с/к в прошлом году: отличия будут, существенные, и название тоже отличается, для тех, кому это важно в учебной части.

Исторический обзор

ИП, вообще говоря, зародился как научно-прикладная дисциплина, зародился до появления интернета и веба, зародился на стыке библиографии и информатики. Сам термин появился в районе 1950 года.

Первая поисковая система появилась в 1993 году и называлась она Wandex.

Несколько слов о том, как устроен полнотекстовый поиск.

Простейший способ: последовательный поиск. Простота этого способа - единственное его достоинство. Недостатки: огромная вычислительная сложность.

Если мы знаем, что искать понадобится много, то можно упростить эту задачу, предварительно к ней подготовившись.

Инвертированный файл (список, индекс). Пусть у нас есть простой текстовый документ: "мама мыла раму и окно". Документ состоит из одного предложения из трёх слов. Тогда можно записать:

и - 4
мама - 1
мыла - 2
окно - 5
раму - 3

Это список всех слов документа в алфавитном порядке и позиции, где оно встретилось. Соответственно, можно составить такой файл не для одного документа, а для всех.

Конкорданс. С ним связана в какой-то степени забавная история. Раньше достаточно часто о том, что такое инвертированный файл, объясняли через конкорданс, поскольку знали тогда его больше людей, сейчас же наоборот. Это термин, идущий из литературоведения: это алфавитный список употребляемых слов некоторым автором в его произведении с некоторым набором параметров. В инвертированном файле тоже могут быть какие-то признаки, параметры, например, то, что слово Мама — с большой буквы.

Если у нас пример "мама мыла раму и окно и дверь"

дверь - 7
и - 4, 6
мама - 1
мыла - 2
окно - 5
раму - 3

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

Начали появляться значимые массивы информации в машиночитаемом виде. И хотелось начинать искать по всему этому. К этому периоду относится первый поиск по документам. Всё росло, развивалось, базы становились больше, и где-то в 1970-е годы была разработана исследовательская система SMART (G. Salton). Корни всё ещё из автоматизации библиотечных каталогов, но тут уже база текстовых документов, и тут уже появились такие операции как полнотекстовый поиск и поиск по ключевым словам.

Важно помнить, что под поиском по ключевым словам разные поколения подразумевают разное: более молодые — полнотекстовый поиск, более старшие — по ключевым словам в метаданных.

Если у нас есть жёстко заданная структура, например, БД, то там есть структура и поиск по ключу.

Примерно тогда же, в 70-80-е появилась система PubMed(?) — поиск медицинской информации для профессионалов.

В поры, когда появилась первая поисковая система, было всего порядка 1000 сайтов, и поскольку сайтов и документов было немного, можно это руками перебрать, и существует два основных направления: поисковые системы и каталоги.

Один из наиболее известных каталогов — Yahoo (как каталог появился в 1994 году). Ещё можно упомянуть DMOZ.

Из ранних поисковых систем стоит упомянуть lycos (1994), AltaVista (1995). Это простой текстовый поиск на основе инвертированных файлов.

Но веб бурно-бурно рос, и нужно было использовать дополнительную информацию о вебе, его структуре. Самыми яркими представителями были компании Google (1996/1997/1998), с ним прежде всего ассоциируется PageRank. Из большого стоит отметить yahoo, у которого появилась собственная поисковая технология (2004 год). Можно ещё упомянуть такой проект как Bing от MS.

Это что касается глобального.

Что касается локального рынка, нашего сегмента интернета. Первой более-менее известной и качественной системой был Апорт (1996), Rambler (1996), Яндекс (1997).

Структура и основные этапы работы поисковой системы

Для пользователей поисковая система зачастую представляет для себя чёрный ящик. Самое типичное заблуждение: вот мы яндексу задали запрос, и после этого он полез в интернет искать запрос. Естественно, это не так. Основные этапы работы:

• Сбор документов
• Построение и поддержание индекса
• Обработка запросов

Первый этап. Для того, чтобы какой-то набор документов был, его надо скачать. Это звучит просто, но есть множество нюансов (в каком порядке скачивать, как не перегрузить сервер)

Второй этап. Вопрос, как хранить, как хранить так, чтобы можно было отвечать пользователю за разумное время.

Обработка запросов. ...

Ещё несколько терминов из ИП.

Несколько слов о качестве поиска.

Основное понятие - релевантность.

Несколько простейших характеристик качества выдачи: полнота (p=a/c) и точность (r=a/b). Где:

• a — количество релевантных документов в выдаче
• b — общее количество выданных документов
• c — общее количество релевантных документов

Пользователи такие, какие они есть, и спрашивают они то, чего не хотят на самом деле.

Типичный пример — граничные порнографические запросы.

Также есть проблема, что из-за замусоривания поисковой выдачи по обыкновенным запросам предоставляется некачественная выдача.

Ещё из забавных вещей: Буш, Лукашенко, Янукович.

Что ещё: помимо текстового поиска, к ИП относится многие другие вещи, и есть тенденция к портализации поиска, поиск по всему.

Литература

С русскоязычной литературой в этой области туговато. Из материалов в интернете можно порекомендовать набор курсов Яндекса, все эти курсы бесплатно доступны по соответствующему адресу: http://company.yandex.ru/academic/class2006/.

Недавно вышел перевод классического западного учебника по ИП: "Введение в информационный поиск", Маннинг, Рагхаван, Шульц. Книга является переводом из двух самых известных учебников по ИП. Книжка была издана при поддержке яндекса. Англоязычный текст (Introduction in Infromation Retrieval) бесплатно доступен в интернетах.

Домашнее задание

• Найти домашнее задание прошлого года.
• Найти телефон Ильи Сегаловича