СРЕДСТВА ПОИСКА ИНФОРМАЦИИ В ИНТЕРНЕТ

Сегодня все большее количество знаний, накопленных человечеством, хранится в компьютеризированных репозиториях, таких как Всемирная Сеть (World Wide Web) Проблема поиск определенной информации в неструктурированных репозиториях решается при помощи ПС Более 75% пользователей Интернет используют поисковые системы для доступа к информации

Репозиторий –множество документов, являющееся внутренним представлением универсума Универсум – множество документов, среди которых ведется поиск: –для ПС Интернета – это html-страницы из сети –для графической ПС – набор изображений –для академической ПС – собрание статей, книг и т.д. Репозиторий содержит документы с привязанными к ним соответствующими уникальными идентификаторами (DOCID)

Концепция ПС пользователь вводит поисковый запрос, состоящий из ключевых слов, относящихся к целевым документам, которые должны быть извлечены из репозитория Результат работы ПС – упорядоченный набор документов, которые считаются релевантными данному запросу

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

Основные составляющие ПС Компонент индексирования Задача – преобразование документов среды, в которой ведется поиск в адекватное представление ПС; –создание для создания внутреннего механизма представления данных Поисковый компонент Задача – программная реализация преобразования поискового запроса пользователя во множество документов из внутренней БД – формирование выдачи релевантных этому запросу

Формально компонент индексации может быть представлен функцией I :U R Множество U – универсум (содержит данные, среди которых будет вестись поиск) Множество R – репозиторий (внутреннее представление универсума U) Репозиторий имеет вид R ={ d | 1 d n}, где d - документ, d - соответствующий уникальный идентификатор этого документа ( DOCID)

Концепция индексирования на примере ПС для WWW Местонахождение веб-страниц обычно определяется по URL (Unified Resource Locator) При индексировании сети система обрабатывает набор URL различных документов и последовательно присваивает им DOCID 2. Данные страницы выгружаются из WWW и создается репозиторий (хранилище внутренних представлений каждой страницы) Количество выгружаемых страниц велико (в современных ПС около документов), но оно значительно меньше реального количества страниц в Интернете Основная задача ПС интернет-систем - определение адекватного подмножества U множества U

Поисковый запрос – введенная пользователем конечная строка, состоящая из терминов, являющихся атомарными словами, поиск которых ведется, и операторов, описывающих способы интерпретации терминов Эффективность поиска – количество возвращаемых документов для данного поискового запроса Пример Запрос «информационная экономика» состоит из терминов «информационная», «экономика» оператора логическое «И» означает поиск документов, содержащих оба термина

Логические операторы Равнозначные операции AND (пересечение) OR (объединение) NOT (дополнение) Примеры логических интерпретаций ПЗ

Результат работы компонента поиска – это информация, предоставляемая пользователю Элементы возвращаемого множества – все документы, которые ПС посчитала подходящими для включения в результирующий набор, представленные в порядке снижения значимости для пользователя Точность поиска – доля возвращенных документов, которые фактически релевантны Точность = |{Релевантные_документы} {Найденные_документы}| Количество возвращенных документов

Процесс получения результирующего множества документов на основании запроса и репозитория Шаг 1 Выбор множества претендентов из репозитория – все элементы в нем в какой-либо степени релевантны ПЗ Релевантность определяется приближенно, например, с использованием логического метода Шаг 2 Для каждого документа множества претендентов определяется его релевантность, а затем множество сортируется в порядке уменьшения релевантности При сортировке, некоторые элементы имеющие релевантность ниже порогового значения, могут исключаться из выборки

Логический метод определения множества претендентов Идея метода – результирующее множество ПЗ должно содержать только страницы, относящиеся ко всем уникальным терминам запроса Ответ за запрос формируется как результирующее множество после просмотра всех полученных документов, содержащих пересечение этих терминов Запрос «информационный бизнес» Термины «информационный» «бизнес» Пересечение терминов «информационный» «бизнес»

Основная задача компонента индексации – построение инвертированного индекса Индекс – структура данных, в которой термам в соответствие ставятся документы (DOCID), содержащие эти слова В ПС изображений как расширение термин «лицо» может быть привязан ко всем документам, которые классифицируются как содержащие лица

Пример инвертированного индекса ТерминDOCID документов, содержащих данный термин информационный34, 675,453,1796,6757, … бизнес7895, 896, 854, 76, … Декомпозиция запроса в древовидную структуру: Листья – термины (атомарные слова или фразы) Узлы – логические операторы Получение множества потенциально релевантных документов выполняется путем логического сравнения

Поисковые системы имеют многоуровневую организацию и состоят, как правило, из программ: 1.Spider (паук) 2.Crawler (сборщик) 3.Indexer (индексатор) 4.Database (база данных) 5.Gateway (шлюз)

Spider (паук) – браузероподобная программа планомерно просматривает и скачивает Web- страницы (считывает HTML-код) Crawler (сборщик) – сканирование Интернет- ресурсов, поиск изменений: просмотр локальных ссылок Web-страницы, анализ перекрестных ссылок и т.п.

Indexer (индексатор) - анализирует скаченные пауком страницы, определяет их тематическую принадлежность, актуальность, популярность, разбивает страницу на части, анализирует ее элементы: заголовки страниц, ссылки, тексты, структурные элементы, стилевые элементы и т.д. Затем индексирует ресурсы (строит БД по ключевым словам и сохраняет их в удобном для поиска виде)

