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

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 B 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 и битовый вектор.Основные алгоритмы кодирования и декодирования довольно просты.Нет информации о сравнении с арифметическим кодированием.

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