Информационно-поисковые системы. Сычев А.В. 2006 г. 1 Воронежский государственный университет Факультет компьютерных наук Кафедра информационных систем. - презентация

1 Информационно-поисковые системы. Сычев А.В г. 1 Воронежский государственный университет Факультет компьютерных наук Кафедра информационных систем Информационный поиск в Веб

2 Информационно-поисковые системы. Сычев А.В г. 2 Особенности Web, затрудняющие классический информационный поиск Распределенность данных Высокий процент изменчивых данных Большой объем данных Неструктурированность данных Избыточность данных Качество данных Разнородность данных

3 Информационно-поисковые системы. Сычев А.В г. 3 Дополнительные характеристики документов: HTML-тэги гиперссылки Неквалифицированные пользователи, предпочитающие короткие запросы Поисковой спам Особенности Web, затрудняющие классический информационный поиск

4 Информационно-поисковые системы. Сычев А.В г. 4 Характеристики статического (поверхностного) Веб Количество документов – более 8 млрд., прирост млн. в день, общее удвоение каждые 8-12 месяцев. Размер словаря – от десятков до сотен миллионов слов. Разнородность ресурсов: По типам и форматам данных По качеству Языки – более 100. Спам – сотни миллионов документов.

5 Информационно-поисковые системы. Сычев А.В г. 5 Размер базы поисковых систем (2005) Поисковая система Заявленный размер базы Глубина индексирования страницы Google8.1 млрд101 К MSN5 млрд.150 К Yahoo4.2 млрд. (оценка)500 К Ask Jeeves2.5 млрд.101 К+

6 Информационно-поисковые системы. Сычев А.В г. 6 Глубинный Веб Глубинный Веб отличается от поверхностного Веб качественно и количественно. Содержимое глубинного Веб хранится в базах данных и генерируется динамически по непосредственному запросу. Данные из глубинного Веб доступны только через интерфейсы (HTML-формы, WSDL веб-сервисы). Исследование (B. He, M. Patel, Z. Zhang, K. Chang, CACM 2006) показало, что глубинный Веб охватывает более 300 тыс. сайтов, связанных с более 450 тыс. БД. Примерный объем ресурсов составляет от 10 до 100 ПБ. Что более чем в сотни раз превосходит объем ресурсов в поверхностном Веб.

7 Информационно-поисковые системы. Сычев А.В г. 7 Глубинный Веб Примеры источников: Электронный бизнес и развлечения: amazon.com, ebay.com, realtor.com, cars.com, imdb.com. amazon.comebay.comrealtor.comcars.com imdb.com Новости, библиотеки, сообщества: cnn.com, yahoo.com, spiegel.com,Terraserve.com, lonelyplanet.com.cnn.com yahoo.comspiegel.comTerraserve.com lonelyplanet.com Научный сервис в интернет: NCBI, SRS, SwissProt, PubMed, GriPhyN.NCBISRS SwissProtPubMedGriPhyN

8 Информационно-поисковые системы. Сычев А.В г. 8 Действия пользователя Технология извлечения информации Пользователь запрашивает информацию в интерактивном режиме 3 способа извлечения: - Перемещение по ссылкам (гипертекст) - Выборка (классические ИПС) - Просмотр и выборка (в современных цифровых библиотеках и веб- системах) Технология предъявления информации - Автоматическое и постоянное предъявление информации пользователю - Программные агенты - Фильтрация релевантной информации с последующим изучением пользователем

9 Информационно-поисковые системы. Сычев А.В г. 9 Таксономия поиска в Веб Все запросы пользователя при поиске в сети Веб можно разбить на 3 класса [Broder 2002]: Навигационные (поиск определенного сайта) Информационные (поиск конкретной информации, которая может размещаться в одном или нескольких документах) Транзакционные (с целью выполнения определенных действий в сети веб, например, загрузка файла или сервиса)

