Некоторые алгоритмы решения задачи о максимальном потоке в сети
ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ
Государственное образовательное учреждение
высшего профессионального образования
“САМАРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ”
Механико-математический факультет
Кафедра информатики и вычислительной математики
Специальность “прикладная математика”
Методы ссылочного ранжированияв информационно-поисковых системах.
Диплом
Выполнил студент
5курса группы 10501
Труфанов Александр Николаевич
_____________________________
Научный руководитель
Борисова С. П.
_____________________________
Работа защищена
“______”_________________2007.
Оценка________________________
Зав. кафедрой
д.ф.-м.н., профессор
Степанов А.Н.
______________________________
Самара 2007
Оглавление
Введение
Информационно-поисковые системы в сети Интернет — на данный момент являются одним из ее краеугольных камней. Необходимость в службах, предоставляющих возможность поиска информации в Интернет, появилась сразу же после возникновения сети и на данный момент, по соотношению качества поиска и количества обработанных источников информационно-поисковые системы не имеют аналогов. Примерами подобных систем могут служить Google, MSN, Yahoo, Яндекс, Рамблер, Апорт и многие другие.
Ссылочное ранжирование позволяет увеличить качество результатов поиска. Для этого, каждому ресурсу сети присваивается ранг, отражающий его важность. В той или иной форме методы ссылочного ранжирования используют все современные информационно-поисковые системы, например они используются при вычислении индексов Тиц в Яндексе и Коэффициента Популярности Рамблера. Однако ссылочное ранжирование имеет ряд недостатков, самым главным из которых является огромная трудоемкость. Она лавинообразно нарастает с увеличением числа ресурсов в сети и является сдерживающим фактором в индексации сети ИПС. К примеру, Google располагает данными о 8 миллиардах документах, и обновляет свой индекс PageRank раз в 3 месяца. Статистические исследования показывают, что число сайтов в Интернет растет экспоненциально, и за последний год их число удвоилось. Исходя из существующих прогнозов, актуальность проблем ссылочного ранжирования будет стремительно возрастать.
Целью данной работы является обзор наиболее распространенных моделей и методов ссылочного ранжирования, их анализ и разработка собственного метода, позволяющего повысить быстродействие ссылочного ранжирования.
Для решения проблемы трудоемкости ссылочного ранжирования проводятся многочисленные исследования, зачастую финансируемые компаниями-владельцами информационно поисковых систем. С каждым годом научный интерес к изучению этой области лишь возрастает. В этих работах можно выделить несколько направлений: изучение свойств web-графа и динамики его развития, исследование моделей ссылочного ранжирования и изучение методов ссылочного ранжирования.
Глава 1. Информационно-поисковые системы
1.1 Основные сведения
С середины 90-х годов поиск информации производился с помощью каталогов, содержащие тематические коллекции ссылок.Каталоги обеспечивали высокое качество поиска, но с ростом ресурсов и числа пользователей всемирной сети, стало очевидно, что ни один каталог не способен поддерживать свою информационную базу в сколь бы то ни было актуальном состоянии. На протяжении последних 7 лет количество сайтов в сети возросло в 10раз и достигло 113,658,468. Самый большой на данный момент каталог: DMOZ (Open Directory Project) содержит лишь 4,830,584 сайта. Темпы роста сети постоянно увеличиваются — за последние 3 года количество ресурсов выросло в 2,5 раза [33]. В русскоязычном сегменте — в 2 раза (на данный момент — 743,883 сайтов) [34].
>
Рис 1. Рост числа web-сайтов в русскоязычном сегменте.
Интернет не только увеличивается в размерах — постоянно изменяется и его структура. Если в начале 90-х содержимое сети представляло собой группу гипертекстовых документов, то сейчас это динамические мультимедийные ресурсы, зачастую использующие СУБД для хранения данных. Информация может изменяться или исчезнуть столь же быстро, как появилась. Появление новых технологий настолько преобразило сеть, что в прессе уже используют новый термин: WEB 2.0.
Обеспечить более качественный поиск информации (в том числе и мультимедийной) в подобном, быстро растущем и развивающемся окружении, смогли лишь информационно-поисковые системы (далее ИПС).
Первая ИПС WebCrawler появилась в 1994 г. В то время каталоги смогли ненадолго составить конкуренцию ИПС: размеры WWW и аудитория Интернет были относительно невелики и каталоги во многом удовлетворяли требованиям пользователей. С ростом числа документов в сети, ИПС столкнулись с проблемой релевантности результатов. Если раньше конкуренция среди ИПС сводилась к размерам индекса, то теперь индексация все большего числа ресурсов уже не гарантировала более качественный поиск. Среднестатистический пользовательский запрос состоит лишь из 2,7 слов, а удовлетворять такому запросу могут сотни тысяч страниц. Просмотреть их все пользователь попросту не может — он ограничится первыми 10-15 результатами. В связи с этим все большую важность приобретает не обнаружение всех релевантных документов, а оценка их качества, обработка и представление результатов поиска.
Современные ИПС не просто ищут удовлетворяющие запросу документы. Они ранжируют их, исходя из предположения системы о качестве и важности найденного результата. С развитием ИПС все больше становятся индексы, и все больше факторов играет роль при ранжировании результатов поиска. Учитываются не только частота употребления слов запроса в документе, но и их расположение относительно друг друга, расположение внутри документа, их выделение в тексте (шрифт, гарнитура), соответствие документа тематике запроса и многое другое.
Настоящим прорывом в обеспечении наилучшего качества поиска стала ИПС Google основанная в 1998 г. Сергеем Брином и Ларри Пейджем. Превосходство Google над ближайшими конкурентами основывалось на использовании при ранжировании алгоритма PageRank. Этот алгоритм ставит в соответствие каждому проиндексированному документу сети ранг его важности (PR), основываясь на ранге ссылающихся на него документов. Ранжирование результатов поиска с учетом PR документов позволило обнаруживать и отображать в первую очередь документы-первоисточники и наиболее “авторитетные” ресурсы сети. В свою очередь, более качественный поиск сделал ИПС Google поисковым сервисом №1 в мире. На сегодняшний день Google предлагает своим пользователям более 50 разнообразных сервисов, а ее чистая прибыль на конец 2006 года превысила 3 миллиарда долларов.
Использование оценок важности документа на основе ссылочной структуры при ранжировании результатов поиска стало стандартом де-факто для большинства современных ИПС. К сожалению, алгоритмы ссылочного ранжирования являются чрезвычайно ресурсоемкими. В связи с этим было произведено множество исследований структуры WWW, ее характеристик и динамики развития.
1.2. Структура и механизм работыинформационно-поисковых систем
Согласно БСЭ: “Информационно-поисковая система — это совокупность информационно-поискового языка, правил перевода с естественного языка на информационно-поисковый и обратного перевода, а также критерия соответствия, предназначенная для осуществления информационного поиска”. Сразу оговорюсь, что в данной работе рассматривается куда более узкий класс ИПС, предназначенный для поиска информации на web ресурсах компьютерных сетей. Подобные системы появились относительно недавно (порядка 10 лет) и терминология еще не устоялась. Во всех зарубежных источниках используется термин “search engines”, что дословно можно перевести как “поисковая машина” или “поисковый двигатель”. В российской прессе часто используется “поисковый движок” или попросту “поисковик”. В то же время, и Яндекс и Рамблер всегда именовали себя “поисковыми системами”, что является еще более широким понятием.
ИПС в компьютерной сети представляет собой автоматизированный аппаратно-программный комплекс, осуществляющий поиск, сбор, классификацию и хранение информации, находящейся на ресурсах сети. ИПС использует информационно-поисковый язык запросов, в соответствии с которыми происходит поиск удовлетворяющей запросу информации, ее обработка и представление. Подробнее рассмотрим ее основные функциональные части и их функционирование:
Поиск информации в сети осуществляется с помощью поискового робота (web crawler), в составе которого выделяют две подпрограммы: паук (spider) и червяк (crawler). Первая осуществляет загрузку данных с информационного ресурса, а вторая ищет в них ссылки на другие ресурсы, добавляя их в список целей паука. Подобным образом поисковый робот движется от ресурса к ресурсу сети. Чаще всего ИПС используют сразу несколько параллельно исследующих сеть поисковых роботов, распределяя нагрузку между ними.
Стоит отметить, что далеко не все данные могут быть обнаружены ИПС. Существует проблема т.н. глубокой (скрытой или невидимой) паутиной (deep/hidden/invisible web). Информация, предоставляемая ресурсами сети, может храниться в базах данных и извлекаться из нее динамически, по запросу пользователя. К тому же, часть ресурсов не предоставляют свободного доступа, требуя аутентификации клиента. И, наконец, многие ресурсы могут быть недоступны или неработоспособны в момент их посещения поисковым роботом. По различным оценкам “невидимая” часть Интернет превосходит исследованную пауками от 10 до 500 раз [2].
Скаченная информация передается программе-индексатору, в задачу которой входит разбор и классификация этих данных. Например, в гипертекстовых страницах определяются заголовок документа и текст, выделенный размером или гарнитурой шрифта, выявляется тема документа и его ключевые слова, производится автореферирование. Процесс обработки информации индексатором и называют индексацией данных ресурса. Современные поисковые системы могут также индексировать документы в форматах pdf, ps, djvu. Предпринимаются попытки индексации графических файлов, а также аудио и видео данных (вещание TV и радио в сети).
Проиндексированные данные заносятся в индекс ИПС — специализированную базу данных. Индекс может достигать огромных размеров и проектируется с учетом повышенной отказоустойчивости, обеспечивать высокую скорость поиска и извлечения данных, а также возможность их распределенного хранения и параллельной обработки. Индекс — одна из самых сложных функциональных частей ИПС и во многом от него зависит производительность всей системы [6].
Ввиду особой важности правильности проектирования индекса ИПС, мы рассмотрим структуру индекса более подробно на примере Google. На данный момент, это — самый большой индекс, он хранит данные о более чем 8-ми миллиардов документов. Все данные размещены в виртуальной распределенной файловой системе GFS — Google File System (до 2003г. использовалась BigFiles). GFS предназначена для работы с файлами большого размера, и хранит информацию в блоках (chunk) по 64Мб. Все блоки маркируется 64-х битными идентификаторами. GFS содержит в себе кластеры, в каждом из которых выделяется главный сервер (master) и хранилища (chunkservers). Хранилища являются рабочими станциями под управлением Linux, а блоки GFS хранятся на них как обычные файлы. Главный сервер играет роль таблицы размещения файловой системы — он содержит метаданные, позволяющие найти идентификаторы блоков запрашиваемого файла и определить хранилища, в которых они находятся. Кроме того, он проверяет работоспособность хранилищ данных. GFS содержит как минимум 3 копии каждого файла в различных хранилищах, и в случае отказа одного из них, главный сервер кластера должен переадресовать запрос другому. Чтобы не допустить превращение главного сервера в “бутылочное горлышко” системы, Google использует порядка 50 кластеров, в каждом из которых находятся сотни хранилищ [16].
Для выполнения распределенных вычислений Google была разработана программа Workqueue, объединяющая множество серверов в одну вычислительную систему. Она предназначена для планирования задач, выделения аппаратных ресурсов, сбора статистики и результатов. Workqueue устанавливается на те же сервера, что используются в GFS, так как их вычислительные ресурсы в основном простаивают. Для упрощения программирования распределенных вычислений над огромными (порядка 100 терабайт) массивами данных в кластерах GFS была создана платформа MapReduce framefork. MapReduce — это библиотека, скрывающая от программиста процесс распределения задач между серверами кластера (map) и сбора воедино результатов их работы (reduce). Она контролирует обработку ошибок и отказоустойчивость вычислений, а также заботиться о том, чтобы сервера по возможности выполняли операции с данными, которые физически расположены на них [9], [24]. Также в Google создан реализующий концепцию MapReduce язык Sawzall, позволяющий максимально упростить программирование параллельных вычислений [24], [30].
Все вышеперечисленное позволило Google спроектировать единую распределенную систему хранения и управления структурированными данными Bigteable. Эту систему используют более 60 продуктов и проектов Google. В документации Google ее никогда не называют базой данной, хотя Bigteable и выполняет схожие функции. Дело в том, что Bigteable не поддерживает реляционную модель данных. Принято считать, что Bigteable представляет собой распределенный упорядоченный многомерный массив. По сути — это таблица, заголовки строк и столбцов которой — произвольные строки, а каждая ячейка измеряется еще и по времени (timestamp). Все данные в этой таблицы — никак не интерпретируемые наборы байт.
Примечательно, что Bigteable оптимизирована для считывания данных из столбцов, а не из строк [8].
>
Рис 2. Структура ИПС Google.
Все вышеперечисленное касалось технического аспекта реализации хранения и обработки индекса, теперь рассмотрим подробнее его содержимое.
Как только документ передается программе-индексатору, она предпринимает попытку определить, был ли он уже проиндексирован. Индексатор ищет в базе не точную копию обрабатываемого документа, а наиболее похожий по содержанию образец. Это позволяет избежать двойного индексирования одного и того же документа, взятого из различных источников, или представленного в другом формате (например, html и pdf). Если документ системе не известен или претерпел изменения, то индексатор предпринимает следующие шаги:
Документу присваивается идентификатор.
В документе выделяются все слова, отфильтровываются не имеющие смысловой нагрузки (предлоги, союзы и т.п.), а затем определяются лексемы.
Данные о соответствии документа содержащимся в нем лексемам заносятся в базу индекса.
В индекс могут помещаться сведения о частоте использования термина в документе, его расположение в тексте, были ли применены к слову средства выделения (шрифт, цвет и т.п.). Также могут присутствовать т.н. “координатные данные” данных: позволяющие быстро найти первые n вхождений лексемы в документе (это позволяет быстро сравнить насколько “близко” в документе несколько различных лексем, не обрабатывая его текст).
Различают прямой и обратный индекс (inverted index). В прямом индексе записи отсортированы по документам, в обратном — по словам [1].
Глава 2. Ссылочное ранжирование
Большинство поисковых запросов пользователей ИПС содержат не более 3-5 слов, и число релевантных им документов измеряется десятками тысяч. Естественно, пользователю предоставляются ссылки лишь на первые 10-15 самых “лучших” результатов. Для этого ИПС определяет не только релевантность документа запросу, но и его “качество” или “авторитетность”. Всем проиндексированным ИПС документам ставится в соответствие рейтинг — некая числовая характеристика. В Google она носит название PageRank, в Яндексе — ТИЦ, в Рамблере — Коэффициент популярности. При вычислении рейтинга документа могут использоваться множество факторов, например наличие регистрации ресурса в различных каталогах (таких как DMOZ), но главным является суммарный ранг ссылающихся на него документов.
Документы и их связи удобно представить в виде сети, получившей название web-граф. Эта сеть строится ИПС на основе данных индекса. Ссылочное ранжирование — механизм, ставящий в соответствие каждой вершине web-графа ранг, в зависимости от ранга ссылающихся на нее вершин. Во всех моделях ссылочного ранжирования, документ получает от ссылающегося на него документа лишь часть ранга, в зависимости от числа содержащихся в нем ссылок. Это позволяет проводить более “честное” ранжирование и избежать неоправданного возрастания ранга информационного ресурса за счет его регистрации в каталогах.
При индексации нового документа поисковым роботом, к web-графу должна быть добавлена новая вершина. В результате, возрастает общее число исходящих дуг в ссылающихся неё вершинах, и уменьшается доля ранга, которую они могут передать другим документам. Таким образом, добавление или удаление документа может оказать влияние на ранг даже непосредственно не связанных с ним документов. На результаты ранжирования может повлиять любое изменение структуры web-графа, например — изменение количества ссылок в одном из документов.
Необходимость пересчета ранга большого числа вершин при незначительных изменениях делает невозможным вычисление ранга нового ресурса непосредственно в момент его индексации. В связи с этим ИПС ранжируют документы индекса через значительные промежутки времени, например в Google процесс обновления PageRank в базе получил название “Google Dance” и происходит раз в 3 месяца.
Из этого следует ряд недостатков ссылочного ранжирования:
Во-первых — возможность злонамеренного завышения ранга документа владельцем информационного ресурса. Попадание в первую десятку или двадцатку результатов поиска имеет большую значимость в электронной коммерции. Поэтому владельцы Интернет-магазинов и им подобных ресурсов, а также администраторы, предоставляющие услуги по размещению рекламы на своем сайте, часто прибегают к недобросовестной конкуренции, “накручивая” свой рейтинг с помощью грамотной расстановки ссылок и наполнения документа “ключевыми” словами. Для этих целей были разработаны такие механизмы как:
Дорвеи (doorway) — генерация множества страниц с определенным образом подобранным наполнением и структурой гиперссылок, ссылающихся на ресурс.