Технологии поиска документальной информации в INTERNET
Московский Государственный Горный ниверситет
Курсовая работа
на тему: Технологии поиска документальной информации в INTERNET<
по дисциплине: ПТК САПР
Выполнил:
Проверил:а
МОСКВА 2002 год.
СОДЕРЖАНИЕ (стр.):
1. ВВЕДЕНИЕ.
1.1. Что такое Internet (3).
1.2. Краткая история Internet (4).
2. БРАУЗЕРЫ: сравнительные характеристики Netscape Navigator и Microsoft Internet Explorer (5).
3. ПОИСКОВЫЕ СИСТЕМЫ (7).
3.1. Механизмы поиска (9).
3.2. Сравнительный обзор поисковых систем. Структура запроса (11).
3.3 Алгоритмы поиска (17).
3.3.1 Алгоритм Кнута-Мориса-Пратта (17).
3.3.2 Алгоритм Бойера-Мура (19).
3.3.3 Алгоритм Рабина (21).
4. ЗАКЛЮЧЕНИЕ (23).
5. СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ (24).
1. ВВЕДЕНИЕ.
1.1. Что такое Internet.
Internet - глобальная компьютерная сеть, охватывающая весь мир. Сегодня Internet имеет около 30 миллионов абонентов в более чем 180 странах мира. Ежемесячно размер сети величивается на 5-7%. Internet образует как бы ядро, обеспечивающее связь различных информационных сетей, принадлежащих различным чреждениям во всем мире, одна с другой.
Всплеск интереса к глобальной информационной сети Internet наблюдается сейчас повсеместно. В сложившихся словиях потребность в информации о сети Internet становится особенно острой. В настоящее время по Internet распространяется множество документов, касающихся как функционирования сети и работы в ней пользователей, так и связанных с различными сферами жизни: наукой, культурой, экономикой и т.д. При чём обновление информации в Internet, обширной разветвленной сети, которая включает в себя компьютерные злы, разбросанные по всему миру, происходит, практически, в режиме реального времени.
В действительности Internet не просто сеть, - она есть структура, объединяющая обычные сети. Internet - это Сеть сетей.
Чтобы описать сегодняшнюю Internet, полезно воспользоваться строгим определением. В своей книге "The Matrix: Computer Networks and Conferencing Systems Worldwide" Джон Квотерман описывает Internet как лметасеть, состоящую из многих сетей, которые работают согласно протоколам семейства TCP/IP, объединены через шлюзы и используют единое адресное пространство и пространство имен.
Для организации межсетевых соединений необходим соответствующий протокол.
Протокол - это набор договоренностей, который определяет обмен данными между различными программами. Протоколы задают способы передачи сообщений и обработки ошибок в сети, также позволяют разрабатывать стандарты, не привязанные к конкретной аппаратной платформе. Все параметры - от скорости передачи данных до методов адресации при транспортировке отдельных сообщений - задаются протоколами, используемыми в данной конкретной сети.
В Internet базовым протоколом служит TCP/IP (Transmission Control Protocol/Internet Protocol). IP отвечает за адресацию сетевых злов, TCP обеспечивает доставку сообщений по нужному адресу. Эти мощные протоколы были предложены в 1974 г. Робертом Кэном, одним из основных разработчиков ARPANET, и ченым-компьютерщиком Винтоном Серфом, вице-президентом CNRI. Следует иметь в виду, что TCP/IP не единственный протокол, пригодный для объединения различных сетей. Internet ныне превратилась в многопротокольную сеть, интегрирующую другие стандарты. Основные среди них - стандарты взаимодействия открытых систем (OSI).
Предложенные Международной организацией по стандартизации (ISO) протоколы OSI получили широкое распространение в Европе. Системы, основанные на других протоколах, тоже подключаются к Internet через шлюзы. Например, BITNET - это сеть, которая использует для передачи данных свои собственные стандарты, однако, по крайней мере, частично, она доступна через шлюзы из Internet.
В Internet нет единого пункта подписки или регистрации; вместо этого вы контактируете с поставщиком слуг, который предоставляет вам доступ к сети через местный компьютер. Последствия такой децентрализации с точки зрения доступности сетевых ресурсов также весьма значительны. Среду передачи данных в Internet нельзя рассматривать только как паутину проводов или оптоволоконных линий. Оцифрованные данные пересылаются через маршрутизаторы, которые соединяют сети и с помощью сложных алгоритмов выбирают наилучшие маршруты для информационных потоков.
1.2. Краткая история Internet.
Вначале ничто не предвещало, что Internet станет общедоступной компьютерной сетью. Как и многие другие великие идеи, Сеть сетей возникла из проекта, предназначавшегося совершенно для других целей. Ее прародительницей стала сеть АRPANET, разработанная и развернутая в 1969г. компанией Bolt, Beranek, and Newman (BBN) по заказу Агентства передовых исследовательских проектов (ARPA) Министерства обороны США.
ARPANET объединяла учебные заведения, военные организации и их подрядчиков. Она была создана с целью помочь исследователям в обмене информацией, также (что явилось одной из главных целей) для отработки методов поддержания связи в случае ядерного нападения.
Основатели ARPANET первоначально позволяли ченым только войти в систему и запустить программу на удаленном компьютере. Скоро к этим возможностям прибавились передача файлов, электронная почта и списки рассылки, обеспечившие общение исследователей, интересовавшихся одной и той же областью науки и техники. Но по мере роста ARPANET развивались и другие сети, и вскоре стала очевидной потребность в новых средствах связи.
Сравнительно недавно появилась новая технология Internet названная World Wide Web (), что обычно переводится как Всемирная паутина. Эта система была разработана, в основном, в Европейской лаборатории элементарных частиц в Швейцарии (CERN). Сеть предназначалась первоначально для физиков, но затем получила широкое признание.
построена по технологии,
в основе которой лежит принцип создания гипертекстовых документов (W Для работы в
используется протокол HTTP (Hyper Text Transmission Protocol), программы,
позволяющие работать с соответствующими документами в Internet, называют просмотрщиками или браузерами. 2. БРАУЗЕРЫ: сравнительные характеристики Netscape Navigator и Microsoft Internet Explorer. Документы Internet предназначены для отображения в электронном виде, причем автор документа не знает возможностей компьютера, на котором будут просматриваться документы. Поэтому был создан стандарт для описания и создания документов, расположенных на Web<-страницах. Этот язык называется HTML (HyperText Markup Language - язык разметки гипертекста). Этот язык описывает логическую структуру документа, правляет форматированием текста и размещением вставных объектов. Форматирование и отображение документа, описанного с помощью HTML, на конкретном компьютере производится специальной программой - браузером. Проще говоря, браузер предназначен для просмотра содержимого Web<-страниц. Основные функции браузеров следующие: становка связи с Web<-сервером,
на котором хранится документ, и загрузка всех его компонентов; форматирование и отображение
Web<-страниц в соответствии с возможностями компьютера, на котором браузер работает; предоставление средств для отображения мультимедийных и других объектов входящих в состав Web<-страниц,
а так же механизма расширения, позволяющего настраивать программу на работу с новыми типами объектов; обеспечение автоматизации поиска Web<-страниц и прощение доступа к страницам, посещавшимся раньше; предоставление доступа к встроенным или автономным средствам для работы с другими службами Internet. В настоящее время на этом рынке доминируют два браузера: Navigator фирмы Netscape и Internet Explorer фирмы Microsoft. Они предоставляют пользователям весьма схожий интерфейс и набор основных возможностей и ведут на этом рынке весьма жесткую конкурентную борьбу, постоянно обновляя предыдущие версии. Ниже приводится описание основных возможностей этих браузеров. Браузер Internet Explorer обеспечивает работу с
<, предоставляет идентичные средства работы с локальными папками компьютера и файловыми архивами FTP, дает доступ к средствам связи с Internet. Для запуска программы можно использовать значока Internet Explorer на Рабочем столе или Главного меню. Кроме того, программа запускается автоматически при попытке открыть документ Internet или локальный документ в формате HTML. Если соединение с Internet отсутствует, то после запуска программы появиться диалоговое окно становки соединения. При невозможности установки соединения сохраняется возможность просмотра в автономном режиме ранее загруженных Web<-документов. При наличии соединения после запуска программы на экране появится основная страница, выбранная при настройке программы. Далее можно работать с Web<-страницами,
просматривая их содержимое, сохраняя его на локальном диске и т.д. При этом можно открывать несколько окон, работая с несколькими Web<-страницами. Для более эффективной работы в Internet необходима настройка Internet Explorer. Параметры оптимальной настройки зависят от: свойств видеосистемы компьютера; производительности действующего соединения с Internet; содержания текущего Web<-документа; личных предпочтений пользователя. Настроить Internet Explorer можно как из самой программы, так и через Панель правления. Если браузер неспособен отображать файлы определенного типа (*. Netscape
Navigator - один из лучших Web<-браузеров, главная программа пакета Netscape Communicator. С его помощью можно просматривать содержимое Web<-страниц, копировать файлы, искать различного рода информацию, работать с текстом и мультимедийными файлами Internet. Оба браузера имеют свои преимущества. Например: Internet
Explorer поставляется бесплатно в составе программного обеспечения фирмы Microsoft; Internet
Explorer имеет более широкие возможности при настройке на конкретные вкусы потребителя и большее количество выполняемых функций; Netscape
Navigator - имеет большую скорость при работе с Web<-страницами. Но в принципе, оба браузера выполняют похожие задачи и полностью довлетворяют запросы пользователей при работе с Internet. Одной из основных архитектурных особенностей Explorer является применение ActiveX - технологии, которая позволяет добно конфигурировать, например, вид и возможности панели инструментов, что делает компьютер доступным даже для детей. Оба браузера поддерживают возможность создания HTML-документов, при чём Explorer позволяет создавать темплайты, что так же прощает создание web-страниц.
Internet
Explorer поддерживает наиболее распространенные языки, облегчая пользовательский интерфейс, поддерживает все основные сетевые стандарты и предусматривает интерфейс без использования мыши и возможность изменять шрифт для добства просмотра. Что касается скорости просмотра W Netscape подчеркивает отличие Navigatora от других браузеров, в особенности от Internet ExplОrer,
количеством необходимой для него памяти, скоростью работы, значительными удобствами для создателей Web<-документов, наличием системы, позволяющей компьютеру пользоваться телефонными слугами Internet в режиме реального времени. К тому же это позволяет избежать неудобств обычной телефонной связи. Когда Netscape неожиданно появилась на рынке,
Microsoft пришлось немедленно отреагировать, чтобы не потерять часть своего бизнеса. Без такой яростной конкуренции между двумя гигантами не было бы ни такого широкого использования
Web, ни коммерческих Web-серверов, ни недорогих браузеров с графическими интерфейсами. Это соперничество породило недорогие продукты, которые, благодаря использованию протоколов Internet,
способны к взаимодействию. Преодолеть несовместимость различных HTML проще, чем те трудности, которые могли бы возникнуть, считают оптимисты. 3. ПОИСКОВЫЕ СИСТЕМЫ. Основная задача Internet - предоставление необходимой информации. Чтобы найти нужную информацию необходимо знать адрес Web<-страницы, на которой эта информация находится. Лучше всего искать в Сети необходимую информацию с помощью поисковых систем. Поисковая система представляет собой специализированный Web<-узел. Поисковые системы классифицируют по методам поиска. Поисковые каталоги предназначены для поиска по темам. Обычно они построены по иерархическому принципу, т.е.
каждый шаг поиска это выбор подраздела с более конкретной тематикой искомой информации. На нижнем ровне поиска пользователь получает относительно небольшой список ссылок на искомую информацию. Поисковый индекс обеспечивает поиск по заданным ключевым словам. Обычно ключевые слова вводятся при заполнении специальной формы поиска, после чего нажимается кнопка Поиск. В результате поиска формируется набор гиперссылок на Web<-страницы, содержащий указанные термины. Обычно поисковые индексы выдают огромное количество искомых страниц. В этом списке представлены ссылнки на различные Web<-страницы, причем ссылки располагаются по степени бынвания встреченных на данных страницах слов, совпадающих с ключевыми словами. При просмотре списк необходимо выбрать те страницы,
конторые нужно просмотреть. Некоторые системы составляют список ссылок по степени свежести страниц, другие же - по степени вероятности того, что данные страницы окажутся искомыми. Вычисление вероятности основывается на данных о том, как скоро на странице встречается исконмое слово. Первыми в таком списке идут ссылки на те страницы, у которых клюнчевые слова встречаются же в названии. Поисковые каталоги предоставляют доступ к меньшему количеству страниц, чем поисковые индексы, но они точнее казывают на основные ресурсы Сети. Поэтому при первичном поиске информации целесообразно использовать поисковые каталоги. А квалифицированным пользователям Internet более полезны поисковые индексы. Они позволяют разыскать малоизвестные и зкоспециализированные ресурсы. Многие современные поисковые системы сочетают в себе оба казанных метода. Программа Internet Explorer 5.0а имеет специальные средства организации поиска без явного обращения к поисковым системам. Можно получить доступ к одной из известных поисковых систем, просто щелкнув на кнопке Поиск, слева появится окно поиска. Далее можно набрать ключевые слова для поиска и выбрать поисковую систему. Результаты поиска будут отражены в правой части окна обозревателя. Если выбрать нужную ссылку, то в правом окне появится содержимое выбранной страницы. Чтобы скрыть окно поиска, необходимо щелкнуть на кнопке Поиск еще раз. При работе с Internet ЕхрL Можно осуществить поиск нажав кнопку Пуск и выбрав опцию меню Найти. Окно Internet Explorer откроется само с же нажатой кнопкой Поиск. Если далось найти то, что искали, но все же не совсем то, то в этом случае пригодится механизм связанных ссылок. Для любой Web<-страницы можно просмотреть список ссылок, имеющих к ней отношенние, возможно, среди них окажется как раз то, что нужно. Чтобы просмотреть связанные ссылки, нужно сделать следующее. Необходимо выбрать в меню Сервис команду Показать связанные ссылки. После этого на панели инструментов нажать кнопку Поиск,
и в левой чансти экрана полнится окно, содержащее список ссылок, связанных с данной страницей. Нужно щелкнуть на одной из ссылок, и просмотреть в правом окне соответствующую Web<-страницу. Чтобы скрыть окно поиска,
необходимо щелкнуть еще раз на кнопке Поиск. 3.1. Механизмы поиска. Поисковые
cистемы обычно состоят из трех компонентов:
агент (паук или кроулер), который перемещается по Сети и собирает информацию;
база данных, которая содержит всю информацию, собираемую пауками;
поисковый механизм, который люди используют как интерфейс для взаимодействия с базой данных. Cредства поиска и структурирования,
иногда называемые поисковыми механизмами, используются для того, чтобы помочь людям найти информацию, в которой они нуждаются. Cредства поиска типа агентов, пауков, кроулеров и роботов используются для сбора информации о документах, находящихся в Сети Интернет. Это специальные программы, которые занимаются поиском страниц в Сети, извлекают гипертекстовые ссылки на этих страницах и автоматически индексируют информацию, которую они находят для построения базы данных. Каждый поисковый механизм имеет собственный набор правил, определяющих, как cобирать документы. Некоторые следуют за каждой ссылкой на каждой найденной странице и затем, в свою очередь, исследуют каждую ссылку на каждой из новых страниц, и так далее. Некоторые игнорируют ссылки, которые ведут к графическим и звуковым файлам, файлам мультипликации; другие игнорируют cсылки к ресурсам типа баз данных WAIS; другие проинструктированны, что нужно просматривать прежде всего наиболее популярные страницы. генты - самые линтеллектуальные из поисковых средств. Они могут делать больше, чем просто искать: они могут выполнять даже транзакции от Вашего имени. же сейчас они могут искать cайты специфической тематики и возвращать списки cайтов,
отсортированных по их посещаемости. Агенты могут обрабатывать содержание документов, находить и индексировать другие виды ресурсов, не только страницы.
Они могут также быть запрограммированы для извлечения информации из же существующих баз данных. Независимо от информации, которую агенты индексируют,
они передают ее обратно базе данных поискового механизма. генты извлекают и индексируют различные виды информации. Некоторые, например,
индексируют каждое отдельное слово во встречающемся документе, в то время как другие индексируют только наиболее важных 100 слов в каждом, индексируют размер документа и число слов в нем, название, заголовки и подзаголовки и так далее.
Вид построенного индекса определяет, какой поиск может быть сделан поисковым механизмом и как полученная информация будет интерпретирована. генты могут также перемещаться по Internet и находить информацию, после чего помещать ее в базу данных поискового механизма. Администраторы поисковых систем могут определить, какие сайты или типы сайтов агенты должны посетить и проиндексировать. Проиндексированная информация отсылается базе данных поискового механизма так же, как было описано выше. Общий поиск информации в Сети осуществляют программы, известные как пауки.
Пауки сообщают о содержании найденного документа, индексируют его и извлекают итоговую информацию. Также они просматривают заголовки, некоторые ссылки и посылают проиндексированную информацию базе данных поискового механизма. Кроулеры просматривают заголовки и возвращают только первую ссылку. Роботы могут быть запрограммированы так, чтобы переходить по различным cсылкам различной глубины вложенности, выполнять индексацию и даже проверять ссылки в документе. Из-за их природы они могут застревать в циклах, поэтому, проходя по ссылкам, им нужны значительные ресурсы Сети. Однако, имеются методы,
предназначенные для того, чтобы запретить роботам поиск по сайтам, владельцы которых не желают, чтобы они были проиндексированы. Люди могут помещать информацию прямо в индекс, заполняя особую форму для того раздела, в который они хотели бы поместить свою информацию. Эти данные передаются базе данных. Когда кто-либо хочет найти информацию,
доступную в INTERNET, он посещает страницу поисковой системы и заполняет форму,
детализирующую информацию, которая ему необходима. Здесь могут использоваться ключевые слова, даты и другие критерии. Критерии в форме поиска должны соответствовать критериям, используемым агентами при индексации информации,
которую они нашли при перемещении по Сети. База данных отыскивает предмет запроса, основанный на информации, казанной в заполненной форме[N1] ,
и выводит соответствующие документы, подготовленные базой данных. Чтобы определить порядок, в котором список документов будет показан, база данных применяет алгоритм ранжирования. В идеальном случае, документы, наиболее релевантные пользовательскому запросу будут помещены первыми в списке.
Различные поисковые системы используют различные алгоритмы ранжирования,
однако, основные принципы определения релевантности следующие: 1.
Количество слов запроса в текстовом содержимом документа. 2.
Тэги, в которых эти слова располагаются. 3.
Местоположение искомых слов в документе. 4.
Удельный вес слов, относительно которых определяется релевантность, в общем количестве слов документа. База данных выводит ранжированный подобным образом список документов с HTML и возвращает его человеку, сделавшему запрос. Различные поисковые механизмы также выбирают различные способы показа полученного списка - некоторые показывают только ссылки; другие выводят cсылки c первыми несколькими предложениями,
содержащимися в документе или заголовок документа вместе с ccылкой. Когда Вы щелкаете на ссылке к одному из документов,
который вас интересует, этот документ запрашивается у того сервера, на котором он находится. 3.2. Сравнительный обзор поисковых систем. Структура запроса. В сети существуют различные способы поиска информации. Конечно же, если имеется справочник, в котором можно найти местонахождение интересующего вас источника конкретной информации, то,
без всякого сомнения, следует этим и воспользоваться. Однако, к сожалению,
такие издания далеко не всегда доступны. Кроме того, сеть является постоянно обновляющейся системой и поэтому находится в курсе всего нового с помощи периодики, тем более с помощью литературы, не всегда представляется возможным. Для поисковых целей в Internet существуют специальные поисковые машины, располагающие значительными базами данных и имеющие связь с себе подобными. Существенно полезными возможностями у них является наличие системы поиска, которая строится по принципу: от общего - к конкретному. Задавая общее понятие (в виде ключевого слова,
нескольких слов или фразы, - в зависимости от сервисных слуг конкретной машины), затем, с каждым новым поиском всё более и более конкретизируя его,
можно получить интересующий результат. Поэтому далее будут рассмотрены несколько основных поисковых систем, использование которых весьма эффективно. Исторически сложилось, что первой такой поисковой машиной являлась Alta Vista, поэтому с неё и начнём рассмотрение. AltaVista.
Наиболее интересная возможность AltaVista - это расширенный поиск. AltaVista разрешает поиск по ключевым фразам, при этом она имеет довольно большой фразеологический словарь. Кроме всего прочего, при поиске в AltaVista можно задать имя поля, где должно встретиться слово. К сожалению, подробно процедура ранжирования в документации по системе не описана, но видно, что ранжирование применяется как при простом поиске, так и при расширенном запросе. Реально эту систему можно отнести к системе с расширенным булевым поиском. Lycos. Как и большинство систем,
Lycos дает возможность применять простой запрос и более изощренный метод поиска. В простом запросе в качестве поискового критерия вводится предложение на естественном языке, после чего Lycos производит нормализацию запроса, даляя из него так называемые stop-слова, и только после этого приступает к его выполнению. Почти сразу выдается информация о количестве документов на каждое слово, позже и список ссылок на формально релевантные документы. В списке против каждого документа казывается его мера близости запросу, количество слов из запроса, попавших в документ, и оценочная мера близости, которая может быть больше или меньше формально вычисленной. Пока нельзя вводить логические операторы в строке вместе с терминами, но использовать логику через систему меню Lycos позволяет. Такая возможность применяется для построения расширенной формы запроса, предназначенной для искушенных пользователей, же научившихся работать с этим механизмом. Yahoo.
Данная система появилась в Сети одной из первых, и сегодня Yahoo сотрудничает со многими производителями средств информационного поиска, на различных ее серверах используется различное программное обеспечение. Язык Yahoo достаточно прост: все слова следует вводить через пробел, они соединяются связкой У При выдаче не казывается степень соответствия документа запросу, только подчеркиваются слова из запроса,
которые встретились в документе. При этом не производится нормализация лексики и не проводится анализ на лобщие слова. Хорошие результаты поиска получаются только тогда, когда пользователь знает, что в базе данных Yahoo информация есть наверняка. Ранжирование производится по числу терминов запроса в документе. Yahoo относится к классу простых традиционных систем с ограниченными возможностями поиска. OpenText.
Информационная система OpenText представляет собой самый коммерциализированный информационный продукт в Сети. Все описания больше похожи на рекламу, чем на информативное руководство по работе. Система позволяет провести поиск с использованием логических коннекторов, однако размер запроса ограничен тремя терминами или фразами. В данном случае речь идет о расширенном поиске. При выдаче результатов сообщается степень соответствия документа запросу и размер документа. Система позволяет также лучшить результаты поиска в стиле традиционного булевого поиска. OpenText можно было бы отнести к разряду традиционных информационно-поисковых систем, если бы не механизм ранжирования. Infoseek. Система Infoseek обладает довольно развитым информационно-поисковым языком, позволяющим не просто казывать, какие термины должны встречаться в документах, но и своеобразно взвешивать их.
Достигается это при помощи специальных знаков л+ - термин обязан быть в документе, и л- - термин должен отсутствовать в документе. Кроме этого, Infoseek позволяет проводить то, что называется контекстным поиском. Это значит, что, используя специальную форму запроса, можно потребовать последовательной совместной встречаемости слов. Также можно казать, что некоторые слова должны совместно встречаться не только в одном документе, даже в отдельном параграфе или заголовке. Имеется возможность казания ключевых фраз, представляющих собой единое целое, вплоть до порядка слов. Ранжирование при выдаче осуществляется по числу терминов запроса в документе, по числу фраз запроса за вычетом общих слов. Все эти факторы используются как вложенные процедуры. Подводя краткое резюме, можно сказать, что Infoseek относится к традиционным системам с элементом взвешивания терминов при поиске. WAIS. WAIS является одной из наиболее изощренных поисковых систем INTERNET. В ней не реализованы лишь поиск по нечетким множествам и вероятностный поиск. В отличие от многих поисковых машин,
система позволяет строить не только вложенные булевые запросы, считать формальную релевантность по различным мерам близости, взвешивать термины запроса и документа, но и осуществлять коррекцию запроса по релевантности.
Система также позволяет использовать сечения терминов, разбиение документов на поля и ведение распределенных индексов. Rambler.
Поисковая система содержит информацию о более чем 12
миллионах документов, расположенных на серверах России и стран СНГ. Rambler обрабатывает ежесуточно не менее 500 тысяч поисковых запросов (в среднем - 5 запросов в секунду), сканируя 48 тысяч W Запрос может состоять из одного или нескольких слов, разделенных пробелами. Могут быть использованы как русские, так и английские слова и словосочетания. По молчанию находятся только те документы, в которых встретились все введенные Вами слова. Чтобы найти документы, содержащие хотя бы одно слово из запроса, используется логическая связка УorФ или выбирается на странице детального запроса: Слова запроса: любое. Чтобы исключить документы, содержащие те или иные слова, надо казать на странице детального запроса: Исключить документы, содержащие следующие слова.... Все равно, с какой буквы написаны слова запроса: с большой или с маленькой. И при построении индекса, и при поиске по запросу все заглавные (большие) буквы лпонижаются. Слова запроса могут быть соединены логическими связками УandФ, У Части запроса могут быть сгруппированы с помощью круглых скобок. Возможна многократная вложенность скобок в сочетании с логическими операторами. Rambler меет искать слова во всех формах (например, аминокислота, аминокислоты,
аминокислотой и т. д.). Чтобы слово находилось во всех формах, перед ним надо поставить служебный символ У#Ф. В меню детального запроса такой режим может быть включен для всех слов: Расширение запроса: все формы слов. Служебный символ У@Ф перед словом позволяет находить не только само это слово, но и однокоренные слова. В меню детального запроса символу У@Ф соответствует режим Расширение запроса: все однокоренные. По молчанию наша система ищет слова запроса так, как Вы их ввели, чтобы меньшить шум в найденных документах. Если Вы не помните, как пишется слово, или хотите расширить запрос, можно использовать метасимволы У*Ф и У?Ф для обозначения произвольной части слова и произвольного символа. Ограничить поиск частями документов, такими как название документа, его заголовок, URL и т.п., можно через меню детального запроса Искать в.... Можно ограничить поиск документами только на русском или только на английском языке.
Для этого надо выбрать соответствующий режим в меню детального запроса Язык документа....
По молчанию поиск выполняется по документам на всех языках. По молчанию найденные документы сортируются по релевантности (соответствию запросу). Однако Вы можете потребовать, чтобы вместо этого в начало списка были помещены самые свежие (или,
наоборот, самые старые документы). Для этого надо выбрать соответствующую установку в меню Сортировать по... на странице детального запроса. Вы можете также ограничить поиск документами, созданными в определенный период времени: для этого необходимо на странице детального запроса казать От даты... до даты.... Можно потребовать, чтобы Rambler возвращал только те документы, где слова из запроса находятся на минимальном расстоянии друг от друга. Режим Ограничить расстояние между словами может быть включен в детальном запросе.
Все перечисленные выше правила могут быть использованы совместно друг с другом в необходимой Вам последовательности. По умолчанию результаты поиска выдаются порциями по 15 документов. Меню Выдавать по... на странице детального запроса позволяет величить это число до 30 или
50. Меню Форма вывода... позволяет получать описания документов с величенной или меньшенной подробностью. Yandex.
Yandex ежедневно просматривает сотни тысяч Web-страниц в поисках изменений или новых ссылок. Коллекция ссылок постоянно растет. Yandex не требует от вас знания специальных команд для поиска. Достаточно набрать вопрос (лгде найти дешевые компьютеры или нужны телефоны москвы и московской области), и вы получите результат - список страниц, где встречаются эти слова. Независимо от того, в какой форме вы потребили слово в запросе, поиск учитывает все его формы по правилам русского языка. Например, если задан запрос лидти, то в результате поиска будут найдены ссылки на документы, содержащие слова лидти, лидет, шел,
лшла и т.д. На запрос локно будет выдана информация, содержащая и слово локон, на запрос лотзывали - документы, содержащие слово лотозвали. При этом поиск не ограничен лишь словами или фразами. Yandex отыщет по названию W Aport. Обычно запрос представляет из себя просто одно или несколько слов. По такому запросу находятся документы, в которых встречаются все слова запроса. Есть, правда, ограниченное число слов (союзы, предлоги и т.п.), которые в запросе игнорируются, так как не несут сами по себе смысловой нагрузки. Например, по запросу: яблоки на снегу будут найдены все документы, в которых встречаются одновременно два слова: ляблоко и снег. Где в пределах документа расположены слова, в какой грамматической форме они находятся - не важно. Стоит еще раз подчеркнуть важное и очень полезное свойство Апорта: независимо от того, в какой грамматической форме вы пишите в запросе слово, оно находится в документах во всех своих формах. Например, по запросу: человек шел будут найдены среди прочих и документы, содержащие текст люди идут.
Распознавание всех форм работает для обычных слов русского языка. Для экзотических слов, неологизмов и т.п. оно не проходит. В этом случае может пригодиться оператор л*. Например, вы хотите найти все, касающееся деятельности президента России, в том числе и документы,
содержащие слово лельцинизм. Воспользуйтесь запросом: ельцин*. Он позволит вам найти то, что вы хотите (а также документы со словами Ельцинище, ельцинцы, ельциненок и т.п), поскольку звездочка заменяет собой любое число любых букв. Вы можете искать документы не только по всему русскоязычному INTERNET, но и по его части. Самый простой случай - поиск по определенному серверу. Например: url=.intel.ru собака По данному запросу будут найдены все документы на сервере.intel.ru, содержащие слово
"собака". Возможно, вам интересно, что будет, если написать просто: url=.intel.ru В этом случае вы получите список всех документов, расположенных на казанном вами сервере Вы можете ограничивать поиск и сильнее - одним из каталогов сервера. Например: По данному запросу документы, содержащие слово сенбернар, будут искаться только в каталоге
/sobaki (и его подкаталогах) московского сервера корпорации Intel. List. На главной странице в верхней ее части расположены ссылки на наиболее популярные проекты. Ниже, под логотипом каталога, поисковая форма. В правой колонке и нижней части страницы - блоки самых актуальных новостей. Список ссылок на основные категории каталога занимает центральную часть. Цифры рядом с названием категории показывают количество сайтов, содержащихся в ней. Записанные мелким шрифтом заголовки отсылают при нажат на подкатегории раздела. Щелкнув по любому из названий, Вы попадете в соответствующую рубрику и под логотипом
List.ru видите полный путь до нее, начиная с главной страницы. Каждый промежуточный ровень структуры доступен по отдельной ссылке. Поиск в каталоге реализован таким образом, что в результате запроса могут быть найдены как отдельные сайты, так и рубрики. Допускается использованием языка запросов Yandex. Расположенная рядом с поисковой формой ссылка Структура каталога открывает в отдельном окне полный рубрикатор каталога.
Реализована возможность перехода из рубрикатора в любую выбранную подкатегорию.
Более детальное тематическое деление текущей рубрики представлено списком ссылок. Помеченные символом У@Ф приведут в подкатегории, структурно входящие в другие разделы, но содержащие близкую по содержанию информацию. Если Вы хорошо представляете, в какой рубрике содержатся нужные ресурсы, лучше перейти в нужную подкатегорию,
воспользовавшись любым из предоставляемых средств навигации по каталогу. В противном случае можно искать их в полном списке. Каталог организован таким образом, что все сайты, содержащиеся на нижних ровнях структуры, представлены и в рубриках. Показываемый ниже список ресурсов упорядочен в алфавитном порядке, но, выбрав соответствующую сортировку (По времени добавления или По переходам), можно просмотреть их по порядку добавления в каталог (начиная с самых свежих) или в зависимости от популярности среди посетителей каталога. Ссылка с названия сайта открывает в отдельном окне его зарегистрированную в данной рубрике страницу. Пометки RUS и ENG означают наличие на сайте страниц, соответственно на русском и английском языках. 3. Алгоритмы поиска. 3.3.1 Алгоритм Кнута-Морриса-Пратта лгоритм Кнута-Морриса-Пратта
(КМП) получает н вход слово X=x[1]x[2]...
x[n] и просматривает его слева направо буква за буквой, заполняя при этом массив натуральных чисел l[1]...
l[n], где l[i]=длина слова l(x[1]...х[i]) (функция l определена в предыдущем пункте). Словами: l[i] есть длина наибольшего начала слова x[1]...x[i],
одновременно являющегося его концом. Какое отношение все это имеет к поиску подслова? Другими словами, как использовать алгоритм КМП для определения того, является ли слово A подсловом слова B?а Решение.
Применим алгоритм КМП к слову A#B, где # - специальная буква, не встречающаяся ни в A, ни в B. Слово A является подсловом слова B тогда и только тогда, когда среди чисел в массиве l будет число, равное длине слова A. Описать алгоритм заполнения таблицы l[1]...l[n]. Решение.
Предположим, что первые i значений l[1]...l[i] же найдены. Мы читаем очередную букву слова (т.е. x[i+1]) и должны вычислить l[i+1]. Другими словами, нас интересуют начала Z слова x[1]...x[i+1, одновременно являющиеся его концами -из них нам надо брать самое длинное. Откуда берутся эти начала? Каждое из них (не считая пустого) получается из некоторого слова Z' приписыванием буквы x[i+1]. Слово Z' является началом и концом слова x[1]...x[i].
Однако не любое слово, являющееся началом и концом слова x[1]...x[i], годится -
надо, чтобы за ним следовала буква x[i+1]. Получаем такой рецепт отыскания слова Z.
Рассмотрим все начала слова x[1]...x[i], являющиеся одновременно его концами.
Из них выберем подходящие - те, за которыми идет буква x[i+1]. Из подходящих выберем самое длинное. Приписав в его конец х[i+1], получим искомое слово Z.
Теперь пора воспользоваться сделанными нами приготовлениями и вспомнить, что все слова, являющиеся одновременно началами и концами данного слова, можно получить повторными применениями к нему функции l из предыдущего раздела. Вот что получается: {таблица
l[1]..l[i] заполнена правильно} while i <> n do begin len:= l[i] {len
- длина начала слова x[1]..x[i], которое является его концом; все более длинные начала оказались неподходящими<} while (x[len+1]<>х[i+1]) and (len>0) do begin {начало не подходит, применяем к нему функцию l} len:=l[len]; end; {нашли подходящее или бедились в отсутствии} if x[len+1]=x[i+1] do begin {х[1]..x[len]
- самое длинное подходящее начало} l[i+1]:=len+1; end else begin {подходящих нет} l[i+1]:=
0; end; i:=i+1; end; Доказать,
что число действий в приведенном только что алгоритме не превосходит Cn для некоторой константы C. Решение. Это не вполне очевидно: обработка каждой очередной буквы может потребовать многих итераций во внутреннем цикле. Однако каждая такая итерация меньшает len по крайней мере на 1, и в этом случае l[i+1] окажется заметно меньше l[i]. С другой стороны, при величении i на единицу величина l[i] может возрасти не более чем на 1, так что часто и сильно бывать она не может - иначе бывание не будет скомпенсировано возрастанием. Более точно, можно записать неравенство l[i+1]<l [i] - (число итераций на
i-м шаге)+1 или (число итераций на i-м шаге)<= l[i]-l[i+1]+1 Остается сложить эти неравенства по всем i и получить оценку сверху для общего числа итераций. Будем использовать этот алгоритм, чтобы выяснить, является ли слово X длины n
подсловом слова Y длины m. (Как это делать с помощью специального разделителя
#, описано выше.) При этом число действий будет не более C(n+m}, и используемая память тоже. Придумать, как обойтись памятью не более Cn (что может быть существенно меньше, если искомый образец короткий, слово, в котором его ищут
- длинное). Решение.
Применяем алгоритм КМП к слову А#В. При этом: вычисление значений l[1],...,l
[n] проводим для слова X длины n и запоминаем эти значения. Дальше мы помним только значение l[i] для текущего i - кроме него и кроме таблицы l[1]...l[n], нам для вычислений ничего не нужно. На практике слова X и Y могут не находиться подряд, поэтому просмотр слова X и затем слова Y добно оформить в виде разных циклов. Это избавляет также от хлопот с разделителем. Написать соответствующий алгоритм (проверяющий, является ли слово X=x[1]...x[n]
подсловом слова Y=y[1]...y[m] Решение.
Сначала вычисляем таблицу l[1]...l[n]как раньше. Затем пишем такую программу: j:=0;
len:=0; {len
- длина максимального качала слова X, одновременно являющегося концом слова y[1]..j[j]} while (len<>n) and (j<>m) do begin while (x[len+1]<>у[j+1]) and (len>0) do begin {начало не подходит, применяем к нему функцию l} len:
= l[len]; end; {нашли подходящее или бедились в отсутствии} if x[len+1]=y[j+1] do begin {x[1]..x[len]
- самое длинное подходящее начало} len:=len+1; end else begin {подходящих нет<} len:=0; end; j:=j+1; end; {если
len=n, слово X встретилось; иначе мы дошли до конца слова
Y, так и не встретив X} 3.3.2 Алгоритм Бойера-Мура Этот алгоритм делает то, что на первый взгляд кажется невозможным: в типичной ситуации он читает лишь небольшую часть всех букв слова, в котором ищется заданный образец. Как так может быть? Идея проста.
Пусть, например, мы ищем образец abcd. Посмотрим на четвертую букву слова:
если, к примеру, это буква e, то нет никакой необходимости читать первые три буквы. (В самом деле, в образце буквы e нет, поэтому он может начаться не раньше пятой буквы.) Мы приведем самый простой вариант этого алгоритма, который не гарантирует быстрой работы во всех случаях. Пусть
x[1]...х[n] - образец, который надо искать. Для каждого символа s найдем самое правое его вхождение в слово X, то есть наибольшее k, при котором х[k]=s. Эти сведения будем хранить в массиве pos[s]; если символ s вовсе не встречается, то нам будет добно положить pos[s]=0 (мы видим дальше, почему). Как заполнить массив pos? Решение. положить все pos[s] равными 0 for i:=1 to n do begin
end; В процессе поиска мы будем хранить в переменной last номер буквы в слове, против которой стоит последняя буква образца. Вначале last=n (длина образца), затем last постепенно увеличивается. last:=n; {все предыдущие положения образца же проверены}
{n - pos[y[last]] - это минимальный сдвиг образца, при котором напротив y[last]
встанет такая же буква в образце. Если такой буквы нет вообще, то сдвигаем на всю длину образца} если нынешнее положение подходит, т.е. если
то сообщить о совпадении; end; Знатоки рекомендуют проверку совпадения проводить справа налево, т.е. начиная с последней буквы образца (в которой совпадение заведомо есть). Можно также немного сэкономить, произведя вычитание заранее и храня не pos[s], n-pos[s], т.е. число букв в образце справа от последнего вхождения буквы Возможны разные модификации этого алгоритма. Например, можно строку last:=last+i заменить на last:=last+(n-u), где u - координата второго справа вхождения буквы x[n] в образец. Как проще всего честь это в программе Решение. При построении таблицы pos написать for
i:=1 to n-1 do... (далее как раньше), в основной программе вместо last:=last+1 написать last:=last+n-pos[y[last]]; Приведенный прощенный вариант алгоритма Бойера-Мура в некоторых случаях требует существенно больше n
действий (число действий порядка mn), проигрывая алгоритму Кнута-Морриса-Пратта. Пример ситуации, в которой образец не входит в слово, но алгоритму требуется порядка mn действий, чтобы это установить. Решение.
Пусть образец имеет вид b... aa, само слово состоит только из букв а.
Тогда на каждом шаге несоответствие выясняется лишь в последний момент. Настоящий (не прощенный)
алгоритм Бойера-Мура гарантирует, что число действий не превосходит C(m+n) в худшем случае. Он использует идеи, близкие к идеям алгоритма Кнута-Морриса-Пратта.
Представим себе, что мы сравнивали образец со входным словом, идя справа налево. При этом некоторый кусок Z (являющийся концом образца) совпал, затем обнаружилось различие: перед Z в образце стоит не то, что во входном слове. Что можно сказать в этот момент о входном слове? В нем обнаружен фрагмент, равный Z, перед ним стоит не та буква, что в образце. Эта информация может позволить сдвинуть образец на несколько позиций вправо без риска пропустить его вхождение. Эти сдвиги следует вычислить заранее для каждого конца Z нашего образца. Как говорят знатоки, все это (вычисление таблицы сдвигов и ее использование) можно ложить в C(m+ n) действий. 3.3.3 Алгоритм Рабина Этот алгоритм основан на простой идее.
Представим себе, что в слове длины m мы ищем образец длины n. Вырежем окошечко размера n и будем двигать его по входному слову. Нас интересует, не совпадает ли слово в окошечке с заданным образцом. Сравнивать по буквам долго. Вместо этого фиксируем некоторую функцию, определенную на словах длины
n. Если значения этой функции на слове в окошечке и на образце различны, то совпадения нет. Только если значения одинаковы, нужно проверять совпадение по буквам. В чем выигрыш при таком подходе. Казалось бы, ничего - ведь чтобы вычислить значение функции на слове в окошечке, все равно нужно прочесть все буквы этого слова. Так ж лучше их сразу сравнить с образцом. Тем не менее выигрыш возможен, и вот за счет чего. При сдвиге окошечка слово не меняется полностью, лишь добавляется буква в конце и убирается в начале. Хорошо бы, чтобы по этим данным можно было рассчитать, как меняется функция. Привести пример добной для вычисления функции. Решение.
Заменим все буквы в слове и образце их номерами, представляющими собой целые числа. Тогда добной функцией является сумма цифр. (При сдвиге окошечка нужно добавить новое число и вычесть пропавшее.) Для каждой функции существуют слова, к которым она применима плохо. Зато другая функция в этом случае может работать хорошо. Возникает идея: надо запасти много функций и в начале работы алгоритма выбирать из них случайную. (Тогда враг,
желающий подгадить нашему алгоритму, не будет знать, с какой именно функцией ему бороться.) Привести пример семейства добных функций. Решение.
Выберем некоторое число p (желательно простое, смотри далее) и некоторый вычет
x по модулю p. Каждое слово длины n будем рассматривать как последовательность целых чисел (заменив буквы кодами). Эти числа будем рассматривать как коэффициенты многочлена степени n-1 и вычислим значение этого многочлена по модулю p в точке x. Это и будет одна из функций семейства (для каждой пары p и
x получается, таким образом, своя функция). Сдвиг окошка на 1 соответствует вычитанию старшего члена (хn-1 следует вычислить заранее), множению на x и добавлению свободного члена. Следующее соображение говорит в пользу того, что совпадения не слишком вероятны. Пусть число p фиксировано и к тому же простое, X и Y - два различных слова длины n. Тогда им соответствуют различные многочлены (мы предполагаем, что коды всех букв различны - это возможно, если p больше числа букв алфавита). Совпадение значений функции означает, что в точке x эти два различных многочлена совпадают, то есть их разность обращается в 0. Разность есть многочлен степени n-1 и имеет не более
n-1 корней. Таким образом, если и много меньше p, то случайному x мало шансов попасть в неудачную точку. 4. ЗАКЛЮЧЕНИЕ. С развитием INTERNET появилась возможность быстрого и добного поиска необходимой документальной информации. Теперь можно не заниматься подбором и изучением огромного количества литературы в книжных магазинах и библиотеках. Информацию можно получить, не выходя из дома или офиса. Для этого нужен только непосредственно сам компьютер, подключенный к INTERNET с становленной специальной программой - браузером, предназначеной для просмотра содержимого Web<-страниц. Благодаря разнообразию поисковых систем, специально разработанным для рядового пользователя, каждый может без труда отсечь заведомо ненужный поток информации, лишь правильно сформулировав цель поиска. 5. СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ. 1. М. Пайк.
Internet. Пб.,
1996. 2.
Пол Гилстер. Навигатор Internet. М.,
1995 3. Энциклопедия Интернет, Пб,
2001 4. Информатика. Базовый курс.
Учебник для ВЗов, Пб, 2001 5.
How the browsers
compare//домен сайта скрыт/p>
6. Нэш К.//Война браузеров.-Сети.-1997г. 7. Крол Эд//Всё об
Internet.-Киев.-Торгово-изд. бюро BHV.-1995г. [N1]