10 Информационно-поисковые системы. Сычев А.В г. 10 Целью является поиск определенного сайта в Веб, который пользователь либо посещал ранее, либо он знает о его существовании Пример Запрос: Don Knuth Вероятная цель поиска: Навигационный запрос

11 Информационно-поисковые системы. Сычев А.В г. 11 Информационный запрос Целью является поиск информации, которая имеется в статической форме (т.е. не создается динамически по запросу) в сети Веб Примерно в 15% запросов предпочтение отдается документам, содержащим коллекцию ссылок по тематике, нежели конкретным документам

12 Информационно-поисковые системы. Сычев А.В г. 12 Можно выделить следующие типы: Поиск ответа на конкретный вопрос, напримерКакова общая площадь России?. Результат – краткий ответ (короткое предложение или часть документа). Поиск документов, содержащих определенную информацию, например Найти страницы, описывающие правило подачи заявки на конкурс проектов …. Результатом является конкретный документ, содержащий необходимую информацию. Информационный запрос

13 Информационно-поисковые системы. Сычев А.В г. 13 Поиск документов по определенной тематике, например Найти информацию по технологиям поисковой оптимизации. Результатом является множество документов, посвященных данной тематике. Информационный запрос

14 Информационно-поисковые системы. Сычев А.В г. 14 Транзакционные запросы Целью является достижение определенного сайта, с которым пользователь предполагает работать дальше. Типичные примеры таких запросов: Покупка товаров Загрузка файлов Поиск сервисов Поиск серверов (например игровых) Обращение к базам данных

15 Информационно-поисковые системы. Сычев А.В г. 15 Эволюция поисковых систем Веб В связи с данной таксономией можно выделить 3 этапа эволюции поисковых систем Веб: Первое поколение (примерно гг.). Поддержка исключительно информационных запросов. Работа с текстовыми данными Частоты терминов Векторные модели Второе поколение (начало с гг. ). Используется гиперссылочный анализ. Поддержка как информационных так и навигационных запросов.

16 Информационно-поисковые системы. Сычев А.В г. 16 Третье поколение (по настоящее время). Стремление использовать все возможные источники данных для ответа на вопрос какая именно потребность кроется за запросом пользователя?. Возможность поддержки всех трех типов запросов. Семантический анализ Большее внимание потребности пользователя нежели содержанию его запроса Привлечение различных контекстов Развитая система помощи пользователю (подсказки, обратная связь и др.) Интеграция поиска и анализа текста. Эволюция поисковых систем Веб

17 Информационно-поисковые системы. Сычев А.В г. 17 Веб-каталоги vs. поисковые системы Веб-каталоги Выбор сайтов вручную Поиск по содержимому описания страниц Изначальное введение иерархии категорий Поисковые системы Все страницы на всех сайтах Поиск непосредственно по содержимому самих страниц Порядок задается после обработки запроса в процессе ранжирования по релевантности или другим показателям

18 Информационно-поисковые системы. Сычев А.В г. 18 Запросы: Короткие (в среднем 2.54 термина) Нечеткие термины 80% запросов не содержат операторов Огромное разнообразие по: Потребностям Ожиданиям Знаниям Каналам Особенности поведения: 85% пользователей просматривают только первую страницу со списком найденных документов 78% пользователей не пытаются изменить запрос Портрет пользователя ИПС ВебПортрет пользователя ИПС Веб

19 Информационно-поисковые системы. Сычев А.В г. 19 Задачи, решаемые поисковыми системами Веб Сбор документов из сети Веб Индексирование документов Поиск по индексу Работа с документами и запросами пользователей

20 Информационно-поисковые системы. Сычев А.В г. 20 Компоненты информационно- поисковой системамы Веб Сетевой робот-паук Хранилище документов Индексатор Обработчик запрос с поддержкой ранжирования.

21 Информационно-поисковые системы. Сычев А.В г. 21 Сбор документов из сети Веб Сеть гипертекстовых документов может быть представлена в виде ориентированного графа G(V,E), содержащего узлы (веб- страницы), которые связаны между собой направленными ребрами (гиперссылками).

