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

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

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

Предположим, что используется алфавит [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 A 0,0 0,6 0,6 C 0,48 0,6 0,12 B 0,552 0,576 0,024 Окончательное двоичное кодовое слово равно 0,1001, что равно 0,5625. Поэтому нужно 4 бита. (3 балла)

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


huffman-code lossless-compression
person Tommy    schedule 15.04.2011    source источник
comment
вау, ты довольно хорошо угадываешь, каким будет твое будущее назначение. Даже до того, сколько баллов за каждый вопрос!   -  person Mat    schedule 15.04.2011
comment
лол, это практический вопрос, но лектор сказал, что это будет похоже, и он только изменит цифры.   -  person Tommy    schedule 15.04.2011
comment
хм... хорошо. с чем у тебя проблемы? это все должно быть описано в вашем учебнике.   -  person Mat    schedule 15.04.2011
comment
Учебник довольно утомительный, толком ничего не объясняет для новичка. У меня проблемы с ответом на первый вопрос, я ответил выше. Не уверен, как он получил ответ.   -  person Tommy    schedule 15.04.2011
comment
Если нужно сделать это на Mathematica, это может быть полезно. academia.edu/19699746/Huffman_Code_on_Mathematica_using_Trees   -  person Sejwal    schedule 26.12.2015

Ответы (3)


arrow_upward
2
arrow_downward

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

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

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

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

person Jaydee    schedule 15.04.2011

arrow_upward
1
arrow_downward

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

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

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

arrow_upward
0
arrow_downward

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

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

person quiet_penguin    schedule 07.12.2011