автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Программное обеспечение для метапоиска информации в гипертекстовой среде

Введение.

1. Анализ методов и систем поиска в гипертекстовых документах.

1.1. Особенности существующих метапоисковых систем.

1.2. Методы извлечения информации из неформальных документов.

1.3. Сравнения слов естественного языка.

1.4. Анализ предложения ограниченного естественного языка.

1.5. Выводы по первой главе.

2. Сравнение предложений естественного языка.

2.1. Схема сравнения предложений естественного языка.

2.2. Морфологический анализ, используемый метапоисковой системой.

2.3. Формальная грамматика предложения естественного языка.

2.4. Синтаксический анализ с использованием управляющих таблиц.

2.5. Модифицированный алгоритм построения П1(1)-таблиц.

2.6. Синтаксический анализатор предложения на основе LR(1) таблиц.

2.7. Возможности уменьшения неоднозначности грамматики.

2.8. Синтаксический анализ без использования управляющих таблиц.

2.9. Представление матрицы синтаксического анализатора предложения.

2.10. Модель представления синтаксиса предложения.

2.11. Критерий сходства предложений естественного языка.

2.12. Определение степени соответствия предложения и текста.

2.13. Выводы по второй главе.

3. Метод извлечения информации из поисковых систем.

3.1. Обмен информацией с поисковыми системами при метапоиске.

3.2. Передача запроса пользователя веб-узлу поисковой системы.

3.3. Структура выходной информации поисковой системы.

3.4. Анализ гипертекстовых страниц со списком найденных документов.

3.5. Алгоритм поиска повторяющихся подстрок.

3.6. Результаты экспериментов по извлечению информации из поисковых систем.

3.7. Поиск документов по ссылкам.

3.8. Выводы по третьей главе.

4. Метапоисковое программное обеспечение.

4.1. Назначение программы и требования к вычислительной системе.

4.2. Функциональная схема программного обеспечения.

4.3. Форматы используемых файлов данных.

4.4. Сравнение с существующими метапоисковыми системами.

4.5. Сравнение с поисковыми системами.

4.6. Выводы по четвертой главе.

Использование современных технологий в различных сферах общества привело к повсеместному распространению электронных носителей информации. Благодаря развитию глобальных сетей широкие слои пользователей смогли .получить доступ к большим объемам информации, представленной в электронном виде, причем в настоящее время наблюдается ее экспоненциальный рост [1]. Основная проблема при работе с большим объемом информации состоит в том, что обычно в нем необходимо найти некоторую конкретную информацию. Это задача информационного поиска, которая заключается в выделении из всего множества документов некоторого подмножества в соответствии с информационной потребностью пользователя.

Из-за постоянно увеличивающихся объемов доступной информации на выполнение поиска может потребоваться время, многократно превышающее время обработки отобранной в результате поиска информации. Особенно остро эта проблема стоит для источников информации, не являющихся структурированными. К структурированным источникам информации относят, например, реляционные базы данных, для которых существуют те или иные общепринятые способы извлечения информации (такие как язык запросов SQL [37]). Для неструктурированных источников информации подобных стандартных методов извлечения информации не существует.

Наиболее известным в настоящее время способом доступа к электронной информации является интернет, особенно его часть, называемая "всемирной паутиной" (world wide web, WWW). Информационное пространство интернета содержит огромное число источников информации, в большинстве своем неструктурированных. "Всемирная паутина" представляет собой практически неконтролируемый, постоянно обновляющийся и хаотично связанный набор отдельных источников информации - веб-узлов. Под гипертекстовой средой (рис. 1) далее понимается "всемирная паутина", или иная компьютерная сеть, поддерживающая протокол HTTP (HyperText Transfer Protocol - протокол передачи гипертекстов), т.е. совокупность связанных физически и гиперссылками веб-серверов, доступных пользователям.

Рис. 1. Гипертекстовая среда

