Кодер и декодер

Размещено на http://www.allbest.ru/

Федеральное агентство по образованию Российской Федерации.

Государственное образовательное учреждение

высшего профессионального образования

"Ивановский государственный энергетический университет имени В.И. Ленина"

Кафедра программного обеспечения компьютерных систем

Кодер и декодер



Задание.

Написать кодер и декодер, использующие динамический алгоритм Хаффмана. Исследовать эффективность (степень и время сжатия) кодера в зависимости от типа и размера сжимаемых файлов. Проверить корректность обратного преобразования путем запуска исполняемых файлов, сжатых при помощи динамического алгоритма Хаффмана.

Исходные данные:

Для демонстрации работы алгоритма мы использовали по 2 файла 3 типов разных размеров: doc, bmp, jpg. После компрессии появляется файл в том же каталоге с именем дополненным суффиксом ".hfm" в конце. После декомпрессии программа создаёт файл, убирая расширение ".hfm" из конца имени файла.

Вся программа представляет собой WindowsForms приложение на языке C#.

Алгоритм.

Адаптивное (динамическое) сжатие позволяет не передавать модель сообщения вместе с ним самим и ограничиться одним проходом по сообщению как при кодировании, так и при декодировании. В общем случае программа, реализующая адаптивное сжатие, может быть выражена в следующей форме:

ИнициализироватьМодель();

Пока не конец сообщения

Символ = ВзятьСледующийСимвол();

Закодировать(Символ);

ОбновитьМодельСимволом(Символ);

Конец Пока

Декодер в адаптивной схеме работает аналогичным образом:

ИнициализироватьМодель();

Пока не конец сжатой информации

Символ = РаскодироватьСледующийСимвол();

ВыдатьСимвол(Символ);

ОбновитьМодельСимволом(Символ);

Конец Пока

Схема адаптивного кодирования/декодирования работает благодаря тому, что и при кодировании, и при декодировании используются одни и те же процедуры "ИнициализироватьМодель" и "ОбновитьМодельСимволом". И кодер, и декодер начинают с "пустой" модели (не содержащей информации о сообщении) и с каждым просмотренным символом обновляют ее одинаковым образом.

В создании алгоритма адаптивного кодирования Хаффмена наибольшие сложности возникают при разработке процедуры ОбновитьМодельСимволом(). Модель данных, лежащая в основе этой процедуры, носит название упорядоченного дерева. Дерево обладает свойством упорядоченности, если его узлы могут быть перечислены в порядке возрастания веса, и в этом перечислении каждый узел находится рядом со своим "братом". Пример упорядоченного дерева приведен на рис. 1.

Рис. 1. Упорядоченное дерево. Указан порядковый номер узла в списке.

Примем без доказательства утверждение о том, что двоичное дерево является деревом кодирования Хаффмена тогда и только тогда, когда оно удовлетворяет свойству упорядоченности.

Сохранение свойства упорядоченности в процессе обновления дерева позволяет нам быть уверенными в том, что двоичное дерево, с которым мы работаем, - это дерево Хаффмена и до, и после обновления веса у листьев дерева. динамический алгоритм хаффман сжатие

Обновление дерева при считывании очередного символа сообщения состоит из двух операций.

Первая - увеличение веса узлов дерева - представлена на рис. 2.

Рис. 2. Обновление дерева кодирования при увеличении веса листа А

Вначале увеличиваем вес листа, соответствующего считанному символу, на единицу. Затем увеличиваем вес родителя, чтобы привести его в соответствие с новыми значениями веса у детей. Этот процесс продолжается до тех пор, пока мы не доберемся до корня дерева. Среднее число операций увеличения веса равно среднему количеству битов, необходимых для того, чтобы закодировать символ.

Вторая операция - перестановка узлов дерева - требуется тогда, когда увеличение веса узла приводит к нарушению свойства упорядоченности, то есть тогда, когда увеличенный вес узла стал больше, чем вес следующего по порядку узла (рис. 3). Если и дальше продолжать обрабатывать увеличение веса, двигаясь к корню дерева, то наше дерево перестанет быть деревом Хаффмена.

Рис. 3. Нарушение свойства упорядоченности

Чтобы сохранить упорядоченность, алгоритм работает следующим образом. Пусть новый увеличенный вес узла равен W + 1. Тогда начинаем двигаться по списку в сторону увеличения веса, пока не найдем последний узел с весом W. Переставим текущий и найденный узлы между собой в списке (рис. 4), восстанавливая таким образом порядок в дереве. (При этом родители каждого из узлов тоже изменятся). На этом операция перестановки заканчивается.