Database (база данных) – хранилище скаченных и обработанных индексатором страниц. Требует огромных ресурсов для хранения и эффективных алгоритмов доступа Индекс поисковой машины - база данных, с помощью которой можно узнать, на какой именно странице в Сети можно встретить данное слово.

Gateway (шлюз) или Search engine (Results engine) – поисковая машина – принимает запросы от пользователей, анализирует их и извлекает результаты поиска из БД для отображения по запросу пользователя и предоставляет интерфейс для просмотра и уточнения результатов

Этапы формирования индекса 1.Индексирование - осуществляется при помощи сетевых роботов - спайдеров (от англ. spider – паук) 2. Занесение индексов в БД ПС При анализе HTML-страницы большинство ПС фиксирует слова, картинки, ссылки, скрипты и другие элементы При отслеживании слов на странице фиксируется их наличие и местоположение: в заголовке (title), подзаголовке (subtitles), в метатэгах (meta tags) и др. Метатэги позволяют владельцам страниц определить ключевые слова, тематику, по которым индексируется страница и ориентируют поисковую систему при выборе из нескольких значений слова единственно правильное

Поисковые системы Паук (поисковый робот) HomePage наука техника образование музыка книги музеи вставки транспорт связь отдых выставки религия экономика рестораны Построение списка слов и указателей на месте их обнаружения Построение индекса на основе алгоритма взвешивания слов Упаковка данных Индекс Сохранение данных для использования

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

ОСНОВНЫЕ ПОНЯТИЯ И ТЕРМИНЫ ПОИСКА В ИНТЕРНЕТ 1. Релевантность ( анг. relevant - относящийся к делу) Документ, найденный по запросу и содержащий искомую информацию, называется релевантным, иначе - нерелевантным (шумовым)

2. Точность поиска - доля релевантных документов в общем числе найденных Точный поиск пользователь быстрее находит нужные документы меньше «шума» Пример - все выданные по запросу документы относятся к делу точность 100%; - все документы шумовые точность поиска 0% Запрос: «Красная площадь» найдено всего 150 док., 70 - содержат словосочетание В остальных присутствуют слова запроса («красная стена окружает площадь») точность поиска 70/150 (~0,5)

Rambler достигает точность за счет использования различных технологий на всех этапах обработки и поиска информации: –Распознавание грамматических омонимов (-) увеличение размера индексной базы и снижение точности поиска –Синтаксический анализ при индексации и обработке запроса учитывается, что в тексте несколько слов подряд написано с большой буквы: Петр Петрович; Алтайский Государственный Университет –Выделение устойчивых обозначений и поиск их как отдельных лексических единиц в Рамблере реализована система распознавания конструкций: C++, б/у, п/п-к.

3. Полнота поиска - доля найденных релевантных документов в общем количестве релевантных документов Пример В Интернет имеется 100 страниц, содержащих словосочетание «Красная площадь» По запросу из них найдено 70 полнота поиска 0,7 Полнота поиска зависит от работы системы сбора и обработки информации система должна быть масштабируемой Рамблер выполняет параллельное исполнение задачи произвольным количеством машин

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

Точность и полнота ответа А на запрос при поиске в коллекции документов С, R - множество истинно релевантных документов

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

5. Поиск по комбинациям слов - поиск в текстовых БД отдельных слов и их логических комбинаций Булевый поиск – поиск по логическим комбинациям ключевых слов (с помощью операндов AND, OR, NOT) OR - расширит область поиска и увеличит полноту NOT - повысит точность поиска за счет нахождения документов, которые содержат одни слова запроса и не содержат другие «+» поиск по нескольким словам или по их логической комбинации понижает уровень шума повышает точность поиска

Расстояние между словами - повышает точность если в искомом словосочетании порядок слов обычно сохраняется Пример Запрос «Красная площадь» указать расстояние для повышения точности (2, Красная площадь) фильтрация документов, в которых слова красная и площадь не расположены рядом, а разбросаны по тексту Поиск в найденном - увеличение точности

ОператорЗначение оператораПример пробел или & логическое И (в пределах предложения) информатика программирование &&логическое И (в пределах документа) информатика && (программирование) |логическое ИЛИфото | фотография | снимок | +обязательное наличие слова в найденном документе +быть или +не быть ( )группирование слов(культура|история)(США|Китая) ~Оператор НЕ (в пределах предложения) банк ~ налоги ~~ или -бинарный оператор И НЕ (в пределах документа) путеводитель по Парижу ~~ (агентство | тур) /(n m)расстояние в словах (-назад +вперед) поставщики /2 кофе « » поиск фразы«красная шапочка» Операторы языка запросов

6. Ранжирование результатов поиска - найденные по запросу документы взвешиваются на предмет близости к запросу (ранжируются) и показываются в порядке уменьшения этой близости Для вычисления веса (ранга) учитываются: - общее количество вхождений слов запроса в документе - расположение слов запроса в документе (в заголовках, названии документа, наличие компактных групп, соответствие грамматических форм и т. д.) - формы слов запроса - приоритет вхождениям, в которых слова имеют тот же падеж, число, склонение и т.д. Пример Запрос «Красная площадь», а не «Красной площадью», кроме точного совпадения, выделяются 2 группы форм слов: близкие - изменения по падежам, склонениям, спряжениям, числам и родам далекие - причастия, деепричастия и т.п. При ранжировании преимущество - близким формам слов запрос