Каждый веб-узел с точки зрения потребителя информации состоит из отдельных гипертекстовых страниц. Каждая страница является документом на языке разметки HTML и может содержать разнородную информацию (текст, изображение, звук). Поскольку текстовая информация является превалирующей и наиболее простой для автоматического анализа, с точки зрения поисковых систем можно считать страницы документом на естественном языке. Каждая страница содержит ссылки на другие ресурсы сети, такие как гипертекстовые страницы или файлы иных видов. Это могут быть ресурсы, как связанные с рассматриваемой страницей по смыслу (ссылки на аналогичные страницы на данном или другом веб-узле), так и не связанные (например, рекламного характера). Кроме того, ссылка может быть ошибочной, т.е. не указывать ни на один из веб-узлов, или недостоверной - например, указывать на отсутствующую страницу существующего узла. Также страница может включать в себя ссылки на саму себя. Возможно существование недостижимых страниц, ссылки на которые не содержит ни одна другая страница. В результате такая структура устроена достаточно хаотично, и поиск в ней информации по ссылкам может занять неопределенно долгое время.

Рис. 2. Схема функционирования поисковой системы в интернете

В настоящее время проблема поиска в интернете решается созданием многочисленных информационно-поисковых систем (рис. 2). До возникновения интернета в его современном виде информационно-поисковые системы применялись в основном для поиска в каталогах печатных изданий [16]. Между такими каталогами и интернетом как множеством электронных документов существует ряд отличий, главные из которых следующие.

1. В настоящее время интернет состоит из миллиардов гипертекстовых страниц. Возможно создание поисковых систем, охватывающих значительную часть интернета, однако такие системы должны неизбежно использовать автоматическое обнаружение и индексирование (выделение главной темы) документов.

2. В силу открытого характера интернета поисковые системы и индексируемые ими документы находятся на разных узлах и имеют различных владельцев. Поэтому с течением времени документы могут быть удалены, перемещены на другой адрес или удалены без уведомления поисковых систем. Таким образом, чем шире охват интернета поисковой системой, тем больше устаревшей информации содержит ее индекс документов. По этим же причинам результатом работы поисковых систем по сути являются ссылки на найденные документы, а не сами документы.

3. С точки зрения пользователя поисковая система является общедоступным веб-узлом. Таким образом поисковая система в интернете может использовать результаты работы других поисковых систем, обмениваясь с ними данными по протоколу HTTP.

Все поисковые системы в интернете разбивают на следующие классы по способу формирования поисковых образов документов и объему поискового массива.

К первому классу относят системы, индексирование документов в которых производится вручную создателем ресурса и ведущим поисковой системы. Обычно такие системы являются каталогами веб-узлов или отдельных документов, как тщательно отобранных в рамках узкой тематики (например, каталоги интернет-магазинов или ресурсов по второй мировой войне), так и всеобъемлющих, несущих обычно много недостоверной информации.

Ко второму классу принадлежат поисковые системы с максимально широким охватом информационного пространства интернета - поисковые машины. Поисковые машины снабжены средствами для автоматического сбора информации в гипертекстовой сети и ее индексирования. Информация о интернет-ресурсе может быть добавлена в индекс поисковой машины по запросу создателя ресурса или автоматически, при обнаружении ресурса по ссылке на него. Реальные коммерческие поисковые системы часто соединяют в себе поисковую машину и каталог.

Третий класс включает в себя системы поиска в пределах одного веб-узла, например поиск по каталогу интернет-магазина или по абстрактам статей, опубликованных издательством.

В поисковом массиве всех поисковых систем интернета хранится адрес документа и его поисковый образ. В некоторых поисковых системах хранится так же сам текст документа. Поисковая система предоставляет пользователям интернета сервис поиска по составленному указателю. Почти все существующие в интернете поисковые системы поддерживают два вида поисковых языков: основанные на иерархической или фасеточной классификации и дескрипторные (на базе слов естественного языка). Поисковые машины используют только дескрипторные языки.

