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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

ОТЧЕТ

по лабораторной работе

на тему: «Алгоритм Хаффмана»

Выполнил:

студент 4-го курса 7-ой группы

Глазьева Ю.В.

Проверил:

доц. Воронков Б.Н.

Воронеж - 2016



Содержание

• 1. Общие сведения
• 1.1 Обозначение и наименование программы
• 1.2 Программное обеспечение, необходимое для функционирования программы
• 1.3.Языки программирования
• 2. Функциональное назначение
• 2.1 Классы решаемых задач и назначение программы
• 3. Описание логической структуры

3.1 Принципы работы алгоритма ГОСТ 28147 - 89

3.2 Описание алгоритма ГОСТ 28147 - 89

3.3 Общая структура

3.4 Код программы

4. Тестирование программного продукта



1. Общие сведения

1.1 Обозначение и наименование программы

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

Обозначение: Алгоритм Хаффмана.

1.2 Программное обеспечение, необходимое для функционирования программы

алгоритм хаффман программирование листинг

Программа, реализующая метод Хаффмана является приложением типа Windows Forms. Основным необходимым требованием для функционирования данного ПО является наличие интегрированный среды разработки Microsoft Visual Studio (не позднее версии Visual Studio 2013). Функционирование ПО шифра Виженера тестировалось под операционной системой для персональных компьютеров: Windows 10.

1.3 Языки программирования

Алгоритм Хаффмана реализован на объектно-ориентированном языке C#. Модули, реализованные на других языках программирования не используются.



2. Функциональное назначение

2.1 Классы решаемых задач и назначение программы

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



3. Описание логической структуры

3.1 Принципы работы алгоритма ГОСТ 28147 - 89

Примечание переводчика: под символом автор подразумевает некий повторяющийся элемент исходной строки -- это может быть как печатный знак (character), так и любая битовая последовательность. Под кодом подразумевается не ASCII или UTF-8 код символа, а кодирующая последовательность битов. К статье прикреплён исходный код, который наглядно демонстрирует, как работает алгоритм Хаффмана -- он предназначен для людей, которые плохо понимают математику процесса. В будущем (я надеюсь) я напишу статью, в которой мы поговорим о применении алгоритма к любым файлам для их сжатия (то есть, сделаем простой архиватор типа WinRAR или WinZIP). Идея, положенная в основу кодировании Хаффмана, основана на частоте появления символа в последовательности.

Символ, который встречается в последовательности чаще всего, получает новый очень маленький код, а символ, который встречается реже всего, получает, наоборот, очень длинный код. Это нужно, так как мы хотим, чтобы, когда мы обработали весь ввод, самые частотные символы заняли меньше всего места (и меньше, чем они занимали в оригинале), а самые редкие -- побольше (но так как они редкие, это не имеет значения). Для нашей программы я решил, что символ будет иметь длину 8 бит, то есть, будет соответствовать печатному знаку. Мы могли бы с той же простотой взять символ длиной в 16 бит (то есть, состоящий из двух печатных знаков), равно как и 10 бит, 20 и так далее.

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

Для этого алгоритма вам потребуется минимальное понимание устройства бинарного дерева и очереди с приоритетами. В исходном коде я использовал код очереди с приоритетами из моей предыдущей статьи. Предположим, у нас есть строка «beep boop beer!», для которой, в её текущем виде, на каждый знак тратится по одному байту. Это означает, что вся строка целиком занимает 15*8 = 120 бит памяти. После кодирования строка займёт 40 бит (на практике, в нашей программе мы выведем на консоль последовательность из 40 нулей и единиц, представляющих собой биты кодированного текста. Чтобы получить из них настоящую строку размером 40 бит, нужно применять битовую арифметику, поэтому мы сегодня не будем этого делать).

Чтобы лучше понять пример, мы для начала сделаем всё вручную. Строка «beep boop beer!» для этого очень хорошо подойдёт. Чтобы получить код для каждого символа на основе его частотности, нам надо построить бинарное дерево, такое, что каждый лист этого дерева будет содержать символ (печатный знак из строки).

Дерево будет строиться от листьев к корню, в том смысле, что символы с меньшей частотой будут дальше от корня, чем символы с большей. Скоро вы увидите, для чего это нужно. Чтобы построить дерево, мы воспользуемся слегка модифицированной очередью с приоритетами -- первыми из неё будут извлекаться элементы с наименьшим приоритетом, а не наибольшим. Это нужно, чтобы строить дерево от листьев к корню.



