Обзор алгоритмов сжатия без потерь

Унарное кодирование

Один из очевидных способов сжатия информации, в особенности текстовой, основывается на том, что вероятность использования в тексте разных символов сильно различна. В частности, в русском языке чаще всего используются буквы “о”, “а”, редко – “ъ”, ”щ” и т.д. Поэтому, предлагается использовать для частых символов более короткий код, для редких – более длинный. Трудность заключается в том, что коды получаются переменной длины и в общем потоке выходных данных трудно обнаружить конец одного кода и начало другого.

Однако, существуют коды, для которых задача определения длины легко решается (так называемые неравномерные коды со свойством однозначного декодирования). Например, унарный код (в двоичной системе), где:

“о”-1
“а”-01
“и”-001
 ...
“щ”-00....1

т.е. для самой частой буквы длина кода составляет 1 бит, для самой редкой - 33 бита (32 нуля и единица). Этот код очень прост, но далеко не эффективен. Однако, он может пригодиться для построения кодов целых переменной длины (Variable Length Integers (VLI) codes). VLI-коды состоят из двух частей: сначала следует унарный код, определяющий группу чисел определенной длины, а затем само число указанной длины. Таким образом, унарный код выполняет роль префикса, указывающего какой длины будет следующее число. Для записи VLI-кодов используют три числа: (start, step, stop), где start определяет начальную длину числа, step – приращение длины для следующей группы, stop – конечную длину.

Например, код (3,2,9) задает четыре группы чисел:
0ххх – числа от 0 до 7, группа 0,
10ххххх – числа от 8 до 39, группа 1,
110ххххххх – числа от 40 до 167, группа 2,
111ххххххххх – числа от 168 до 679, группа 3.

Унарный код для n-ой группы – n единиц, затем ноль; для последней группы – только n единиц, так как это не вносит неопределенности. Размер числа из n-ой группы равен start+n*step. VLI-коды удобно применять для кодирования монотонных источников, для которых вероятность появления меньших чисел выше, чем больших. При отсутствии кодирования любое число представлялось бы десятью битами.