Для ввода поисковых предписаний (запросов) на иерархическом языке в поисковых системах существует визуальное представление иерархии в виде гипертекстовой страницы. Поисковый запрос на дескрипторном языке является вводимым пользователем набором слов, возможно содержащим логические операторы и скобки. Кроме того, многие поисковые системы, особенно работающие с документами в пределах одного веб-узла, не используют логические связки в поисковом языке.

При обработке запроса на дескрипторном языке поисковая машина проверяет его совпадение с поисковыми образами документов. При индексации запросов и документов часть поисковых систем приводит все слова в них к начальной форме или отбрасывает окончания. Автоматически функционирующие поисковые машины не могут устранить синонимию и омонимию.

Несмотря на то, что существующие в настоящее время поисковые системы часто успешно решают проблему поиска, они не лишены определенных особенностей и даже недостатков, среди которых можно отметить следующие.

1. Существующие поисковые системы или ведут сравнение образа документа и запроса без учета морфологии, или используют только морфологический анализ для приведения всех слов к начальной форме. Синтаксический анализ предложения не используется поисковыми системами, что может привести, например, к ложной идентификации имеющих одинаковое написание слов, являющихся разными частями речи.

2. Увеличение индекса поисковой машины приводит к росту периода обновления информации. Чем больше индекс поисковой машины или каталога ресурсов, тем больше он содержит устаревшей информации. Крупные каталоги ресурсов, ведущиеся вручную, обычно не проверяют доступность и актуальность ресурсов автоматически, что так же приводит с течением времени к уменьшению доли "живых" ссылок.

3. При непосредственной обработке запроса пользователя поисковые машины обычно игнорируют какие-либо ссылки на смежные ресурсы, имеющиеся в документе, в результате чего пользователь вынужден сам просматривать их.

4. Поисковые машины не способны автоматически добавлять в каталог страницы, создаваемые при помощи передачи данных через формы HTML и интерфейса CGI (Common Gateway Interface - общий интерфейс обмена).

5. Некоторые поисковые машины включают в результаты поиска несколько ссылок на один и тот же документ.

Существует значительное количество поисковых машин, частично дублирующих друг друга, и большое число специализированных поисковых систем. При этом взаимное перекрытие баз данных даже наиболее крупных поисковых машин оценивается в 30-40% [49]. Таким образом, уже на первом этапе поиска пользователь вынужден работать с несколькими источниками информации. Каждая поисковая система, в свою очередь, часто возвращает значительное число найденных документов. Затем пользователь должен просмотреть содержимое найденных документов и, вероятно, продолжить поиск по найденным в документах ссылках. По сути пользователь вынужден вручную вести поиск "в глубину"" или "в ширину" в гипертекстовой среде как в ориентированном графе. Таким образом, встает задача интеграции отдельных поисковых систем, проверки найденных документов и автоматического продолжения поиска по ссылкам.

Рис. 3. Метапоисковая система

Для интеграции различных поисковых систем предназначены метапоисковые системы (рис. 3), которые не ведут собственный поисковый массив документов, храня вместо этого информацию об используемых поисковых системах. Такие системы передают запрос пользователя в другие поисковые системы, после чего передают полученные ответы пользователю. Работа метапоисковой системы состоит из трех этапов - выбор поисковых систем, в которые будет передан запрос пользователя, преобразование и передача запроса, а так же объединение и проверка результатов работы поисковых систем [29].

Принципиальным недостатком существующих метапоисковых систем является невозможность их настройки пользователем на извлечение информации из новых источников информации и ограниченность средств проверки возвращаемых результатов. Создание настраиваемой метапоисковой системы с расширенными средствами проверки найденных документов и возможностью поиска смежных документов дает возможность интеграции различных источников информации в соответствии с потребностями пользователя и приведет к уменьшению времени, необходимого для обработки результатов поиска.

В силу указанных особенностей существующих поисковых и метапоисковых систем разработка метапоискового программного обеспечения представляется важной и актуальной.

Целью работы является разработка программного обеспечения для метапоиска текстовой информации в гипертекстовой среде, позволяющего интегрировать несколько поисковых систем, проверять соответствие документов запросу пользователя на основе анализа естественного языка и вести поиск по найденным в документах ссылкам.

