Энтропийное сжатие.
Энтропийное сжатие в отличие от последовательного, в качестве информации о входном массиве использует только частоты встречаемости в нем отдельных байтов. Эту информацию он использует как при кодировании, так и при декодировании массива. Ее представляют в виде 256 компонентного вектора, координата i которого представляет собой сколько раз байт со значением i встречается в исходном массиве. Данный вектор занимает небольшое пространство и почти не влияет на степень компрессии. Многие методы энтропийного кодирования видоизменяют данный вектор в соответствии с используемым алгоритмом. Рассмотрим два наиболее часто используемых методов:
Метод Хаффмана. Данный метод сокращает избыточность массива, создавая при кодировании переменную битовую длину его элементов. Основной принцип таков: наиболее часто встречающемуся байту - наименьшую длину, самому редкому - наибольшую. Рассмотрим простейший пример кодирования методом Хаффмана - способ конечного нуля. Любой элемент кодируется цепочкой битов, состоящей из одних единиц и кончающийся нулем. Таким образом, самый частый закодируем одним битом - 0, следующий за ним по частоте как 10, далее - 110, 1110, 11110 и т.д. Процедура декодирования также очевидна.
Рассмотрим вышесказанное на примере. Пусть дана часть изображения длиной 80 бит - десять цветов и каждый из них закодирован одним байтом (индексированное 256 цветами изображение): КЗСГКСКБСК (где К - красный, З - зеленый и т.д.). Закодируем его. Построим таблицу частоты встречаемости цвета и кода ему соответствующего:
|
Цвет |
Частота |
Код |
|
К |
4 |
0 |
|
З |
1 |
110 |
|
С |
3 |
|
|
Г |
1 |
1110 |
|
Б |
1 |
11110 |
Таким образом, мы закодировали исходный массив как 0 110 10 1110 0 10 0 11110 10 0. Итого: длина выходного сообщения - 22 бита. Степень компрессии ~4.
Метод арифметического кодирования. Данный метод появился позднее. Его принцип - кодирование исходного массива одним числом. Часто входной массив разбивают на одинаковые небольшие участки и кодируют их по отдельности, получая в результате последовательность кодовых чисел. Закодируем предыдущий пример числом, лежащим в единичном диапазоне. Схема кодировки следующая. Строим таблицу частот, каждому элементу таблицы ставим в соответствие диапазон, равный его частоте поделенной на длину входного массива. Устанавливаем верхнюю границу ВГ в 1, нижнюю НГ в 1. Далее N раз выполняем следующую последовательность действий (где N - длина кодируемого участка или всего массива):
- 1. Читаем из массива очередной символ.
- 2. Установка текущего интервала. Интервал И = ВГ - НГ.
- 3. ВГ = НГ + И*ВГ символа (берем из таблицы).
- 4. НГ = НГ + И*НГ символа (берем из таблицы).
Рассмотрим на примере: КЗСГКСКБСК. Построим необходимую таблицу:
|
Цвет |
Частота |
Нижняя граница НГ |
Верхняя граница ВГ |
|
К |
4 |
0 |
0.4 |
|
З |
1 |
0.4 |
0.5 |
|
С |
3 |
0.5 |
0.8 |
|
Г |
1 |
0.8 |
0.9 |
|
Б |
1 |
0.9 |
1 |
Теперь, собственно, сама процедура кодирования:
|
Шаг |
Символ |
НГ |
ВГ |
Интервал |
|
0 |
0 |
1 |
1 |
|
|
1 |
К |
0 |
0.4 |
0.4 |
|
2 |
З |
0.16 |
0.2 |
0.04 |
|
3 |
С |
0.18 |
0.192 |
0.012 |
|
4 |
Г |
0.1896 |
0.1908 |
0.0012 |
|
5 |
К |
0.19008 |
0.00048 |
|
|
6 |
С |
0.18984 |
0.189984 |
0.000144 |
|
7 |
К |
0.18984 |
0.1898976 |
0.0000576 |
|
8 |
Б |
0.18989184 |
0.1898976 |
0.00000576 |
|
9 |
С |
0.18989472 |
0.189896448 |
0.000001728 |
|
10 |
К |
0.18989472 |
0.1898954112 |
0.0000006912 |
Таким образом, любое число в диапазоне [0.18989472 .. 0.1898954112] однозначно кодирует исходный массив. В двоичном дробном виде как 0.XXXXXXXX...Для хранения такого числа хватит n бит (размерность XXXXXXXX....), где n ближайшее целое, удовлетворяющее неравенству: 2n > Интервал-1=0.0000006912-1. Искомое n равно 21. То есть мы можем закодировать исходный массив 21 битом. В данном примере - 001100001001110111111. Процедура декодирования обратная и состоит в выполнении n раз следующего:
- 1. Ищем в таблице интервал, в который попадает наше число Ч, и выдаем символ в него входящий в декодируемый массив.
- 2. Интервал И = ВГ символа - НГ символа (оба значения - из таблицы).
3. Ч = (Ч - НГ) / И.
|
Шаг |
Число |
Символ |
НГ |
ВГ |
Интервал |
|
1 |
0.18989472 |
К |
0 |
0.4 |
0.4 |
|
2 |
0.4747368 |
З |
0.4 |
0.5 |
0.1 |
|
3 |
0.747368 |
С |
0.5 |
0.8 |
0.3 |
|
4 |
0.82456 |
Г |
0.8 |
0.9 |
0.1 |
|
5 |
0.2456 |
К |
0 |
0.4 |
0.4 |
|
6 |
0.614 |
С |
0.8 |
0.3 |
|
|
7 |
0.38 |
К |
0 |
0.4 |
0.4 |
|
8 |
0.95 |
Б |
0.9 |
1 |
0.1 |
|
9 |
0.5 |
С |
0.5 |
0.8 |
0.3 |
|
10 |
0 |
К |
0 |
0.4 |
0.4 |
В данном примере арифметический кодер «обогнал» метод Хаффмана на 1 бит. В отличие от метода Хаффмана трудоемкость алгоритма значительна. В чем же тогда «полезность» алгоритма? Рассмотрим последовательность КККККККС. При кодировании методом Хаффмана получим выходную последовательность длиной в 9 бит (можно и в 8, так как массив состоит из 2 разных байт). При арифметическом кодировании данную последовательность можно закодировать числом 0.4375 или в двоичном виде как 0111, занимающей 4 бита. То есть при арифметическом кодировании возможно получать плотность кодирования меньше бита на символ. Это свойство проявляется, когда во входном массиве частоты некоторых символов значительно выше остальных.