Курсовая на тему «Разработка программы архивации по алгоритму арифметического кодирования»

Сравнение типов представлено в таблице 1. Из таблицы 1 видно, что наибольшее число значащих цифр у типа decimal. Таблица 1Характеристики встроенных типов.

ТипДиапазон.

ТочностьFloat+1.5*10−45… +3.4*10 387 цифрDouble+5.0*10−324…+1.7*1 030 815−16 цифрDecimal+1.0*10−28…+7.9*102 828−29 значащих цифр

В таблице 2 представлены результаты тестирования программы арифметического кодирования. Из таблицы 2 видно, что при использовании формата decimal было закодировано в сообщении длиной 20 байт без ошибок. Таблица 2Результаты тестирования.

Используемый тип.

РезультатВыводfloatРезультат кодирования: 7 значащих цифр

Корректно декодировано: 7 буквdoubleРезультат кодирования: 15 значащих цифр

Корректно декодировано: 11 буквdecimalРезультат кодирования: 28 значащих цифр

Корректно декодировано: 20 букв.

В работе [2] предложен алгоритм, который позволяет исключить влияние ошибок округления. Данный алгоритм выполняет арифметические операции дробями. Ошибки компьютерных вычислений возникают при приближении нижней и правой границы интервалов. В данном алгоритме, если нижняя и правая граница интервала приближаются друг к другу, то числитель и знаменатель дробей умножается на некоторое число. для того чтобы избежать ошибок переполнения в данном алгоритме Старшие биты границ, которые перестают меняться сохраняют и в дальнейшем они не участвуют в вычислениях границ интервалов. Другим способом для борьбы с ошибками округления в этом алгоритме является использование библиотек длинных вычислений, в которых вычисления с плавающей точкой реализованный программа и есть возможность задать любую произвольную длину мантиссы. В языке C# есть BigInteger и BigFloat для поддержки вычислений с числами большой длины.

С помощью данного класса возможно реализовать арифметическое кодирование для сообщений произвольной длины. Программа на основе алгоритм, реализующего арифметическое кодирование на основе описанного выше подхода более эффективна по сравнению с программой на основе BigFloat. Для тестирования корректности сжатие и декодирование данных в программе был разработан класс TestingFloatВ этом классе есть две функции: GenerateString () — Функция генерации строки из случайного количества символов фиксированной длиныTesting () — функция тестирования корректности кодирование и декодирование некоторые строки, функция работает следующим образом: случайная строка сжимается, а затем восстанавливается и проверяется совпадает ли восстановленный результат с исходной строкой, Если нет то выводится сообщение. Проверки производятся для 10 случайных строк.

Заключение

.

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

В ходе проведенных экспериментов была обнаружена и подтверждено что из-за ошибок округления возможны ошибки и сжатие декодирования информации. Только короткие сообщения могли обрабатываться без ошибок. Для решения этой проблемы в работе предложено использовать существующий алгоритм, устойчивый к ошибкам округления, который позволяет сжимать и декодировать сообщение любой длины. В курсовой работе приведено краткое описание этого алгоритма и источника литературы, где он описан подробно. Реализация данного алгоритма в настоящей работе не рассматривается. В работе также описывается в другой подход, связанной с применением вычислений высокой точности с плавающей точкой (класс BigFloat). Список Использованной литературы.

В.И. Шульгтн «Основы теории связи». Часть 1 Теория и практика кодирования — Харьков, 2005 — 194 с.Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин «Методы сжатия данных» — М.: «Диалог МИФИ», 2003. — 384 с. Иринёв Антон, Каширин Виктор «Арифметическое кодирование», электронный источник.

http://rain.ifmo.ru/cat/data/theory/data-compression/arithmetic-coding-2006/article.pdfМ.Н. Аршинов, Л. Е. Садовский «Коды и математика» — М.: Наука, Главная редакция физико-математической литературы, 1983 — 144 сД. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин и др. «Идея арифметического кодирования», 2001;2003,электронный источник.

http://www.compression.ru/arctest/descript/arithm.htmЛидовский В. В. Теория информации: Учебное пособие. -.