Разработка программного обеспечения в диссертации основана на решении следующих основных задач.

1. Создание метода извлечения информации о найденных по запросу пользователя документах из существующих информационно-поисковых систем.

Анализ существующих методов извлечения информации, разработанных С. Хсу [36], Н. Кушмериком [43], а также реализованных в различных метапоисковых программных продуктах, дан в первой главе. В третьей главе предложен алгоритм извлечения ссылок на документы метапоисковой системой.

2. Разработка критерия формального соответствия запроса пользователя и документа на естественном языке, основанном на синтаксическом анализе. Выбор метода синтаксического разбора естественного языка и его модификация для применения к анализу документов в гипертекстовой среде. Разработка алгоритма сравнения запроса пользователя и предложения на естественном языке.

Применимость методов анализа ограниченного естественного языка к задаче поиска информации исследуется в первой главе работы. Алгоритм сравнения предложений на основе анализа естественного языка описан во второй главе. Полученные результаты лежат в рамках направления, развиваемого М. Гаррисоном, С. Грехам [32, 33] и М. Томитой [55].

3. Создание программного средства - метапоисковой системы. Разработанное программное обеспечение описывается в четвертой главе.

Методы исследования. В диссертации применяются методы дискретной математики, теории формальных грамматик и формальных языков.

Научная новизна работы. Предложен метод анализа содержимого документов с текстовой разметкой, основанный на выделении повторяющихся конструкций языка разметки. Произведена модификация двух существующих методов разбора контекстно-свободных формальных языков для их применения в предложенной схеме сравнения предложений естественного языка. Разработана форма представления предложения естественного языка, методика ее получения из дерева вывода и основанный на ней алгоритм сравнения предложений.

Основные результаты работы. Предложен алгоритм выделения данных с результатами поиска из поисковых систем интернета на основе анализа повторяющихся конструкций гипертекстовой страницы. Показана его практическая применимость к существующим в настоящий момент поисковым системам. Даны теоретические и эмпирические оценки затрат времени, необходимого для обработки результатов работы поисковых систем.

В разработанном метапоисковом программном обеспечении использован механизм выделения релевантных документов на основе синтаксического анализа предложений естественного языка. Предложена модификация способа построения LR-таблиц для их использования в модифицированном алгоритме LR-разбора и модификация метода Эрли для неоднозначных грамматик. Для разработанных методов оценены временные затраты на разбор структуры предложения на ограниченном естественном языке и область применимости при разборе предложений естественного языка.

Предложен вариант дерева предложений, пригодный в качестве модели синтаксической структуры для сравнения предложений. Разработан алгоритм построения такого дерева предложения из дерева вывода, построенного синтаксическим анализатором. Разработан метод сравнения деревьев двух предложений, даны критерии сходства запроса пользователя и просматриваемого текста на естественном языке.

Практическая и теоретическая ценность. Полученные результаты позволяют извлекать информацию из большинства существующих поисковых систем и осуществлять синтаксический разбор предложений естественного языка с учетом его применения для поиска информации в глобальных сетях. Практическим результатом работы является программное обеспечение для метапоиска информации в интернет, внедренное в БЕН РАН, о чем имеется соответствующий акт.

Апробация результатов работы. Результаты диссертации докладывались в 2000 и 2001 годах на третьем и четвертом научно-практических семинарах "Новые электронные технологии" в МГИЭМ (г. Москва), и на восьмой международной конференции "Математика, компьютер, образование" (2001 г., г. Пущино).

Публикации. Основные результаты диссертационной работы опубликованы в пяти печатных трудах.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы и трех приложений. Диссертация изложена на 144 страницах текста, содержит 53 рисунка и 13 таблиц. Библиография состоит из 66 наименований.

4.6. Выводы по четвертой главе

Созданный программный продукт использует разработанные в диссертации методы извлечения информации из поисковых систем и определения соответствия документов на основе синтаксического анализа для метапоиска документов в гипертекстовой среде.