22 Информационно-поисковые системы. Сычев А.В г. 22 Обход веб-графа Обход или исследование веб-графа – процесса поиска узлов и ребер графа, начиная корневого подмножества узлов. Данная процедура реализуется с помощью компоненты, которая называется сетевым роботом-пауком или просто пауком.

23 Информационно-поисковые системы. Сычев А.В г. 23 Типовая структура Паука

24 Информационно-поисковые системы. Сычев А.В г. 24 Узкие места в работе ПаукаУзкие места в работе Паука Отображение доменных имен в URL в IP адреса с помощью DNS Установление соединения сокета с сервером и отправка запроса Получение запрошенного документа в ответе сервера Для небольших документов наибольшие задержки связаны с первыми двумя задачами. Решение проблемы узких мест заключается в том, что весь цикл закачки документа определяется логическим потоком управления

25 Информационно-поисковые системы. Сычев А.В г. 25 Типичные проблемы при разработке крупномасштабного Паука Основные проблемы: Задержка, связанная с закачкой одного документа может составлять несколько секунд. Однако пропускная способность сети позволяет передавать от сотен до тысяч документов одновременно. Одновременная загрузка множества документов возможна в случае обеспечения множественного доступа к DNS, например за счет репликации.

26 Информационно-поисковые системы. Сычев А.В г. 26 Использование средств мнозадачности, предоставляемых операционными системами, нежелательно в виду больших накладных расходов. Лучшее решение - использование асинхронных сокетов. При работе с URL необходимо решать задачи дублирования ссылок, избеганияловушек. Типичные проблемы при разработке крупномасштабного Паука

27 Информационно-поисковые системы. Сычев А.В г. 27 DNS: кеширование, предвыборка, разрешение имен Паук формирует десятки запросов на разрешение имен в секунду. Кроме того, во избежание перегрузки веб- серверов, паук стремится распределить обращение сразу между несколькими серверами. Использование стандартных функция, например gethostbyname, неоправдано, ввиду отсутствия поддержки обработки множественных запросов. Решение: использование собственного DNS- клиента. Для URL, ещё ни разу не встречавшихся, используется предвыборка на основе UDP.

28 Информационно-поисковые системы. Сычев А.В г. 28 Проблема одновременной множественной закачки документов. Поскольку закачка документа длится в течение нескольких секунд, паук должен одновременно устанавливать сокет- соединения с различными HTTP-серверами При этом, поскольку основные ограничения накладываются сетью и дисковыми операциями, многопроцессорные ЭВМ не помогут решить проблему.

29 Информационно-поисковые системы. Сычев А.В г. 29 Дополнительные задачи Множественность отображения доменных имен и IP-адресов: зеркалирование, виртуальный хостинг, прокси-серверы. Абсолютные и относительные URL. Каноническая форма URL: Протокол Имя хоста и номер порта (если необходимо) Путь Исключение повторных закачек документа

30 Информационно-поисковые системы. Сычев А.В г. 30 Исключение повторных закачек документа Использование списка закачанных уже документов (URL). Для ускорения поиска используется хеширование (MD5: от 32 до 128 бит). Возможно раздельное кодирование имени хоста и пути.

31 Информационно-поисковые системы. Сычев А.В г. 31 Одновременная множественная закачка документов. Подходы. Многопоточность Выделяется фиксированное количество блокируемых сокетов Они используют общую очередь заданий – проблема одновременного доступа к общим структурам данных (блокировки) и фрагментирования операций чтения-записи на дисковых устройствах при одновременной записи документов и индексировании (издержки сериализации).

32 Информационно-поисковые системы. Сычев А.В г. 32 Неблокируемые сокеты и управление событиями Функции connect, send, recv возвращают значение немедленно без ожидания завершения сетевой операции. Одновременная множественная закачка документов. Подходы.

