Содержание к диссертации
Введение
1. Анализ методов и систем поиска в гипертекстовых документах 14
1.1. Особенности существующих метапоисковых систем 14
1.2. Методы извлечения информации из неформальных документов 17
1.3. Сравнения слов естественного языка 25
1.4. Анализ предложения ограниченного естественного языка 29
1.5. Выводы по первой главе 37
2. Сравнение предложений естественного языка 38
2.1. Схема сравнения предложений естественного языка 38
2.2. Морфологический анализ, используемый метапоисковой системой 39
2.3. Формальная грамматика предложения естественного языка 42
2.4. Синтаксический анализ с использованием управляющих таблиц 46
2.5. Модифицированный алгоритм построения 1Л(1)-таблиц 50
2.6. Синтаксический анализатор предложения на основе LR(1) таблиц 59
2.7. Возможности уменьшения неоднозначности грамматики 62
2.8. Синтаксический анализ без использования управляющих таблиц 63
2.9. Представление матрицы синтаксического анализатора предложения 68
2.10. Модель представления синтаксиса предложения 71
2.11. Критерий сходства предложений естественного языка 76
2.12. Определение степени соответствия предложения и текста 80
2.13. Выводы по второй главе 81
3. Метод извлечения информации из поисковых систем 82
3.1. Обмен информацией с поисковыми системами при метапоиске 82
3.2. Передача запроса пользователя веб-узлу поисковой системы 83
3.3. Структура выходной информации поисковой системы 87
3.4. Анализ гипертекстовых страниц со списком найденных документов 90
3.5. Алгоритм поиска повторяющихся подстрок 98
3.6. Результаты экспериментов по извлечению информации из поисковых систем 105
3.7. Поиск документов по ссылкам 109
3.8. Выводы по третьей главе 109
4. Метапоисковое программное обеспечение 111
4.1. Назначение программы и требования к вычислительной системе 111
4.2. Функциональная схема программного обеспечения 113
4.3. Форматы используемых файлов данных 124
4.4. Сравнение с существующими метапоисковыми системами 127
4.5. Сравнение с поисковыми системами 130
4.6. Выводы по четвертой главе 130
Заключение 132
Литература 133
Приложение
- Методы извлечения информации из неформальных документов
- Морфологический анализ, используемый метапоисковой системой
- Передача запроса пользователя веб-узлу поисковой системы
- Функциональная схема программного обеспечения
Введение к работе
Использование современных технологий в различных сферах общества привело к повсеместному распространению электронных носителей информации. Благодаря развитию глобальных сетей широкие слои пользователей смогли .получить доступ к большим объемам информации, представленной в электронном виде, причем в настоящее время наблюдается ее экспоненциальный рост [1]. Основная проблема при работе с большим объемом информации состоит в том, что обычно в нем необходимо найти некоторую конкретную информацию. Это задача информационного поиска, которая заключается в выделении из всего множества документов некоторого подмножества в соответствии с информационной потребностью пользователя.
Из-за постоянно увеличивающихся объемов доступной информации на выполнение поиска может потребоваться время, многократно превышающее время обработки отобранной в результате поиска информации. Особенно остро эта проблема стоит для источников информации, не являющихся структурированными. К структурированным источникам информации относят, например, реляционные базы данных, для которых существуют те или иные общепринятые способы извлечения информации (такие как язык запросов SQL [37]). Для неструктурированных источников информации подобных стандартных методов извлечения информации не существует.
Наиболее известным в настоящее время способом доступа к электронной информации является интернет, особенно его часть, называемая "всемирной паутиной" (world wide web, WWW). Информационное пространство интернета содержит огромное число источников информации, в большинстве своем неструктурированных. "Всемирная паутина" представляет собой практически неконтролируемый, постоянно обновляющийся и хаотично связанный набор отдельных источников информации - веб-узлов. Под гипертекстовой средой (рис. 1) далее понимается "всемирная паутина", или иная компьютерная сеть, поддерживающая протокол HTTP (HyperText Transfer Protocol - протокол передачи гипертекстов), т.е. совокупность связанных физически и гиперссылками веб-серверов, доступных пользователям.
Веб-узел
Рис. 1. Гипертекстовая среда
Каждый веб-узел с точки зрения потребителя информации состоит из отдельных гипертекстовых страниц. Каждая страница является документом на языке разметки HTML и может содержать разнородную информацию (текст, изображение, звук). Поскольку текстовая информация является превалирующей и наиболее простой для автоматического анализа, с точки зрения поисковых систем можно считать страницы документом на естественном языке. Каждая страница содержит ссылки на другие ресурсы сети, такие как гипертекстовые страницы или файлы иных видов. Это могут быть ресурсы, как связанные с рассматриваемой страницей по смыслу (ссылки на аналогичные страницы на данном или другом веб-узле), так и не связанные (например, рекламного характера). Кроме того, ссылка может быть ошибочной, т.е. не указывать ни на один из веб-узлов, или недостоверной - например, указывать на отсутствующую страницу существующего узла. Также страница может включать в себя ссылки на саму себя. Возможно существование недостижимых страниц, ссылки на которые не содержит ни одна другая страница. В результате такая структура устроена достаточно хаотично, и поиск в ней информации по ссылкам может занять неопределенно долгое время.
Адреса найденных документов
Рис, 2. Схема функционирования поисковой системы в интернете
В настоящее время проблема поиска в интернете решается созданием многочисленных информационно-поисковых систем (рис. 2). До возникновения интернета в его современном виде информационно-поисковые системы применялись в основном для поиска в каталогах печатных изданий [16]. Между такими каталогами и интернетом как множеством электронных документов существует ряд отличий, главные из которых следующие.
1. В настоящее время интернет состоит из миллиардов гипертекстовых страниц. Возможно создание поисковых систем, охватывающих значительную часть интернета, однако такие системы должны неизбежно использовать автоматическое обнаружение и индексирование (выделение главной темы) документов.
2. В силу открытого характера интернета поисковые системы и индексируемые ими документы находятся на разных узлах и имеют различных владельцев. Поэтому с течением времени документы могут быть удалены, перемещены на другой адрес или удалены без уведомления поисковых систем. Таким образом, чем шире охват интернета поисковой системой, тем больше устаревшей информации содержит ее индекс документов. По этим же причинам результатом работы поисковых систем по сути являются ссылки на найденные документы, а не сами документы.
3. с точки зрения пользователя поисковая система является общедоступным веб-узлом. Таким образом поисковая система в интернете может использовать результаты работы других поисковых систем, обмениваясь с ними данными по протоколу HTTP.
Все поисковые системы в интернете разбивают на следующие классы по способу формирования поисковых образов документов и объему поискового массива.
К первому классу относят системы, индексирование документов в которых производится вручную создателем ресурса и ведущим поисковой системы. Обычно такие системы являются каталогами веб-узлов или отдельных документов, как тщательно отобранных в рамках узкой тематики (например, каталоги интернет-магазинов или ресурсов по второй мировой войне), так и всеобъемлющих, несущих обычно много недостоверной информации.
Ко второму классу принадлежат поисковые системы с максимально широким охватом информационного пространства интернета - поисковые машины. Поисковые машины снабжены средствами для автоматического сбора информации в гипертекстовой сети и ее индексирования. Информация о интернет-ресурсе может быть добавлена в индекс поисковой машины по запросу создателя ресурса или автоматически, при обнаружении ресурса по ссылке на него. Реальные коммерческие поисковые системы часто соединяют в себе поисковую машину и каталог.
Третий класс включает в себя системы поиска в пределах одного веб-узла, например поиск по каталогу интернет-магазина или по абстрактам статей, опубликованных издательством.
В поисковом массиве всех поисковых систем интернета хранится адрес документа и его поисковый образ. В некоторых поисковых системах хранится так же сам текст документа. Поисковая система предоставляет пользователям интернета сервис поиска по составленному указателю. Почти все существующие в интернете поисковые системы поддерживают два вида поисковых языков: основанные на иерархической или фасеточной классификации и дескрипторные (на базе слов естественного языка). Поисковые машины используют только дескрипторные языки.
Для ввода поисковых предписаний (запросов) на иерархическом языке в поисковых системах существует визуальное представление иерархии в виде гипертекстовой страницы. Поисковый запрос на дескрипторном языке является вводимым пользователем набором слов, возможно содержащим логические операторы и скобки. Кроме того, многие поисковые системы, особенно работающие с документами в пределах одного веб-узла, не используют логические связки в поисковом языке.
При обработке запроса на дескрипторном языке поисковая машина проверяет его совпадение с поисковыми образами документов. При индексации запросов и документов часть поисковых систем приводит все слова в них к начальной форме или отбрасывает окончания. Автоматически функционирующие поисковые машины не могут устранить синонимию и омонимию.
Несмотря на то, что существующие в настоящее время поисковые системы часто успешно решают проблему поиска, они не лишены определенных особенностей и даже недостатков, среди которых можно отметить следующие.
Существующие поисковые системы или ведут сравнение образа документа и запроса без учета морфологии, или используют только морфологический анализ для приведения всех слов к начальной форме. Синтаксический анализ предложения не используется поисковыми системами, что может привести, например, к ложной идентификации имеющих одинаковое написание слов, являющихся разными частями речи.
Увеличение индекса поисковой машины приводит к росту периода обновления информации. Чем больше индекс поисковой машины или каталога ресурсов, тем больше он содержит устаревшей информации. Крупные каталоги ресурсов, ведущиеся вручную, обычно не проверяют доступность и актуальность ресурсов автоматически, что так же приводит с течением времени к уменьшению доли "живых" ссылок.
При непосредственной обработке запроса пользователя поисковые машины обычно игнорируют какие-либо ссылки на смежные ресурсы, имеющиеся в документе, в результате чего пользователь вынужден сам просматривать их.
Поисковые машины не способны автоматически добавлять в каталог страницы, создаваемые при помощи передачи данных через формы HTML и интерфейса CGI (Common Gateway Interface - общий интерфейс обмена).
Некоторые поисковые машины включают в результаты поиска несколько ссылок на один и тот же документ.
Существует значительное количество поисковых машин, частично дублирующих друг друга, и большое число специализированных поисковых систем. При этом взаимное перекрытие баз данных даже наиболее крупных поисковых машин оценивается в 30-40% [49]. Таким образом, уже на первом этапе поиска пользователь вынужден работать с несколькими источниками информации. Каждая поисковая система, в свою очередь, часто возвращает значительное число найденных документов. Затем пользователь должен просмотреть содержимое найденных документов и, вероятно, продолжить поиск по найденным в документах ссылках. По сути пользователь вынужден вручную вести поиск "в глубину" или "в ширину" в гипертекстовой среде как в ориентированном графе. Таким образом встает задача интеграции отдельных поисковых систем проверки найденных документов и автоматического продолжения поиска по ссылкам.
Адреса пайденных документов
Рис. 3. Метапоисковая система
Для интеграции различных поисковых систем предназначены метапоисковые системы (рис.3), которые не ведут собственный поисковый массив документов, храня вместо этого информацию об используемых поисковых системах. Такие системы передают запрос пользователя в другие поисковые системы, после чего передают полученные ответы пользователю. Работа метапоисковой системы состоит из трех этапов - выбор поисковых систем, в которые будет передан запрос пользователя, преобразование и передача запроса а так же объединение и проверка результатов работы поисковых систем [29].
Принципиальным недостатком существующих метапоисковых систем является невозможность их настройки пользователем на извлечение информации из новых источников информации и ограниченность средств проверки возвращаемых результатов. Создание настраиваемой метапоисковой системы с расщиренными средствами проверки найденных документов и возможностью поиска смежных документов дает возможность интеграции различных источников информации в соответствии с потребностями пользователя и приведет к уменьщению времени, необходимого для обработки результатов поиска.
В силу указанных особенностей существующих поисковых и метапоисковых систем разработка метапоискового программного обеспечения представляется важной и актуальной.
Целью работы является разработка программного обеспечения для метапоиска текстовой информации в гипертекстовой среде, позволяющего интегрировать несколько поисковых систем, проверять соответствие документов запросу пользователя на основе анализа естественного языка и вести поиск по найденным в документах ссылкам.
Разработка программного обеспечения в диссертации основана на рещении следующих основных задач.
1. Создание метода извлечения информации о найденных по запросу пользователя документах из существующих информационно-поисковых систем.
Анализ существующих методов извлечения информации, разработанных С. Хсу [36], Н.Кушмериком [43], а также реализованных в различных метапоисковых программных продуктах, дан в первой главе. В третьей главе предложен алгоритм извлечения ссылок на документы метапоисковой системой.
2. Разработка критерия формального соответствия запроса пользователя и документа на естественном языке, основанном на синтаксическом анализе. Выбор метода синтаксического разбора естественного языка и его модификация для применения к анализу документов в гипертекстовой среде. Разработка алгоритма сравнения запроса пользователя и предложения на естественном языке.
Применимость методов анализа ограниченного естественного языка к задаче поиска информации исследуется в первой главе работы. Алгоритм сравнения предложений на основе анализа естественного языка описан во второй главе. Полученные результаты лежат в рамках направления, развиваемого М. Гаррисоном, С. Грехам [32, 33] и М. Томитой [55].
3. Создание программного средства - метапоисковой системы. Разработанное программное обеспечение описывается в четвертой главе.
Методы исследования. В диссертации применяются методы дискретной математики, теории формальных грамматик и формальных языков.
Научная новизна работы. Предложен метод анализа содержимого документов с текстовой разметкой, основанный на выделении повторяющихся конструкций языка разметки. Произведена модификация двух существующих методов разбора контекстно-свободных формальных языков для их применения в предложенной схеме сравнения предложений естественного языка. Разработана форма представления предложения естественного языка, методика ее получения из дерева вывода и основанный на ней алгоритм сравнения предложений.
Основные результаты работы. Предложен алгоритм выделения данных с результатами поиска из поисковых систем интернета на основе анализа повторяющихся конструкций гипертекстовой страницы. Показана его практическая применимость к существующим в настоящий момент поисковым системам. Даны теоретические и эмпирические оценки затрат времени, необходимого для обработки результатов работы поисковых систем.
В разработанном метапоисковом программном обеспечении использован механизм выделения релевантных документов на основе синтаксического анализа предложений естественного языка. Предложена модификация способа построения LR-таблиц для их использования в модифицированном алгоритме LR-разбора и модификация метода Эрли для неоднозначных грамматик. Для разработанных методов оценены временные затраты на разбор структуры предложения на ограниченном естественном языке и область применимости при разборе предложений естественного языка.
Предложен вариант дерева предложений, пригодный в качестве модели синтаксической структуры для сравнения предложений. Разработан алгоритм построения такого дерева предложения из дерева вывода, построенного синтаксическим анализатором. Разработан метод сравнения деревьев двух предложений, даны критерии сходства запроса пользователя и просматриваемого текста на естественном языке.
Практическая и теоретическая ценность. Полученные результаты позволяют извлекать информацию из большинства существующих поисковых систем и осуществлять синтаксический разбор предложений естественного языка с учетом его применения для поиска информации в глобальных сетях. Практическим результатом работы является программное обеспечение для метапоиска информации в интернет, внедренное в БЕН РАН, о чем имеется соответствующий акт.
Апробация результатов работы. Результаты диссертации докладывались в 2000 и 2001 годах на третьем и четвертом научно-практических семинарах "Новые электронные технологии" в МГИЭМ (г.Москва), и на восьмой международной конференции "Математика, компьютер, образование" (2001 г., г. Пущино).
Публикации. Основные результаты диссертационной работы опубликованы в пяти печатных трудах.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы и трех приложений. Диссертация изложена на 144 страницах текста, содержит 53 рисунка и 13 таблиц. Библиография состоит из 66 наименований.
Методы извлечения информации из неформальных документов
Одной из задач, решаемой метапоисковой системой, является работа с интерфейсом поисковых систем для передачи им запроса пользователя и получения адресов найденных документов. Все поисковые системы интернет предназначены прежде всего для работы с конечным пользователем, поэтому их интерфейс разработан для человека. Таким образом, для реализации метапоискового программного обеспечения необходимо разработать метод автоматического обмена данными с существующими информационно-поисковыми системами, реализованными в виде веб-узлов. Такие системы позволяют пользователю при помощи веб-интерфейса ввести запрос и затем передают ему гипертекстовые страницы с результатами поиска, содержащие список адресов найденных документов в произвольной форме. Кроме адресов и других атрибутов найденных документов, такие страницы могут содержать любую постороннюю информацию. Поэтому одной из задач, которую необходимо решить в разрабатываемом программном обеспечении является извлечение информации из документов, имеющих определенную внутреннюю структуру и предназначенных для просмотра человеком. Такие страницы включает набор записей, каждая из которых состоит из отдельных атрибутов (полей). В случае страниц, выдаваемых поисковыми системами в ответ на запрос пользователя, запись может включать такие поля, как гипертекстовая ссылка на найденный ресурс, его название, степень соответствия запросу пользователя, адрес, дата модификации и другие свойства найденного документа и/или веб-узла, которому он принадлежит. Поля обычно отделяются друг от друга некоторой последовательностью конструкций языка разметки страницы.
Задача извлечения информации из представленных в виде гипертекстовых страниц результатов работы поисковых систем заключается в выделении адресов найденных документы. Выделение остальных свойств найденных документов не является обязательным для функционирования метапоисковой системы. Кроме того, адрес найденного документа всегда представлен гиперссылкой на него, в то время как набор и форма представления остальных атрибутов документа отличается для различных поисковых систем.
Можно предъявить следующие требования к анализатору гипертекстовых страниц с результатами поиска, которой будет применен в разрабатываемой метапоисковой системе [45]. 1. Анализатор должен отделять полезные ссылки (на найденные поисковой системой документы) от всех прочих. Кроме того, анализатор должен быть способен извлекать из каждой страницы ссылки на остальные страницы с результатами поиска, поскольку, как правило, результаты поиска размещаются на нескольких страницах. 2. Анализатор должен охватывать как можно более широкий класс поисковых систем, поэтому он должен использовать минимум предположений о разметке страницы с результатами поиска. 3. Анализатор должен пытаться автоматически подстраиваться под различную разметку страниц с результатами поиска, в том числе в пределах одной поисковой системы.
В настоящее время в качестве языка разметки гипертекстовых документов интернета в основном используется HTML 4.0 (Hyperext Markup Language -язык разметки гипертекстов [14], официальная информация о котором находится по адресу http://www.w3.org/). HTML-документ состоит из особых конструкций, называющихся тегами, и текста между ними. Каждый тег имеет имя и может содержать набор атрибутов. Часть тегов должна иметь парный закрывающий тег. На рис 1.2 приведен фрагмент HTML-страницы с тремя гипертекстовыми ссылками на иные HTML-документы. определяют способ представления заключенного между ними текста на экране или ином устройстве вывода. По способу задания этого представления все теги можно условно разделить на теги логической и физической разметки [4]. Теги логической разметки, рекомендованные в HTML версии 2.0, не дают прямых указаний на то, как должна отображаться информация на экране, оставляя окончательное решение этого вопроса за программой просмотра HTML-страниц. С другой стороны, они позволяют определить логическую структуру представленной в документе информации. К таким тегам относятся теги заголовков ( hl , h2 , h3 ), теги указания значимости текста ( em , strong ), теги описания списков ( dl , dt , dd , li ) и некоторые другие ( cite , var и т.д.). Извлечение информации из страниц поисковой системы можно было бы построить на анализе структуры страницы, размеченной тегами логической разметки. Таким образом, использование только тэгов логической разметки позволило бы значительно упростить поставленную задачу извлечения информации. Однако, в связи с растущими требованиями потребителей и поставщиков информации к увеличению гибкости HTML в стандарте HTML 3.2 было введено большое количество тэгов физической разметки, используемых в настоящее время повсеместно. Такие теги (например, font и div ) позволяют достаточно жестко определить способ представления информации на экране, но не имеют определенного логического содержания. В HTML 3.2 и 4.0 появилась также поддержка механизма спецификаций стилей (Cascading Style Sheets, CSS). Данный механизм позволил точно управлять всеми аспектами визуального представления документа, но с точки зрения выявления логической структуры документа он обычно не несет полезной информации.
Таким образом, автоматическое выделение результатов поиска из гипертекстовых страниц, созданных произвольной поисковой системой, представляет определенную трудность.
Морфологический анализ, используемый метапоисковой системой
Морфологический анализ должен определить все возможные наборы морфологических признаков для данного слова. Он заключается в поиске в словаре выделенной из предложения словоформы. Для сокращения времени поиска в морфологическом словаре используется хеширование по первым двум буквам слова. Структура словаря представлена на рис 2.2. Подробнее состав используемого морфологического словаря и способ его построения с точки зрения лингвистики описан в приложении.
Морфологический анализатор ищет слово в хешированном списке словоформ и выдает в качестве результата морфологического разбора все возможные начальные формы и соответствующие им морфологические признаки. Одно и то же по написанию слово может принадлежать к различным частям речи, поэтому отделенный от синтаксиса морфологический анализатор в общем случае не может однозначно распознать словоформу из входного предложения. Эта неоднозначность во многих случаях может быть уменьшена в ходе синтаксического анализа, когда некоторые варианты морфологического разбора предложения не будут удовлетворять формальной грамматике, описывающей структуру предложения. Если же на основе неверного (с точки зрения человека) результата морфологического анализа синтаксическому анализатору удастся построить некоторую структуру предложения, то это может быть как следствием двусмысленности естественного языка, так и свидетельством некорректности формальной грамматики, описывающей структуру предложения.
Если слово из разбираемого предложения не обнаружено в морфологическом словаре, то это может означать, что в написании известного слова содержится ошибка. Исходя из предположения о малой вероятности ошибки в первых двух символах слова [1], анализатор должен рассмотреть все слова с тем же двухбуквенным префиксом и определить количество элементарных операций, необходимых для преобразования словоформы в словаре в неизвестное слово из предложения. Под элементарными операциями подразумевается удаление вставка или замена одного символа а также перестановка двух символов местами. Как кандидаты на правильное написание слова должны быть рассмотрены те словоформы для которых количество таких операций не превышает ПОРоГОВОГО значения (обычно в качестве него используется 1 или 2)
Возможно, что неизвестное слово является новым словом, отсутствующем в словаре. Следует рассмотреть не менее двух случаев: термин может быть существительным или прилагательным. Вероятность появления новых глаголов и других частей речи существенно меньше [41]. Способность морфологического анализатора определить возможные части речи для неизвестного слова в значительной степени зависит от естественного языка. Например, для русского языка часто имеется возможность по окончанию слова однозначно определить его часть речи, для английского языка это практически невозможно.
Поскольку синтаксический анализатор формального языка оперирует с цепочкой символов из формального алфавита, то после завершения морфологического анализа каждому варианту разбора слова надо поставить в соответсиве символ из алфавита, используемый синтаксическим анализатором. Это преобразование и используемый формальный алфавит зависят от применяемой анализатором формальной грамматики предложения (см. 2.3). В таблице 2 приведена часть возможного преобразования для английского языка. Формальный алфавит для такого преобразования будет иметь следующий вид: V-p {п, рп, adj, a, а, comma, that, and).
Все возможные цепочки, соответствующие предложению, создаются как сочетания для всех возможных символов для каждого слова или знака препинания. Каждая полученная на основе результатов морфологического анализа цепочка символов разбирается синтаксическим анализатором. Однако, число таких цепочек для английского языка растет как т", где п - количество слов в предложении, т - оценка числа вариантов морфологического разбора для одного слова. Абсолютное большинство таких цепочек содержит неправильный морфологическим разбор того или иного слова с точки зрения человека. Поэтому следует передавать синтаксическому анализатору по одному символу для каждой цепочки. Синтаксический анализатор должен в этом случае отвергнуть неправильные цепочки по некоторому префиксу, а не прочитав цепочку до конца, если это возможно.
Передача запроса пользователя веб-узлу поисковой системы
Для передачи запроса пользователя в поисковую систему необходимо сформировать адрес первой гипертекстовой страницы с результатами поиска. Для существующих систем это адрес программы, работающей через интерфейс CGI [11], которая создает HTML-страницы с результатами поиска. Данные в такую программу передаются со стартовой страницы системы, адрес которой указывается пользователем (например, http://yandex.ru или На указанной странице необходимо найти конструкцию языка HTML [14], отвечающую за передачу запроса в поисковую систему. Она имеет вид form action= .. ... /form и называется в дальнейшем формой. Если на стартовой странице присутствует несколько форм, то одна из них может быть выбрана на основе следующих критериев. 1) Форма для ввода запроса поиска обязательно включает текстовое поле, обозначаемое такими конструкциями HTML, как input type=text ... или textarea ... ... /textarea (последний вариант в настоящий момент не встречается, но теоретически возможен). Результаты исследования существующих поисковых систем показывают, что поле для ввода запроса пользователя имеет наибольшую ширину из всех текстовых полей страницы (атрибут width тега input ).
Кроме того, такое текстовое поле может иметь адекватное своему назначению название (атрибут пате), такое как "query". 2) В существующих поисковых машинах основная форма поиска находится ближе к началу страницы при ее просмотре пользователем при помощи http-клиента. 3) Имя указанной в форме программы CGI, которой передаются данные (атрибут action тега form) обычно включает слова search, query и т.д., например, "query.cgi". Однако возможен случай, когда несколько форм документа ссылаются на одну и ту же программу или адреса нескольких программ отвечают этому критерию. 4) Имя или текст кнопки для передачи запроса пользователя поисковой системе обычно содержит такие слова, как search в атрибутах value, пате или alt. После нахождения на странице формы для ввода пользователем запроса для поиска необходимо сформировать адрес первой страницы с результатами поиска. Он состоит из адреса программы (атрибут action тега form ) и ее параметров, соответствующих различным элементам управления (полям) формы, например Для подготовки списка параметров необходимо проанализировать поля найденной формы. Все их можно разделить на следующие виды. 1) Поля ввода текста, имеющие вид input type=text пате=[имя поля]... (возможно так же использование тега textarea ). Самое широкое из таких полей предназначено для ввода запроса пользователя. Этому полю в адресе первой странице с результатами соответствует параметр вида [имя поля]=[запрос поиска], значением которого является запрос пользователя, преобразованный по правилам передачи текста через интерфейс CGI [11]. Если форма содержит иные текстовые поля, то метапоисковая система вынуждена их игнорировать, поскольку невозможно автоматически определить, для чего именно они используются. Так же нужно учесть, что у тэга input атрибут type по умолчанию имеет значение text, поэтому некоторые поисковые системы описывают поле ввода опуская этот атрибут например: input name=search size=20 .
Функциональная схема программного обеспечения
Составим функциональную схему созданного метапоискового программного средства в соответствии со стандартом IDEFO [15]. Рассматривая метапоисковую систему на верхнем уровне (рис. 4.1), можно выделить ее вход (информационная потребность пользователя) и выход (найденные документы). Для функционирования метапоисковой системы необходимо существование поисковых систем. Для описания естественного языка требуется специалист по компьютерной лингвистике. Поиск документов ведется в гипертекстовой среде. На рис. 4.2. показана схема дальнейшей детализации функций разработанной метапоисковой системы. Далее представлено описание функций в порядке, соответствующему рис 4.2. На рис 4.3 изображен первый уровень детализации ИМС с выделением следующих основных функций: - подготовка специалистом по компьютерной лингвистике формального описания ограниченного естественного языка с помощью ИМС; - автоматизированная настройка ИМС на извлечения данных из необходимых пользователю поисковых систем; - обмен информацией между ИМС и поисковыми системами с целью получения результатов поиска по запросу пользователя; - проверка ИМС полученной от поисковых систем информации и поиск новых документов, соответствующих запросу пользователя.
Подготовка формализованного описания естественного языка заключается в создании морфологического словаря, словаря синонимов и формальной грамматики, задающей возможные структуры предложения (рис 4.4). Кроме того, устанавливаются правила преобразования слов с теми или иными морфологическими признаками в терминалы грамматики. Специалист по лингвистике может протестировать разработанные словари и грамматику на примерах, представляющих собой цепочки терминалов из алфавита грамматики или целые предложения на естественном языке. На этапе тестирования грамматики система может использовать любой из двух описанных во второй главе синтаксических анализаторов. Функциональная схема использующегося при тестировании синтаксического анализа в целом совпадает со схемой анализа при разборе документов, которая приведена далее на рис. 4.10. В разработанную систему уже входит морфологический словарь английского языка и грамматика структуры предложения для английского языка, описанные в приложениях 1 и 2 соответственно.
Перед использованием разработанной метапоисковой системы пользователю необходимо задать адреса стартовых страниц существующих поисковых систем и проверить возможности программного обеспечения по автоматическому извлечению информации из них (рис. 4.5). Под тестовым запросом на рис. 4.5 понимается такой запрос, для которого поисковая система возвратит не меньше двух страниц с результатами поиска. В системе имеются следующие настройки для более гибкого извлечения информации. 1. Система может пытаться задать заданное пользователем число результатов, выводимых на одной странице, возвращаемой поисковой системой. Для этого системе нужно найти в форме поиска параметр, выбираемый из списка целых значений. 2. Пользователь может указать для каждой поисковой системы параметры сценариев CGI, указывающие, что включающие их ссылки не являются ссылками на найденные документами. Например, имена параметров lang или language обычно указывают на ссылки автоматического перевода. Кроме того, можно указать типичные имена перенаправляющих сценариев CGI (например, redir) и указать на необходимость выявлять перенаправляющие ссылки. 3. Пользователь может дать ИМС указание извлекать только внутренние или только внешние ссылки. Например, при настройке на поисковую машину следует дать указание извлекать только внешние ссылки, а при настройке на поиск по каталогу журналов - только внутренние. 4.
Пользователь должен указать для каждой подключаемой поисковой системы максимальное число страниц с результатами, которое будет обработано. ИМС может определять формальную релевантность найденных документов запросу пользователя и прекращать извлечение информации из поисковой систем, когда велича релевантности опускается ниже заданного пользователем порогового значения. 5. Пользователь может явно указать, какой вид ссылки на последующие страницы поиска используется поисковой системой: гиперссылка или кнопка, в противном случае система пытается определить это автоматически. При настройке системы можно указать возможные подстроки имени кнопки, указывающую на следующую страницу с результами поиска.
Имеется возможность проверить работу ИМC для различных вариантов настройки для каждой поисковой системы. Процесс извлечения информации из поисковых систем в целом совпадает с показанным далее на рис. 4.7 и будет описан ниже. Если ИМС не способна правильно выделить ссылки на найденные документы из какой-либо поисковой системы, то пользователь может выбрать одну из найденных повторяющихся цепочек в качестве окружения ссылки. Разработанная программа позволяет организовывать список используемых поисковых систем в виде дерева, произвольно объединяя их таким образом в категории и подкатегории произвольного уровня вложенности. Поисковые машины можно перемещать между категориями и сортировать в пределах одной категории.