По сравнению с существующими аналогами, разработанный программный продукт имеет ряд принципиальных отличий, а именно: возможность применения к широкому классу поисковых систем при минимальной настройке со стороны пользователя и реализует новый критерий соответствия найденных документов запросу.

Проведенное сравнение созданного программного обеспечения с аналогами показало целесообразность использования разработанного метода метапоиска.

ЗАКЛЮЧЕНИЕ

1. Проведен анализ существующих в интернет поисковых систем и использующих их метапоисковых систем. Рассмотрены методы извлечения информации из гипертекстовых документов и методы синтаксического разбора естественного языка. Построена классификация существующих методов.

2. Предложена схема сравнения предложений естественного языка на основе синтаксического анализа при помощи формальных грамматик. Произведена модификация двух существующих методов разбора контекстно-свободных формальных языков для их применения в предложенной схеме. Проведено сравнение модифицированных алгоритмов синтаксического разбора, установлена применимость созданного метода для предложений английского языка.

3. Разработан алгоритм преобразования результатов синтаксического анализа в представление структуры предложения и алгоритм сравнения таких представлений.

4. Разработан метод извлечения результатов поиска из широкого класса поисковых систем. Создан алгоритм извлечения информации из гипертекстовых документов, содержащих списки, основанный на поиске часто повторяющихся конструкций. Проведены эксперименты по извлечению информации из существующих поисковых систем, подтверждена работоспособность метода.

5. Создано метапоисковое программное обеспечение, принципиальным отличием которого от существующих аналогов является возможность применения к широкому классу поисковых систем. В разработанном программном обеспечении реализован новый критерий соответствия найденных документов запросу пользователя. Проведенное сравнение созданного программного обеспечения с аналогами показало целесообразность использования разработанного метода метапоиска.

1. Бойцов JL Поиск по сходству в документальных базах данных // Программист. - 2001. - № 1. - С. 32 - 35.

2. Герман О.В. Введение в теорию экспертных систем и обработку знаний. -Минск.: ДизайнПРО., 1995. 256 с.

3. Керстеттер Д. Электронная торговля обогащается интеллектуальными агентами // PCWeek RE, № 10 от 18.03.1997.

4. Кирсанов Д. Веб-дизайн. СПб: Символ-Плюс, 1999. - 376 с.

5. Кнут Д. Искусство программирования для ЭВМ. В 3-х томах. М.: Мир, 1978. - Т. 3 - Сортировка и поиск. - 843 с.

6. Лахути Д.Г. Проблемы интеллектуализации информационно-поисковых систем: Диссертация в виде научного доклада на соискание ученой степени доктора технических наук. М., 1999. - 210 с.

7. Либерти Дж. Создание документов XML для Web на примерах. -М.: Вильяме, 2000. 256 с.

8. Овчинников С.М. XML: язык форматирования документов World Wide Web. -М.: Майор, 2001.-160 с.

9. Поляков В. Н. Синтез формальных моделей языка и смысла как проблема семантической обработки естественного языка // Новости искусственного интеллекта. 1997. -№ 1. - С. 6 - 63.

10. Ю.Попов Э. В. Общение с ЭВМ на естественном языке. М.: Наука, 1982. -360 с.

11. ГПэтчетт К., Райт М. CGI/Perl: создание программ для Web -Киев: Издательская группа BHV, 2000. 624 с.

12. Старшинова Е.К., Васильева М.А., Щилюгина А.И. Практическая грамматика английского языка. М.: Изд-во МГУ, 1970. - 214 с.

13. Урманн Дж. Oracle 8. Программирование на языке PL/SQL. М.: Лори, 1999. -610с.

14. Хольцшлаг М. Использование HTML 4. М: Вильяме, 2000. - 1008 с.

15. Черемных С.В., Семенов И.О., Ручкин B.C. Структурный анализ систем:

16. EF-технологии. М.: Финансы и статистика, 2001. - 208 с.

17. Черный А.И. Введение в теорию информационного поиска. М: Наука, 1975.-240 с.

