Кодирование Хаффмана для сжатия без потерь

Question

Мне действительно нужна помощь с кодированием Хаффмана для сжатия без потерь. Я готовлюсь к экзамену, и мне нужно это понять, знает ли кто-нибудь простые уроки, чтобы понять это, или кто-то может объяснить.

Вопросы на экзамене, вероятно, будут:

Предположим, что алфавит [A, B, C], а известное распределение вероятностей P(A)=0,6, P(B)=0,2 и P(C)=0,2. Для простоты давайте также предположим, что и кодер, и декодер знают, что длина сообщений всегда равна 3, поэтому нет необходимости в терминаторе.

1. Сколько битов необходимо для кодирования сообщения ACB с помощью кодирования Хаффмана? Вам нужно предоставить дерево Хаффмана и код Хаффмана для каждого символа. (3 оценки)

2. Сколько бит необходимо для кодирования сообщения ACB с помощью арифметического кодирования? Вам необходимо предоставить подробную информацию о процессе кодирования. (3 оценки)

3. Используя приведенные выше результаты, обсудите преимущество арифметического кодирования над кодированием Хаффмана. (1 оценка)

ответы:

1. Код Хаффмана: A - 1, B - 01, C - 00. Результат кодирования - 10001, поэтому необходимо 5 бит. (3 оценки)

2. Процесс кодирования арифметического кодирования: Высокий диапазон символа Низкий 0,0 1,0 1,0 А 0,0 0,6 0,6 С 0,48 0,6 0,12 В 0,552 0,576 0,024 Конечное двоичное кодовое слово равно 0,1001, то есть 0,5625. Поэтому необходимо 4 бита. (3 оценки)

3. В кодировании Хаффмана длина кодового слова для каждого символа должна быть целым числом. Но это может быть дробным в арифметическом кодировании. Следовательно, арифметическое кодирование часто более эффективно, чем кодирование Хаффмана, как показано выше. (1 оценка)

Answer 1

http://en.wikipedia.org/wiki/Huffman_coding

Если вы посмотрите на дерево (вверху справа), то увидите, что каждый родительский узел представляет собой сумму двух под ним. Значения в узлах являются частотами букв. Каждый бит в двоичной последовательности является правой / левой ветвью в дереве.

Это помогает?

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

Answer 2

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

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

1. Построить таблицу сущностей в исходном потоке с их распределением.
2. Выберите две записи в таблице, которые имеют наименьшее распределение.
3. Сделайте узел дерева из этих двух записей.
4. Удалите только что использованные записи из таблицы.
5. Добавьте новую запись в таблицу с объединенным распределением только что удаленных узлов, а также узел дерева.
6. если в таблице осталось более одной записи, перейдите к шагу 2.
7. Запись, оставленная в таблице, является вашим корнем.

Answer 3

Базовая реализация Хаффмана вполне подойдет. Но если вы строите с нуля, вам может понадобиться более 1 другой структуры данных в вашем наборе инструментов, чтобы упростить такие вещи, как minHeap и битовый вектор. Основные алгоритмы кодирования и декодирования довольно просты. Нет информации о сравнении с арифметическим кодированием.

Пример реализации