Файл: Методы кодирования данных (Общая информации о сжатии данных).pdf

Большая часть работы по оптимизации модели PPM - это обработка входных данных, которые еще не встречались во входном потоке. Очевидным способом их обработки является создание «невидимого» символа, который запускает escape-последовательность. Но какую вероятность следует присвоить символу, который никогда не видел? Это называется проблемой с нулевой частотой. Один вариант присваивает «неизведанному» символу фиксированное количество псевдо-хитов. Вариант, называемый PPM-D, увеличивает каждый раз, когда используется символ «невидимый», псевдо-хит «невидимого» символа. (Другими словами, PPM-D оценивает вероятность появления нового символа как отношения числа уникальных символов к общему количеству наблюдаемых символов).

Реализации сжатия PPM сильно различаются в других деталях. Фактический выбор символа обычно записывается с использованием арифметического кодирования, хотя также возможно использовать кодировку Хаффмана или даже какой-либо метод кодирования словаря. Базовая модель, используемая в большинстве алгоритмов PPM, также может быть расширена для прогнозирования нескольких символов. Также возможно использовать немарковское моделирование для замены или дополнения марковского моделирования. Размер символа обычно статичен, как правило, один байт, что упрощает общую обработку любого формата файла.

Опубликованные исследования этого семейства алгоритмов можно найти еще в середине 1980-х годов. Реализация программного обеспечения не пользовалась популярностью до начала 1990-х годов, потому что алгоритмы PPM требуют значительного объема оперативной памяти. Последние реализации PPM являются одними из наиболее эффективных программ сжатия без потерь для текста естественного языка.

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

Согласно исходной кодовой теореме Шеннона, оптимальная длина кода для символа -logbP, где b - количество символов, используемых для создания выходных кодов, а P - вероятность ввода символа.

Двумя из наиболее распространенных методов энтропийного кодирования являются кодирование Хаффмана и арифметическое кодирование. Если приблизительные энтропийные характеристики потока данных известны заранее (особенно для сжатия сигнала), может оказаться полезным более простой статический код, такой как унарное кодирование, гамма-кодирование Elias, кодирование Фибоначчи, кодирование Голомба или кодирование Rice.

---

В информатике и теории информации кодирование Хаффмана является алгоритмом энтропийного кодирования, используемым для сжатия без потерь данных. Термин относится к использованию таблицы кодов переменной длины для кодирования исходного символа (например, символа в файле), где таблица кодов переменной длины была получена определенным образом на основе предполагаемой вероятности появления для каждого возможного значение символа источника. Он был разработан Дэвидом А. Хаффманом и опубликован в статье 1952 года «Метод построения кодов минимальной избыточности»^[5].

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

Для набора символов с равномерным распределением вероятности и количеством членов, который является степенью двух, кодирование Хаффмана эквивалентно простому двоичному блочному кодированию, например кодированию ASCII. Кодирование Хаффмана - такой распространенный метод создания префикс-свободных кодов, что термин «код Хаффмана» широко используется как синоним «кода без префикса», даже если такой код не создается алгоритмом Хаффмана.

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

---

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

Арифметическое кодирование - это метод сжатия данных без потерь. Это форма энтропийного кодирования, но в тех случаях, когда другие методы кодирования энтропии разделяют входное сообщение на его компонентные символы и заменяют каждый символ кодовым словом, арифметическое кодирование кодирует все сообщение в единственное число, причем доля n где (0.0 = n <1,0).

Глава 2. Практическая реализация кодирования информации

. Выбор среды разработки

PascalABC.NET - это интегрированная среда разработки на языке программирования Pascal, которая реализует классические функции языка Pascal, большинство языков Delphi, а также ряд собственных расширений. Он реализован на платформе .NET Framework и содержит все современные языковые функции: классы, перегрузку операторов, интерфейсы, обработку исключений, общие классы и подпрограммы, сбор мусора, лямбда-выражения, средства параллельного программирования (OpenMP только с 2016 года).

PascalABC.NET - это также простая и мощная среда разработки с интегрированным отладчиком, системой IntelliSense, дизайнером форм, шаблонами кода и автоматическим форматированием кода. Компилятор командной строки PascalABC.NET также доступен в Linux и MacOS (под Mono).

PascalABC.NET популярен в российских школах и университетах. В Южном федеральном университете он используется в качестве основного языка для обучения студентов информационным технологиям в курсе «Основы программирования» и для обучения детей в одной из крупнейших компьютерных школ России.

Справочник по программированию, разработанный профессором М. Э. Абрамяном, входит в состав PascalABC.NET. Эта книга содержит 1100 учебных заданий и охватывает почти все разделы базовой учебной программы.

Структура программы

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

---

type Node = record

Letter: char;

Pi: double;

Code: string;

