Глава 1. Статистические методы
Для всех статистических методов сжатия характерно присвоение символам определенных кодов переменной длины при кодировании. Такие методы основаны на вероятности появления того или иного символа в потоке данных.
Прежде чем говорить о методах кодирования, разберем правила построения кодов переменной длины и введем некоторые основополагающие термины.
Собственно, кодом С для источника S, выдающего символы из алфавита {m1, m2,…mn} с вероятностями {p1, p2…pn} независимо друг от друга, называется множество {c1,c2…cn}, при условии, что символ mi кодируется двоичной строкой сi длины li, 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, которое можно разбить двумя способами: Wi=Wi1Wi2…Wik=Wj1Wj2…Wjk. Причем до номера t подслова Wi и Wj совпадают, а Wit и Wjt различны. Отбросив одинаковые префиксы, получаем совпадающие окончания, начинающиеся с различных подслов. Если окончания равны, то должны совпадать первые, вторые и т.д. буквы подслов Wit и Wjt, следовательно, разница у них будет только в длине. А это противоречит префиксности кода.
Таким образом, один из ключевых принципов построения кодов переменной длины заключается в том, что коды должны декодироваться однозначно, дабы не вводить декодер в заблуждение. Второй основополагающий принцип достаточно очевиден и заключается в том, чтобы короткие коды присваивать часто встречающимся символам и длинные – редко встречающимся. С построенными таким образом кодами работать гораздо удобнее. В дополнение к этим принципам необходим алгоритм, который всегда порождает множество коротких кодов. Исходными данными этого алгоритма должны быть вероятности символов алфавита. К счастью, такой алгоритм существует – это алгоритм Хаффмана.