12. Переход от данных к конечному автомату

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

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

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

Несложно решение также когда вместо таблицы-массива используется списочная структура. Об этом говорит сайт https://intellect.icu . По существу ничто, кроме доступа к данным, который можно строго локализовать в соответствующих процедурах, не изменится. Выполните это решение самостоятельно. В то же время решение разработки текстового представления таблицы с числовой разметкой было бы во всех отношениях опрометчивым. Оно сложнее и не дает никаких преимуществ даже в тех случаях, когда процесс построения автомата отделен от его использования во времени. По тем же причинам вариант с XML не имеет никаких преимуществ. Другое дело, если речь пойдет об оперировании со списком слов (а не с таблицей!). Этот список целесообразно редактировать, запуская программу построения графа с помощью соответствующего обработчика списка слов и затем вызывая интерпретатор для работы с файлом. Рациональность такого подхода нужно оценить на этапе анализа жизненного цикла конструируемой программной системы.

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

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

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

   

   Вершина, содержащая \n, объявляется выходной для графа в целом (есть горизонтальная исходящая из нее дуга, которая никуда не ведет). Она обозначается далее E. На данном этапе входной вершиной является та, которая пропускает все символы (по определению у нее нет вертикальной исходящей дуги).

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

   1. по слову строится список вида

      

      который рассматривается как заготовка для пополнения графа G
   2. если есть собственная часть какого-либо слова, то склейка заготовки с графом сводится к добавлению пометки k+1 у соответствующей горизонтальной дуги; в противном случае перейти к следующим пунктам;

   3. для каждого слова из ищутся такие и . В графе G есть фрагменты, отвечающие за распознавание Следовательно, надо склеить заготовку с каждым из таких фрагментов, т. е. вставить вертикальную дугу от последнего вертикального преемника вершины x x₁,...,_i к остатку заготовки:

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

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

Только что решенная задача, разумеется, является модельной. На практике подобные задачи приходится решать в основном в частных случаях (например, игнорируются пересечения слов, вместо подсчета числа вхождений может потребоваться другая обработка). Дополнительные условия существенно влияют на выбор подхода, но применение метода динамически порождаемого автомата — это хорошее решение с точки зрения эффективности, наглядности и автономности.

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

Анализ предложенной двухэтапной схемы (построение автомата и его применение), показывает, что естественный метод реализации первого этапа — алгоритм, который на концептуальном уровне следует отнести либо к стилю сентенциального программирования, либо к рекурсивному варианту структурного. В качестве языка его реализации примерно одинаково адекватны LISP, Рефал и Prolog. В то же время адекватный стиль реализации второго этапа — автоматное программирование. Таким образом, разделение стилей требует в идеале применения двуязычной системы программирования. К сожалению, сугубо технические трудности сопряжения двух языков (упомянем только одну из них: согласование представлений данных) часто приводят к тому, что разработчики предпочитают моделирование стиля. И это порою прагматически обоснованное решение, особенно если систему не придется развивать дальше. Но если это потребуется, лучше один раз преодолеть технические трудности¹, зато в дальнейшем работать концептуально продуманно. Хорошим примером здесь является система Autocad, языком для преобразования планов в которой служит расширение языка LISP.

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

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

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

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