18. Aho A.V., Johnson S.C., Ulman J.D. Deterministic parsing of ambiguous grammars // Communications of the ACM. 1975. - V. 18, № 8. - P. 441 - 452.

19. Aho A.V., Sethi R., Ullman J.D. Compilers: principles, techniques and tools. -Reading (MA): Addison-Wesley, 1986. 796 p.

20. Aho A.V., Ulman J.D. A Technique for speeding up LR(k) parsers // SIAM Journal of Computers. 1973. -V. 2, № 2. - P. 106 - 127.

21. Aho A. V., Ulman J.D. Optimization of LR(k) Parsers // Journal of Computer and System Sciences. 1972. - V. 6. - P. 573 - 602.21 .Anderson Т., Eve J., Horning J.J. Efficient LR(1) parsers // Acta Informatica. -1973.-V. 2.- P. 12-39.

22. Barton E.G., Berwick R.C., Ristad E.S. Computational complexity and natural language. Cambridge (MA): MIT Press, 1987. - 378 p.

23. Basch R., Bates M.E. Researching online for dummies. Foster City (CA): IDG Books Worldwide. - 1998. - 408 p.

24. Bouckaert M., Pirotte A., Snelling M. Efficient parsing algorithms for general context-free grammars // Information Sciences. 1975. - V. 8. - P. 1 - 26.

25. Chalker S., Weiner E. The Oxford dictionary of English grammar. Oxford: Oxford University Press, 1998. - 448 p.

26. Chomsky N. On certain formal properties of grammars // Information Control. -1959.-V. 2.-P. 137- 167.

27. Cocke J., Schwartz J.I. Programming languages and their compilers : preliminary notes. -NY: Courant Institute of Mathematical Sciences, 1970. 767 p.

28. Doorenbos R., Etzioni O., Weld D. A scalable comparison-shopping agent for the world wide web // Proc. First International Conference Autonomous Agents. -Marina del Rey, 1997. P. 39 - 48.

29. Dreilinger D., Howe, A. E. experiences with selecting search engines using metasearch // ACM Transactions on Information Systems. 1997. - V. 15, № 3. -P. 195-222.

30. Earley J. An efficient context-free parsing algorithm // Communications of ACM. 1970.-V. 13, №2.-P. 94- 102.

31. Freitag D. Information extraction from HTML: application of a general machine learning approach // Proc. AAAI-98. Madison (WI), 1998. - P. 517 - 523.

32. Graham S.L., Harrison M.A. Parsing of general context-free languages // Advances in Computing. 1976. - V. 14. - P. 77 - 185.

33. Graham S.L., Harrison M.A., Ruzzo W.L. An improved context-free recognizer // ACM Transactions on Programmnig Languages and Systems. 1980.1. V. 2, №3.-P. 415-462.

34. Gravano L., Garcia-Molina H. Generalizing GIOSS to vector-space databases and broker hierarchies // Proceedings of 21th International Conference on Very Large Data Bases Conference Zurich, 1995. - P. 78-89.

35. Grune D., Jacobs C. Parsing techniques: a practical guide. Chichester: Ellis Horwood Limited, 1990. - 332 p.

36. Hsu C., Dung M. Generating finite-state transducers for semi-structured data extraction from the web // Information Systems. 1998. - V. 23, №. 8.1. P. 521 538.

37. Hursch C.J. SQL, structured query language. Winddcrest: Blue Ridge, 1991. — 203 p.

38. Jansen В., Spink A., Bateman J. Real life information retrieval: a study of user queries on the web // ACM SIGIR Forum. 1998. -V. 32, №. 1. - P. 22-28.

39. Joshi A.K. An introduction to tree adjoining grammars // Mathematics of Language / A. Manaster-Ramer (ed.) Benjamins Publishing Company, 1987. -P. 87- 115.

40. Jul E. Now that we know the answer, what are the questions? // Journal Internet catalog. 1998.-V. 1,№3.-P. 9- 14.

41. Karp D., Schabes Y., Zaidel M. A freely available wide coverage morphological analyzer for English // Proceedings of the 14th International Conference on Computational Linguistics. Nantes, 1992 - P. 120 - 126.

