algan21


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте файл и откройте на своем компьютере.
Алгоритмический анализ. Лекция 2 1 . Программирование на Scheme Конечные автоматы ( продолжение) Вернемся к примеру программы , которая выделяет все комментарии из одного файла в другой. Был приведен один из вариантов реализации идеи конечных автоматов на основе хранения текущего со стояния автомата в некоторой переменной. Другой подход к реализации абсолютно при той же идее алгоритма связан с созданием отдельных функций, каждая из которых отвечает за свое состояние автомата. Таким образом, количество вспомогательных функций должно р авняться числу разных состояний автомата. Напомним, что в разобранном примере мы имели следующие состояния: 0. Находимся в обычном тексте. 1. Находимся внутри комментария. 2. Находимся в строке. 3. Был \ и, следовательно, сейчас будет символ. Напомним сам текст прошло го примера. (define (comment file - in file - out) (define in (open - input - file file - in)) (define out (open - output - file file - out #:exists 'replace)) (define (next s) (define c (read - char in)) (if (equal? c eof) (close - output - port out) (cond ((= s 0) (cond ((equal? c # \ ;) (next 1)) ((equal? c # \ ") (next 2)) ((equal? c # \ \ ) (next 3)) (else (next s)))) ((= s 1) (write - char c out) (cond ((equal? c # \ newline) (next 0)) (else (next s)))) ((= s 2) (cond ((equal? c # \ ") (next 0)) (else (next s)))) ((= s 3) (cond ((equal? c # \ \ ) (next 3)) (else (next 0))))))) (next 0)) Значит, в соответствии с новой концепцией, создаем четыре вспомогательных функции. Смена состояний в этом случае соответствует вызову соответствующей функции. В итоге имеем : ( define ( comments file - in file - out ) ( define in ( open - input - file file - in )) ( define ou + t ( open - output - file file - out #: exists 'replace)) (define (s0) (define c (read - char in)) (if (equal? c eof) (close - output - port out) (cond ((equal? c # \ ;) (s1)) ((equal? c # \ ") (s2)) ((equal? c # \ \ ) (s3)) (else (s0))))) (define (s1) (define c (read - char in)) (if (equal? c eof) (close - outpu t - port out) (begin (write - char c out) (cond ((equal? c # \ newline) (s0)) (else (s1)))))) (define (s2) (define c (read - char in)) (if (equal? c eof) (close - output - port out) (begin (write - char c out) (cond ((equal? c # \ ") (s0)) (else (s2)))))) (define (s3) (define c (read - char in)) (if (equal? c eof) (close - output - port out) (begin (write - char c out) (cond ((equal? c # \ \ ) (s3)) (else (s0)))))) (s0)) Рассмотрим применение метода конечных автоматов к поиску подстроки в строке. Пусть требуется в некотором тексте найти слово " ананас " . Будем считать, что состояние определяется количеством совпавших на данный момент символов. Таким образом, для нашего слов а возможные состояния будут от 0 до 6, при этом 0 – начальное состояние, а 6 – итоговое, равное длине строки, признак удачного поиска. Основу алгоритма составляет построение таблицы переходов. Работая с ней, мы должны знать имеющееся на данный момент состо яние и очередной символ строки, где ведется поиск. Значит, для нашего примера в этой таблице должно быть 6 строк с номерами от 0 до 5 , а столбцы должны соответствовать различным символам того слова, которое ищем, т.е. в нашем случае трем буквам : а, н, с. В итоге таблица должна быть следующей: состояние а н с 0 1 0 0 1 1 2 0 2 3 0 0 3 1 4 0 4 5 0 0 5 1 4 6 Попытаемся автоматизировать процесс построения таких таблиц для произвольной строки. Во - первых, необходимо найти алфавит строки, т.е. из каких си мволов она состоит. Поскольку нам все время будет необходимо по символу узнавать его номер в этом алфавите, будет удобно иметь список пар. Первым элементом каждой пары будет символ, а вторым – его номер в алфавите. (define (what - num x dic) (define tmp (findf (lambda (a) (equal? (car a) x)) dic) ) (if (equal? tmp #f) #f (cdr tmp) ) ) (define (make - dic s) (foldl (lambda (x dic) (if (equal? (what - num x dic) #f) (cons (cons x (+ (cdar dic) 1)) dic) dic) ) (list (cons (car s) 0) ) s) ) Здесь нам удобно реализовать эту функцию так, что параметром является список символов. Процесс заполнения таблицы начинается со списка, где в одной позиции (буква а) стоит единица, а остальные нули. Построение таблицы можно проиллюстрировать так: а н с а н с 0 а 0 0 0 1 0 0 1 н 1 0 0 1 2 0 2 а 1 0 0 3 0 0 3 н 1 2 0 1 4 0 4 а 3 0 0 5 0 0 5 с 1 4 0 1 4 6 В результате, имеем алгоритм поиска подстроки в строке с помощью конечных автоматов. Заметим, что для обработки очередного символа строк и, где ведется поиск, требуется только взять строку таблицы с текущим состоянием и выбрать тот элемент строки, который соответствует текущему символу. Это и будет новое состояние автомата. Иначе, при отсутствии текущего символа в алфавите, состояние сбрасы вается в ноль. Обычно этот вариант поиска работает - быстрее, чем с хэш - функцией. (define (change - item lst i item) (append (take lst i) (cons item (drop lst (+ i 1))))) (define (iter lines next - num str dic) (define n (length lines)) (if (emp ty? str) lines ((i (what - num (car str) dic)) (next ( - n (list - ref (list - ref lines next - num) i)))) (iter (cons (change - item (list - ref lines next - num) i (+ n 1)) lines) next (cdr str) dic)))) (define (mak e - auto s dic) (reverse (iter (list (change - item (build - list (length dic) (lambda (x) 0)) (what - num (car s) dic) 1)) 0 (cdr s) dic))) (define (search - auto sub str) (def ine (search state s) (if (empty? s) #f (if (= state n) ( - (string - length str) (length s) n) - num (car s) dic))) (if (equal? num #f) (search 0 (cdr s)) (search (list - ref (list - ref auto state) (what - num (car s) dic)) (cdr s))))))) (define s (string - �list sub)) (define n (length s)) (define dic (make - dic s)) (define auto (make - auto s dic)) (write auto) (search 0 (string - �list str))) Dictionaries В язык е scheme имеется возможность не писать собственные средства аналогичные написанным нами выше функциям what - num и make - dic . Для этой цели можно использовать Dictionaries или иначе – ассоциативные массивы. На самом деле, мы их уже использовали, поскольку тип vector является простым примером такого ассоциативного массива, в котором индексу от 0 до n - 1 (где n – размер вектора) поставлен в соответствие элемент вектора. Другим вариантом Dictionaries является список из пар. В этом случае первый элемент пары выступ ает в роли ключа, а второй – значение. Мы располагаем следующими средствами для работы с ассоциативными массивами. (dict - например : � (dict - ((a . "apple")) � (dict - ((a . "apple") (b . "banana")) (dict - ref dict key [failure - result]) � (dict - ref '((a . "apple") (b . "banana")) 'b) "banana" � (dict - ref #("apple" "banana") 1) "banana" � (dict - ref #("apple" "banana") 3 #f) #f � (dict - ref #("apple" "banana") - 3 #f) #f (dict - remove dict key) � (dict - remove '((a . "apple") (b . "banana")) 'a) ((b . "banana")) (dict - map dict proc) � (dict - map '((a . 1) (b . 5)) (lambda (x y) x)) (a b) � (dict - map '((a . 1) (b . 5)) (lambda (x y) y)) (1 5) (dict - count dict) � (dic t - count '((a . 1) (b . 5) (t . 4))) 3

Приложенные файлы

  • pdf 1280035
    Размер файла: 174 kB Загрузок: 0

Добавить комментарий