ОператорЗначение оператораПример запроса $title (выражение)поиск в заголовке$title (CompTek) $anchor (выражение)поиск в тексте ссылок$anchor (CompTek | Dialogic) #keywords=(выражение)поиск в ключевых словах#keywords=(поисковая система) #abstract=(выражение)поиск в описании#abstract=(искалка | поиск) #image="значение"поиск файла изображения#image="tort*" #hint=(выражение)поиск в подписях к изображениям #hint=(lenin | ленин) #url="значение"поиск на заданном сайте (странице) #url=" Поиск в определенных элементах гипертекстового документа

-Относительная частота - отношение количества вхождений слов запроса в документ к общему количеству слов в документе В документе из 100 слов словосочетание встречается 10 раз документ более соответствует запросу, чем если оно встречается 10 раз в документе из 20 тысяч слов - Расстояние между словами запроса - если запрос состоит из нескольких слов, то в найденных документах оценивается, насколько близко друг от друга расположены эти слова Преимущество - документам, в которых слова запроса находятся ближе друг к другу (они с большей вероятностью связаны между собой) Пример Слово «Красная» расположено в тексте на 5й позиции слово «площадь» - на 650й более вероятно, что в документе речь идет не о Красной площади

-Посещаемость документа – составление рейтингов Преимущество - более посещаемым ресурсам -Ссылочный вес документа - при ранжировании учитывается ссылочный вес страницы, рассчитанный на основании учета гиперссылок, содержащих слова запроса Пример на документ словами «Красная площадь» ссылается большое количество авторитетных страниц отдается приоритет по запросу Красная площадь. -Контекстный поиск - запрос или его часть, взятые в кавычки, обрабатываются с учетом всех стоп-слов, форм, порядка, знаков препинания повышает точность поиска, но уменьшает его полноту (если часть, заключенная в кавычки, неточна, нужный документ найден не будет)

Охват - объем базы индексов ПС (измеряется количеством уникальных URL и уникальных документов) Скорость обхода скорость формирования индексов

Основные показатели качества поисковой системы: 1.Соотношение полнота-точность. 2.Система должна уметь индексировать документы заранее, в режиме off-line и быстро пополнять индекс в режиме on-line 3.Проводить поиск по комбинациям слов 4.Помнить координаты слов в документах 5.Ранжировать найденные документы по их релевантности

6. Узнавать различные кодировки и форматы 7. Отличать прописные и строчные буквы, даты и числа, распознавать слова во всех грамматических формах 8. Выделять предложения 9. Иметь список (списки) шумовых слов и выражений

Проблема ранжирования Ранжирование зависит от окружения универсума, из которого извлечены документы ПС Интернет сталкиваются с проблемой спама – ранжирование в неконтролируемой среде Функция ранжирования учитывает внешние и внутренние факторы: контент, его размещение на странице, логические связи страниц и др.

Методы определения релевантности документов 1.Логический метод ранжирования 2.Ранжирование на основе вектора документа 3.Реалистические модели ранжирования

Логический метод ранжирования - тривиальный Значения внешних факторов всех страниц считается одинаково – все страницы, имеющие любое отношение к терминам, которые ищет пользователь, одинаково релевантны ПЗ Результирующее множество – множество претендентов, отсортированных по убыванию значимости внутренних факторов страниц

Ранжирование на основе вектора документа 1. Документ имеет высокий рейтинг по термину ПЗ, если термин часто встречается на странице Частота термина (TF) – отношение количества появлений термина в документе к размеру документа в некоторых единицах измерения (например, количество слов или байтов) 2. Определение значимости терминов – нахождение IDF (инверсивная частота документа – оценка количества информации, свойственной термину) Если термин часто встречается в документах репозитория, то высока вероятность, что он общий и поиск ресурса с помощью ПС не даст хороший результат и он получает низкий IDF

Недостаток модели вектора документа – ошибки при подсчет частот вхождения терминов Если термин часто встречается в документах репозитория, то высока вероятность, что термин «общий» и поиск ресурса с помощью ПС не даст хороший результат термин получает низкий IDF

Можно рассматривать поисковый запрос как документ, в котором каждый из термов запроса встречается только один раз υ – это L-вектор для каждого S – размер запроса, представленный в тех же единицах измерения, что и размер документа) Можно рассматривать это как вектор документа для запроса, т.к. неизвестно, как пользователь задает приоритеты термам в его запросе и весовые коэффициенты термам будут присвоены в соответствии с их IDF

Пример применения векторной модели поиска для запроса «связный граф» В ПС ~ 20·10 9 документов, в которых терм «связный» встречается в 7·10 9 документах, терм «граф» в 150·10 6 документах Значения IDF будут следующими: IDF(связный) = 0.46 IDF(граф) = 2.1 Используя количество слов как единицу измерения, получаем размер запроса, равный 2, и вектор запроса

IDF, вычисленные по запросу «Цепь Маркова» ПС Yahoo! (Репозиторий~20*10 9 ) Обобщение приводит к снижению полезной информации в документах ТерминКоличество вхождений IDF Теорема Перрона8 2706,38 Цепь Маркова ,28 Теория вероятностей ,26 Математика ,33 Наука ,39