3.2 Описание алгоритма ГОСТ 28147 - 89

Закодируем строку "Сжатие Хаффмана"

Вначале нужно подсчитать количество вхождений каждого символа в тексте.

С	ж	а	т	и	е		Х	ф	м	н
1	1	4	1	1	1	1	1	2	1	1

Эта таблица называется "таблица частот".

Теперь будем строить дерево

Узел дерева будет образован набором символов и числом - суммарным количеством вхождений данных символов в тексте. Назовем указанное число - весом узла.

Листьями дерева будут узлы, образованные одним символом:

Теперь будем циклически делать следующее:

1) Ищем среди узлов, не имеющих родителя, два узла, имеющих в сумме наименьший вес.

2) Создаем новый узел, его потомками будут два выбранных узла. Его весом будет сумма весов выбранных улов. Его набор символов будет образован в результате объединения наборов символов выбранных узлов.

Создаем первый узел



Создаем еще один узел

Создаем еще один узел

Создаем еще один узел

Создаем еще один узел



Создаем еще один узел

Создаем еще один узел

Создаем еще один узел



Создаем еще один узел

Создаем еще один узел



Теперь для каждого узла, имеющего потомков, пометим дуги, идущие вниз, на одной дуге напишем 0, на другой 1.

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

Получаются следующие коды

С	0001
ж	0000
а	01
т	0010
и	0011
е	1011
	1010
Х	111
ф	110
м	1000
н	1001

Заметим, что код является префиксным, т. е. ни один код символа не является префиксом кода другого символа. Также видно, что для часто встречающихся символов коды короче.

Как будет выглядеть закодированная строка:

С	ж	а	т	и	е		Х	а	ф	ф	м	а	н	а
0001	0000	01	0010	0011	1011	1010	111	01	110	110	1000	01	1001	01

Т. е.

0001000001001000111011101011101110110100001100101

1 Декодирование

Для декодирования можно воспользоваться построенным деревом. Начинаем с корня дерева и в качестве текущего бита берем начало текста.

В цикле делаем следующее

1) Смотрим, какое значение у текущего бита, и идем в низ по дереву по дуге, на которой указано такое же значение.

2) Переходим к следующему биту.

3) Если сейчас находимся в листе дерева: читаем символ находящийся в этом листе и записываем его в результат декодирования, переходим снова в корень дерева.

3.2 Общая структура

Программа "Алгоритм шифрования данных ГОСТ 28147 - 89" выполняет 2 из 4-х основных режимов шифрования:

режим гаммирования;

режим выборки имитовставки.

Рассмотрим алгоритм каждого из них в отдельности.



3.3 Код программы

using System;

using System.Collections;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

using System.Windows.Forms;

namespace Haffman

{

public partial class Form1: Form

{

public HuffmanTree htree = new HuffmanTree(); //дерево хаффмана

public BitArray encoded; //закодированные данные

public Form1()

{

InitializeComponent();

}

private void button1_Click(object sender, EventArgs e)

{

htree = new HuffmanTree(); //дерево хаффмана

int i = 0;

richTextBox1.Text = "";

//строим дерево

htree.Build(textBox1.Text);

//кодируем

encoded = htree.Encode(textBox1.Text);

MessageBox.Show("Закодировано");

//выводим закодированные данные

foreach (bool bit in encoded)

{

richTextBox1.Text += ((bit ? 1: 0).ToString()+" ");

}

//выводим текст

foreach (KeyValuePair<char, int> item in htree.Frequencies)

{

richTextBox3.Text += ("Символ: " + item.Key + "\tКоличество: " + item.Value.ToString() + "\tЧастота: " + (Math.Round((float)item.Value / textBox1.Text.Length, 3))+"\tКод " + htree.codec.ToArray()[i]+ "\n");

i++;

}

}

private void button2_Click(object sender, EventArgs e)

{

richTextBox2.Text = "";

//декодируем

richTextBox2.AppendText(htree.Decode(encoded));

}

private void Form1_Load(object sender, EventArgs e)

{

}

private void textBox1_Leave(object sender, EventArgs e)

{

}

}

}

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace Haffman

