Информационный сайт

 

Реклама
bulletinsite.net -> Книги на сайте -> Программисту -> Непейвода Н.Н. -> "Основания программирования " -> 221

Основания программирования - Непейвода Н.Н.

Непейвода Н.Н., Скопин И.Н. Основания программирования — Институт компьютерных исследований , 2002. — 919 c.
Скачать (прямая ссылка): osnovanprogramm2002.pdf
Предыдущая << 1 .. 215 216 217 218 219 220 < 221 > 222 223 224 225 226 227 .. 316 >> Следующая

ыполните это реение самостоятельно. В то е время, реение разработки текстового представления таблицы с числовой разметкой было бы во всех отношениях опрометчивым. Оно и сложнее, и не дает никаких преимуществ да е в тех случаях, когда процесс построения автомата отделен во времени от его использования. о тем е причинам вариант с XML не имеет никаких преимуеств. ругое дело, если речь пойдет об оперировании со списком слов (а не с таблицей!). Этот список целесообразно уметь редактировать, запуская программу построения графа с помощью соответствующего обработчика списка слов, и затем вызвая интерпретатор для работы с файлом.
елесообразность такого подхода ну но оценить на этапе анализа изнен-ного цикла конструируемой программной системы.
Для обоих удовлетворительных решений требуется разработка алгоритма построения автомата по заданному набору слов. Если используется таблица-массив, то результатом такого построения дол ен быть заполненный массив. ри списочной организации таблицы ну но составить соответству-ий список. ля реения задачи могут быть построен различне автомат , но эффективность дальнейего их использования будет различна. Следовательно, можно ставить задачу оптимизации: выбор такого автомата из мно ества автоматов, которй справляется с подсчетом вхо дений за наиболее короткое время.
остроение графа автомата, достаточного для реения задачи, но не обязательно оптимального, мо но реализовать, используя следуее рекуррентное описание алгоритма:
1. Если мно ество слов пустое, то граф задается структурой:
10.6. ПЕРЕХОД ОТ ДАННЫХ К КОНЕЧНОМУ АВТОМАТУ
631
Вершина, содержащая '\n', объявляется выходной для графа в целом (есть горизонтальная исходящая из нее дуга, которая никуда не ведет). Она обозначаемая далее как E. Hа данном этапе входной вершиной является та, которая пропускает все символы (по определению у нее нет вертикальной исходяей дуги).
2. Пусть граф G определяет автомат, распознающий некоторое множество слов Ja1, a2,..., ак}, и пусть есть слово ak+i, которое нужно добавить к этому множеству Добавление слова достигается с помощьюи следующих шагов:
(а) по слову ak+1 = A1... am строится список вида
k+1
графа
E G;
который рассматривается как заготовка для пополнения
(b) для каждого слова a из Ja1, a2,..., ak} ищутся такие в, Y = е, S и ?, что a = ?jS, ak+1 = и (S = xS1 &^ = y?' =>- x = y). В графе G есть фрагменты, отвечающие за распознавание y. Следовательно, надо склеить заготовку с каждым из таких фрагментов, т. е. вставить вертикальну дугу от верины x или ее вертикаль-тіх преемников X1,... ,Xi к остатку заготовки:
632
ГЛАВА 10. МЕТОДЫ ПРОГРАММИРОВАНИЯ ОТ СОСТОЯНИЙ
(c) если otk+i есть собственная часть какого-либо слова, то склейка заготовки с графом сводится к добавлению пометки к + 1 у соответствующей горизонтальной дуги;
(d) повторять (b,) пока можно найти соответствующие ?, 7, 8 и е.
3. Последовательно выполнить процесс, описанный в п. 2, для всех слов из набора.
Доведите этот алгоритм до программной реализации самостоятельно.
Улучшение данного алгоритма возможно, в частности, за счет стандартного приема оптимизации задач, обрабатываих сло но структурированную взаимосвязанную информацию. Этот прием состоит в упорядочении данных. Слова можно расположить таким образом, что будет минимизировано число проверок в кадом (вертикальном) состоянии автомата. ругая идея улучшения алгоритма — в некоторых случаях, когда линейные участки распознавания оказыва тся относительно независимыми, вычислить локально оптимальные последовательности и распознавать сразу их вхождения. Такое агрегирование данных так е является стандартным приемом. аконец, чуть-чуть повысит эффективность размно ение входной верины графа. Подобные модификации алгоритма предлагается выполнить самостоятельно.
"3t "3t "3t
10.6.
633
Только что решенная задача, разумеется, является модельной. В реальной практике подобные по постановке задачи приходится решать в основном в частных случаях (например, вводится требование игнорирования пересечения слов, вместо подсчета числа вхо дений мо ет потребоваться другая обработка, в частности, для используей программ ). одобные дополнительные условия суественно влия т на выбор подхода, но применение метода динамически порождаемого автомата — это хорошее решение с многих точек зрения: высокая эффективность, наглядность, автономность.
огически подобные задачи возника т в случае предварительного планирования действий по сло ной структуре данных, и они, как правило, ее сло нее, хотя часто подход к их реени упроается тем, что требуется найти приемлемый, а не оптимальный, план действий. Тут такой прием динамического порождения и последующей интерпретации еще более ценен.
нализ предло енного реения, которое исходит из двухэтапной схемы (построение автомата и его применение), показвает, что естественнй метод реализации первого этапа — рекурсивный алгоритм, которй на концептуальном уровне следует отнести к стил функционального программирования. Возможно, что и в качестве языка его реализации вам покажется наиболее подходящим, к примеру, LISP. В то же время адекватный стиль реализации второго этапа — программирование от состояний. Таким образом, разделение стилей требует в идеале применения двуязычной системы программирования. К сожалению, чисто технические трудности сопряжения двух языков (упомянем только одну из них: согласование представлений данных) часто приводят к тому, что предпочита т моделирование стиля. это поро прагматически обоснованное реение, особенно если систему не придется развивать далье. о если ее придется развивать, луче один раз преодолеть технические трудности14, зато затем работать концептуально продуманно. Хорошим примером здесь является система Autocad, языком для преобразования планов в которой слу ит расирение языка LISP.
Предыдущая << 1 .. 215 216 217 218 219 220 < 221 > 222 223 224 225 226 227 .. 316 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100