Файл: Оглавление Цель работы 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));

}

}

}

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

---