Рис. 4. Дерево кодирования после первой перестановки узлов ( Г и А )

После перестановки операция увеличения веса узлов продолжается дальше. Следующий узел, вес которого будет увеличен алгоритмом, - это новый родитель узла, увеличение веса которого вызвало перестановку. Вид дерева кодирования после двукратного вызова процедуры обновления символом A показан на рис. 5.

Рис. 5. Дерево после завершения процедуры обновления

В целом алгоритм обновления дерева может быть записан следующим образом:

ОбновитьМодельСимволом(Символ)

{

Текущий узел - ЛистСоответствующий(Символ)

Всегда

УвеличитьВес(ТекущийУзел)

Если ТекущийУзел - КореньДерева

Выход:

Если Вес(ТекущийУзел)>

Вес(СледующийЗа(ТекущийУзел))

Перестановка();

ТекущийУзел - Родитель(ТекущийУзел);

Конец Всегда

}

Первой проблемой, возникающей при реализации адаптивного метода Хаффмена, является инициализация кодировочного дерева. Если в классическом алгоритме Хаффмена в результате предварительного просмотра входного потока известна таблица частот, по которой может быть восстановлено дерево кодировки, то в адаптивной версии алгоритма статистика заранее неизвестна. Можно проинициализировать дерево Хаффмена так, чтобы оно имело все 256 символов алфавита (для 8-битовых кодов) с частотой, равной 1. В начале кодирования каждый код будет иметь длину 8 битов. По мере адаптации модели наиболее часто встречающиеся символы будут кодироваться все меньшим и меньшим количеством битов. Такой подход работоспособен, но он значительно снижает степень сжатия, особенно на коротких сообщениях.

Лучше начинать моделирование с пустого дерева и добавлять в него символы только по мере их появления в сжимаемом сообщении. Но это приводит к очевидному противоречию: когда символ появляется в сообщении в первый раз, он не может быть закодирован, так как его еще нет в дереве кодирования.

Чтобы разрешить это противоречие, введем специальный ESCAPE - код, который для декодера будет означать, что следующий символ закодирован вне контекста модели сообщения. Например, его можно передать в поток сжатой информации как есть, не кодируя вообще. Метод "ЗакодироватьСимвол" в алгоритме адаптивного кодирования Хаффмена можно записать следующим образом.

ЗакодироватьСимвол(Символ)

{

Если СимволУжеЕстьВТаблице(Символ)

ВыдатьКодХаффменаДляСимвола(Символ)

Иначе

{

ВыдатьКодХаффменаДляСимвола(ESCAPE)

ВыдатьСимвол(Символ)

}

}

Использование специального символа ESCAPE подразумевает определенную инициализацию дерева до начала кодирования и декодирования: в него помещаются 2 специальных символа: ESCAPE и EOF (конец файла), с весом, равным 1 (рис. 6).

Рис. 6. Дерево кодирования после иницализации

Поскольку процесс обновления дерева не коснется их веса, то по ходу кодирования они будут перемещаться на самые удаленные ветви дерева и иметь самые длинные коды.

Исходный код.

В программе использовались следующие АТД (абстрактные типы данных):

1) АТДпирамида.

представляет собой полное бинарное дерево. В данном случае используется в качестве очереди с приоритетами.

using System;

usingSystem.Collections.Generic;

usingSystem.Linq;

usingSystem.Text;

usingSystem.Threading.Tasks;

namespaceХаффман

{

// АТД пирамида.

// представляет собой полное бинарное дерево. В данном случае используется в качестве очереди с приоритетами.

classpiramida<T>where T : IComparable

{

private T[] A = new T[1000];

privateint N;

publicpiramida()

{

N = 0;

}

public void Swap(ref T X, ref T Y)

{

T Temp;

Temp = X;

X = Y;

Y = Temp;

}

publicint Parent(inti)

{

returni / 2;

}

publicint Left(inti)

{

return 2 * i;

}

publicint Right(inti)

{

return 2 * i + 1;

}

private void MinHeapify(inti)

{

int smallest;

int l = Left(i), r = Right(i);

if ((l <= N) && (A[l].CompareTo(A[i]) < 0))

smallest = l;

else

smallest = i;

if ((r <= N) && (A[r].CompareTo(A[smallest]) < 0))

smallest = r;

if (smallest != i)

{

Swap(ref A[i], ref A[smallest]);

MinHeapify(smallest);

}

}

public void BuildMinHeap()

{

for (inti = N / 2; i>= 1; i--)

MinHeapify(i);

}

//Возвращает ключ с минимальным значением

public T HeapGetMin()

{

return A[1];

}

// Извлекает и возвращает ключ с минимальным значением

public T HeapExtractMin()

{

T Min;

Min = A[1];

A[1] = A[N];

N--;

MinHeapify(1);

return Min;

}

publicintHeapIncreaseKey(inti, T Key)

{

A[i] = Key;

while ((i> 1) && (A[Parent(i)].CompareTo(A[i]) > 0))

{

Swap(ref A[i], ref A[Parent(i)]);

i = Parent(i);

}

return 0;

}

// Вставляет новый ключ в пирамиду

// "Key" - Ключдлявставки

public void HeapInsert(T Key)

{

N++;

HeapIncreaseKey(N, Key);

}

}

}

