§10. Сжатие на основе статистических свойств данных и неравномерные коды

Методы такого сжатия изучаются в специальном разделе теории информации (подразделе теоретической информатики), который называется теорией экономного или эффективного кодирования. Экономное кодирование основано на использовании систем кодирования с переменной длиной кодового слова.

В системах равномерного кодирования, как нам уже известно, каждому символу алфавита A={a_i}, i=1,…,n, ставится в соответствие кодовое слово с фиксированным числом разрядов. Например, в случае рассмотренного нами посимвольного двоичного кодирования каждому знаку алфавита A соответствует илибит (двоичных разрядов). Однако давно известны и системы кодирования, в которых длина кодового слова непостоянна, например, код Морзе.

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

Пусть, например, A={0,1, … ,9}. Закодируем символы данного алфавита наборами двоичных знаков следующим образом:

0 – 00 5 – 110

1 ­– 01 6 – 1110

2 – 1000 7 – 11110

3 – 1001 8 – 111110

4 – 101 9 – 111111

Нетрудно видеть, что перед нами – префиксный код. Теперь появляется возможность однозначного декодирования любого сообщения. Например, последовательность 1110110111110100000000110011111110101 допускает лишь одно разбиение на кодовые слова 1110 110 111110 1000 00 00 01 1001 111111 01 01 и соответствует сообщению 65820013911.

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

§11. Двоичное кодирование и бинарные деревья

Двоичное кодирование удобно представлять в виде бинарного кодового дерева. Если условиться сопоставлять любой левой ветви бинарного дерева нуль, а любой правой – единицу, то каждой вершине дерева будет однозначно соответствовать некоторый набор двоичных знаков, показывающий, в какой последовательности нужно сворачивать налево и направо, добираясь до этой вершины из корня дерева. Любой из таких наборов может быть выбран в качестве кодового слова. Например, рассмотренному выше коду соответствует дерево, приведенное на рис. 1.4.

Рис.1.4

Пример кодового дерева примитивного префиксного кода

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

Процесс двоичного кодирования можно интерпретировать следующим образом. На каждом шаге движения по кодовому дереву, начиная от корня, происходит выбор одного из двух поддеревьев: правого и левого. Это соответствует разбиению множества знаков алфавита на два подмножества – правое и левое – с присвоением им очередных двоичных знаков (единицы и нуля). Так, в рассмотренном примере множество {0,…,9} было разбито на два подмножества {0,1} и {2,3,…,9}. При дальнейшем движении вправо множество {2,3,…,9} в свою очередь было разбито на два подмножества {2,3,4} и {5,6,…,9}, а при движении влево множество {0,1} было разбито на два подмножества {0} и {1} и т.д. до тех пор, пока во всех подмножествах не осталось по одному элементу.

Таким образом, двоичные коды, соответствующие вершинам кодового дерева, характеризуют «историю» последовательного разбиения исходного множества знаков на правые и левые подмножества.