constructor Create(Letter: char; Pi: double; Code: string);

begin

Self.Letter := Letter;

Self.Pi := Pi;

Self.Code := Code;

end;

end;

Как можно видеть, запись содержит в себе следующие поля:

• символ;
• вероятность;
• код.

Также у структуры есть конструктор, который позволяет инициализировать поля записи.

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

Собственно, в таковом классе необходимо реализовать следующее:

• список узлов;
• список слов;
• чтение файла;
• построение кода;
• нахождение медианы;
• печать построенного кода.

Алгоритм построения частотных вероятностей

Данный алгоритм может быть представлен в следующем виде:

1. Загрузить входной файл в оперативную память;
2. Читать все слова из входного файла;
3. Для каждого слова:
4. Для каждого символа в слове произвести поиск в списке узлов:
   1. Если в списке узлов присутствует данный символ – увеличить количество его на единицу;
   2. Иначе – добавить символ в список узлов с количеством равным единице.
5. Для каждого узла в списке узлов разделить вероятность на количество считанных символов из файла, получив таким образом вероятность каждого символа.

Алгоритм сжатия Метода-Фано

Данный алгоритм может быть представлен в следующем виде:

1. Если поданный входной список узлов содержит количество элементов меньше либо равного единице – досрочно прекратить процедуру;
2. Найти медиану для поданного на вход списка узлов;
3. Для каждого узла в входном списке узлов:
   1. если индекс итерации меньше медианы – добавить узел в левую ветку, иначе в правую.
4. Если левая или правая ветка пусты – досрочно прекратить процедуру;
5. Для каждого узла в входном списке узлов:
   1. если итерируемый узел есть в левой ветке – добавить к коду узла ‘0';
   2. если итерируемый узел есть в правой ветке – добавить к коду узла ‘1'.
6. Вызвать процедуру кодирования для левой и правой веток рекурсивно.

Процедура кодирования Шеннона-Фано доступна в процедуре code.

Построение вероятностей происходит во время чтения файла в процедуре readFile.

Полный код доступен далее:

type Node = record

Letter: char;

Pi: double;

Code: string;

constructor Create(Letter: char; Pi: double; Code: string);

---

begin

Self.Letter := Letter;

Self.Pi := Pi;

Self.Code := Code;

end;

end;

type SF = class

private

_nodes: List<Node>;

_words: List<string>;

procedure sortNodes;

begin

for var i:= 0 to _nodes.Count - 2 do

begin

for var j:= 0 to _nodes.Count - i - 2 do

begin

if (_nodes[j].Pi < _nodes[j + 1].Pi) then

begin

var temp := _nodes[j];

_nodes[j] := _nodes[j + 1];

_nodes[j + 1] := temp;

end;

end;

end;

end;

function contains(c: char; nodes: List<Node>): boolean;

begin

for var i:= 0 to nodes.Count - 1 do

begin

if (nodes[i].Letter = c) then

begin

Result := true;

exit;

end;

end;

Result := false;

end;

function getIndex(c: char): integer;

begin

for var i:= 0 to _nodes.Count do

begin

if (_nodes[i].Letter = c) then

begin

Result := i;

exit;

end;

end;

Result := -1;

end;

procedure readFile(filename: string);

var input: text;

fileword: string;

allSize: integer;

begin

Assign(input, filename);

Reset(input);

while not eof (input) do

begin

read (input, fileword);

_words.Add(fileword);

allSize := allSize + fileword.Length;

for var i := 1 to fileword.Length do

begin

if (contains(fileword[i], _nodes) = false) then

begin

var newNode: Node := (Letter: fileword[i]; Pi: 1; Code: '');

_nodes.Add(newNode);

end

else

begin

var newNode: Node := (Letter: _nodes[getIndex(fileword[i])].Letter; Pi: _nodes[getIndex(fileword[i])].Pi + 1; Code: '');

_nodes[getIndex(fileword[i])] := newNode;

end;

end;

end;

close(input);

for var i:= 0 to _nodes.Count - 1 do

begin

var newNode: Node := (Letter: _nodes[i].Letter; Pi: _nodes[i].Pi / allSize; Code: '');

_nodes[i] := newNode;

end;

sortNodes;

end;

function getMedian(nodes: List<Node>): integer;

var accumulate, sum: double;

begin

sum := 0;

for var i:= 0 to nodes.Count - 1 do sum := sum + _nodes[i].Pi;

accumulate := 0;

for var i:= 0 to nodes.Count - 1 do

begin

accumulate := accumulate + _nodes[i].Pi;

if (accumulate > (sum / 2)) then begin Result := i; exit; end;

end;

Result := 0;

end;

procedure code(nodes: List<Node>; debug: boolean);

begin

if (nodes.Count <= 1) then exit;

var m := getMedian(nodes);

---