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

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

Версия от 08:52, 14 октября 2010; ESyr01 (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Перейти к: навигация, поиск

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

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

Леонид Дмитриев, 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-е появилась система ... — поиск мед. инф. для профессионалов.

В поры, когда появилась первая поисковая система, было всего порядка 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) бесплатно доступен в интернетах.

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