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

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

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

Пусть L будет максимальной длиной любого кодового слова. Пусть p1, …, pn — частоты символов алфавит, который нужно закодировать. Сначала мы сортируем символы так, чтобы pi ≤ pi +1. Создайте монеты L для каждого символа номиналом 2−1, …, 2−L, каждая из нумизматических значение pi. Используйте алгоритм слияния пакетов, чтобы выбрать набор монет минимальной нумизматической стоимости, номиналы которых в сумме n − 1. Пусть hi будет числом выбрано монет нумизматического достоинства pi. Оптимальный код Хаффмана с ограниченной длиной будет кодировать символ i битовой строкой длины hi».


algorithm huffman-code
person user693711    schedule 24.04.2011    source источник

Ответы (2)


arrow_upward
2
arrow_downward

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

person Gigamegs    schedule 24.04.2011

arrow_upward
2
arrow_downward

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

Код Хаффмана кодирует каждую букву алфавита двоичной строкой, которую можно однозначно определить. Например, если ваш алфавит {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-1, 2-2, ..., и вы хотите построить из них общую стоимость 100 центов, вы можете подумать о этот процесс состоит в том, чтобы сначала получить монету номиналом 100, а затем разделить ее на два 50 цента (2−1), а затем продолжить делить ваши монеты пополам столько, сколько вы хотите, например 50 центов + 25 центов + 12,5 центов + 12,5 центов. Это соответствует построению бинарного дерева; всякий раз, когда вы разделяете монету, вы создаете внутренний узел в двоичном дереве и добавляете два листа на один уровень глубже.

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

Детали оставлены читателю в качестве упражнения.

person Antti Huima    schedule 25.04.2011