Алгоритмы и структуры данных. Соколов А.С. Курсовой 4-80к. Курсовая работа по курсу Алгоритмы и структуры данных
 Скачать 140.61 Kb.
|
Оценка эффективностиДанная программа была пропущена через некий ряд файлов различных расширений и размеров, чтобы затем сделать выводы об этом алгоритме. Таблица 1 – результаты работы программы.
Минимальная полученная степень сжатия – 57% для расширения .xml, максимальная – 116 для .png. Всех лучше поддаются сжатию файлы, содержащие небольшую вариацию символов с большой частотой их встречи, что характерно для файлов, содержащих текстовую информацию (протоколы, файлы с настройками и пр.) или .exe, в которых в силу кодирования набралось много одинаковых символов. Эффективность сжатия алгоритма сильно зависит от типов данных, а также от размера сжимаемого файла. Например, если файл слишком маленького размера, тогда передача модели кодирования может свести на нет весь результат. Стоит отметить, что файлы типа jpeg не подвергаются сжатию, поскольку представляют результат сжатия по Хаффману. ВыводыВ ходе работы была разработана программа, реализующая один из методов работы статическим алгоритмом сжатия Хаффмана. Оценка эффективности работы кодера на различных файлах показала, что кодер достаточно эффективно сжимает определенные форматы файлов (текстовые, исполняемые); форматы, которые несут в себе результат работы алгоритмов сжатия, показали невысокую степень сжатия. Библиографический список1 Пантелеев Е.Р., Фомин П.А. Структуры данных и алгоритмы сжатия информации без потерь: Метод. указания/Иван.гос.энерг.ун-т. – Иваново, 2001. – 28 с 2 Свами М., Тхуласираман К. Графы, сети и алгоритмы: Пер.с англ. – М.: Мир, 1984. – 455 с. 3 “Алгоритмы: построение и анализ”, Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. – 2е издание, Издательский дом “Вильямс”, 2007г. Приложение А(обязательное) Код быстрого прототипа Файл Node.cs using System; namespace Huff.ATD { /// /// Класс инкапсулирует узел дерева Хаффмана /// public class Node : IEquatable { /// /// Конструктор /// public Node() { } /// /// Указатель на левый узел /// public Node LeftNode { get; set; } /// /// Указатель на правый узел /// public Node RightNode { get; set; } /// /// Указатель на родителя /// public Node Parent { get; set; } /// /// Вес узла /// public int Weight { get; set; } /// /// Значение /// public byte Value { get; set; } public bool Equals(Node other) { return (this.Value == other.Value && this.LeftNode == other.LeftNode && this.RightNode == other.RightNode); } public int CompareTo(Node other) { if (other == null) { throw new Exception("Невозможно сравнить два объекта"); } if (this.Weight > other.Weight) { return -1; } else { if (this.Weight < other.Weight) { return 1; } } return 0; } } } Файл HuffmanTree.cs using System; using System.Collections; using System.Collections.Generic; using System.Linq; using System.Text; namespace Huff.ATD { /// /// Класс инкапсулирует дерево Хаффмана /// public class HuffmanTree { public Node Root { get; set; } private static Node[] _nodes; List /// /// Метод сторит дерево из таблицы частот /// public void BuildTree(int[] byteMap) { for (int i = 0; i < 256; i++) if (byteMap[i] > 0) HuffmansNodes.Add(new Node { Value = (byte)i, Weight = byteMap[i] }); // добавляем все узлы _nodes = HuffmansNodes.ToArray(); while (HuffmansNodes.Count > 1) { Node firstNode = null; Node secondNode = null; GetPair(ref firstNode, ref secondNode);// ищем 2 самых легких Node newNode = new Node() { LeftNode = firstNode, RightNode = secondNode, Weight = firstNode.Weight + secondNode.Weight }; firstNode.Parent = newNode; secondNode.Parent = newNode; HuffmansNodes.Add(newNode);// заменяем 2 самых легких на один с весом = сумме } Root = HuffmansNodes.First(); // в итоге - дерево, корень в руте } /// /// Возвращает пару узлов с минимальной частотой /// /// value1"> /// value2"> private void GetPair(ref Node value1, ref Node value2) { Sort();//предварительно сортируем value1 = HuffmansNodes.Last(); HuffmansNodes.Remove(value1);//убрали последний элемент value2 = HuffmansNodes.Last(); HuffmansNodes.Remove(value2);//убрали предпоследний элемент } /// /// Располагаем символы в порядке убывания их частот /// private void Sort() { HuffmansNodes.Sort((a, b) => a.CompareTo(b)); } /// /// Метод возвращает таблицу кодов Хаффмана /// /// public Dictionary {// получаем карту для кодирования var output = new Dictionary var sb = new StringBuilder(); foreach (Node currentNode in _nodes) // для каждого узла строим код Хаффмана { //бежим по дереву var huffmanTree = currentNode; sb.Clear(); //тут составляем код while (huffmanTree.Parent != null) { sb.Append(huffmanTree == huffmanTree.Parent.LeftNode ? "0" : "1"); // если ветвь левая - добавляем 0, если правая -1 huffmanTree = huffmanTree.Parent; } var bitArray = new BitArray(sb.Length); byte b = new byte(); for (int j = 0; j < sb.Length; j++) { b |= (byte) ((sb[j]) << j); } output.Add(currentNode.Value, b); } return output; } } } Файл Huffman.cs using System; using System.Collections.Generic; using System.Diagnostics; using System.IO; using Huff.ATD; namespace Huff { public class Huffman { /// /// Таблица частот /// readonly int[] _byteMap = new int[256]; Stopwatch time = new Stopwatch();//таймер /// /// Запускает процесс кодирования /// public void Coding() { time.Start(); string strFileName = "EntityFramework"; string strPath = "C:\\Users\\User\\Documents\\Visual Studio 2017\\Projects\\Huff\\Файлы для кодирования\\FastPrototype\\"; string strFormat = ".xml"; FillByteMap($"{strPath}{strFileName}{strFormat}"); //1.Заполнили карту частот HuffmanTree tree = new HuffmanTree(); tree.BuildTree(_byteMap); //2.Построили дерево Хаффмана //3.Пишем в файл var huffmapMap = tree.GetMap(); WriteToFile($"{strPath}{strFileName}{strFormat}", $"{strFileName}.huff", huffmapMap); //4.Выводим на экран инфоормацию о файлах FileInfo file = new FileInfo($"{strPath}{strFileName}{strFormat}"); FileInfo file2 = new FileInfo($"{ Directory.GetCurrentDirectory()}\\{strFileName}.huff"); long size, size2, count; size = file.Length; size2 = file2.Length; count = (size2 * 100 / size); Console.WriteLine($"Файл «{file.FullName}» успешно закодирован"); Console.WriteLine($"Размер файла был: {size} байт"); Console.WriteLine($"Размер файла стал: {size2} байт"); Console.WriteLine($"Коэффициент сжатия: {count} %"); Console.WriteLine($"Время кодирования: {time.Elapsed}"); time.Reset(); } /// /// Пишем код иходя из кодовой карты Хаффмана в поток /// /// newFileName">Имя файла /// huffmapMap">Кодовая карта (По Хаффману) private void WriteToFile(string origFileName, string newFileName, Dictionary { var codes = new List using (var fs = new FileStream(origFileName, FileMode.Open)) { for (int i = 0; i < fs.Length; i++) { var myByte = (Byte)fs.ReadByte(); //Каждому символу соответствует код в дереве Хаффмана codes.Add(huffmapMap[myByte]); //собираем закодированное сообщение } using (var sw = new FileStream(newFileName, FileMode.Create)) using (var bw = new BinaryWriter(sw)) { foreach (var b in _byteMap) { bw.Write(b);// сначала пишем в фаил карту баит } //byte addBits = (byte)_nCountBytes; //кол-во байт в закодированном сообщении //bw.Write(addBits); // количество доп бит foreach (var b in codes)//для каждого символа кодовой карты Хаффмана { bw.Write(b); // пишем сам код } } } } /// /// Количество байт в закодированном сообщении /// private int _nCountBytes; /// /// Заполняет таблицу частот /// /// strFileName">Имя файла private void FillByteMap(string strFileName) { using (var fs = new FileStream(strFileName, FileMode.Open)) { for (int i = 0; i < fs.Length; i++) { Byte myByte = (Byte)fs.ReadByte(); _byteMap[myByte]++; _nCountBytes++; } } } } } Файл Program.cs using System; namespace Huff { class Program { static void Main(string[] args) { (new Huffman()).Coding(); Console.ReadLine(); } } } Приложение Б(обязательное) Код оптимизированной версии Файл Node.cs using System; namespace HuffOptima.ATD { /// /// Класс инкапсулирует узел дерева Хаффмана /// public class Node : IEquatable { /// /// Конструктор /// public Node() { } /// /// Указатель на левый узел /// public Node LeftNode { get; set; } /// /// Указатель на правый узел /// public Node RightNode { get; set; } /// /// Указатель на родителя /// public Node Parent { get; set; } /// /// Вес узла /// public int Weight { get; set; } /// /// Значение /// public byte Value { get; set; } public bool Equals(Node other) { return (this.Value == other.Value && this.LeftNode == other.LeftNode && this.RightNode == other.RightNode); } public int CompareTo(Node other) { if (other == null) { throw new Exception("Невозможно сравнить два объекта"); } if (this.Weight > other.Weight) { return -1; } else { if (this.Weight < other.Weight) { return 1; } } return 0; } } } Файл HuffmanTree.cs using System.Collections; using System.Collections.Generic; using System.Linq; using System.Text; using HuffOptima.ATD; namespace Huff.ATD { /// /// Класс инкапсулирует дерево Хаффмана /// public class HuffmanTree { public Node Root { get; set; } private static Node[] _nodes; List /// /// Метод сторит дерево из таблицы частот /// public void BuildTree(int[] byteMap) { for (int i = 0; i < 256; i++) if (byteMap[i] > 0) HuffmansNodes.Add(new Node { Value = (byte)i, Weight = byteMap[i] }); // добавляем все узлы _nodes = HuffmansNodes.ToArray(); while (HuffmansNodes.Count > 1) { Node firstNode = null; Node secondNode = null; GetPair(ref firstNode, ref secondNode);// ищем 2 самых легких Node newNode = new Node() { LeftNode = firstNode, RightNode = secondNode, Weight = firstNode.Weight + secondNode.Weight }; firstNode.Parent = newNode; secondNode.Parent = newNode; HuffmansNodes.Add(newNode);// заменяем 2 самых легких на один с весом = сумме } Root = HuffmansNodes.First(); // в итоге - дерево, корень в руте } /// /// Возвращает пару узлов с минимальной частотой /// /// value1"> /// value2"> private void GetPair(ref Node value1, ref Node value2) { Sort();//предварительно сортируем value1 = HuffmansNodes.Last(); HuffmansNodes.Remove(value1);//убрали последний элемент value2 = HuffmansNodes.Last(); HuffmansNodes.Remove(value2);//убрали предпоследний элемент } /// /// Располагаем символы в порядке убывания их частот /// private void Sort() { HuffmansNodes.Sort((a, b) => a.CompareTo(b)); } /// /// Метод возвращает таблицу кодов Хаффмана /// /// public Dictionary {// получаем карту для кодирования var output = new Dictionary var sb = new StringBuilder(); foreach (Node currentNode in _nodes) // для каждого узла строим код Хаффмана { //бежим по дереву var huffmanTree = currentNode; sb.Clear(); //тут составляем код while (huffmanTree.Parent != null) { sb.Append(huffmanTree == huffmanTree.Parent.LeftNode ? "0" : "1"); // если ветвь левая - добавляем 0, если правая -1 huffmanTree = huffmanTree.Parent; } var bitArray = new BitArray(sb.Length); for (int j = 0; j < sb.Length; j++) { bitArray[j] = sb[j] - '0' == 1; // собираем в битареи и добавляем в карту } output.Add(currentNode.Value, bitArray); } return output; } } } Файл Huffman.cs using System; using System.Collections; using System.Collections.Generic; using System.Diagnostics; using System.IO; using System.Linq; using System.Windows.Forms; using Huff.ATD; namespace Huff { public class Huffman { /// /// Размер начального файла /// public long sizeBegin { get; private set; } /// /// Размер конечного файла /// public long sizeEnd { get; private set; } public TimeSpan codingTime { get; private set; } /// /// Дельта файла /// public long delta { get; set; } /// /// Таблица частот /// readonly int[] _byteMap = new int[256]; Stopwatch time = new Stopwatch(); //таймер /// /// Запускает процесс кодирования /// public void Coding(string strFileName) { time.Start(); FillByteMap(strFileName); //1.Заполнили карту частот HuffmanTree tree = new HuffmanTree(); tree.BuildTree(_byteMap); //2.Построили дерево Хаффмана var huffmapMap = tree.GetMap(); WriteToFile(strFileName, $"{strFileName}.huff", huffmapMap); FileInfo file = new FileInfo(strFileName); FileInfo file2 = new FileInfo($"{strFileName}.huff"); long size, size2, count; size = file.Length; size2 = file2.Length; count = (size2 * 100 / size); sizeBegin = size; //Размер файла был sizeEnd = size2; //Размер файла стал codingTime = time.Elapsed; //Время кодирования delta = count; //Размер файла уменьшился на MessageBox.Show("Кодирование файла успешно завершено","Кодирование Хаффмана",MessageBoxButtons.OK,MessageBoxIcon.Information); time.Reset(); } /// /// Пишем код иходя из кодовой карты Хаффмана в поток /// /// newFileName">Имя файла /// huffmapMap">Кодовая карта private void WriteToFile(string origFileName, string newFileName, Dictionary { var codes = new List using (var fs = new FileStream(origFileName, FileMode.Open)) { for (int i = 0; i < fs.Length; i++) { var myByte = (Byte)fs.ReadByte(); //Каждому символу соответствует код в дереве Хаффмана codes.Add(huffmapMap[myByte]); //собираем закодированное сообщение } var count = codes.Sum(bitArray => bitArray.Count); var additionBits = (byte)((8 - count % 8) % 8); // количесто доп бит (ибо может получиться н байт с хвостиком, хвостик нужно будет добить нулями до байта) var bitCount = (count + 7) / 8; // количество байт в закодрованном файле var bitarr = new BitArray(count + additionBits, false); var add = 0; foreach (var t in codes) { for (var j = 0; j < t.Count; j++) { bitarr[add + j] = t[t.Count - 1 - j]; } add += t.Count;//собираем из массива поток } var bytes = new byte[bitCount]; bitarr.CopyTo(bytes, 0); using (var sw = new FileStream(newFileName, FileMode.Create)) using (var bw = new BinaryWriter(sw)) { foreach (var b in _byteMap) { bw.Write(b);// сначала пишем в фаил карту баит } bw.Write(additionBits); // количество доп бит foreach (var b in bytes)//для каждого символа кодовой карты Хаффмана { bw.Write(b); // пишем сам код } } } } /// /// Заполняет таблицу частот /// /// strFileName">Имя файла private void FillByteMap(string strFileName) { using (var fs = new FileStream(strFileName, FileMode.Open)) { for (int i = 0; i < fs.Length; i++) { Byte myByte = (Byte)fs.ReadByte(); _byteMap[myByte]++; } } } } } Файл Program.cs using System; using System.Collections.Generic; using System.Linq; using System.Threading.Tasks; using System.Windows.Forms; namespace HuffOptima { static class Program { /// /// Главная точка входа для приложения. /// [STAThread] static void Main() { Application.EnableVisualStyles(); Application.SetCompatibleTextRenderingDefault(false); Application.Run(new Form1()); } } } | ||||||||||||||||||||||||||||||||||||||||||||||||||||||