Введение
Современный этап развития цивилизациихарактеризуется переходом наиболее развитой части человечества отиндустриального общества к информационному. Одним из наиболее ярких явленийэтого процесса является возникновение и развития глобальной информационнойкомпьютерной сети. В данной работе рассматриваются теоретические основыинформационного поиска, классификация и разновидности информационно поисковыхсистем. При появлении сети Интернет проблема поиска становилась болееактуальной. Интернет – всемирная компьютерная сеть, представляющая собой единуюинформационную среду и позволяющая получить информацию в любое время. Но сдругой стороны в Интернете храниться очень много полезной информации, но дляпоиска её требуется затрачивать много времени. Эта проблема послужила поводом кпоявлению поисковых машин. Информационные системы являются основным средством,инструментарием решения задач информационного обеспечения различных видовдеятельности и наиболее бурно развивающейся отраслью индустрии информационныхтехнологий. Структура информационной системы.
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 fromourtable 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, который выдаст только те номерадокументов, которые содержат эти два слова. Вотпример этого запроса: SELECTdoc_id FROM match where dict_id =$dict_id1 group by doc_id INTERSECT SELECTdoc_id FROM match where dict_id=$dict_id2 group by doc_id. В случае если пользователь введет три слова, то вампридется добавить еще раз INTERSECT и третью часть SQL запроса. По полученным врезультате запроса doc_id можно извлечь информацию об имени файла документа изтаблицы document.
3.5 Комплексное функционирование
Что бы увидеть общее представление механизмавзаимодействия с поисковой системой нужно взглянуть на рисунок 3.3:
/>
Рисунок 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).
На текущий момент в поиск включено 77backend'ов. Они сгруппированы по 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 г.