Кодирование Хаффмана

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

При передаче информации по незашумленному каналу приоритетной задачей является минимизация размера представления информации: это проблема сжатия данных. Код Хаффмана (1952) является оптимальным кодом переменной длины, то есть таким, что средняя длина закодированного текста минимальна. Таким образом, наблюдается уменьшение размера порядка 20 до 90%.

Двоичный код, связанный с каждой буквой, определяется бинарное дерево. Листья дерева соответствуют буквам алфавита. Внутренние узлы не содержат информации. Путь, пройденный для достижения листа от корня, определяет код буквы на этом листе: слева 0, справа 1. Например:

кодирование Хаффмана кодирование дерева Хаффмана декодирование

Дерево Хаффмана

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

кодирование Хаффмана кодирование дерева Хаффмана декодирование

Исходя из этих частот, алгоритм инициализирует дерево для каждого символа с количеством появлений символа в качестве веса:

кодирование Хаффмана кодирование дерева Хаффмана декодирование

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

кодирование Хаффмана кодирование дерева Хаффмана декодирование

и после еще четырех итераций:

кодирование Хаффмана кодирование дерева Хаффмана декодирование

Когда останется только одно дерево, алгоритм завершится.

Вот пример построения дерева Хаффмана, чтобы лучше понять процесс. В этом примере мы разместили буквы в порядке возрастания, в отличие от предыдущего примера:

кодирование Хаффмана кодирование дерева Хаффмана декодирование

Алгоритм Хаффмана

Более формально алгоритм Хаффмана выглядит следующим образом:

кодирование Хаффмана кодирование дерева Хаффмана декодирование алгоритм Хаффмана

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

Мы можем переписать дерево в виде массива. Кодирование буквы связано с пройденным в дереве путем до нужной буквы. Возьмите следующую таблицу:

Кодирование по Хаффману Кодирование по Хаффману

Этот тип кода называется префиксным, что означает, что ни один код не является префиксом другого (код A равен 10, и никакие другие коды не начинаются с 10, код B равен 001, и никакой другой код не начинается с 001). ). Это свойство позволяет однозначно разделять символы.

Внимание, здесь все наводит на мысль, что предложенная таблица не оптимальна. Действительно, есть 8 символов, поэтому, используя двоичный код, мы могли бы использовать 3 бита для кодирования всех символов (2^3 = 8 вариантов). 

Здесь сумма битов закодированных букв составляет 2+3+3+4+2+4+4+4 = 26 бит или в среднем 26/8 = 3,25 бит на символ. Но на самом деле учитываться будет не среднее значение, а средневзвешенное по частоте, как мы увидим в примере упражнения.

Используя массив, можно закодировать сообщение (здесь + — это конкатенация):

КЭШ=000+10+000+1111+01=00010000111101.

Таким образом, мы имеем 14-битное сообщение вместо 5*3=15 бит, что соответствует сокращению памяти для хранения текста (15-14)/15 = 6,6%. Хотя в среднем кодировка больше, на самом деле мы имеем уменьшение используемого пространства памяти!

Пример

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

а) Сколько бит необходимо для кодирования каждой из 8 букв алфавита.

б) Какова длина в байтах 1000-символьного сообщения, построенного на этом алфавите?

2) Предоставьте код фиксированного размера для каждого символа 8-буквенного алфавита.

3) Рассмотрим теперь следующее кодирование, причем длина кода каждого символа является переменной.

Кодирование по Хаффману Кодирование по Хаффману

а) Используя предыдущую таблицу, введите код сообщения: КЭШ.

б) Какое сообщение соответствует коду 001101100111001.

4) В тексте каждый из 8 символов встречается разное количество раз. Это обобщено в следующей таблице, составленной из текста длиной 1000 символов.

кодирование Хаффмана кодирование дерева Хаффмана декодирование

a) Используя код фиксированного размера, предложенный в вопросе 2., какова длина в битах сообщения, содержащего 1000 символов, перечисленных в предыдущей таблице?

б) Используя код из вопроса 3., какова длина того же сообщения в битах.

5) Реализуйте дерево Хаффмана, оптимизирующее пространство памяти. Повторите вопросы 3 и 4 с новым деревом.

Исправление примера

1a — Для кодирования 8 букв необходимо 3 бита, потому что 23 = 8.

1b – 1000 символов соответствуют 1000*3 = 3000 бит. Мы делим на 8, чтобы получить количество байтов = 375.

2 - Поскольку с 3 битами есть 8 возможностей, мы назначим каждую возможность символу, например:

кодирование Хаффмана кодирование дерева Хаффмана декодирование

3a – Мы видели это в тексте CACHE, он закодирован как 00010000111101.

3b — Читаем биты слева направо, как только чтение дает букву пишем ее и начинаем снова искать в таблице соответствующий символ.

0 ничего не дает, 00 ничего не дает, 001 дает B. 1 ничего не дает, 10 дает A и так далее. Последнее слово ЗНАЧОК.

4a — Длина будет 1000*3 = 3000 бит. 

4b – Чтобы узнать длину с таблицей кодирования, мы умножим для каждого символа его частоту на его длину кодирования: 240*2 + 140*3 + 160*3 + 51*4 + 280*2 + 49*4 + 45* 4 + 35*4. То есть 2660 бит с уменьшением (3000-2660)/3000 = 11% (что на самом деле не страшно…).

5 – После выполнения метода Хаффмана вы получите следующее дерево:

кодирование Хаффмана кодирование дерева Хаффмана декодирование

В конце концов, это была та таблица, которая уже была предоставлена ранее, так что она уже была оптимальной!

Делиться
ru_RURU
%d такие блоггеры, как: