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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Новая: Введение в информационный поиск. Матспецкурс. Полугодовой спецкурс. В конце экзамен, две попытки. Мин...)
Текущая версия (11:13, 17 октября 2010) (править) (отменить)
(fixed book name)
 
(1 промежуточная версия не показана)
Строка 1: Строка 1:
-
Введение в информационный поиск.
+
==Введение в информационный поиск==
-
Матспецкурс. Полугодовой спецкурс. В конце экзамен, две попытки. Минимальное требование — быть хоть бя на одной лекции.
+
Матспецкурс. Полугодовой спецкурс. В конце экзамен, две попытки. Минимальное требование — быть хотя бы на одной лекции.
Леонид Дмитриев, leozub@cs.msu.su
Леонид Дмитриев, leozub@cs.msu.su
-
Информационный поиск - прежде всего поиск прежде всего информации.
+
Информационный поиск - прежде всего, поиск, прежде всего, информации.
Это поиск в массиве каких бы то ни было документов.
Это поиск в массиве каких бы то ни было документов.
-
Само понятие инф. поиск появилось до интернета, но сейчас оно ассоц. в первую очередь с ним. действ., в этом курсе будет упор сделан на поиск в интрнете, но будут затронуты и вопросы классич. инф. поиска.
+
Само понятие информационного поиска появилось до интернета, но сейчас оно ассоциируется в первую очередь с ним. Действительно, в этом курсе будет упор сделан на поиск в интернете, но будут затронуты и вопросы классического информационного поиска.
Это не с/к о том, как искать, и не с/к по поисковой оптимизации.
Это не с/к о том, как искать, и не с/к по поисковой оптимизации.
-
О чём же будет спецкурс. В с/к будут расск. базовые структуры данный поиска, будут нек-рые примеры из поиск. систем, но не будет подр. расск о внутр. устройстве гугла или яндекса, поск не всё известно, а то, что известно, предст. комм.тайну, но некоторые вещи затронуты будут. Далее будут затронуты такие вещи, как лингвистические технологии в поиске. Будет расск. о том, как устр маш. морылология, и какие тезн. ... применяются в поиске. Будет расск. о мультимедийном поиске (поиск картинок). Про seo будет в контексте поискового спама. Будет расск. в том числе про особенности поиска в вебе и в больших объёмах данных.
+
В с/к будут рассмотрены базовые структуры данных поиска, будут некоторые примеры из поисковых систем, но не будет подробно рассказано о внутреннем устройстве гугла или яндекса, поскольку не всё известно, а то, что известно, представляет коммерческую тайну, но некоторые вещи затронуты будут. Далее будут затронуты такие вещи, как лингвистические технологии в поиске. Будет рассказано о том, как устроена машинная морфология, и какие технологии применяются в поиске. Будет рассказано о мультимедийном поиске (поиск картинок). Про seo будет в контексте поискового спама. Будет рассказано в том числе про особенности поиска в вебе и в больших объёмах данных.
-
Также принимаются пожелания, о чём же хотелось послушать. Для тех, кто ходил на этот же с/к в прошлом году: отличия будут, существенные, и название тоже отличается, для тех, кому это важно у учебной части.
+
Также принимаются пожелания, о чём же хотелось послушать. Для тех, кто ходил на этот же с/к в прошлом году: отличия будут, существенные, и название тоже отличается, для тех, кому это важно в учебной части.
-
Исторический обзор.
+
==Исторический обзор==
-
ИП, вообще говоря, зародился как науч-прикл. дисц, зародился до появляения интернета и веба, зародился на стыке библиот=графии и иноформатики. Сам термин появлися в районе 1950 года.
+
ИП, вообще говоря, зародился как научно-прикладная дисциплина, зародился до появления интернета и веба, зародился на стыке библиографии и информатики. Сам термин появился в районе 1950 года.
Первая поисковая система появилась в 1993 году и называлась она Wandex.
Первая поисковая система появилась в 1993 году и называлась она Wandex.
-
несколько слов о том, как устроен полнотекстовый поиск.
+
Несколько слов о том, как устроен полнотекстовый поиск.
-
Простейший способ: посл. поиск. Простота этого способа - единственное его достоинство. Недостатки: огромная выч. сложность.
+
Простейший способ: последовательный поиск. Простота этого способа - единственное его достоинство. Недостатки: огромная вычислительная сложность.
-
Если мы знаем, что искать понадобится много, то можно упростить эту задачу, предв. к ней подг.
+
Если мы знаем, что искать понадобится много, то можно упростить эту задачу, предварительно к ней подготовившись.
-
Инвертированный файл (список, индекс). Пусть у нас есть простой текстовый документ: "мама мыла раму и окно". Документ сост. из одного предл. из трёх слов. Тогда можно записать:
+
Инвертированный файл (список, индекс). Пусть у нас есть простой текстовый документ: "мама мыла раму и окно". Документ состоит из одного предложения из трёх слов. Тогда можно записать:
и - 4
и - 4
мама - 1
мама - 1
Строка 35: Строка 35:
окно - 5
окно - 5
раму - 3
раму - 3
-
Это список всех слов документа в алф. порядке и позиции, где оно встретилось. Соотв., можно сост. такой файл не для одного док., а для всех.
+
Это список всех слов документа в алфавитном порядке и позиции, где оно встретилось. Соответственно, можно составить такой файл не для одного документа, а для всех.
-
Конкорданс. С ним связана в какой-то степени забавная история. Раньше дост. часто о том, что такое инв. файл, объясняли через конкорданс, поск. знали тогда его больше людей, сейчас же наоборот. Это термин, идущий из литературоведения: это алф. список употр. слов некоторым автором в его произведении с нккоторым набором параметров. В инв. файле тоже могут быть какие-то признаки, параметры, например, то, что слово Мама — с большой буквы.
+
Конкорданс. С ним связана в какой-то степени забавная история. Раньше достаточно часто о том, что такое инвертированный файл, объясняли через конкорданс, поскольку знали тогда его больше людей, сейчас же наоборот. Это термин, идущий из литературоведения: это алфавитный список употребляемых слов некоторым автором в его произведении с некоторым набором параметров. В инвертированном файле тоже могут быть какие-то признаки, параметры, например, то, что слово Мама — с большой буквы.
Если у нас пример "мама мыла раму и окно и дверь"
Если у нас пример "мама мыла раму и окно и дверь"
Строка 47: Строка 47:
раму - 3
раму - 3
-
Если вспомнить основы образа и прообраза инф. поиска. ... в одном средн. монастыре для уск. поиска к библии монахи выучили её наизусть. .... появились библиотечные каталогии. В середине прошлого века началось бурное разв. комп. техники, и с её помощью начали автомат. всё, что можно и нельзя, и появилась идея, не авт. ли библиотечные каталоги.
+
Если вспомнить основы образа и прообраза информационного поиска. ... в одном средневековом монастыре для ускорения поиска к библии монахи выучили её наизусть. .... появились библиотечные каталоги. В середине прошлого века началось бурное развитие компьютерной техники, и с её помощью начали автоматизировать всё, что можно и нельзя, и появилась идея, не автоматизировать ли библиотечные каталоги.
-
Началаи появляться значимые массивы инф. в машиночитаемом виде. И хотелось начинать искать по всему этому. К этому периоду отн. первый поиск по документам. Всё росло, развивалось, базы становились больше, и где-то в 1970-е годы была разработана исслед. система SMART (G. Salton). Корни всё ещё из автоматизации библ. каталогов, но тут уже база текстовых документов, и тут уже появились такие операции как полнотекстовый поиск и поиск по ключевым словам.
+
Начали появляться значимые массивы информации в машиночитаемом виде. И хотелось начинать искать по всему этому. К этому периоду относится первый поиск по документам. Всё росло, развивалось, базы становились больше, и где-то в 1970-е годы была разработана исследовательская система SMART (G. Salton). Корни всё ещё из автоматизации библиотечных каталогов, но тут уже база текстовых документов, и тут уже появились такие операции как полнотекстовый поиск и поиск по ключевым словам.
Важно помнить, что под поиском по ключевым словам разные поколения подразумевают разное: более молодые — полнотекстовый поиск, более старшие — по ключевым словам в метаданных.
Важно помнить, что под поиском по ключевым словам разные поколения подразумевают разное: более молодые — полнотекстовый поиск, более старшие — по ключевым словам в метаданных.
Строка 55: Строка 55:
Если у нас есть жёстко заданная структура, например, БД, то там есть структура и поиск по ключу.
Если у нас есть жёстко заданная структура, например, БД, то там есть структура и поиск по ключу.
 +