Реалистические модели ранжирования (Использование улучшенной модели вектора документа) 1. Вводятся корректирующие коэффициенты: – Учет расположения терминов относительно друг друга – Измерение корреляции между терминами и аспектами форматирования страницы (шрифт и размер шрифта терминов) 2. Функция Okapi BM25F – ранжирующая функция разбивается на части относительно полей документа: заголовок, ссылки, основной текст и т.д.

Один из популярных методов ранжирования Okapi BM25, где рейтинг документа вычисляется на основе формулы: обычно, k=1.2, b=0.75, τ d – длина документа τ (т.е. количество слов в документе) d – средняя длина всех документов Данная функция пытается нормализовать рейтинги документов, исходя из их длины: большой документ может содержать гораздо больше повторений отдельных термов, чем маленький, и быть менее релевантным запросу

Оценка качества документа на основе цитирования Метод рейтинга цитируемости - метод оценки качества документов, основанный на ссылках между документами Цитата - это ссылка с одной страницы на другую без атрибутов (т.е.не учитывается размещение ссылки в документе, ее формат и т.д.) Пример – список цитированной литературы в научных работах – гиперссылки между html-страницами Задача рейтинга цитируемости - определение качественной оценки документа на основании количества и качества ссылающихся на него документов

Ссылочную структуру можно представить в виде графа Репозиторий состоит из n документов, имеющих уникальные идентификаторы DOCID, последовательно присвоенные документам и находящиеся в интервале V = [1,n]. Цитата (ссылка) – упорядоченная пара документов (i, j) V 2 Ссылками называются исходящая связь документа i и входящая связь документа j

Сформировав из всех ссылок между документами из V множество E, получаем ориентированный граф G = (V,E) с вершинами, являющимися ссылками (граф ссылок) Определение Пусть G = (V,E) где V - конечное множество вершин графа, E V *V, и i V Тогда множество входящих связей будет обозначаться как I (i), а множество исходящих связей как O(i), т.е. Определение Документ i V называется висячим, если O(i) =

Пример простого рейтинга цитируемости q(i) = const I (i) документу i присваивается рейтинг прямо пропорциональный числу документов, ссылающихся на него На графе простой подсчет входящих связей для каждого узла формирует представленные показатели рейтинга (после нормализации по общему числу связей в графе) I(i) |I(i)| Рейтинг цитирования =

Недостаток метода цитирования – всем цитатам присваиваются равные весовые коэффициенты Т.е. цитата автора, на которого имеется много ссылок из других ресурсов, приравнивается цитате автора, не имеющего ссылок с других ресурсов. В среде Интернет, такая оценка неадекватна, т.к. основная задача данного метода – простой подсчет огромного количества входящих ссылок со страниц с низким качеством

Вычисление рейтинга страницы по алгоритму PageRank Рейтинг цитируемости (подсчет ссылок на страницу из разных источников) дает приближенное значение важности (качества) страницы Алгоритм PageRank расширяет этот подход: – подсчитывает количество ссылок (считает значимость ссылок с каждой из страниц равной) – упорядочивает страницы по количеству ссылок, содержащихся в них

