Статический алгоритм Хаффмана

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

Выбираются два свободных узла дерева с наименьшими весами.

Создаётся их родитель с весом, равным их суммарному весу.

Родитель добавляется в список свободных узлов, а двое его детей удаляются из этого списка.

Одной дуге, выходящей из родителя, ставится в соответствие бит 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).

Поскольку ни один из полученных кодов не является префиксом другого, они могут быть однозначно декодированы при чтении их из потока. Алгоритм декодирования предполагает просмотр потока битов и синхронное перемещение от корня вниз по дереву Хаффмана в соответствии со считанным значением до тех пор, пока не будет достигнут лист, то есть декодировано очередное кодовое слово, после чего распознавание следующего слова вновь начинается с вершины дерева.

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

Детали реализации

Главной проблемой статического алгоритма Хаффмана является запись в файл модели кодирования. В данной программе мы записываем модель кодирования таким образом: сначала идёт сам байт, а затем его количество появлений в исходном тексте(4 байта - стандартный тип int): итого 1 + 4 = 5 байт, т.е. в худшем случае - 256 * 5 = 1280 примерно 1 кб.

Результат работы программы

Используемые АТД

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

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

classMinHeap<T>where T : IComparable

{

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

privateint N;

publicMinHeap()

{

N = 0;

}

publicvoid 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;

}

privatevoidMinHeapify(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);

}

}

publicvoidBuildMinHeap()

{

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" - Ключ для вставки

publicvoidHeapInsert(T Key)

{

N++;

HeapIncreaseKey(N, Key);

}

}

}

2) АТД бинарное дерево.

- дерево, каждый узел которого имеет не более 2 дочерних узлов.

// Узел дерева

publicclassNode : IComparable

{

static Node() { }

publicintCompareTo(Object node)

{

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

return 1;

elseif (this.Weight< ((Node)node).Weight)

return -1;

else

return 0;

}

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

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

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

publicNode 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;

}

}

}

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

publicclassTree

{

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

private NodeRoot;

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

privateDictionary<byte, string> table;

publicstaticTree Create(Dictionary<byte, int> table)

{

int N = table.Count;

MinHeap<Node> heap = newMinHeap<Node>();

foreach (var t in table)

{

heap.HeapInsert(newNode(t.Value, t.Key));

}

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

{

Node x = heap.HeapExtractMin();

Node y = heap.HeapExtractMin();

Node z = newNode(y, x, x.Weight + y.Weight);

heap.HeapInsert(z);

}

returnnewTree(heap.HeapExtractMin());

}

public Tree(Node root)

{

Root = root;

table = newDictionary<byte,string>();

}

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

publicDictionary<byte, string>Interpretate()

{

if (Root != null)

{

DFS(Root, "");

return table;

}

else

returnnull;

}

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

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

publicList<byte> Recognize(string input)

{

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

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

{

Nodecurr = 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;

}

privatevoid DFS(Nodenode, stringstr)

{

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();

}

}

}

}

Структура программы

кодирование информация алгоритм хаффман

Главную логику программы инкапсулируют 2 класса:

Static Haffman Compressor и Static Haffman Decompressor, которые реализуют 2 основных метода - Compress и Decompress.

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

publicclassStaticHaffmanCompressor

{

publicStaticHaffmanCompressor()

{

}

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

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

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

publicvoid Compress(stringinputFileName, stringoutputFileName)

{

FileStreamfileStream = newFileStream(inputFileName, FileMode.Open, FileAccess.Read);

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

List<byte> input = newList<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 = newFileStream(outputFileName, FileMode.Create, FileAccess.Write);

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

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

fileStream.WriteByte(byteN[i]);

foreach (var pair infrequenceTable)

{

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

fileStream.WriteByte(pair.Key);

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

fileStream.WriteByte(b[i]);

}

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

Treetree = Tree.Create(frequenceTable);

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

StringBuilder code = newStringBuilder("");

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();

}

}

}

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

publicclassStaticHaffmanDecompressor

{

publicStaticHaffmanDecompressor()

{

}

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

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

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

publicvoid Decompress(stringinputFileName, stringoutputFileName)

{

FileStreamfileStream = newFileStream(inputFileName, FileMode.Open, FileAccess.Read);

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

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

byte[] byteN = newbyte[4];

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

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

inttableSize = Converter.convertByteToInt(byteN);

byte key;

byte[] pair = newbyte[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));

}

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

Treetree = Tree.Create(frequenceTable);

StringBuilder input = newStringBuilder("");

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();

FileStreamfileOutputStream = newFileStream(outputFileName, FileMode.Create);

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

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

fileOutputStream.Close();

}

}

}

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

publicstaticclassConverter

{

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

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

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

publicstaticintconvertByteToInt(byte[] key)

{

if (key.Length != 4)

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

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

}

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

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

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

publicstaticbyte[] convertIntToByte(int key)

{

if (key < 0)

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

int key1 = key;

byte[] b = newbyte[4];

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

{

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

key1 /= 256;

}

returnb;

}

}

}

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

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

Вывод

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

Список литературы

1. “Структуры данных и алгоритмы сжатия информации без потерь” - Методическое пособие, Пантеллев Е.Р. - Иваново 2001г.

2. “Алгоритмы: построение и анализ”, Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. - 2е издание, Издательский дом “Вильямс”, 2007г.

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