33 Информационно-поисковые системы. Сычев А.В г. 33 Обход веб-графа. Общие вопросы. Как обходить? Качество: лучшие документы в первую очередь. Эффективность: избегать дулирования Правила этикета: перегрузка веб-сервера, файл robots.txt Насколько много обходить, сколько закачивать? Как часто обходить?

34 Информационно-поисковые системы. Сычев А.В г. 34 Стратегии обхода веб-графа Приоритет в ширину. Приоритет в глубину. Эвристические методы (приоритет для более качественных ресурсов).

35 Информационно-поисковые системы. Сычев А.В г. 35 Ограничение доступа для робота Большинство поисковых систем придерживаются политики регламентирующей работу сетевого робота на веб-сайте. Данная политика допускает возможность исключения доступа робота к определенным ресурсам веб-сайта, но не гарантирует этого.

36 Информационно-поисковые системы. Сычев А.В г. 36 Два подхода: Файл robots.txt в корневом каталоге веб- сайта. Подробное описание приводится по адресу Мета тэги в HTML страницах, указывающие на необходимость исключения страницы при индексировании. Ограничение доступа для робота

37 Информационно-поисковые системы. Сычев А.В г. 37 Актуальность метапоиска Проблемы: Ограниченный охват поисковыми системами индексируемой части Веб. Разные ИПС индексируют, хотя и перекрывающиеся, но различные области Веб. Разные ИПС базируются на различных моделях информационного поиска, и как следствие, выдают разные результаты на один и тот же запрос. Возможно использования различных ИПС (в т.ч. и специализированных) для различных запросов, но большинство пользователей не ориентируются в них.

38 Информационно-поисковые системы. Сычев А.В г. 38 Возможное решение проблемы – метапоиск: Веб-сервер посылает запросы одновременно нескольким поисковым системам, каталогам и др. Полученные от них результаты собираются вместе Выполняется объединение результатов в общем списке Достоинства: больший охват и увеличение эффективности Актуальность метапоиска

39 Информационно-поисковые системы. Сычев А.В г. 39 Структура метапоисковой системы

40 Информационно-поисковые системы. Сычев А.В г. 40 Индексирование документа Процесс построения индекса ИПС Веб включает в себя: Анализ мета-тэгов, удаление стоп-слов, сведение слов к их словарным формам Определение местоположения слов (необходимо при поиске фраз) Вычисление весов с учетом частоты, положения в документе, шрифта и т.д. Принятие мер противодействия спаму

41 Информационно-поисковые системы. Сычев А.В г. 41 Преобразование полнотекстового документа в набор индексных терминов

42 Информационно-поисковые системы. Сычев А.В г. 42 Использование текста входящих гиперссылок Привлечение текста входящей гиперссылки для индексирования оправдано ввиду того, что: Этот текст может содержать более лаконичное описание, чем сам документ Может содержать более значимые термины, чем сам документ Представляет страницы недоступные для скачивания Представляет нетекстовые ресурсы: изображения, программы и др.

43 Информационно-поисковые системы. Сычев А.В г. 43 Выполнение запросов Обработка запроса: Нормализация (удаление стоп-слов, выделение именных форм и т.д.) Обработка сложных запросов (содержащих указание на дату, структуру, регион и др.) Обработка булевских выражений Ранжирование Анализ содержания документа (логическая модель, векторная модель и др.) Анализ гиперссылок Комбинированные алгоритмы

44 Информационно-поисковые системы. Сычев А.В г. 44 Литература A. Broder A taxonomy of Web search. SIGIR Forum, 36(2), Fall ( Ray Larson Principles of Information Retrieval. Слайды ( D.Carmel, A.Soffer Information Retrieval. Слайды. ( Soumen ChakrabartiMining the Web. Discovering Knowledge from Hypertext Data. Morgan Kaufmann Publishers, ( ) )

45 Информационно-поисковые системы. Сычев А.В г. 45 Mercator: A scalable, Extensible Web Crawler ( ml) ml R. Baeza-Yates, B. Ribeiro-Neto Modern Information Retrieval. Addison Wesley, ( ) Литература