Непейвода Н.Н., Скопин И.Н. Основания программирования

Подождите немного. Документ загружается.

10.6. ПЕРЕХОД ОТ ДАННЫХ К КОНЕЧНОМУ АВТОМАТУ

625

XML

. Документ является правильно составленным, если для каждого откры-

вающего тега имеется соответствующий закрывающий тег, а накладываю-

щиеся теги отсутствуют. (Таким образом, большая часть документов

HTML

составлена неправильно.) Документ является действительным, если он со-

держит

DTD

и соответствует его правилам.

§ 10.6. ПЕРЕХОД ОТ ДАННЫХ К КОНЕЧНОМУ АВТОМАТУ

Таблицы переходов и состояний являются методом программирования не

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

таксических таблиц и

XML/XSL

подхода к задаче стандартизованного пред-

ставления таблиц переходов были указаны возможности применения мето-

дики оперирования со структурными представлениями данных и программ

для более широкого класса алгоритмов.

Однако мы пока не решали задачи, когда какое-либо представление ал-

горитма зависит от входных данных. Эта задача расклассифицирована для

автоматов как задача динамического порождения автомата (см. § 10.5, пункт

3 на стр. 613). Конечно же, под таким углом зрения можно рассматривать

трансляцию: текстовый файл на входном языке есть часть данных, фиксиру-

ющая план обработки другой части данных, которая предъявляется для ре-

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

(см. § 3.9.3) также может рассматриваться как уточнение общего плана, ис-

ходя из частичного знания обрабатываемых данных. Упомянутые случаи ха-

рактеризуются тем, что представление алгоритма, зависящее от части вход-

ных данных, строится из заранее определенных заготовок. Например, для

трансляции такими заготовками являются алгоритмы выполнения абстракт-

но-синтаксического представления программы.

В данном разделе показан иной метод построения алгоритма, зависящего

от входных данных. Его идея не в компиляции некоего объектного кода из за-

готовок, комбинируемых по принципу домино, а прямом составлении такого

представления алгоритма,которое допускает непосредственную интерпрета-

цию. Естественный путь демонстрации метода — взять за основу известный

класс алгоритмов, конкретный представитель которого выбирается, исходя

из знания о входных данных.

Будем решать задачу, которая для каждого конкретного случая решается

с помощью конечного автомата специального вида (как и всегда, выбор кон-

кретного представления сильно влияет на сложность и другие характеристи-

626

ГЛАВА 10. МЕТОДЫ ПРОГРАММИРОВАНИЯ ОТ СОСТОЯНИЙ

ки программы, и автоматическое применение ранее использованных пред-

ставлений в других задачах не рекомендуется).

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

чается в некотором большом файле (теперь слово — это любая последова-

тельность символов). α

, α

, ..., α

— вводимые слова; α

= a

. . . a

—

слово. Напечатать:

Число вхождений α

= <Число 1>,

Число вхождений α

= <Число 2>,

...,

Число вхождений α

= <Число n>

где <Число k> — полное число вхождений слова α

в файл с учетом возмож-

ного перекрытия слов (например, в строке “*МАМАМА{}” два вхождения

слова “МАМА”).

Для заданных заранее слов легко построить граф, каждая вершина кото-

рого представляет символы внутри слов. Его вершины помечены символом.

Из такой вершины исходят две дуги: первая указывает на вершину, к которой

следует переходить, когда очередной читаемый символ совпадает с пометкой

вершины, а вторая — на вершину, которая должна стать преемником данной

в случае несовпадения. Легко видеть, что это одна из форм представления ко-

нечного автомата, каждое состояние которого кодирует множество всех вер-

шин, связанных дугами второго вида, а состояния-преемники определяются

дугами первого вида исходного графа. Чтобы этот автомат работал, т.е.решал

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

увеличению счетчиков, соответ-ствующих найденным словам, а также опре-

делить начальное и конечное состояния. Мы не будем заниматься переделкой

исходного графа, поскольку такая его форма удобнее для интерпретации.

Если дуги первого вида изображать стрелками, исходящими в горизон-

тальном на-правлении, дуги второго вида - вертикальными стрелками, а дей-

ствия со счетчиками - соответствующими пометками при дугах, то, напри-

мер, для множества слов

1) МАМА,

2) МАШИНА,

3) ШИНА,

4) МАТ,

5) НА

10.6. ПЕРЕХОД ОТ ДАННЫХ К КОНЕЧНОМУ АВТОМАТУ

627

может быть построен граф, показанный на рис. 10.6.

На языке

С++/C#

структура, которая представляет граф, почти такой, как

только что описанный, может быть изображена следующим образом:

struct {

bool Tag; //

поле признака текущего значения в

union:

union { char Symb; // <- Tag = true

int Num; // <- Tag = false

}; //

имя объединения здесь не нужно

int yes; //

индекс перехода по совпадению

int no; //

индекс перехода по несовпадению

} Table[];

Особенность данной интерпретации таблицы в том, что она соответству-

ет автоматам Мура: действия ассоциируются с вершинами, а не с дугами, с

состояниями, а не с переходами. Вершина, которой сопоставлено действие,