{

//класс для построения дерева

public class Node

{

//символ

public char Symbol { get; set; }

//частота

public int Frequency { get; set; }

//правая ветка

public Node Right { get; set; }

//левая ветка

public Node Left { get; set; }

//возвращает путь

public List<bool> Traverse(char symbol, List<bool> data)

{

// если лист

if (Right == null && Left == null)

{

//символ найден

if (symbol.Equals(this.Symbol))

{

//возарвщаем результат

return data;

}

else

{

return null;

}

}

else

{

List<bool> left = null;

List<bool> right = null;

//переходим на левую ветку

if (Left != null)

{

List<bool> leftPath = new List<bool>();

leftPath.AddRange(data);

leftPath.Add(false);

left = Left.Traverse(symbol, leftPath);

}

//переходим на правую ветку

if (Right != null)

{

List<bool> rightPath = new List<bool>();

rightPath.AddRange(data);

rightPath.Add(true);

right = Right.Traverse(symbol, rightPath);

}

if (left != null)

{

return left;

}

else

{

return right;

}

}

}

}

}

using System;

using System.Collections;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace Haffman

{

public class HuffmanTree

{

//список узлов дерева

private List<Node> nodes = new List<Node>();

//корень дерева

public Node Root { get; set; }

//словарь частот, соотносит символ с частотой

public Dictionary<char, int> Frequencies = new Dictionary<char, int>();

//построение дерева

public void Build(string source)

{

//заполняем словарь частот

for (int i = 0; i < source.Length; i++)

{

if (!Frequencies.ContainsKey(source[i]))

{

Frequencies.Add(source[i], 0);

}

Frequencies[source[i]]++;

}

//добавляем все частоты в список узлов

foreach (KeyValuePair<char, int> symbol in Frequencies)

{

nodes.Add(new Node() { Symbol = symbol.Key, Frequency = symbol.Value });

}

//пока в списке узлов элементов >1

while (nodes.Count > 1)

{

//сортируем по частотам во возрастанию

List<Node> orderedNodes = nodes.OrderBy(node => node.Frequency).ToList<Node>();

//если элементов 2 или больше

if (orderedNodes.Count >= 2)

{

//берем первые два элемента

List<Node> taken = orderedNodes.Take(2).ToList<Node>();

//создаем родительский элемент комбинированием дочерних частот, потомками назначаем дочерние узлы

Node parent = new Node()

{

Symbol = '*',

Frequency = taken[0].Frequency + taken[1].Frequency,

Left = taken[0],

Right = taken[1]

};

//удаляем из списка узлов дочерние узлы

nodes.Remove(taken[0]);

nodes.Remove(taken[1]);

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

nodes.Add(parent);

}

//корнем назначается первый элемент списка узлов

this.Root = nodes.FirstOrDefault();

}

}

private List<string> code = new List<string>(); //список кодов символов

public IEnumerable<string> codec; //список кодов из которого удалены все повторения символов

public BitArray Encode(string source)

{

List<bool> encodedSource = new List<bool>(); //для результата

//проходим по всему сообщению

for (int i = 0; i < source.Length; i++)

{

//получаем список кодов для символа

List<bool> encodedSymbol = this.Root.Traverse(source[i], new List<bool>());

//добавляем к результату

encodedSource.AddRange(encodedSymbol);

this.code.Add("");

//добавляем к списку кодов

foreach (bool a in encodedSymbol.ToArray())

{

this.code[i] += Convert.ToInt32(a).ToString();

}

}

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

codec = code.Distinct();

//возвращаем результат в виде массива бит

BitArray bits = new BitArray(encodedSource.ToArray());

return bits;

}

public string Decode(BitArray bits)

{

Node current = this.Root;

string decoded = "";

//проходим по всем битам

foreach (bool bit in bits)

{

//идем по дереву

if (bit)

{

if (current.Right != null)

{

current = current.Right;

}

}

else

{

if (current.Left != null)

{

current = current.Left;

}

}

//если лист, то добавляем к тексту

if (IsLeaf(current))

{

decoded += current.Symbol;

current = this.Root;

}

}

return decoded;

}

//проверка лист или нет

public bool IsLeaf(Node node)

{

// если нет потомков, то лист

return (node.Left == null && node.Right == null);

}

}

}



4. Тестирование программного продукта

Вводим «сообщение» текст, например, гаммирование

При нажатии кнопки кодировать мы получаем зашифрованное сообщение в соответствующем поле и получаем имитовставку, а при нажатии декодировать получаем расшифрованное сообщение, т.е. изначально введенный нами текст.

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