М.: Компания Спутник+, 2004.Б. Д. Кудряшов Теория информации. С.—Пб.: Питер, 2009 — с. 36. ПРИЛОЖЕНИЯПРИЛОЖЕНИЕ 1ФайлArithFloatusingSystem;using System.Collections.Generic;using System. Linq;using System. Text;namespace ArithCode_double{ public class Arithdouble { public string message; public List<string> alfaList = new List<string>(); // алфавит public List<int> kolList = new List<int>(); // количество повтрений public List<double> probList = new List<double>(); // вероятности public List<Interval> intervList = new List<Interval>(); // интервалы public string message_out; public void FillAlfavit () { double Low = 0; double High = 0; for (int j = 0; j < message. Length; j++) { if (!alfaList.Contains (message[j]. T oString ())) { alfaList. Add (message[j]. T oString ()); // добавили первый символ// ищем его количество повторенийintcount = 0;for (int i = 0; i < message. Length; i++) { if (message[j].

T oString () == message[i]. T oString ()) count++; }kolList.Add (count); // добавляем соотвествующую количество probList. Add ((double)count / (double)message.Length); High = High + (double)count / (double)message.Length; Interval interval = new Interval (); interval. Low = Low; interval. High = High; intervList. Add (interval); Low = High; } } } public void outputAlfavit () { foreach (string pr in alfaList) { Console. Write (pr); Console. Write (««); } Console. WriteLine (); foreach (int pr in kolList) { Console. Write (pr); Console. Write (««); } Console. WriteLine (); foreach (double pr in probList) { Console. Write (pr); Console. Write (««); } Console. WriteLine (); foreach (Interval pr in intervList) { pr. Output (); Console. Write (««); } } public string decode (Interval msg) { string rez = «»; double Code = 0; // ищем первый символ int index = 0; foreach (Interval pr in intervList) { if (pr.IsInterv_first_in_second (pr, msg)) break; ++index; } rez = rez + alfaList[index]; Code = msg. Low; do { Code = Math. Abs ((Code — intervList[index]. L ow)) / (intervList[index]. H igh — intervList[index].

L ow); Console. WriteLine (Code); index = 0; foreach (Interval pr in intervList) { if (pr.Double_in_Interval (pr, Code)) break; ++index; } rez = rez + alfaList[index]; if ((Code < 0.01f) — (Code > 0.999 9999f)) break; } while (Code ≠ 0); return rez; } public Interval code () { // рабочий интервал double OldLow = 0; double OldHigh = 1; double NewHigh = 0; double NewLow = 0; Interval rabInterval = new Interval (); Console. WriteLine (); // обрабатываем сиволы for (int i = 0; i < message. Length; i++){ // узнаем индекс символ который поступил в обработку int index = alfaList. FindIndex (s => s. Contains (message[i]. T oString ())); Console. WriteLine (alfaList[index]); intervList[index]. O utput (); NewHigh = OldLow + (OldHigh — OldLow) * intervList[index]. H.

igh; NewLow = OldLow + (OldHigh — OldLow) * intervList[index]. Low; Console. WriteLine («Work interval: „); rabInterval. Low = NewLow; rabInterval. High = NewHigh; rabInterval. Output (); OldLow = NewLow; OldHigh = NewHigh; } return rabInterval; } }}ФайлInterval.csusing System;using System.Collections.Generic;using System. Linq;using System. Text;namespace ArithCode_double{ public class Interval { public double Low; public double High; public void Output () { Console. Write („[“ + Low. ToString () + “ ,» + High. ToString () + «]»); Console. WriteLine (); } public bool IsInterv_first_in_second (Interval i1, Interval i2) { if ((i1.Low<=i2.Low) && (i1.High>=i2.High)) return true; else return false; } public bool Double_in_Interval (Interval i1, double Code) { if ((i1.Low <= Code) && (i1.High >= Code)) return true; else return false; } }}Файл Program. csusing System;using System.Collections.Generic;using System. Linq;using System. Text;namespace ArithCode_double{ class Program { static void Main (string[] args) { Arithdouble ar = new Arithdouble (); ar. message = «RADAOVIZIR»; ar. FillAlfavit (); ar. outputAlfavit (); Console. WriteLine (ar.decode (ar.code ())); Console. ReadLine (); } }}ФайлTestFloatusing System;using System.Collections.Generic;using System. Linq;using System. Text;namespace ArithCode_double{ public class TestingFloat { public string GenerateString () { var chars = «ABCDEFGH»; var stringChars = new char[4]; var random = new Random (); for (int i = 0; i < stringChars. Length; i++) { stringChars[i] = chars[random.Next (chars.Length)]; } return new String (stringChars); } public void Testing () { TestingFloat test1 = new TestingFloat (); string msg = «»; Interval interv_out = new Interval (); Arithdouble ar = new Arithdouble (); for (int i = 0; i < 10; i++) { msg = test1. GenerateString (); interv_out = ar. code (); if (ar.decode (interv_out)≠msg) Console. WriteLine (msg); } } }}.