не требует чтения очередного символа и его анализа. Вместо символьных

пометок вершины-действия содержат числовые номера, идентифицирующие

соответствующие счетчики (использовано размеченное объединение для то-

го, чтобы отразить это соглашение). При желании можно считать, что дей-

ствия приписаны только тем дугам, которые ведут из этих вершин (специ-

альные пометки этих дуг не нужны).

Для нашего примера граф-автомат представляется следующей таблицей

(переход 111, указывающий за пределы таблицы, использован для обозначе-

ния завершения просмотра файла):

1) МАМА, 2) МАШИНА, 3) ШИНА, 4) МАТ, 5) НА.

0. ’\n’ 111 1

1. М 2 15

2. А 3 0

3. М 4 6

4. А 5 0

5. <1> 3 -

6. Ш 7 14

7. И 8 0

8. Н 9 0

9. А 10 0

10. <2> 11 —

628

ГЛАВА 10. МЕТОДЫ ПРОГРАММИРОВАНИЯ ОТ СОСТОЯНИЙ

М А М А

Н А

Ш И Н А

‘\n’

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

10.6. ПЕРЕХОД ОТ ДАННЫХ К КОНЕЧНОМУ АВТОМАТУ

629

11. <3> 12 —

12. <5> 1 —

13. Т 14 0

14. <4> 1 —

15. Ш 16 19

16. И 17 0

17. Н 18 0

18. А 11 0

19. Н 20 0

20. А 12 0

∀

0 —

Программа интерпретации графа достаточно проста. Для данной задачи

нет смысла использовать транслирующий вариант реализации оперирования

с таблицей (операторы

Current_Reaction();

Final_Reaction();

использованы

для обозначения действий со счетчиками, например тех, которые приведены

в комментариях):

Программа 10.6.1

s = getchar ();

i = 1;

