Алгоритмы и структуры данных. Соколов А.С. Курсовой 4-80к. Курсовая работа по курсу Алгоритмы и структуры данных
 Скачать 140.61 Kb.
|
|
Минобрнауки Российской Федерации Государственное образовательное учреждение высшего профессионального образования «Ивановский государственный энергетический университет им. В.И. Ленина» Кафедра программного обеспечения компьютерных систем КУРСОВАЯ РАБОТА по курсу «Алгоритмы и структуры данных» Выполнил: студент гр. VI-80к, Соколов А.С. Номер зачетной книжки: 915079 Проверил: д.т.н., проф. Пантелеев Е.Р. Иваново 2019 СодержаниеТекст задания 3 История метода 3 Список допущений для разработки быстрого прототипа 6 Оптимизация быстрого прототипа 6 Разработка интерфейса и испытания 7 Оценка эффективности 8 Выводы 8 Библиографический список 9 Приложение А 10 Приложение Б 14 Текст заданияНаписать кодер, использующий статический алгоритм Хаффмана. Исследовать его эффективность (степень сжатия) в зависимости от типа и размера сжимаемых файлов. (уровень сложности 2) История методаАлгоритм Хаффмана — жадный алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью. Был разработан в 1952 году аспирантом Массачусетского технологического института Дэвидом Хаффманом при написании им курсовой работы. В настоящее время используется во многих программах сжатия данных. Данный алгоритм является исторически первым методом группы частотных алгоритмов. Оригинальная работа была опубликована в 1952 г. под названием "A Method for The Constructionof Minimum Redundancy Codes". В основе метода лежит модель кодирования в виде бинарного дерева с минимальной длиной взвешенных путей. Бинарным деревом называется ориентированное дерево, полустепень исхода любой из вершин которого не превышает двух. Вершина бинарного дерева, полустепень захода которой равна нулю, называется корнем. Для остальных вершин дерева полу степень захода равна единице. Вершина m-дерева, полустепень исхода которой равна нулю, называется листом. Для остальных вершин полустепень исхода составляет 1 или 2. Пусть T – бинарное дерево, А = (0,1) – двоичный алфавит, и каждому ребру Т- дерева приписана одна из букв алфавита таким образом, что все ребра, исходящие из одной вершины, помечены различными буквами. Тогда любому листу T - дерева можно приписать уникальное кодовое слово, образованное из букв, которыми помечены ребра, встречающиеся при движении от корня к соответствующему листу. Особенность описанного способа кодирования в том, что полученные коды являются префиксными. Очевидно, что стоимость хранения информации, закодированной при помощи T – дерева, равна сумме длин путей из корня к каждому листу дерева, взвешенных частотой соответствующего кодового слова, или длиной взвешенных путей: Σwili, где wi– частота кодового слова длины li во входном потоке. Алгоритм Хаффмана позволяет уменьшить стоимость хранения потока кодовых слов путём такого подбора длин кодовых слов, который минимизирует длину взвешенных путей. Будем называть дерево с минимальной длиной взвешенных путей деревом Хаффмана. Классический алгоритм Хаффмана на входе получает таблицу частот символов во входном потоке. Ниже описан алгоритм построения дерева Хаффмана. Символы входного алфавита образуют список свободных узлов. Каждый имеет вес, который может быть равен либо вероятности, либо количеству вхождений символа в ожидаемое сообщение. Выбираются два свободных узла дерева с наименьшими весами. Создается их родитель с весом, равным их суммарному весу. Родитель добавляется в список свободных узлов, а двое его детей удаляются из этого списка. Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой – бит 0. Шаги, начиная со второго, повторяются до тех пор, пока в списке свободных узлов не останется только один свободный узел. Он и будет считаться корнем дерева. Допустим, у нас есть следующая таблица частот: 15 7 6 6 5 А Б В Г Д На первом шаге из листьев дерева выбираются два с наименьшими весами – Г и Д. Они присоединяются к новому узлу-родителю, вес которого устанавливается 5 + 6 = 11. Затем узлы Г и Д удаляются из списка свободных. Узел Г соответствует ветви 0 родителя, узел Д – ветви 1. На следующем шаге то же происходит с узлами Б и В, так как теперь эта пара имеет самый меньший вес в дереве. Создается новый узел с весом 13, а узлы Б и удаляются из списка свободных. После всего этого дерево кодирования выглядит так, как показано на рис. 1.  Рисунок 1 - Дерево кодирования Хаффмана после второго шага На следующем шаге «наилегчайшей» парой оказываются узлы Б/В и Г/Д. Для них еще раз создается родитель, теперь уже с весом 24. Узел Б/В соответствует ветви 0 родителя, Г/Д–ветви 1. На последнем шаге в списке свободных осталось только два узла – это А узел Б (Б/В)/(Г/Д). В очередной раз создается родитель с весом 39 и бывшие свободными узлы присоединяются к разным его ветвям. Поскольку свободным остался только один узел, то алгоритм построения дерева кодирования Хаффмана завершается. Н-дерево представлено на рис. 2.  Рисунок 2 - Окончательное дерево кодирования Хаффмана Каждый символ, входящий в сообщение, определяется как конкатенация нулей и единиц, сопоставленных ребрам дерева Хаффмана, на пути от корня к соответствующему листу. Для данной таблицы символов коды Хаффмана будут выглядеть следующим образом. А 0 Б 100 В 101 Г 110 Д 111 Наиболее частый символ сообщения А закодирован наименьшим количеством битов, а наиболее редкий символ Д – наибольшим. Стоимость хранения кодированного потока, определенная как сумма длин взвешенных путей, определится выражением: 15*1+7*3+6*3+6*3+5*3 =87, что существенно меньше стоимости хранения входного потока (312). Поскольку ни один из полученных кодов не является префиксом другого, они могут быть однозначно декодированы при чтении их из потока. Алгоритм декодирования предполагает просмотр потока битов и синхронное перемещение от корня вниз по дереву Хаффмана в соответствии со считанным значением до тех пор, пока не будет достигнут лист, то есть декодировано очередное кодовое слово, после чего распознавание следующего слова вновь начинается с вершины дерева. Классический алгоритм Хаффмана имеет один существенный недостаток. Для восстановления содержимого сжатого сообщения декодер должен знать модель кодирования, которой пользовался кодер. Следовательно, длина сжатого сообщения увеличивается на размер модели кодирования, которая должна посылаться впереди данных, что может свести на нет все усилия по сжатию сообщения. Кроме того, необходимость наличия полной частотной статистики перед началом собственно кодирования требует двух проходов по сообщению: одного – для построения модели сообщения (таблицы частот и дерева Хаффмана), другого – для собственно кодирования. Эффективность алгоритма Хаффмана оценивалась коэффициентом сжатия, который вычисляется по формуле  |