алгоритм слияния пакетов для кодов Хаффмана с ограниченной длиной

Question

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

• как мы упаковываем?
• как мы сливаемся?
• как мы узнаем длину строки битов для символов?

Пусть L - максимальная длина, которую может иметь любое кодовое слово. Пусть p ₁ ,…, p _n - частоты символов алфавита для кодирования , Сначала мы сортируем символы так, чтобы p _i ≤ p _i + 1 , Создайте L монет для каждого символа номиналом 2 ^-1 ,…, 2 ^{- L} , каждый из нумизматического значения р _я . Используйте алгоритм слияния пакетов, чтобы выбрать набор монет с минимальным нумизматическим значением, номинал которых составляет n - 1. Пусть ч _i будет количеством монет нумизматическое значение p _i выбрано. Оптимальный код Хаффмана с ограниченной длиной закодирует символ i с битовой строкой длиной h _i . "

Answer 1

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

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

A - 0
B - 10
C - 11

Кодированная строка, такая как 0010110, может быть уникально закодированапотому что длина строки битов кодирования уже определена кодом Хаффмана (здесь --- каждая строка, которая начинается с 0, имеет длину 1, а каждая строка, которая существует с 1, имеет длину 2).Таким образом, строка декодируется в 0 | 0 | 10 | 11 | 0 = AABCA.

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

Детали алгоритма слияния пакетов не важны, поскольку ключ заключается в том, что вы используете алгоритм для выбора «набора монет минимумнумизматическое значение, чьи достоинства составляют всего n - 1 ".Если у вас есть монеты достоинством 2 ⁻¹ , 2 ⁻² , ..., и вы хотите получить из них общую стоимость 100 центов, вы можете подумать об этом процессеимея сначала монету достоинством 100, а затем разделив ее на два 50 цента (2 ^-1 ), а затем продолжая делить ваши монеты пополам так долго, как вы хотите, например, 50 центов + 25 центов+ 12,5 цента + 12,5 цента.Это соответствует построению бинарного дерева;всякий раз, когда вы разбиваете монету, вы создаете внутренний узел в бинарном дереве и добавляете два листа на один уровень глубже.

Теперь идея минимизации нумизматического значения состоит в том, что те «монеты», которые связаны с «высшимЧастота "символов более дорогая в использовании, поэтому вы хотите разделить эти монеты меньше, что соответствует более коротким кодам.

Подробности оставлены в качестве упражнения для читателя.

Answer 2

Может быть, это просто альтернативный способ создания кода Хаффмана.Вы смотрели на http://cbloomrants.blogspot.com/2010/07/07-02-10-length-limitted-huffman-codes.html? IMO, алгоритм слияния пакетов не строит дерево Хаффмана.Вы хотите найти код Голомба.