При вычислении рейтинга страницы A по PageRank также учитываются рейтинги страниц T 1...T n по PageRank (PR( T k ) Вывод: рейтинг документа зависит от качества ссылающихся на него страниц PageRank определяет распределение вероятностей для каждой страницы так, что сумма рейтингов PageRank всех страниц равна 1 PR(A) может быть вычислен с использованием простого итеративного алгоритма и будет соответствовать главному собственному вектору нормализованной матрицы ссылок Например, рейтинг PageRank для 26 миллионов веб-страниц может быть вычислен за несколько часов на рабочей станции средней мощности

Определение рейтинга страницы по PageRank Пусть на документ A ссылаются страницы T 1...T n d - коэффициент затухания в интервале (0;1), обычно d=0,85 (коэффициент d необходим для ограничения количества переходов по ссылкам в графе документов) Функция C(T) определяет количество исходящих со страницы T ссылок Рейтинг страницы A по PageRank определяется формулой

PR как модель поведения пользователя Гипотеза PR Пользователь с заданной случайным образом стартовой страницы переходит по ссылкам на другие страницы и никогда не возвращается на предыдущую, иногда прерывая переход по ссылкам и начиная снова с другой случайной страницы PR страницы – вероятность посещения пользователем данной страницы Коэффициент затухания - определяет как скоро пользователь начнет процесс заново, перейдя на случайную страницу (может быть присвоен как группе страниц, так и отдельной странице)

На повышение PR страницы влияют также: – количество ссылающихся на нее страниц с высоким PR – ссылки с домашней страницы Yahoo! – результаты анализа рекурсивных ссылок

В настоящее время PageRank не используется непосредственно в алгоритме Google Для ранжирования Google использует тематический PageRank, учитывающий только ссылки с тематически связанных страниц Детали этого алгоритма известны лишь разработчикам Google Узнать значение PageRank для любой веб-страницы можно с помощью Google ToolBar, который показывает значение PR в диапазоне от 0 до 10 (не точное значение PR, а диапазон PR, в который попадает сайт, номер диапазона (от 0 до 10) определяется по логарифмической шкале)

Пример страница имеет точное значение PR, известное только Google Для определения нужного диапазона и вывода информации на ToolBar используется логарифмическая шкала Реальное значение PR Значение ToolBar и т.д. Все цифры условны, но демонстрируют, что диапазоны PR, показываемые в Google ToolBar, не равнозначны Например, поднять PageRank c 1 до 2 легко, а с 6 до 7 сложно

Практическое использование PageRank 1. Быстрая оценка уровня раскрученности сайта PR не дает точной информации о ссылающихся страницах, но позволяет быстро определить уровень развития сайта Для англоязычных сайтов: – PR 4-5 – имеет большинство сайтов средней раскрученности – PR 6 – очень хорошо раскрученный сайт – PR 7 – величина, недостижимая для обычного разработчика – PR 8, 9, 10 – встречаются только у сайтов крупных компаний (Microsoft, Google и т.п.) Знание PR можно использовать при обмене ссылками, для того чтобы оценить качество предложенной к обмену страницы и в других подобных ситуациях

2. Оценка уровня конкуренции по поисковому запросу PR не используется непосредственно в алгоритмах ранжирования, но позволяет косвенно оценить конкурентность заданного запроса Пример Если в выдаче ПС стоят сайты с PR 6-7 сайт с PR 4 имеет очень мало шансов оказаться в Тор Значения PR, показываемые в Google ToolBar пересчитываются редко (раз в несколько месяцев), поэтому ToolBar показывает устаревшую информацию, т.е. ПС Google учитывает изменения во внешних ссылках быстрее, чем они в Google ToolBar.

Новый алгоритм поиска Яндекса «Снежинск» Основные изменения – способ учета стоп-слов (выросло качество ранжирования по запросам со стоп-словами) – новый подход к машинному обучению – расширен тезаурус путем автоматического анализа проиндексированного корпуса текстов Например, появились сочетания слов, которые в раздельном написании означают то же самое, что и в «склеенном» виде (теперь по запросу [авто ваз] найдутся страницы и со словом «автоваз»)

Новый алгоритм Яндекса Снежинск Алгоритм на стадии тестирования и натсройки Первые выводы: 1. Увеличился вес старых ссылок. 2. Не смотря на увеличение веса старых ссылок в выдаче присутствуют более молодые домены. 3. Очень важен хороший качественны и уникальный контент на сайте. 4. Роль внутренней перелинковки снизилась. 5. Снизилась роль Википедии (Википедия теперь на более низких местах по многим запросам). 6. Большую роль играет в названии сайта ключевое слово (написанное в транслитерации). 7. Снизилась роль количества знаков для целевых страниц. 8. Снизился коэффициент плотности ключевых слов для целевых страниц. 9. По высокочастотным запросам целесообразно продвигать только главную страницу сайта.

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

Особенности обработки анкерного текста в Google 1.Анкеры содержат более точное описание страниц, чем сами страницы 2. Анкеры могут описывать документы, которые не могут быть проиндексированы системой без графического интерфейса (изображения, приложения и БД), т.е. возможно отбирать веб- страницы, которые фактически не были проиндексированы Неиндексированные страницы могут вызвать проблемы, т.к. они не проверялись на точность до представления пользователю В таких случаях ПС никогда не сможет вернуть страницу, ко- торой фактически не существует, но имеются гиперссылки, указывающие на нее

Привязка анкерного текста к странице, на которую он ссылается, впервые была реализована в World Wide Web Worm именно из-за того, что данный подход позволяет находить информацию, представленную не в виде текста и расширяет возможности стандартной поисковой системы В Google используют анкерную привязку в основном для того, чтобы получить наиболее качественную выборку Эффективное использование анкерного текста проблематично с технической точки зрения - нужно обрабатывать огромное количество информации Например, для репозитория, содержащего 24 милн. страниц, было проиндексировано более 259 миллионов анкеров

Поисковые системы в Интернете проблемы и тенденции развития Тенденции 1. Сделать поиск более точным изучать истории запросов и поведения пользователей: – Когда появилась страница или ссылка? – Какие запросы задавал пользователь ранее? – Какие результаты он выбирал? различать настоящие и спамерские страницы

2. Использовать социальную структуру Интернета поиск новых источников социальных знаний Пример Проект «MyWeb 2.0» каталога Yahoo! планирует использовать «ручную» работу пользователей для улучшения качества поиска. Пользователи могут: –сохранить понравившуюся страницу, –пометить ее тэгом, –запретить в поиске плохой документ –Yahoo!

3. Глубокий анализ текстов и запросов Анализ фактологической информации в тексте страницы: –имена, фамилии, –адреса, телефоны, – цены и пр. Классификация типа и жанра текста страницы Понять что на самом деле хотел узнать человек, задавая в запросе конкретное словосочетание Пример, Яндекс.Новости показывают список персон, упомянутых в текстах новостей, что позволяет быстро понять смысл новостного сюжета

4. Тематическая кластеризация результатов повышенная настраиваемость интерфейса –подключение любых OpenSearch-поисков –настройки представления выдач результатов Пример Поисковый сервис A9.com интернет-магазина Amazon Для поиска по WEB на сайте используется Google Одновременно A9 запрашивает результаты поиска в базе текстов книг Amazon, а данные о сайтах, берутся из систем, принадлежащих Amazon: Alexa, кинобазы данных IMDB и др. возможность поиска узкоспециализированных ресурсов Многочисленные исследования, показывают, что даже самая полная база одной ПС охватывает не более 40% открытой части Интренет Пример Сервис Яндекса «Искать в других ПС»

5. Развитие бизнес-инструметов Рост числа предложений и объема информации требуют новых сервисов поиска и агрегирования информации – ресурсы новостных сайтов агрегированы в сервис Яндекс.Новости: кластеризация сюжетов показ новостной картины дня выбор новостных источников – объединение интернет-магазинов сервис Яндекс.Маркет: выбор и сравнение товаров и цен технология Яндекс.Гуру - выбор сложных товаров, не углубляясь в технические детали каждый месяц более 1,5 миллионов человек выбирают на Маркете товары из 1,5 миллионов предложений от 800 электронных магазинов.

Бизнес-коммуникации и электронный документооборот –Мобильные устройства –технология Wi-Fi –ЭЦП Поисковая реклама –возможность выйти на целевую аудиторию –высокая результативность, с точки зрения рекламодателя –увеличение возможных площадей для показа рекламы –упрощение работы рекламодателя за счет инструментов, позволяющих автоматически отсечь неэффективную рекламу –контроль бюджета и др.

Рекомендации по поиску 1. Проверять орфографию 2. Использовать синонимы 3. Составлять запрос более чем по одному слову 4. Не использовать большие буквы 5. Использовать знаки «+» и «-» 6. Использовать язык запросов 7. Использовать возможности «искать в найденном», «найти похожий документ» 8. Использовать поиск в зонах для картинок и фотографий

Советы от Александра Садовского, руководителя отдела веб-поиска «Яндекс» 1.Будьте проще 2.Не пытайтесь описать свою потребность в запросе полностью, поисковая машина никогда не станет психотерапевтом. Просто назовите объект поиска в запросе: [экслер], [спорт экспресс] или [работа] Не нужно писать [сайт писателя Алексея Борисовича Экслера] или [высокооплачиваемая работа в офисе]. 3.Если задача - найти редкий текст, представьте себе, как выглядит идеальный ответ и какие слова он содержит. Задайте эти слова в качестве запроса. Предположим, вы хотите найти скорость, с которой летает сокол-сапсан. Задайте запрос [сокол сапсан летает «км/ч»]. Яндекс умеет давать хорошие ответы и на запросы вида [что такое перцепция], [кто такие Нибелунги], [как будет по-французски булка] [Бетховен та-да-да-да - это что?], но понимание, что именно вы хотите найти, полезно, даже если вы решите оставить запрос на естественном языке. Кубок Яндекса по поиску ( и наблюдение за лучшими игроками показало, что они задают запросы, похожие на запросы других пользователей, но при этом умеют быстро выбирать правильные документы среди найденных, лучше «читают». Учитесь наблюдать за поисковой системой, ее реакцией на ваши запросы, и она обязательно ответит вам взаимностью!

Наиболее популярные зарубежные системы Google Alta Vista Excity Наиболее крупные российские системы Апорт Яндекс Ремблер

Русские поисковые системы и каталоги Rambler Апорт! Yandex Ау! Lycos Punto Лупа Созвездие Интернет Россия в Сети Weblist Улитка Релком Diamond Tree Иван Сусанин List

Зарубежные поисковые системы и каталоги AltaVista Excite HotBot InfoSeek InfoSeek Ultra LinkStar LinkMaster Lycos Magellan OpenText Switchboard Webcrawler All 4 One Yahoo European Directory EZ-Find Internet Directory Web Yellow Pages Cyberlands Web Search All In One Search Page Internet Sleuth ISP Internet Yellow Pages W3 Search Engines Home Page Directory The WWW Worm WebSearchWebSearch·

Яndex Создана компанией CompTek International, работает с сентября 1997 г. 1,5 млн. российских и зарубежных серверов 200 млн. оригинальных документов актуализация базы еженедельно единственная российская ПС индексирующая документы в форматах PDF, RTF, DOC

Rambler Российская поисковая система работает с октября 1996 г. В 2002 г. проведена модернизация программно-аппаратной части ПС и сегодня занимает 2-е место после Yandex по объему БД – около 120 млн. страниц Индексирует 6,9 млн. страниц в сутки Поиск по новостям каждые 2 часа

Поисковая система г. - студенты Стэнфордского университета Ларри Пейдже и Сергей Брин создали новую поисковую систему Google 2000 г. - подписано соглашение об обслуживании поисковых запросов сайте Yahoo.com

Поисковая система Создана студентами Стэнфордского университета в 1998 г. «+» самая большая широта охвата среди всех поисковых систем -индекс составляет более 8 млрд. страниц «+» за сутки индексируется 5 млн. новых и обновленных страниц «+» актуализация базы каждые 28 дней

Поисковая система Создана студентами Стэнфордского университета в 1998 г. В 2000 г. подписано соглашение об обслуживании поисковых запросов сайте Yahoo.com

Поисковая система Создана студентами Стэнфордского университета в 1998г. «+» самая большая широта охвата среди всех поисковых систем -индекс составляет более 8 млрд. страниц «+» за сутки индексируется 5 млн. новых и обновленных страниц «+» актуализация базы каждые 28 дней

Поисковая система Google переведен на 90 языков мира. Ежедневно ПС обрабатывает более 200 млн запросов и 6 млрд страниц. Основной доход поисковых систем – контекстная и банерная реклама.

«+» индексирует документы в форматах HTML, PDF, PS, DOC, XLS, PPT и др. «+» дает хорошие результаты поиска по тривиальным словам: Автомобили (Cars), Интернет (WWW, Internet), Игры (Games) и др. «+» платный сервис - поиск труднодоступной информации не роботом, а человеком (2,5$ за ответ)

Система Google при генерации списка ссылок сначала выдает ссылки на те Web-страницы к которым из других документов ведет наибольшее число ссылокGoogle

AltaVista ( Основана в декабре 1995 г. эта ПС Имеет возможность настройки на 26 языков, включая русский С 2002 г. имеет в составе интеллектуальный модуль AltaVista куплена корпорацией Yahoo! и является ее дублером (т.е. поиск ведется из БД Yahoo!)

Yahoo! ( Создана Дэвидом Фило и Джерри Янгом в апреле 1994 г. Одна из самых первых ПС Сочетает поиск по ключевым словам и поиск с помощью иерархического дерева разделов Тематические разделы каталога пополняются 150 редакторами (используется человеческий фактор)

The Electric Library Принадлежит Infonautics Corp Вход для авторизованных пользователей Предлагает поиск полнотекстовых электронных версий : более 150 газет, нескольких тысяч журналов, 2000 книг, поиск карт, фотографий и др.

Апорт! Поисковый сервер компании Агама Работает с февраля 1996 г. Объем индекса 70 млн. документов Использует двуязычную технологию поиска, схожую с AltaVista Качественный поиск MP3-файлов Единственная российская система для качественного поиска аудиофайлов

Апорт! Единственный профессионально поддерживаемый российский справочник интернет-ресурсов Наиболее эффективен при поиске серверов российских учреждений, для выявления сайтов однородных объектов, имеющих разные названия: известных футболистов, коллекции географических карт, кадровых агентств и др.

@Rus Каталог, до июля 1999 года назывался Ау! (Копия ПС Апорт!) «+» Имеет качественно скомпонованный и постоянно пополняемый рубрикатор

Каталог (бывший каталог «Созвездие Интернет» ) Охватывает около 400 серверов Возможность усечения терминов Содержит названия и краткие характеристики серверов Привлекательная графика Небольшая зона поиска Слабая иерархия

Метапоисковые системы MetaCrawler Создана Go2Net, Inc. в 1996 г My Starting Point - Создання в 1996 г. компанией MyStartingPoint.com, Inc. Использует ресурсы 12 основных и более 150 дополнительных поисковых ресурсов

C4 - Владелец – крупнейшая Интернет- компании Cyber Network, Inc. Использует ресурсы 40 крупнейших ПС - по различным областям поиска

Поисковые системы и электронные библиотеки До сих пор различают поисковые системы и электронные библиотеки, хотя понятия эти два значительно пересекаются

1993 г. Началось создание электронных библиотек (electronic libraries) Правительство США объявило о важности переноса как можно большего количества «бумажной» информации в цифровой формат

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

Поиск людей - интернет-коллекция сведений о людях России «Всероссийское Генеалогическое Древо» >> - База данных лица России

- поиск людей - информационно- поискового портала Адресное.ру - бюро находок Гуманитарный проект «Поиск 24» разработан и запущен в 2001 г. фирмой K&D (Hannover), специализирующейся на этническом маркетинге в русскоязычном сегменте Германии

- поиск одноклассников - проект был запущен в начале марта 2006 года и рассчитан на самую широкую русскоязычную аудиторию, как в России, так и за ее пределами, количество пользователей

- биографии и жизнь Людей

– информация об известных людях

Социальный поиск на mail.ru Современные проблемы поисковых систем Нежелательные результаты в выдаче Неполнота выдачи Неестественный язык запросов Общение с машиной, а не с живым человеком –Часто нужна информация, которой вообще нет на сайтах. Нужно спросить совета, или попросить кого-то поделиться опытом. Иногда нужно найти знающих людей.

Механизм социального поиска Пользователь может: Задать вопрос, поместив его в общую базу данных. Просмотреть существующие вопросы, распределенные по категориям. Ответить на любой открытый вопрос. Оценить вопросы и ответы других пользователей. Лично пообщаться с любым пользователем

Необходимые условия работы Критическая масса пользователей Система индикаторов доверия Сообщество постоянных пользователей с высокими показателями Механизм мотивации пользователей почти 24 миллиона пользователей Mail.Ru сбалансированная система КПД десятки тысяч продвинутых участников с высоким рейтингом система баллов и рейтингов

Типы пользователей социального поиска Обычные пользователи Отвечают на вопросы с главной страницы и на вопросы легких категорий. Качество ответов – среднее. Среднее время появления ответа – несколько секунд. Специалисты Предпочитают отвечать в своих сферах компетенции. Качество ответов – высокое. Среднее время появления ответа – несколько минут. Профессионалы Отвечают только в «своих» категориях. Качество ответов – очень высокое. Среднее время появления ответа – часов минут.

Типы пользователей

Типы поисковых запросов Навигационные (~30%) пользователь ищет конкретный сайт (к примеру, сайт компании). Примеры: Samsung, Конференция по оптимизации, Райффайзенбанк, Sting. Информационные (~50%) пользователь ищет просто информацию о чем-то. Эта информация может быть представлена на разных сайтах. Сам сайт в данном случае не играет роли. Примеры: Приколы, рецепты десертов, фотографии бабочек Транзакционные (~20%) пользователь сообщает поисковой машине, что хочет найти сайты содержащие конкретные объекты и возможность произвести с этими объектами конкретные действия: Примеры: Музыка mp3, купить книгу, скачать программу, загрузить заставку для рабочего стола.

Навигационные и транзакционные запросы Навигационные запросы Здесь машинный поиск справляется, безусловно, лучше за очень редким исключением. Например, с запросом «официальный сайт BMW» русские поисковики справились плохо. Транзакционные вопросы Социальный поиск дает доступ к опыту других пользователей. Социальный поиск дает более чистые результаты Например запросу «где бесплатно скачать MP3». В выдаче машинного поиска пользователь станет жертвой борьбы оптимизаторов за трафик. Социальный поиск даст реальные результаты.

Информационные запросы Преимущества социального поиска: Можно сформулировать запрос максимально точно на понятном языке Нет необходимости переходить на другие сайты Есть возможность связаться напрямую с человеком, ответившим на вопрос Пользователи сообщают даже больше чем нужно Реальные примеры запросов с проекта Что с машиной: стреляет в карбюратор? Что такое коллаген? Как быстро вылечить насморк? Почему человек хочет спать? На сколько процентов человек состоит из воды?

Человеческие запросы Реальные примеры с проекта А кто работает курьером, и расскажите, как вам работается? Какое соотношения ват к амперам, если аппарат потребляет 1000вт. сколько это ампер? Скажите, как выставить диафрагму и выдержку для съемки дома днем, и для съемки дома вечером при включенном свете? Какие витамины, и как часто вы употребляете и какие улучшения заметили? Кто был зимой в Хургаде? Там холодно? Ветрено? Купаться можно? Темнеет рано?

Услуга «Тематические эксперты» Эксперт: получает уведомления о всех вопросах своей категории. имеет право отвечать неограниченное количество раз. имеет право упоминать свои товары и услуги, если они соответствуют вопросу. К ответам экспертов добавляется: –ссылки на сайт (не закрываемые тегами NOINDEX и NOFOLLOW). –короткий рекламный текст. –логотип.

Сейчас на проекте Более 900 тысяч вопросов (из них 16 тысяч открыты и ждут ваших ответов). Более 8 млн. ответов. Более 1,5 млн. зарегистрированных пользователей. Каждый день на проекте задается более 17 тысяч вопросов и дается около 160 тысяч ответов.

Инструменты поиска в Интернете Разная информация Разные инструменты поиска поисковые системы, индексированные каталоги (рубрикаторы), рейтинги, метапоисковые системы, тематические списки ссылок, онлайн-энциклопедии и справочники

Индексированные каталоги Каталог - данные, структурированные по темам в виде иерархических структур Тематические разделы первого уровня определяют наиболее популярные темы: спорт, отдых, наука, магазины и т.д. Для уточнения области поиска в каждом разделе есть подразделы

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

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

Виды каталогов Общего профиля, например, List.ru ( Специализированные, например, Рейтинги - сортировка в каталоге ресурсов по популярности, например, рейтинг Rambler Top 100

Российские каталоги: List.ru Lycos Апорт Catalogue3 Russia on the Net Весь Русский internet Rax.ru Search Centre Peeps.ru Look.ru LinkMaker Elestim Город Иван-Сусанин Закладки Интернет Столица Улитка Сокровища Интернет

Рейтинги похожи на каталоги, но сайты в нем находятся в зависимости от их посещаемости - наиболее посещаемые наверху, наименее посещаемые внизу рейтинга Для определения посещаемости рейтинги предоставляют по почте коды счетчика в которые необходимо вставить в свой сайт

Российские рейтинги: Rambler's top 100 TopList SpyLOG HotLog Mafia`s Top100 TopCTO KMiNDEX One.Ru SUPERTOP

Russia on the Net Первый каталог ресурсов о России в Интернете Открыт в сентябре 1995 г. и поддерживается крупнейшим российским провайдером - компанией Demos

- отраслевая агропромышленная поисковая система - отраслевой специализированный каталог - каталог детских ресурсов - Поисковая система файлов MP3

Ранжирование ссылок в рейтинге Rambler Top 100 хосты – количество посещений с уникальных IP-адресов, которые учитываются для постановки рейтинга посетители - количество уникальных посетителей в единицу времени хиты – количество заходов на сайт за определенный промежуток времени

Тематические коллекции ссылок – это списки, составленные группой профессионалов или коллекционерами Очень часто узкоспециализированная тема может быть раскрыта одним- единственным специалистом лучше, чем группой сотрудников крупного каталога

Подбор доменного имени Компания имеет односложное название и реализует в Сети свой сервер, то его имя с большой долей вероятности имеет формат, При поиске малоизвестной компании подбор адреса может конкурировать с другими приемами поиска

Российские представительства некоторых западных компаний Тематические сайты