2) Упорядоченноедерево.

Дерево обладает свойством упорядоченности, если его узлы могут быть перечислены в порядке возрастания веса, и в этом перечислении каждый узел находится рядом со своим "братом".

usingSystem;

usingSystem.Collections.Generic;

usingSystem.Linq;

usingSystem.Text;

usingSystem.Threading.Tasks;

namespaceХаффман

{

//Упорядоченноедерево.

public class Node : IComparable

{

static Node() { }

publicintCompareTo(Object node)

{

if (this.Weight> ((Node)node).Weight)

return 1;

else if (this.Weight< ((Node)node).Weight)

return -1;

else

return 0;

}

public byte? Char{ get; set; } // Символузла, еслинеnull

publicint Weight { get; set; } // Весузла

public Node Right { get; set; } // Ссылканаправоеподдерево

public Node Left { get; set; } // Ссылканалевоеподдерево

public Node()

{

Char = null;

Weight = 0;

}

public Node(int weight, byte c)

{

Weight = weight;

Char = c;

}

public Node(Node left, Node right, int weight)

{

Left = left;

Right = right;

Weight = weight;

}

public Node(Node left, Node right, int weight, byte? c)

{

Left = left;

Right = right;

Weight = weight;

Char = c;

}

}

// Деревокодирования

public class Tree

{

// Ссылка на корень дерева

privateХаффман.NodeRoot;

// Таблицасоответствиясимволуегокода

private Dictionary<byte, string> table;

public static Tree Create(Dictionary<byte, int> table)

{

int N = table.Count;

Хаффман.piramida<Хаффман.Node> heap = new Хаффман.piramida<Хаффман.Node>();

foreach (var t in table)

{

heap.HeapInsert(new Хаффман.Node(t.Value, t.Key));

}

for (inti = 0; i< N - 1; ++i)

{

Хаффман.Node x = heap.HeapExtractMin();

Хаффман.Node y = heap.HeapExtractMin();

Хаффман.Node z = new Хаффман.Node(y, x, x.Weight + y.Weight);

heap.HeapInsert(z);

}

return new Tree(heap.HeapExtractMin());

}

public Tree(Хаффман.Node root)

{

Root = root;

table = new Dictionary<byte, string>();

}

// Возвращает таблицу соответствия символа его коду

public Dictionary<byte, string>Interpretate()

{

if (Root != null)

{

DFS(Root, "");

return table;

}

else

returnnull;

}

// Возвращает раскодированную последовательность

// "input" - Строка битов

public List<byte> Recognize(string input)

{

List<byte> total = new List<byte>();

for (inti = 0; i<input.Length; )

{

Хаффман.Node curr = Root;

while (true)

{

if (i>= input.Length) break;

if (curr.Char != null)

{

total.Add(Convert.ToByte(curr.Char));

break;

}

else

{

if (input[i] == '0')

curr = curr.Left;

else

curr = curr.Right;

i++;

}

}

}

return total;

}

private void DFS(Хаффман.Node node, string str)

{

if (node.Char == null)

{

if (node.Left != null)

DFS(node.Left, str + "0");

if (node.Right != null)

DFS(node.Right, str + "1");

}

else

{

table[Convert.ToByte(node.Char)] = str.ToString();

}

}

}

}

· Исходный код кодера:

usingSystem;

usingSystem.Collections.Generic;

usingSystem.Linq;

usingSystem.Text;

usingSystem.Threading.Tasks;

namespace Хаффман