42. Kasami Т., Torii K. A syntax-analysis procedure for unambiguous context-free grammars // Journal of ACM. 1969. - V.16, №. 3. - P. 423 - 431.

43. KushmerickN. Wrapper induction: efficiency and expressiveness // Artificial Intelligence. 2000. - V. 118 - P. 15 - 68.

44. Lawrence, S., Giles, C. L. Searching the World Wide Web // Science. 1998. -V.280.-P. 98-101.

45. Levy A.Y., Weld D.S. Intelligent internet systems // Artificial Intelligence. -2000.-V. 118-P. 1 14.

46. Lidsky, D., Kwon, R. Your complete guide to searching the Net // PC Magazine. 1997. - V. 16.-P. 227-229.

47. Maes P. Intelligent software // Scientific American. 1995. - V. 273, № 3. - P. 84 -86.

48. Meng W., Yu C., Wang X. Determining text databases to search in the internet // Proceedings of 24th International Conference on Very Large Data Bases Conference NY, 1998.-P. 14-25.

49. Notess, G. Measuring the size of internet databases // Database. 1997. - V 20. -P. 69-72.

50. Notess, G. R. Toward more comprehensive web searching: single searching versus megasearching // Online. 1998. - V. 3. - P. 52-58.

51. Learning to understand information on the internet: an example-based approach / Perkowitz M, Doorenbos R., Etzioni O., Weld D. // J. Intelligent Information Systems. 1997. - V. 8, № 2. - P. 133 - 153.

52. Shabes Y., Paroubek P. XT AG a graphical workbench for tree adjoining grammars // Proceedings 3rd Conference on Applied Natural Language Processing. - Trento, 1992. - P. 216-223.

53. Shang H., Merrett Т. H. Tries for approximate string matching // IEEE Trans, on Knowledge and Data Engineering. 1996.- V. 8, № 4. - P 540 - 547.

54. Sowa J.F. Conceptual Structures : Information processing in mind and machine. -Reading (MA): Addison-Wesley, 1984 481 p.

55. Tomita M. Efficient parsing for natural language. Boston: Kluwer Academic Publishers, 1986.-201 p.

56. Unger S.H. A global parser for context-free phrase structure grammars // Communications of ACM. 1968 - V. 11, № 4. - P. 240 - 247.

57. Wu S., Manber U. Fast text searching allowing errors // Communications of the ACM. 1992.- V. 35. - P. 83 - 91.л

58. Younger D.H. Recognition of context-free languages in time n // Information Control. 1967. - V. 10, № 2. - P. 189 - 208.

59. Yu C., Meng W. Principles of Database Query Processing for Advanced Applications. San Francisco: Morgan Kaufmann Publishers, 1998. - 512 p.

60. Крищенко B.A. Использование LR таблиц для разбора естественного языка // Исследовано в России: Электронный журнал 2000. - Т. 67. - С. 948 - 945г^http://zhurnal.ape.relarn.ru/articles/2000/067.pdf)

61. Крищенко В.А. Автоматизированная обработка информации в Интернет // Математика. Компьютер. Образование: Тезисы VIII международной конференции. М., 2001. - С. 174.

62. Крищенко В.А. Модель представления и критерий релевантности для предложения на естественном языке // Математическое и программное обеспечения вычислительных систем: Межвуз. сб. науч. тр. / РГРТА; Под ред. Л.П. Коричнева. Рязань, 2001. - С. 69 - 73.

63. Козлов А.Д, Крищенко В.А. Автоматическое извлечение информации из Интернет метапоисковым агентом // Новые электронные технологии: Материалы четвертого научно-практического семинара с участием стран СНГ. М., 2001. - С. 201 - 207.

64. Козлов А.Д, Крищенко В.А. Анализ текстов для информационного поиска в глобальных компьютерных сетях // Новые электронные технологии: Материалы третьего научно-практического семинара с участием стран СНГ. М., 2000. - С. 68 - 69.