Восходящий анализ

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

Пусть требуется определить принадлежность нашему языку следующие формы: «он кот». Для этой строки в нашей грамматике фразами являются «он» и «кот», причем «он» - это основа. Приведение он→ <М> дает строку <М> и <кот>, причем основа → <М>:

он→<М>

<М> кот, <П><кот>, <П><ис>, <П><П> - некорректно.

1. Автоматическое индексирование. Автоматическое аннотирование и реферирование. Автоматическая классификация документов. Пример программ автоматического реферирования, принцип работы. Модели, Методы и программы реферирования.

Автоматическое аннотирование и реферирование (summarization)

Реферирование подразделяют на несколько категорий в зависимости от целей составления реферата:

- повествовательный реферат (формируется по классическому способу извлечения информации и имеет достаточный объем);

- информативный реферат (главная цель - выборка основной информации из текста, объем 5 - 30% от исходного текста. сюда же относится аннотация: 1 - 5% исходной информации);

- критический реферат (предполагает сокращение информации и выражает определенное мнение об этой информации. например, в виде критического обзора статьи).

Основные методы систем автоматического реферирования базируются на трех основных этапах работы:

1. анализ исходного текста (на базе статистики)

2. определение его характерных фрагментов

3. формирование статистического метода по тексту.

При этом существует два основных метода реферирования

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

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

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

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