{

classCompressor

{

publicCompressor()

{

}

// Сжимает входной файл и записывает результат в выходной

// "inputFileName" - Имя входного файла для компрессии

// "outputFileName" - Имя выходного файла для компрессии

public static void Compress(string inputFileName, string outputFileName)

{

System.IO.FileStreamfileStream = new System.IO.FileStream (inputFileName, System.IO.FileMode.Open, System.IO.FileAccess.Read);

Dictionary<byte, int>frequenceTable = new Dictionary<byte, int>();

List<byte> input = new List<byte>();

// Чтение входного файла и формирование таблицы частот

for (inti = 0; i<fileStream.Length; i++)

{

byte b = (byte) fileStream.ReadByte();

input.Add(b);

if (frequenceTable.ContainsKey(b))

frequenceTable[b]++;

else

frequenceTable.Add(b, 1);

}

fileStream.Close();

// Запись таблицы частот в файл

fileStream = new System.IO.FileStream (outputFileName, System.IO.FileMode.Create, System.IO.FileAccess.Write);

byte[] byteN = Converter.convertIntToByte(frequenceTable.Count);

for (inti = 0; i< 4; i++)

fileStream.WriteByte(byteN[i]);

foreach (var pair in frequenceTable)

{

byte[] b = Converter.convertIntToByte(pair.Value);

fileStream.WriteByte(pair.Key);

for (inti = 0; i< 4; i++)

fileStream.WriteByte(b[i]);

}

// Запись в файл закодированной последовательности

Tree tree = Tree.Create(frequenceTable);

Dictionary<byte, string>charCodes = tree.Interpretate();

StringBuilder code = new StringBuilder("");

for (inti = 0; i<input.Count; i++)

{

code.Append(charCodes[input[i]].ToString());

}

// Записьдлиныпоследнегобайта

fileStream.WriteByte(Convert.ToByte(code.Length% 8));

bytenewByte = 0;

bytepow = 1;

for (inti = 0, j = 0; i<code.Length; i++, j = (j + 1)% 8)

{

if (code[i] == '1')

{

newByte += pow;

}

if (j == 7)

{

fileStream.WriteByte(newByte);

pow = 1;

newByte = 0;

}

else

{

pow *= 2;

}

}

if (code.Length% 8 != 0)

{

fileStream.WriteByte(newByte);

}

fileStream.Close();

}

}

}

· Исходный код декодера:

usingSystem;

usingSystem.Collections.Generic;

usingSystem.Linq;

usingSystem.Text;

usingSystem.Threading.Tasks;

namespace Хаффман

{

// Класс, инкапсулирующий логику декомпрессии по алгоритму Хаффмана

classDecompressor

{

publicDecompressor()

{

}

// Разжимает входной файл, и записывает результат в выходной

// "inputFileName" - Имя входного файла для декомпрессии

// "outputFileName" - Имя выходного файла для декомпрессии

public static void Decompress(string inputFileName, string outputFileName)

{

System.IO.FileStreamfileStream = new System.IO.FileStream(inputFileName, System.IO.FileMode.Open, System.IO.FileAccess.Read);

Dictionary<byte, int>frequenceTable = new Dictionary<byte, int>();

// Чтение таблицы частот из файла

byte[] byteN = new byte[4];

for (inti = 0; i< 4; i++)

byteN[i] = (byte)fileStream.ReadByte();

inttableSize = Converter.convertByteToInt(byteN);

byte key;

byte[] pair = new byte[4];

for (inti = 0; i<tableSize; i++)

{

key = (byte)fileStream.ReadByte();

for (int j = 0; j < 4; j++)

pair[j] = (byte)fileStream.ReadByte();

frequenceTable.Add(key, Converter.convertByteToInt(pair));

}

//Декомпрессия

Tree tree = Tree.Create(frequenceTable);

StringBuilder input = new StringBuilder("");

byte tail = (byte)fileStream.ReadByte();

for (inti = 0; i<fileStream.Length - 1 - 4 - 5 * tableSize; i++)

{

byte b = (byte)fileStream.ReadByte();

if ((i == fileStream.Length - 2) && (tail != 0))

{

for (int j = 0; j <= tail; j++)

{

input.Append((b% 2).ToString());

b /= 2;

}

}

else

{

for (int j = 0; j < 8; j++)

{

input.Append((b% 2).ToString());

b /= 2;

}

}

}

fileStream.Close();

System.IO.FileStreamfileOutputStream = new System.IO.FileStream(outputFileName, System.IO.FileMode.Create);

List<byte>toFile = tree.Recognize(input.ToString());

fileOutputStream.Write(toFile.ToArray(), 0, toFile.Count);

fileOutputStream.Close();

}

}

}

//Также используется вспомогательный статический класс Converterдля преобразования intвbyte и обратно:

publicstaticclassConverter