Примерно тогда же, в 70-80-е появилась система PubMed(?) — поиск медицинской информации для профессионалов.
-
Примерно тогда же, в 70-80-е появилась система ... — поиск мед. инф. для профессионалов.
+
В поры, когда появилась первая поисковая система, было всего порядка 1000 сайтов, и поскольку сайтов и документов было немного, можно это руками перебрать, и существует два основных направления: поисковые системы и каталоги.
-
В поры, когда появилась первая поисковая система, было всего порядка 1000 сайтов, и поск. сайтов и документов было немного, можно это руками перебрать, и сущ. два осн. направления: поисковые системы и каталоги.
+
Один из наиболее известных каталогов — Yahoo (как каталог появился в 1994 году). Ещё можно упомянуть DMOZ.
-
Один из наиб. известных каталогов — Yahoo (как каталог появился в 1994 году). Ещё можно упомянуть DMOZ.
+
Из ранних поисковых систем стоит упомянуть lycos (1994), AltaVista (1995). Это простой текстовый поиск на основе инвертированных файлов.
-
Из ранних поисковых систем стоит упомянуть lycos (1994), AltaVista (1995). Это прост. текстовый поиск на осн. инв. фалойв.
+
Но веб бурно-бурно рос, и нужно было использовать дополнительную информацию о вебе, его структуре. Самыми яркими представителями были компании Google (1996/1997/1998), с ним прежде всего ассоциируется PageRank. Из большого стоит отметить yahoo, у которого появилась собственная поисковая технология (2004 год). Можно ещё упомянуть такой проект как Bing от MS.
-
 