for (;;) {

if (Table[i].Tag) {

if ( Table[i].Symb == s ) {

i = Table[i].yes; // следующая строка

if ( s != ’\n’)

s = getchar ();

else return;

}

else

i = Table[i].no; // следующая строка

}

else {

Current_Reaction(); // M[Table[i].Num]++

i = Table[i].yes; // следующая строка

}

Final_Reaction(); // Распечатка M

630

ГЛАВА 10. МЕТОДЫ ПРОГРАММИРОВАНИЯ ОТ СОСТОЯНИЙ

В данном интерпретаторе структура данных не содержит описаний действий —

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

цы, а потому нет противоречий двойной трактовки данных как информаци-

онных и операционных единиц, т. е. нет тех проблем, которые были отме-

чены выше для автомата, использованного для подсчета длин слов. Важно,

что здесь достигается универсальность, независимость от таблицы для всех

вариантов ввода слов.

Ничуть не сложнее решение, когда вместо таблицы-массива используется

списочная структура. По существу ничто, кроме доступа к данным, который

можно строго локализовать в соответствующих процедурах, не изменится.

Выполните это решение самостоятельно. В то же время, решение разработ-

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

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

даже в тех случаях, когда процесс построения автомата отделен во времени

от его использования. По тем же причинам вариант с

XML

не имеет ника-

ких преимуществ. Другое дело, если речь пойдет об оперировании со спис-

ком слов (а не с таблицей!). Этот список целесообразно уметь редактировать,

запуская программу построения графа с помощью соответствующего обра-

ботчика списка слов, и затем вызывая интерпретатор для работы с файлом.

Целесообразность такого подхода нужно оценить на этапе анализа жизнен-

ного цикла конструируемой программной системы.

Для обоих удовлетворительных решений требуется разработка алгорит-

ма построения автомата по заданному набору слов. Если используется та-

блица-массив, то результатом такого построения должен быть заполненный

массив. При списочной организации таблицы нужно составить соответству-

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

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

довательно, можно ставить задачу оптимизации: выбор такого автомата из

множества автоматов, который справляется с подсчетом вхождений за наи-

более короткое время.

Построение графа автомата, достаточного для решения задачи, но не обя-

зательно оптимального,можно реализовать,используя следующее рекуррент-

ное описание алгоритма:

1. Если множество слов пустое, то граф задается структурой:

10.6. ПЕРЕХОД ОТ ДАННЫХ К КОНЕЧНОМУ АВТОМАТУ

631

‘\n’

∀

Вершина, содержащая ‘\n’, объявляется выходной для графа в целом

(есть горизонтальная исходящая из нее дуга, которая никуда не ведет).

Она обозначаемая далее как

. На данном этапе входной вершиной

является та, которая пропускает все символы (по определению у нее

нет вертикальной исходящей дуги).

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

слов {α

, α

, . . . , α

}, и пусть есть слово α

k+1

, которое нужно добавить

к этому множеству. Добавление слова достигается с помощьюи следу-

ющих шагов:

(a) по слову α

k+1

= a

. . . a

строится список вида

k+1

...

который рассматривается как заготовка для пополнения графа G;

(b) для каждого слова α из {α

, α

, . . . , α

} ищутся такие β, γ 6= ε, δ

и ξ, что α = βγδ, α

k+1

= γξ и (δ = xδ

&ξ = yξ

⇒ x 6= y). В

графе G есть фрагменты, отвечающие за распознавание γ. Следо-

вательно, надо склеить заготовку с каждым из таких фрагментов,

т. е. вставить вертикальную дугу от вершины x или ее вертикаль-

ных преемников x

, . . . , x

к остатку заготовки:

632

ГЛАВА 10. МЕТОДЫ ПРОГРАММИРОВАНИЯ ОТ СОСТОЯНИЙ

y a

k+1

...

⇒

...

k+1

есть собственная часть какого-либо слова, то склейка

заготовки с графом сводится к добавлению пометки k + 1 у соот-

ветствующей горизонтальной дуги;

(d) повторять (b,) пока можно найти соответствующие β, γ, δ и ε.

3. Последовательно выполнить процесс, описанный в п. 2, для всех слов

из набора.

Доведите этот алгоритм до программной реализации самостоятельно.

Улучшение данного алгоритма возможно, в частности, за счет стандарт-

ного приема оптимизации задач, обрабатывающих сложно структурирован-

ную взаимосвязанную информацию.Этот прием состоит в упорядочении дан-

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

число проверок в каждом (вертикальном) состоянии автомата. Другая идея

улучшения алгоритма — в некоторых случаях, когда линейные участки рас-

познавания оказываются относительно независимыми, вычислить локально

оптимальные последовательности и распознавать сразу их вхождения. Та-

кое агрегирование данных также является стандартным приемом. Наконец,

чуть-чуть повысит эффективность размножение выходной вершины графа.

Подобные модификации алгоритма предлагается выполнить самостоятель-

но.

* * *

10.6. ПЕРЕХОД ОТ ДАННЫХ К КОНЕЧНОМУ АВТОМАТУ

633

Только что решенная задача, разумеется, является модельной. В реаль-

ной практике подобные по постановке задачи приходится решать в основном

в частных случаях (например, вводится требование игнорирования пересе-

чения слов, вместо подсчета числа вхождений может потребоваться другая

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

нительные условия существенно влияют на выбор подхода, но применение

метода динамически порождаемого автомата — это хорошее решение с мно-

гих точек зрения: высокая эффективность, наглядность, автономность.

Логически подобные задачи возникают в случае предварительного пла-

нирования действий по сложной структуре данных, и они, как правило, еще

сложнее, хотя часто подход к их решению упрощается тем, что требуется

найти приемлемый, а не оптимальный, план действий. Тут такой прием ди-

намического порождения и последующей интерпретации еще более ценен.

Анализ предложенного решения, которое исходит из двухэтапной схемы

(построение автомата и его применение), показывает, что естественный ме-

тод реализации первого этапа — рекурсивный алгоритм, который на концеп-

туальном уровне следует отнести к стилю функционального программирова-

ния. Возможно, что и в качестве языка его реализации вам покажется наибо-

лее подходящим, к примеру,

LISP

. В то же время адекватный стиль реализа-

ции второго этапа — программирование от состояний. Таким образом, разде-

ление стилей требует в идеале применения двуязычной системы программи-

рования. К сожалению, чисто технические трудности сопряжения двух язы-

ков (упомянем только одну из них: согласование представлений данных) ча-

сто приводят к тому, что предпочитают моделирование стиля. И это порою

прагматически обоснованное решение, особенно если систему не придется

развивать дальше. Но если ее придется развивать, лучше один раз преодо-

леть технические трудности

, зато затем работать концептуально продуман-

но. Хорошим примером здесь является система

Autocad

, языком для преобра-

зования планов в которой служит расширение языка

LISP

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

зования в других подобных ситуациях.

Глава 11

Методы, основанные на рекурсии

Использование рекурсии являются характерным для нескольких стилей

программирования. Прежде всего, надо отметить функциональное и струк-

турное программирование, а затем нужно упомянуть многие разновидности

объектно-ориентированного. Это можно объяснить, вспомнив наблюдение,

что при структурном программировании и действия, и условия локальны.

Такая локальность приводит к достаточно гибким средствам оперирования

с контекстами, причем как раз к тем, которые даны в современных функци-

ональных языках в качестве базовых возможностей комбинирования функ-

ций.

Языковые средства задания рекурсии в этих стилях различаются, прежде

всего, в следующих отношениях. Для функционального программирования

рекурсия — атомарное действие, реализация которого остается за рамками

модели вычислений. В структурном программировании средства задания ре-

курсии основываются на оперировании со стековой структурой контекстов.

Они дают возможность говорить об экземплярах действий, о других элемен-

тах данных и действий абстрактного вычислителя языка, необходиых для

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

проявляется в том, что при программировании в функциональном стиле по-

ощряется свободное применение рекурсии над значениями высших типов,

что расширяет потенциальные возможности стиля. Но, как уже неоднократ-

но говорилось, реализация значений высших типов в настоящее время без-

надежно плоха. Она всегда проецирует (причем ошибочно во многих тонких

случаях) программу на операционные вычисления. Даже если нет ошибок,

то программы, написанные в функциональном стиле, могут проигрывать в

эффективности на три-четыре порядка. По этой причине в изложении мето-

634