{

// Конвертирует четыре байта в целое число

// "key" - Массив из 4 байтов

// возвращает Целое число

public static intconvertByteToInt(byte[] key)

{

if (key.Length != 4)

throw new ArgumentException("Неверныйаргументдляметода convert ByteToInt");

return key[0] + key[1] * 256 + key[2] * 65536 + key[3] * 16777216;

}

// Конвертирует целое число в массив из четырёх байтов

// "key" - Целое число

// возвращает Массив 4 байтов

public static byte[] convertIntToByte(int key)

{

if (key < 0)

throw new ArgumentException("Неверныйаргументдляметода convert IntToByte");

int key1 = key;

byte[] b = new byte[4];

for (inti = 0; i< 4; i++)

{

b[i] = (byte)(key1% 256);

key1 /= 256;

}

return b;

}

}

Результаты запуска программы.

На рисунке 7 представлено основное меню при запуске программы.

Рисунок 7 - основное меню при запуске программы.

При нажатии на кнопку "Choosefile (.doc, .bmp, .jpg)" появляется диалоговое окно для выбора файла. Чтобы выбрать необходимый файловый формат, следует в поле для выбора фильтра выбрать один из трех предложенных форматов (.doc, .bmp, .jpg). После этого в поле ниже появится путь к выбранному файлу. При нажатии на кнопку "Закодировать" кодер осуществляет сжатие выбранного файла, и в папке по указанной в код программы директории создается файл с расширением .hfm. При нажатии на кнопку "Декодировать" декодер преобразовывает ранее сжатый декодером файл к его изначальному виду.

На рисунках 8-9представлены результаты запуска программы для файла типа .bmp для маленького и среднего файлов, соответственно.

Сначала рассмотрим этот процесс для маленького файла:

На рисунке 8 представлен размер входного файла до сжатия, после сжатия и после декодирования (для маленького файла).

Рисунок 8 - представлен размер входного файла до сжатия, после сжатия и после декодирования (для маленького файла .bmp).

Далее рассмотрим этот процесс для среднего файла:

На рисунке 9 представлен размер входного файла до сжатия, после сжатия и после декодирования (для среднего файла).

Рисунок 9 - представлен размер входного файла до сжатия, после сжатия и после декодирования (для среднего файла .bmp) .

Коэффициент сжатия для маленького файла формата .bmp составил 2,0. А для среднего файла формата .bmp 1,05.

Оценка эффективности

Проведя серию данных, мы получили следующие коэффициенты сжатия:

Формат входного файла	.doc	.bmp	.jpg
Размер файла до сжатия (Маленький файл|Средний файл)	97 Кб|768 Кб	32,8 Кб|870 Кб	305 Кб|1,02 Мб
Размер файла после сжатия (Маленький файл|Средний файл)	48,5 Кб|731 Кб	21,6 Кб|625 Кб	305 Кб|1,02 Мб
Маленький файл (коэффициент)	2,0	1,5	1
Средний файл (коэффициент)	1,05	1,39	1
Время сжатия (Маленький файл|Средний файл)	2 сек | 19 сек	2 сек | 14 сек	4 сек | 1 мин 12 сек

Что касается времени, потраченного на сжатие файлов, то можно сделать вывод о том, что время сжатия напрямую зависит от размера сжимаемых файлов: то есть, чем больше размер файла, тем большее время требуется на его сжатие.

При обратном преобразовании были получены корректные результаты.



Выводы

Таким образом, нами была изучена тема "Алгоритмы сжатия" и была реализована программа, реализующая алгоритм кодера и декодера на основе динамического алгоритма Хаффмана. В результате работы программы были получены корректные результаты. Из теоретических и экспериментальных данных можно сделать вывод, что степень сжатия не зависит от размера файла (Исключение - когда файл слишком маленького размера и модель кодирования сводит на нет весь результат), а зависит лишь от частот появлений тех или иных символов во входном файле. Если частота появления всех символов примерно одинакова то сжатие не будет удачным, иначе можно ожидать хорошего сжатия. Также стоит обратить внимание на файлы типа jpg, которые не подвергаются сжатию, так как уже представляют собой результат сжатия по Хаффману. Что касается времени, потраченного на сжатие файлов, то можно сделать вывод о том, что время сжатия напрямую зависит от размера сжимаемых файлов: то есть, чем больше размер файла, тем большее время требуется на его сжатие. При обратном преобразовании были получены корректные результаты: файл был восстановлен и открыт, не содержал ошибок при чтении.

Размещено на Allbest.ru

...