Алгоритм сжатия Хаффмана - Лабораторная работа

Лабораторная работа №1. Алгоритм сжатия Хаффмана Следующим шагом в развитии алгоритма Хаффмана стала его адаптивная версия. В общем случае программа, реализующая адаптивное сжатие, может быть выражена в следующей форме: ИнициализироватьМодель(); Пока не конец сообщения Символ = ВзятьСледующийСимвол(); Закодировать(Символ); ОбновитьМодельСимволом(Символ); Конец пока; Декодер в адаптивной схеме работает аналогичным образом: ИнициализироватьМодель(); Пока не конец сжатой информации Символ = РаскодироватьСледующий(); ВыдатьСимвол(Символ); ОбновитьМодельСимволом(Символ); Конец пока; Схема адаптивного кодирования/декодирования работает благодаря тому, что при кодировании, и при декодировании используются одни и те же процедуры ИнициализироватьМодель и ОбновитьМодельСимволом И компрессор, и декомпрессор начинают с пустой модели (не содержащей информации о сообщении) и с каждым просмотренным символом обновляют ее одинаковым образом. Адаптивное кодирование Хаффмана В создании алгоритма адаптивного кодирования Хаффмана наибольшие сложности возникают при разработке процедурыОбновитьМодельСимволом(); можно было бы просто вставить внутрь этой процедуры полное построение дерева Хаффмана. В целом алгоритм обновления дерева может быть записан следующим образом: Алгоритм обновления дерева ОбновитьМодельСимволом(Символ) {ТекущийУзел = ЛистСоответствующий(Символ); Всегда УвеличитьВес(ТекущийУзел); Если ТекущийУзел = КореньДерева Выход; Если Вес(ТекущийУзел) > Вес(СледующийЗа(ТекущийУзел)) Перестановка(); ТекущийУзел = Родитель(ТекущийУзел); Конец Всегда;} Исходный код реализации адаптивного сжатия Хаффмана // HuffAdapt.cpp : #include #include #include #include #include // Константы, используемые в алгоритме кодирования #define END_OF_STREAM 256 /* Маркер конца потока */ #define ESCAPE 257 /* Маркер начала ESCAPE последовательности */ #define SYMBOL_COUNT 258 /* Максимально возможное количество листьев дерева (256 2 маркера)*/ #define NODE_TABLE_COUNT ((SYMBOL_COUNT * 2) - 1) #define ROOT_NODE 0 #define MAX_WEIGHT 0x8000 /* Вес корня, при котором начинается масштабирование веса */ #define TRUE 1 #define FALSE 0 #define PACIFIER_COUNT 2047 // шаг индикатора выполнения /* Коды ошибок */ #define NO_ERROR 0 #define BAD_FILE_NAME 1 #define BAD_ARGUMENT 2 // Эта структура данных нужна для побитового доступа к файлам typedef struct bit_file { FILE *file; unsigned char mask; int rack; int pacifier_counter; } COMPRESSED_FILE; // структура, описывающая узел дерева struct node { unsigned int weight; /* Вес узла */ int parent; /* Номер родителя в массиве узлов */ int child_is_leaf; /* Флаг листа (TRUE, если лист) */ int child; }; /* Эта структура данных используется для работы с деревом кодирования Хаффмана процедурами кодирования и декодирования */ typedef struct tree { int leaf[ SYMBOL_COUNT ]; /* Массив листьев дерева */ int next_free_node; /* Номер следующего свободного элемента массива листьев */ node nodes[ NODE_TABLE_COUNT ]; /* Массив узлов */ } TREE; // Сервисные функции void usage_exit (void); void print_ratios (char *input, char *output); long file_size (char *name); void fatal_error (char *fmt); // Функции побитового доступа к файлам COMPRESSED_FILE *OpenInputCompressedFile(char *name); COMPRESSED_FILE *OpenOutputCompressedFile(char *name); void OutputBit (COMPRESSED_FILE *, int bit); void OutputBits (COMPRESSED_FILE *bit_file, unsigned long code, int count); int InputBit (COMPRESSED_FILE *bit_file); unsigned long InputBits (COMPRESSED_FILE *bit_file, int bit_count); void CloseInputCompressedFile (COMPRESSED_FILE *bit_file); void CloseOutputCompressedFile (COMPRESSED_FILE *bit_file); // Собственно адаптивное кодирование Хаффмена void CompressFile (FILE *input, COMPRESSED_FILE *output); void ExpandFile (COMPRESSED_FILE *input, FILE *output); void InitializeTree (TREE *tree); void EncodeSymbol (TREE *tree, unsigned int c, COMPRESSED_FILE *output); int DecodeSymbol (TREE *tree, COMPRESSED_FILE *input); void UpdateModel (TREE *tree, int c); void RebuildTree (TREE *tree); void swap_nodes (TREE *tree, int i, int j); void add_new_node (TREE *tree, int c); //========================================================= //--------------------------------------------------------- // Вывод помощи о пользовании программой void help () { printf(HuffAdapt e(encoding)|d(decoding) input output

); } //--------------------------------------------------------- // Эта функция возвращает размер указанного ей файла #ifndef SEEK_END #define SEEK_END 2 #endif long file_size (char *name) { long eof_ftell; FILE *file; file = fopen(name, r); if (file == NULL) return(0L); fseek(file, 0L, SEEK_END); eof_ftell = ftell(file); fclose(file); return(eof_ftell); } //--------------------------------------------------------- /* Эта фунцция выводит результаты сжатия после окончания сжатия */ void print_ratios (char *input, char *output) { long input_size; long output_size; int ratio; input_size = file_size(input); if (input_size == 0) input_size = 1; output_size =