Файл: Оглавление Цель работы 1 Формулировка задачи 2 Теоретическое обоснование 2 Программная реализация 2 Скриншот выполнения программы 4 Цель работы.doc

Оглавление

Цель работыИзучение арифметического кодирования.

Формулировка задачи

Программная реализация сжатия текстовых данных без потери информации с использованием арифметического кодирования.

Теоретическое обоснование

Арифметическое кодирование (англ. Arithmetic coding) — алгоритм сжатия информации без потерь, который при кодировании ставит в соответствие тексту вещественное число из отрезка [0;1)[0;1). Данный метод, каки алгоритм Хаффмана, является энтропийным, то есть длина кода конкретного символа зависит от частоты встречаемости этого символа в тексте. Арифметическое кодирование показывает более высокие результаты сжатия, чем алгоритм Хаффмана, для данных с неравномерными распределениями вероятностей кодируемых символов.Принцип действия. Пусть имеется некий алфавит, а также данные о частотности использования символов (опционально). Тогда рассмотрим на координатной прямой отрезок от 0 до 1. Назовём этот отрезок рабочим.Расположим на нём точки таким образом, что длины образованных отрезков будут равны частоте использования символа, и каждый такой отрезок будет соответствовать одному символу. Теперь возьмём символ из потока и найдём для него отрезок среди только что сформированных, теперь отрезок для этого символа стал рабочим. Разобьём его таким же образом, как разбили отрезок от 0 до 1. Выполним эту операцию для некоторого числа последовательных символов. Затем выберем любое число из рабочего отрезка. Биты этого числа вместе с длиной его битовой записи и есть результат арифметического кодирования использованных символов потока.Программная реализацияusing System;using System.Collections.Generic;

---

using System.Linq;using System.Threading.Tasks;namespace toi1{class Program{public struct Segment{public double left;public double right;public char character;};public static Segment[] DefineSegments(char[] letters, double[] probability){Segment[] segments = new Segment[letters.Length];double l = 0;for (int i = 0; i < letters.Length; i++){segments[i].left = l;segments[i].right = l + probability[i];l = segments[i].right;segments[i].character = letters[i];}return segments;}public static double artimeticCoding(char[] letters, double[] probability, string word){Segment[] segments = DefineSegments(letters, probability);double left = 0;double right = 1;for (int i = 0; i < word.Length; i++){char symb = word[i];for (int j = 0; j < segments.Length; j++){if (segments[j].character == symb){double newRight = left + (right - left) * segments[j].right;double newLeft = left + (right - left) * segments[j].left;left = newLeft;right = newRight;break;}}}return (left + right) / 2;}public static string arithmeticDecoding(char[] letters, double[] probability, double code, int n){Segment[] segments = DefineSegments(letters, probability);string s = "";for (int i = 0; i < n; i++){for (int j = 0; j < letters.Length; j++){if (code >= segments[j].left && code < segments[j].right){s += segments[j].character;code = (code - segments[j].left) / (segments[j].right - segments[j].left);break;}}}return s;}static void Main(string[] args){char[] letters;double[] probability;Console.Write("Enter a message: ");string word = Console.ReadLine();Dictionary character = word.GroupBy(x => x).OrderByDescending(x => x.Count()).ToDictionary(x => x.Key, x => x.Count());

letters = new char[character.Count];

probability = new double[character.Count];

int i = 0;
foreach (KeyValuePair keyValuePair in character)

{

letters[i] = keyValuePair.Key;

probability[i] = (double)keyValuePair.Value / (double)word.Length;

i++;

}

double code = artimeticCoding(letters, probability, word);

Console.WriteLine("\nEncoded message: \n" + code + "\n");

Console.WriteLine("Decoded message: \n" + arithmeticDecoding(letters, probability, code, word.Length));

}

}

}

Скриншот выполнения программы

---