Построение поисковых индексов Автор: Елисафенко М.Е. гр

Задача Находить информацию в интернет сети по запросу пользователя

Задача Поиск в сети с миллиардами узлов

Задача Поиск фразы в книге

Сохранение web-страниц Обработка информации Построение индекса Занесение индекса в БД Обновление индекса Выдача запросов из БД по индексу Схема работы поисковых машин

Сохранение web-страниц Обработка информации Построение индекса Занесение индекса в БД Обновление индекса Выдача запросов из БД по индексу Схема работы поисковых машин

Индекс Таблица соответствий Матрица Двумерный ассоциативный массив

Структурированная упорядоченная копия данных из сети Индекс

Сбор страниц из интернета (робот-паук) Группировка страниц по сайтам на жёстком диске Удаление «мусора» из страниц (получение чистого текста) Анализатор и лингвистическая машина Сбор информации и обработка

Прямой индекс Сопоставляет на каких страницах какие слова встречаются кошкасобакастолчашкаягодаребро Док Док Док Док

Прямой индекс Дополнительная информация о словах Цитата исходного текста Где встречалось (картинки, ссылки и т.д.) В каких формах встречалось Контекст и т.д.

Выбор метрик Подсчёт весовых коэффициентов Ранжирование Упорядочивание информации по важности для пользователей

PageRank Ранжирование ссылочных документов по важности информации Оценка ориентированных графов =

PageRank

Обратный индекс Сопоставляет словам список страниц на которых они упоминаются

Обратный индекс Сортировка по метрикам ранжирования doc1doc2doc3doc4doc5doc6 кошка собака стол чашка

Обратный индекс Перестроение прямого индекса в обратный

Индекс и БД Обратный индекс Прямой индекс 1 Прямой индекс 2 Прямой индекс 3

Добавление в индекс Обновление данных индекса Удаление из индекса Индекс и БД После построения обратного индекса:

Морфология и языки Отсечение дубликатов Хранение большого объёма информации Быстрое обновление индекса Проблемы

Проблемы морфологии кошкакошкойкошкекошку

Проблемы лингвистики кошкакошкойкошкекошку cat gatokatze

Проблемы семантики кошкакошкойкошкекошку cat gatokatze ГРАФ

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

Проблемы БД

doc1doc2doc3doc4doc5doc6 кошка собака стол чашка

Проблемы БД кошка Doc4:50Doc5:8Doc1:5Doc2:1Doc6:1 собака Doc4:10Doc1:3Doc6:2 стол Doc3:35Doc5:7Doc6:5Doc1:1 чашка Doc4:16Doc5:6Doc3:3 Сортировка

Проблема обновления Вставка в конец (быстро) Вставка в середину (медленно) Вставка в начало (очень медленно)

Общий обратный индекс Слова на «А» Слова на «Б» Слова на «Я» …… Разбиение базы данных Проблема обновления

Поиск в индексе по ID слова Обычные булевы операции (объединение, пересечение и отрицание запросов по каждому слову) Запросы к индексу

Обратный индекс лимонныйсок

Запросы к индексу лимонныйсок РЕЗУЛЬТАТ ЗАПРОСА

СПАСИБО ЗА ВНИМАНИЕ!