Введение
Современный этап развития цивилизации характеризуется переходом наиболее развитой части человечества от индустриального общества к информационному. Одним из наиболее ярких явлений этого процесса является возникновение и развития глобальной информационной компьютерной сети. В данной работе рассматриваются теоретические основы информационного поиска, классификация и разновидности информационно поисковых систем. При появлении сети Интернет проблема поиска становилась более актуальной. Интернет – всемирная компьютерная сеть, представляющая собой единую информационную среду и позволяющая получить информацию в любое время. Но с другой стороны в Интернете храниться очень много полезной информации, но для поиска её требуется затрачивать много времени. Эта проблема послужила поводом к появлению поисковых машин. Информационные системы являются основным средством, инструментарием решения задач информационного обеспечения различных видов деятельности и наиболее бурно развивающейся отраслью индустрии информационных технологий. Структура информационной системы.
1 Постановка задачи
Основной целью данной исследовательской работы является анализ существующих информационно-поисковых систем. Их назначение и применение, а также этапы разработки систем.
В процессе исследования необходимо решить следующие задачи:
– проанализировать возможные особенности поисковых систем;
– провести классификацию поисковых систем;
– раскрытие особенностей поисковых систем;
– описание основных этапов разработки.
2 Информационно-поисковые системы
2.1 Развитие поисковых систем
Исторические предпосылки развития поисковых систем. Обратимся к истории возникновения сети Internet, которая была создана в связи с возникшей необходимостью совместного использования информационных ресурсов, распределенных между различными компьютерными системами. Большинство первых приложений, включая FTP и электронную почту, были разработаны исключительно для обмена данными между хост-компьютерами Internet. Другие приложения, такие как Telnet, создавались для того, чтобы пользователь получил возможность доступа не только к информации, но и к рабочим ресурсам удаленной системы. По мере развития Internet (увеличения пользователей и хост-компьютеров) прежние методы обмена данными перестали отвечать возросшим потребностям пользователей. Возникла необходимость разработки новых способов поиска сетевых ресурсов и доступа к ним, которые позволяли бы использовать информацию независимо от ее формата и расположения. Для удовлетворения таких потребностей сначала были созданы поисковая система Archie, решающая задачу локализации ресурсов на FTP-сервере, и система Gopher, упрощающая доступ к различным сетевым ресурсам. Затем были разработаны сетевые информационные системы WWW и WAIS, предлагающие абсолютно новые методы получения информации. Принципы работы этих систем позволяют легко ориентироваться в огромном количестве информационных ресурсов без необходимости предоставления механизмов работы самой сети Internet. Такой подход позволяет говорить уже не просто о ресурсах взаимосвязанных компьютерных систем, а об особых информационных пространствах сети. Система Archie представляет собой комплекс программных средств, работающих со специальными базами данных. В этих базах данных содержится постоянно пополняющаяся информация о файлах, к которым можно получить доступ через сервис FTP. Пользуясь услугами системы Archie, можно осуществить поиск файла по шаблону его имени. При этом пользователь получит список файлов с точным указанием места их хранения в сети, а также с информацией о типе, времени создания и размере файлов. Доступ к информационно-поисковой системе Archie может осуществляться различными путями, начиная от запросов по электронной почте и с помощью сервиса Telnet и заканчивая использованием графических Archie-клиентов. Система Gopher была разработана для упрощения процесса локализации FTP-ресурсов Internet и для более удобного представления сведений о содержании хранящихся на FTP-серверах файлов. Система Gopher дает возможность в удобной форме (в виде меню) представлять пользователям об имеющихся файлах и их содержании. Меню Gopher-серверов могут содержать ссылки на другие Gopher- и FTP-серверы. Таким образом, пользователь получает возможность “путешествовать” по Internet, не обращая внимания на местонахождение интересующих его ресурсов, и получать доступ к этим ресурсам. Под информационной системой в дальнейшем понимается – организованная совокупность программно – технических и других вспомогательных средств, технологических процессов и функционально – определённых групп работников, обеспечивающих сбор, представление и накопление информационных ресурсов в определённой предметной области, поиск и выдачу сведений, необходимых для удовлетворения информационных потребностей установленного контингента пользователей – абонентов системы.
2.2 Особенности поисковых систем
Особенности поисковых систем. В работе поисковый процесс представлен четырьмя стадиями: формулировка (происходит до начала поиска); действие (начинающийся поиск); обзор результатов (результат, который пользователь видит после поиска); и усовершенствование (после обзора результатов и перед возвращением к поиску с иной формулировкой той же потребности). Более удобная нелинейная схема поиска информации состоит из следующих этапов:
– фиксация информационной потребности на естественном языке;
– выбор нужных поисковых сервисов сети и точная формализация записи информационной потребности на конкретных информационно-поисковых языках (ИПЯ);
– выполнение созданных запросов;
– предварительная обработка и выборка полученных списков ссылок на документы;
– обращение по выбранным адресам за искомыми документами;
– предварительный просмотр содержимого найденных документов;
– сохранение релевантных документов для последующего изучения;
– извлечение из релевантных документов ссылок для расширения запроса;
– изучение всего массива сохраненных документов;
– если информационная потребность не полностью удовлетворена, то возврат к первому этапу.
3 Строение поисковой системы
3.1 Архитектура поисковой системы
Рассмотрим классическую архитектуру, которая чаще всего реализована на корпоративных сайтах и информационных порталах. Такая архитектура изображена на рисунке 3.1
Рисунок 3.1 Архитектура поисковой системы
Разберем по частям то, что изображено на рисунке. Существует клиентская вычислительная машина под управлением ОС Windows и существует Web-сервер под управлением UNIX-подобной ОС. На стороне клиента запущен типичный браузер, такой как Netscape. На стороне сервера запущен web сервер, который обслуживает запросы от браузера, передавая запросы презентационному слою понимающему CGI. Презентационный слой передает запросы к поисковому механизму в случае вызова услуги поиска или отображает наполнение (content) сайта. При работе администратора презентационный слой также может передавать запросы на инициализацию механизма индексации нового контента, который еще не индексирован. Это необходимо по той причине, что пока текст не индексирован, поиск в нем с помощью поисковой машины невозможен.
Идея заключается в следующем. Существуют мегабайты текстовой информации, и скорость поиска документов содержащих заданные ключевые слова отнимает очень многопроцессорного времени. Предположим, в 10 мегабайтах текстовой информации ключевое слово будет находиться в течение 10 секунд. И вот заходит посетитель на Ваш сайт, задает ключевые слова, вызывает услугу поиска и ждет 10 секунд, пока ваш сервер не выдаст ему результат. Предположим, случилось так, что одновременно запросило поиск 5 человек. Естественно, время ответа увеличится в 5 раз. Получается, что в среднем по 50 секунд пользователь будет ждать ответа от вашего сервера. Это не приемлемо, особенно если у Вас сотни мегабайт текстовой информации и время реакции системы будет катастрофически велико. Необходимо использовать другой подход при поиске ключевых слов в текстовой информации - время ответа сократить до миллисекунд.
3.2 ER-модель поискового механизма
Существует такая хорошая характеристика реляционных баз данных, как очень маленькое время выборки конкретной записи из миллионов других. Это достигается созданием, так называемого, индекса к таблице на какое-то из полей этой таблицы. Обычно индексы реализуются с применением алгоритма сбалансированного двоичного дерева. Предположим, у нас есть таблица, в которой всего один столбец и в каждой записи таблицы хранится фамилия человека. Предположим, мы загнали в такую таблицу 1 миллион фамилий. Нам необходимо проверить существует ли в этой таблице фамилия ИГУМНОВ. Предположим, что мы еще никаких индексов на эту таблицу не сделали, так же фамилия ИГУМНОВ стоит посередине таблице. Когда мы пошлем вот такой запрос: select surname from ourtable where surname='ИГУМНОВ' база данных переберет пол миллиона записей пока не дойдет до фамилии ИГУМНОВ и не выдаст результат. Получается слишком медленно. Но как только мы сделаем индекс на поле нашей таблицы, как сразу все наши запросы будут обрабатываться за миллисекунды, чего мы и добиваемся. Естественно, одной таблицы будет мало для решения нашей проблемы. Классическая структура базы данных, которая позволит решить нашу проблему, изображена на рисунке 3.2:
Рисунок 3.2 Классическая структура базы данных
Начнем с таблицы document. В этой таблице хранятся имена файлов или URL'ы страниц и каждой такой записи сопоставлен уникальный ключ id. В таблице dictionary хранятся все слова, которые могут встретиться в наших документах, и каждому слову сопоставлен уникальный id. Естественно, создаются индексы на поле word в таблице dictionary и на поле id в таблице document. В нашем примере существует отношение многие ко многим. Это необходимо, так как в таблице match мы храним соответствие слова и документа. Другими словами, в таблице match хранится информация о том, какие слова есть в каждом документе. На таблицу match создают индекс, на поле dict_id.
3.3 Индексный механизм
Прежде чем ваши документы будут доступны для поиска, их необходимо проиндексировать. Объем индексной информации, полученной из текста, может быть в два раза больше чем сам тексте. А может еще больше, в случае если вы будете не оптимально использовать память. Алгоритм выглядит следующим образом:
1. получаем документ для индексирования;
2. регистрируем его в таблице document, запоминаем полученный его уникальный id и будем его называть doc_id;
3. разбиваем документ на отдельные слова;
4. узнаем уникальные id этих слов из таблицы dictionary и будем их называть dict_id;
5. потом заносим записи с нашим одним doc_id и разными dict_id (для каждого слова в документе) в таблицу match.
3.4 Поисковый механизм
После того как мы проиндексировали наши документы, нужно понять какие запросы посылать в базу, что бы искать эти документы по ключевым словам. Предположим, есть поисковая фраза "река объ". Пользователю необходимо получить все документы содержащие эти два слова. Сначала нужно обратиться к таблице dictionary и узнать уникальные id этих слов, далее будем их называть $dict_id1 и $dict_id2. Потом необходимо послать такой запрос в таблицу match, который выдаст только те номера документов, которые содержат эти два слова. Вотпримерэтогозапроса: SELECT doc_id FROM match where dict_id =$dict_id1 group by doc_id INTERSECT SELECT doc_id FROM match where dict_id=$dict_id2 group by doc_id. В случае если пользователь введет три слова, то вам придется добавить еще раз INTERSECT и третью часть SQL запроса. По полученным в результате запроса doc_id можно извлечь информацию об имени файла документа из таблицы document.
3.5 Комплексное функционирование
Что бы увидеть общее представление механизма взаимодействия с поисковой системой нужно взглянуть на рисунок 3.3:
Рисунок
Как видно из рисунка, существует три потока управления. Первый обслуживает запросы пользователя, второй выполняет поисковые запросы, а третий занимается индексированием новых документов поступающих в систему. Первый поток - это скрипт на Perl, Servlet, ASP или PHP, который из ключевых слов пользователя формирует поисковые SQL запросы. Второй поток - это СУ базой данных, которая поддерживает целостность данных, индексный механизм и обслуживает SQL запросы. Третий поток - это тоже скрипт, который работает с новыми документами, индексирует их и посылает запросы в базу данных на внесения новой индексной информации.
4 Принципы работы поисковой машины Рамблер
Интернет постоянно растет, так же как растет и число пользователей, которые обращаются с запросами к поисковым системам. Увеличение объема информации и количества запросов, в свою очередь, приводит к повышению требований к скорости работы поисковых машин, качеству поиска и наглядности представления результатов. Так, для того чтобы пользователь остался доволен результатом, на сегодняшний день поисковой системе нужно собрать, обработать, обновить, найти и отсортировать в два раза больше документов, чем год назад. А основная задача поиска как раз и состоит в том, чтобы пользователь был доволен его результатами.
Когда пользователь обращается с запросом к поисковой машине, он хочет найти то, что ему нужно, максимально быстро и просто. Получая результат, он оценивает работу системы, руководствуясь несколькими основными параметрами. Нашел ли он то, что искал? Если не нашел, то сколько раз ему пришлось переформулировать запрос, чтобы найти искомое? Насколько актуальную информацию он смог найти? Насколько быстро обрабатывала запрос поисковая машина? Насколько удобно были представлены результаты поиска? Был ли искомый результат первым или сотым? Как много ненужного мусора было найдено наравне с полезной информацией? Сможет ли он, вернувшись завтра и дав тот же запрос, получить те же результаты?
Для того, чтобы ответы на эти вопросы оставались хоть немного удовлетворительными, разработчики поисковых машин постоянно совершенствуют алгоритмы и принципы поиска, добавляют новые функции, ускоряют работу системы. В этой статье мы обратимся к механизму работы поисковой машины Рамблер, и на примере ее устройства продемонстрируем, как достигается повышение качества и скорости поиска в условиях постоянного роста объема информации в сети Интернет.
Полнота - это одна из основных характеристик поисковой системы, которая представляет собой отношение количества найденных по запросу документов к общему числу документов в Интернете, удовлетворяющих данному запросу.
Полнота поиска в большой мере зависит от работы системы сбора и обработки информации. В связи с постоянным ростом количества документов в сети, эта система в первую очередь должна быть масштабируемой. В Рамблере масштабируемость достигается за счет параллельного исполнения задачи произвольным количеством машин.
Сбором информации занимается робот-паук, который обходит страницы с заданными URL и скачивает их в базу данных, а затем архивирует и перекладывает в хранилище суточными порциями. Робот размещается на нескольких машинах, и каждая из них выполняет свое задание. Так, робот на одной машине может качать новые страницы, которые еще не были известны поисковой системе, а на другой - страницы, которые ранее уже были скачаны не менее месяца, но и не более года назад. Хранилище у всех машин едино. При необходимости работу можно распределить другим способом, например, разбив список URL на 10 частей и раздав их 10 машинам. Параллельная работа программы позволяет легко выдерживать дополнительную нагрузку: при увеличении количества страниц, которые нужно обойти роботу, достаточно просто распределить задачу на большее число машин.
После того, как все части информации обработаны, начинается объединение (слияние) результатов. Благодаря тому, что частичные индексные базы и основная база, к которой обращается поисковая машина, имеют одинаковый формат, процедура слияния является простой и быстрой операцией, не требующей никаких дополнительных модификаций частичных индексов. Основная база участвует в анализе как одна из частей нового индекса.
Сборка единой базы из частичных индексных баз представляет собой простой и быстрый процесс. Сопоставление страниц не требует никакой интеллектуальной обработки и происходит со скоростью чтения данных с диска. Если информации, которая генерируется на машинах-индексаторах, получается слишком много, то процедура "сливания" частей проходит в несколько этапов. Вначале частичные индексы объединяются в несколько промежуточных баз, а затем промежуточные базы и основная база предыдущей редакции пересекаются. Таких этапов может быть сколько угодно. Промежуточные базы могут сливаться в другие промежуточные базы, а уже потом объединяться окончательно. Поэтапная работа незначительно замедляет формирование единого индекса и не отражается на качестве результатов.
Точность - еще одна основная характеристика поисковой машины, которая определяется как степень соответствия найденных документов запросу пользователя. Например, если по запросу "Красная площадь" находится 150 документов, в 70 из них содержится словосочетание "Красная площадь", а в остальных просто присутствуют эти слова ("красная баба кричала на всю площадь"), то точность поиска считается равной 70/150 (~0,5). Чем точнее поиск, тем быстрее пользователь находит нужные ему документы, тем меньше "мусора" среди них встречается, тем реже найденные документы не соответствуют запросу.
Способ повышения точности поиска - это выделение устойчивых обозначений и поиск их как отдельных лексических единиц. На сегодняшний день в Рамблере реализована система распознавания таких конструкций, например C++, б/у, п/п-к. Если по запросу С++ поднимать все тексты, в которых присутствуют латинская буква С, а также знак +, то получится огромное количество документов, далеко не все из которых соответствуют запросу; кроме того, это большая работа, значительно увеличивающая время поиска.
Помимо автоматических способов увеличения точности поиска, существуют различные средства, с помощью которых пользователь сам может уточнить поиск по отдельным запросам. В первую очередь к ним относится специальный язык поискового запроса, используя который можно ограничивать количество найденных документов. Например, запрос или его часть, взятые в кавычки, обрабатываются буквально, с учетом всех стоп-слов, форм, порядка, знаков препинания. Это повышает точность поиска, но уменьшает его полноту: если часть, заключенная в кавычки, неточна, нужный документ найден не будет.
Актуальность - не менее важная характеристика поиска, которая определяется временем, проходящим с момента публикации документов в сети Интернет, до занесения их в индексную базу. Например, на следующий день после теракта в Тушино огромное количество пользователей обратились к поисковой машине Рамблер с соответствующими запросами. Объективно с момента публикации новостной информации на эту тему прошло меньше суток. Однако основные документы уже были заиндексированы и доступны для поиска, благодаря существованию "быстрой базы", которая обновляется два раза в день, а при необходимости может обновляться быстрее.
Скорость поиска тесно связана с его устойчивостью к нагрузкам. На сегодняшний день в рабочие часы к поисковой машине Рамблер приходит около 60 запросов в секунду. Такая загруженность требует сокращения времени обработки отдельного запроса. Здесь интересы пользователя и поисковой системы совпадают: посетитель хочет получить результаты как можно быстрее, а поисковая машина должна отрабатывать запрос максимально оперативно, чтобы не тормозить вычисление следующих. Схематично обработка поискового запроса изображена на рисунке 4.1
Рисунок 4.1 Схематично обработка поискового запроса
Запрос поступает в поисковую систему через маршрутизатор Cisco 6000 series. Cisco передает его наименее загруженной машине первого уровня - frontend (1.1 - 1.3, на рис. машине 1.3). Frontend, в свою очередь, отправляет запрос дальше, на один из восьми proxy-серверов, также выбирая наиболее свободный сервер (2.1 - 2.8, на рис. машине 2.2). Одновременно frontend отправляет запрос на машины, осуществляющие поиск по товарам (3.1 - 3.2, на рис. машине 3.1) и по базе Тор 100 (4.1 - 4.2, на рис. машине 4.1). На proxy проводится поиск по ссылочному индексу, и его результаты вместе с поисковым запросом передаются на машины, которые содержат основную индексную базу, - backends (5.1.х - 5.7.х, на рис. машинам 5.1.2, 5.2.11, 5.3.1 и т.д.) Та же информация отправляется на машины с "быстрой базой" (6.1 - 6.2, на рис. 6.1).
На текущий момент в поиск включено 77 backend'ов. Они сгруппированы по 11 машин, и каждая группа содержит копию одной из частей поискового индекса. Таким образом, информация о сайтах, условно входящих в красный сектор Интернета, находится на backend'ах первой группы (5.1.1 - 5.1.11 на рис), оранжевый сектор - на backend'ах второй группы (5.2.1 - 5.2.11) и т.д. Proxy-сервер выбирает наименее загруженный backend в каждой группе машин и отправляет на него поисковый запрос с результатами ссылочного поиска. На backend'ах осуществляется поиск по частям индексной базы и ранжирование с учетом результатов поиска по ссылочному индексу. При ранжировании для всех найденных документов высчитываются веса по конкретному запросу.
После того, как запрос обработан на backend'ах, информация о результатах и ранжировании отдается обратно на proxy-сервер. Туда же поступают отсортированные результаты с машин "быстрой базы". Proxy интегрирует данные, полученные с восьми машин: клеит дубли, объединяет зеркала сайтов, переранжирует документы в общий список по весам, рассчитанным на backend'ах. Так, первым в списке найденного может быть документ с машины 5.3.1, вторым и третьим - с 6.1, четвертым - с 5.5.2 и т.д. На proxy-сервере также реализуется построение цитат к документам и подсветка слов запроса в тексте. Полученные результаты отдаются на frontend.
Помимо информации с proxy-сервера, frontend получает результаты из поиска по товарам и из базы Тор 100, отсортированные, с цитатами и подсветкой слов запроса. Frontend осуществляет окончательное объединение результатов, генерирует html со списком найденного, вставляет баннеры и перевязки (ссылки на различные разделы Рамблера) и отдает html Cisco, который маршрутизирует информацию пользователю.
Каждый из этапов обработки запроса многократно продублирован и защищен системой балансировки нагрузки. Благодаря дублированию информации поисковая система Рамблер является устойчивой к сбоям на отдельных участках, авариям, отказам оборудования. Если одна их машин перестала функционировать, нагрузка перераспределяется на другие машины, и выпадения документов из поиска не происходит. Масштабируемость достигается простым добавлением в систему машин соответствующего уровня. До недавнего времени в Рамблере работало 45 backend'а. В связи с тем, что осенью нагрузка на поисковые системы обычно возрастает, число backend'ов было увеличено до 77, что позволило значительно ускорить вычисление запросов.
Выводы
Заключение пишется в конце и предполагает конечность. Но рост информации бесконечен, а потому нет предела совершенствованию поисковых машин. Важнейшей задачей разработчиков является улучшение качества поиска, движение в сторону большей эффективности и удобства в использовании системы. С этой целью постоянно меняются поисковые алгоритмы, создаются дополнительные сервисы, дорабатывается дизайн.
Однако для того, чтобы выжить в мире динамичного Интернета, при разработке необходимо закладывать большой запас устойчивости, постоянно заглядывать в завтрашний день и примерять будущую нагрузку на сегодняшний поиск. Такой подход позволяет заниматься не только постоянной борьбой и приспособлением поисковой машины к растущим объемам информации, но и реализовывать что-то новое, действительно важное и нужное для повышения эффективности поиска в сети Интернет.
Список использованных источников
1. Таненбаум Э. Компьютерные сети. Спб.: «Питер», 2002.
2. Справочная информация по сетям ЭВМ и телекоммуникациям www.index.com
3. Закер К. Компьютерные сети. Модернизация и поиск неисправностей. Спб.: «БХВ-Петербург», 2002 г.