+
-
Но веб бурно-бурно рос, и нужно было исп. доп. инф. о вебе, его структуре. Самыми яркими представителями были компании Google (1996/1997/1998), с ним прежде всего ассоц. PageRank. Из большого стоит отметить yahoo, у которого появилась собств. поиск. техонология (2004 год). Можно ещё упомянуть такой проект как Bing от MS.
+
Это что касается глобального.
Это что касается глобального.
-
Что касается локального рынка, нашего сегмента интернета. Первой более-менее изв. и кач. системой был Апорт (1996), Rambler (1996), Яндекс (1997).
+
Что касается локального рынка, нашего сегмента интернета. Первой более-менее известной и качественной системой был Апорт (1996), Rambler (1996), Яндекс (1997).
-
Структура и осн жтапы работы поиск. системв..
+
==Структура и основные этапы работы поисковой системы==
-
Для пользователей поисковая система зачастую предст. для себя чёрный ящик. Самое типичное заблуждение: вот мы яндексу задали запрос, и после этого он полез в интернет искать запрос. Естественно, это не так. Основные этапы работы:
+
Для пользователей поисковая система зачастую представляет для себя чёрный ящик. Самое типичное заблуждение: вот мы яндексу задали запрос, и после этого он полез в интернет искать запрос. Естественно, это не так. Основные этапы работы:
* Сбор документов
* Сбор документов
* Построение и поддержание индекса
* Построение и поддержание индекса
* Обработка запросов
* Обработка запросов
-
Первый этап. Для того, чтобы какой-то набор документов был, его надо скачать. Это звучит просто, но есть множество ньюансов (в каком порядке скачивать, как не перегрузить сервер)
+
Первый этап. Для того, чтобы какой-то набор документов был, его надо скачать. Это звучит просто, но есть множество нюансов (в каком порядке скачивать, как не перегрузить сервер)
-
Второй этап. Вопроос, как хранить, как хранить так, чтобы можно было отвечать польз. за разумное время.
+
Второй этап. Вопрос, как хранить, как хранить так, чтобы можно было отвечать пользователю за разумное время.
Обработка запросов. ...
Обработка запросов. ...
-
Ещё неск. терминов из ИП.
+
Ещё несколько терминов из ИП.
Несколько слов о качестве поиска.
Несколько слов о качестве поиска.
-
Осно понятие - релевантность.
+
Основное понятие - релевантность.
Несколько простейших характеристик качества выдачи: полнота (p=a/c) и точность (r=a/b). Где:
Несколько простейших характеристик качества выдачи: полнота (p=a/c) и точность (r=a/b). Где:
Строка 98: Строка 97:
Типичный пример — граничные порнографические запросы.
Типичный пример — граничные порнографические запросы.
-
Также есть проблема, что из-за замусоваривания поисковой выдачи по обыкновенным запросам предоставляется некачественная выдача.
+
Также есть проблема, что из-за замусоривания поисковой выдачи по обыкновенным запросам предоставляется некачественная выдача.
-
Ещё из забавных вещей: бушб лукашенко, янукович.
+
Ещё из забавных вещей: Буш, Лукашенко, Янукович.
-
Что ещё: помимо тектосового поиска, к ИП относится многие другие вещи, и есть тенденция к портализации поиска, поиск по всему.
+
Что ещё: помимо текстового поиска, к ИП относится многие другие вещи, и есть тенденция к портализации поиска, поиск по всему.
-
Литература.
+
==Литература==
-
С русскояз. литературой в этой обл. туговато. Из материалов в инт. можно порекомендовать набор курсов Яндекса, все эти курсы бесплатно доступны по соотв адресу: http://company.yandex.ru/academic/class2006/.
+
С русскоязычной литературой в этой области туговато. Из материалов в интернете можно порекомендовать набор курсов Яндекса, все эти курсы бесплатно доступны по соответствующему адресу: http://company.yandex.ru/academic/class2006/.
-
Недавно вышел перевод классич. западного уч. по ИП: "Введение в информационный поиск", Маннинг, Рагхаван, Шульц. Книга явл. переводом из двух самых изв. уч. по ИП. Книжка была издана при поддержке яндекса. Англоязычный текст (Introduction in Infromation Retrieval) бесплатно доступен в интернетах.
+
Недавно вышел перевод классического западного учебника по ИП: "Введение в информационный поиск", Маннинг, Рагхаван, Шульц. Книга является переводом из двух самых известных учебников по ИП. Книжка была издана при поддержке яндекса. Англоязычный текст (Introduction to Information Retrieval) бесплатно доступен в интернетах.
-
Домашнее задание.
+
'''Домашнее задание'''
* Найти домашнее задание прошлого года.
* Найти домашнее задание прошлого года.

Текущая версия

Содержание

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

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

Леонид Дмитриев, 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 to Information Retrieval) бесплатно доступен в интернетах.

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

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


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


01 02 03 04 05 06 07 08 09


Календарь

Октябрь
13 20 27
Ноябрь
17 24
Декабрь
01 08 15 22


Эта статья является конспектом лекции.

Эта статья ещё не вычитана. Пожалуйста, вычитайте её и исправьте ошибки, если они есть.
Личные инструменты
Разделы