Энтропийное сжатие.
Энтропийное сжатие в отличие от последовательного, в качестве информации о входном массиве использует только частоты встречаемости в нем отдельных байтов. Эту информацию он использует как при кодировании, так и при декодировании массива. Ее представляют в виде 256 компонентного вектора, координата i
которого представляет собой сколько раз байт со значением i встречается в исходном массиве. Данный вектор занимает небольшое пространство и почти не влияет на степень компрессии. Многие методы энтропийного кодирования видоизменяют данный вектор в соответствии с используемым алгоритмом. Рассмотрим два наиболее часто используемых методов:
Метод Хаффмана. Данный метод сокращает избыточность массива, создавая при кодировании переменную битовую длину его элементов. Основной принцип таков: наиболее часто встречающемуся байту - наименьшую длину, самому редкому - наибольшую. Рассмотрим простейший пример кодирования методом Хаффмана - способ конечного нуля. Любой элемент кодируется цепочкой битов, состоящей из одних единиц и кончающийся нулем. Таким образом, самый частый закодируем одним битом - 0, следующий за ним по частоте как 10, далее - 110, 1110, 11110 и т.д. Процедура декодирования также очевидна.
Рассмотрим вышесказанное на примере. Пусть дана часть изображения длиной 80 бит - десять цветов и каждый из них закодирован одним байтом (индексированное 256 цветами изображение): КЗСГКСКБСК (где К - красный, З - зеленый и т.д.). Закодируем его. Построим таблицу частоты встречаемости цвета и кода ему соответствующего:
| Цвет | Частота | Код | |||
| К | 4 | 0 | |||
| З | 1 | 110 | |||
| С | 3 | 10 | |||
| Г | 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.1896 |
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 |
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.5 |
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 |
алгоритма? Рассмотрим последовательность КККККККС. При кодировании методом Хаффмана получим выходную последовательность длиной в 9 бит (можно и в 8, так как массив состоит из 2 разных байт). При арифметическом кодировании данную последовательность можно закодировать числом 0.4375 или в двоичном виде как 0111, занимающей 4 бита. То есть при арифметическом кодировании возможно получать плотность кодирования меньше бита на символ. Это свойство проявляется, когда во входном массиве частоты некоторых символов значительно выше остальных.
