Основные понятия. Глава 1. Статистические методы

Глава 1. Статистические методы

Для всех статистических методов сжатия характерно присвоение символам определенных кодов переменной длины при кодировании. Такие методы основаны на вероятности появления того или иного символа в потоке данных.

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

Собственно, кодом С для источника S, выдающего символы из алфавита {m₁, m₂,…m_n} с вероятностями {p_1, p₂…p_n} независимо друг от друга, называется множество {c₁,c₂…c_n}, при условии, что символ m_i кодируется двоичной строкой с_i длины l_i, 1<=i<=n. Суть кодирования в том, чтобы имеющийся объект – текст, изображение, звук – уменьшить в объеме за счет представления в бинарном виде.

Существует один важный момент. Полученную двоичную строку принимающая сторона должна расшифровать безошибочно, зная код. Например, если будет передана строка 010100 с кодом {0, 01, 10}, приемник будет испытывать затруднение, так как строку можно расшифровать по-разному: как 0-10-10-0 либо как 01-01-0-0. Соответственно, приемник придет к неверному результату.

Однозначно декодируемым кодом (ОД-кодом) называется код С, содержащий в себе такие кодовые слова, что любую составленную из них строку можно однозначно на них разбить. Наиболее полный критерий однозначной декодируемости сформулировал А.А. Марков в 1960-х гг., предложив решение с помощью графов.

Покажем суть этого критерия на примере. Возьмем код С={01, 010, 011, 11, 101}, каждому из двоичных кодовых слов пусть соответствуют буквы А, Б, В, Г, Д соответственно. Согласно методу Маркова, построим граф следующим образом:

1. Определим все последовательности (строки), которые
а) совпадают с началом какого-то кодового слова и одновременно с концом какого-то кодового слова и
б) сами не являются кодовыми словами.
В данном случае это две последовательности:
0 (начало кода буквы А и конец кода буквы Б) и
1 (начало кода буквы Г и конец кода буквы Д);
10 (начало кода буквы Д и конец кода буквы Б);
(последовательности 01 и 11 не учитываем, потому что они совпадают с кодами букв А и Г);

2. Добавим к этому множеству {0, 1, 10} пустую строку, которую обычно обозначают греческой буквой Λ; элементы полученного множества {Λ, 0, 1, 10} будут вершинами графа;

3. Соединяем вершины дугами (направленными ребрами) по такому правилу: две вершины X и Y соединяются дугой, если последовательная запись кода вершины X, кода некоторой буквы (или нескольких букв) и кода вершины Y дает код ещё одной буквы:

Согласно Маркову, код является однозначно декодируемым тогда и только тогда, когда в построенном таким образом графе нет ориентированных циклов, включающих величину Λ. Как видно, взятый в качестве примера код не является однозначно декодируемым, так как построенный на его основе граф имеет 4 ориентированных цикла: Λ0Λ, Λ1Λ, Λ01Λ, Λ0101Λ.

Из понятия однозначно декодируемого кода вытекает понятие префиксного: код С является префиксным, когда ни одно его кодовое слово не является префиксом другого.

Докажем, что префиксный код всегда однозначно декодируемый.

Предположим противное. Тогда существует слово W, которое можно разбить двумя способами: W_i=W_i1W_i2…W_ik=W_j1W_j2…W_jk. Причем до номера t подслова W_i и W_j совпадают, а W_it и W_jt различны. Отбросив одинаковые префиксы, получаем совпадающие окончания, начинающиеся с различных подслов. Если окончания равны, то должны совпадать первые, вторые и т.д. буквы подслов W_it и W_jt, следовательно, разница у них будет только в длине. А это противоречит префиксности кода.

Таким образом, один из ключевых принципов построения кодов переменной длины заключается в том, что коды должны декодироваться однозначно, дабы не вводить декодер в заблуждение. Второй основополагающий принцип достаточно очевиден и заключается в том, чтобы короткие коды присваивать часто встречающимся символам и длинные – редко встречающимся. С построенными таким образом кодами работать гораздо удобнее. В дополнение к этим принципам необходим алгоритм, который всегда порождает множество коротких кодов. Исходными данными этого алгоритма должны быть вероятности символов алфавита. К счастью, такой алгоритм существует – это алгоритм Хаффмана.