Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 39
Текст из файла (страница 39)
Обратите внимание на проверкуошибок в конце choose-branch, которая заставляет программу протестовать, если вовходных данных обнаруживается что-либо помимо единиц и нулей.168Глава 2. Построение абстракций с помощью данныхМножества взвешенных элементовВ нашем представлении деревьев каждая нетерминальная вершина содержит множество символов, которое мы представили как простой список. Однако алгоритм порождения дерева, который мы обсуждали выше, требует, чтобы мы работали еще и смножествами листьев и деревьев, последовательно сливая два наименьших элемента.Поскольку нам нужно будет раз за разом находить наименьший элемент множества,удобно для такого множества использовать упорядоченное представление.Мы представим множество листьев и деревьев как список элементов, упорядоченныйпо весу в возрастающем порядке.
Следующая процедура adjoinset для построениямножеств подобна той, которая описана в упражнении 2.61; однако элементы сравниваются по своим весам, и никогда не бывает так, что добавляемый элемент уже содержитсяв множестве.(define (adjoin-set x set)(cond ((null? set) (list x))((< (weight x) (weight (car set))) (cons x set))(else (cons (car set)(adjoin-set x (cdr set))))))Следующая процедура принимает список пар вида символ–частота, например ((A4) (B 2) (C 1) (D 1)), и порождает исходное упорядоченное множество листьев,готовое к слиянию по алгоритму Хаффмана:(define (make-leaf-set pairs)(if (null? pairs)’()(let ((pair (car pairs)))(adjoin-set (make-leaf (car pair)(cadr pair))(make-leaf-set (cdr pairs))))))Упражнение 2.67.Пусть нам даны дерево кодирования и пример сообщения:(define sample-tree(make-code-tree (make-leaf ’A 4)(make-code-tree(make-leaf ’B 2)(make-code-tree (make-leaf ’D 1)(make-leaf ’C 1)))))(define sample-message ’(0 1 1 0 0 1 0 1 0 1 1 1 0))Раскодируйте сообщение при помощи процедуры decode.Упражнение 2.68.Процедура encode получает в качестве аргументов сообщение и дерево, и порождает списокбитов, который представляет закодированное сообщение.2.3.
Символьные данные169(define (encode message tree)(if (null? message)’()(append (encode-symbol (car message) tree)(encode (cdr message) tree))))Encode-symbol — процедура, которую Вы должны написать, возвращает список битов, который кодирует данный символ в соответствии с заданным деревом. Вы должны спроектироватьencode-symbol так, чтобы она сообщала об ошибке, если символ вообще не содержится в дереве.Проверьте свою процедуру, закодировав тот результат, который Вы получили в упражнении 2.67,с деревом-примером и проверив, совпадает ли то, что получаете Вы, с исходным сообщением.Упражнение 2.69.Следующая процедура берет в качестве аргумента список пар вида символ-частота (где ни одинсимвол не встречается более, чем в одной паре) и порождает дерево кодирования по Хаффману всоответствии с алгоритмом Хаффмана.(define (generate-huffman-tree pairs)(successive-merge (make-leaf-set pairs)))Приведенная выше процедура make-leaf-set преобразует список пар в упорядоченное множество пар.
Вам нужно написать процедуру successive-merge, которая при помощи make-codetree сливает наиболее легкие элементы множества, пока не останется только один элемент, который и представляет собой требуемое дерево Хаффмана. (Эта процедура устроена немного хитро, ноона не такая уж сложная. Если Вы видите, что строите сложную процедуру, значит, почти наверняка Вы делаете что-то не то. Можно извлечь немалое преимущество из того, что мы используемупорядоченное представление для множеств.)Упражнение 2.70.Нижеприведенный алфавит из восьми символов с соответствующими им относительными частотами был разработан, чтобы эффективно кодировать слова рок-песен 1950-х годов.
(Обратитевнимание, что «символы» «алфавита» не обязаны быть отдельными буквами.)ABOOMGETJOB2122NASHAYIPWAH16391При помощи generate-huffman-tree (упр. 2.69) породите соответствующее дерево Хаффмана,и с помощью encode закодируйте следующее сообщение:Get a jobSha na na na na na na na naGet a jobSha na na na na na na na naWah yip yip yip yip yip yip yip yip yipSha boomСколько битов потребовалось для кодирования? Каково наименьшее число битов, которое потребовалось бы для кодирования этой песни, если использовать код с фиксированной длиной дляалфавита из восьми символов?170Глава 2. Построение абстракций с помощью данныхУпражнение 2.71.Допустим, у нас есть дерево Хаффмана для алфавита из n символов, и относительные частотысимволов равны 1, 2, 4, .
. . , 2n−1 . Изобразите дерево для n = 5; для n = 10. Сколько битов в такомдереве (для произвольного n) требуется, чтобы закодировать самый частый символ? Самый редкийсимвол?Упражнение 2.72.Рассмотрим процедуру кодирования, которую Вы разработали в упражнении 2.68. Каков порядокроста в терминах количества шагов, необходимых для кодирования символа? Не забудьте включить число шагов, требуемых для поиска символа в каждой следующей вершине. Ответить наэтот вопрос в общем случае сложно.
Рассмотрите особый случай, когда относительные частотысимволов таковы, как описано в упражнении 2.71, и найдите порядок роста (как функцию от n)числа шагов, необходимых, чтобы закодировать самый частый и самый редкий символ алфавита.2.4. Множественные представления для абстрактных данныхВ предыдущих разделах мы описали абстракцию данных, методологию, позволяющуюструктурировать системы таким образом, что бо́льшую часть программы можно специфицировать независимо от решений, которые принимаются при реализации объектов,обрабатываемых программой. Например, в разделе 2.1.1 мы узнали, как отделить задачу проектирования программы, которая пользуется рациональными числами, от задачиреализации рациональных чисел через элементарные механизмы построения составныхданных в компьютерном языке. Главная идея состояла в возведении барьера абстракции, — в данном случае, селекторов и конструкторов для рациональных чисел (makerat, numer, denom), — который отделяет то, как рациональные числа используются,от их внутреннего представления через списковые структуры.
Подобный же барьер абстракции отделяет детали процедур, реализующих рациональную арифметику (add-rat,sub-rat, mul-rat и div-rat), от «высокоуровневых» процедур, которые используютрациональные числа. Получившаяся программа имеет структуру, показанную на рис. 2.1.Такие барьеры абстракции — мощное средство управления сложностью проекта. Изолируя внутренние представления объектов данных, нам удается разделить задачу построения большой программы на меньшие задачи, которые можно решать независимо другот друга.
Однако такой тип абстракции данных еще недостаточно мощен, поскольку невсегда имеет смысл говорить о «внутреннем представлении» объекта данных.Например, может оказаться более одного удобного представления для объекта данных, и мы можем захотеть проектировать системы, которые способны работать с множественными представлениями. В качестве простого примера, комплексные числа можнопредставить двумя почти эквивалентными способами: в декартовой форме (действительная и мнимая часть) и в полярной форме (модуль и аргумент). Иногда лучше подходитдекартова форма, а иногда полярная.
В сущности, вполне возможно представить себесистему, в которой комплексные числа представляются обоими способами, а процедурыоперации над комплексным числами способны работать с любым представлением.Еще важнее то, что часто программные системы разрабатываются большим количеством людей в течение долгого времени, в соответствии с требованиями, которые также2.4. Множественные представления для абстрактных данных171Программы, использующие комплексные числаadd-complex sub-complex mul-complex div-complexПакет комплексной арифметикиДекартовоПолярноепредставлениепредставлениеСписковая структураРис.
2.19. Барьеры абстракции данных в системе работы с комплексными числами.со временем меняются. В такой ситуации просто невозможно заранее всем договоритьсяо выборе представления данных. Так что в дополнение к барьерам абстракции данных,которые отделяют представление данных от их использования, нам нужны барьеры абстракции, которые отделяют друг от друга различные проектные решения и позволяютразличным решениям сосуществовать в рамках одной программы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
