Редактирование: Код Хаффмана с длиной кодового слова не более L бит

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
'''Оптимальный префиксный код с длиной кодового слова не более L бит''' это код, в котором длина каждого кодового слова не должна превышать заданной константы. Здесь будет приведен алгоритм, решающий эту задачу за время <tex> O(nL) </tex>, где <tex>L</tex> максимальная длина кодового слова, <tex>n</tex> размер алфавита, c помощью сведения задачи к [[Задача_о_рюкзаке | задаче о рюкзаке]].
+
'''Код Хаффмана с длиной слова не более L бит''' - это вариация классического кода Хоффмана с дополнительным ограничением: длина каждого кодового слова не должна превышать заданной константы. Здесь будет приведен алгоритм, решающий эту задачу за время <tex> O(nL) </tex>, где <tex>L</tex> - максимальная длина кодового слова, <tex>n</tex> - размер алфавита, c помощью сведения задачи к одной из вариаций '''задачи о банкомате'''.  
 
+
Данный алгоритм бывает полезен, когда нам нужно ограничить максимальную длину кодового слова, а при использовании алгоритма Хаффмана самому редко встречающемуся символу соответствует слишком длинное кодовое слово. Например, пусть дан алфавит из 5 символов <tex>A=\{A,B,C, C, D\}</tex>, а частоты символов являются степенями двойки: <tex>P=\{1,2,4, 8, 16\}</tex>. Тогда классический код Хоффмана будет выглядеть следующим образом:
Данный алгоритм бывает полезен, когда нам нужно ограничить максимальную длину кодового слова, а при использовании алгоритма Хаффмана самому редко встречающемуся символу соответствует слишком длинное кодовое слово. Например, пусть дан алфавит из 5 символов <tex>A=\{A,B,C,D,E\}</tex>, а частоты символов являются степенями двойки: <tex>P=\{1,2,4, 8, 16\}</tex>. Тогда классический код Хоффмана будет выглядеть следующим образом:
 
  
 
<tex> A = 1111 </tex>
 
<tex> A = 1111 </tex>
Строка 13: Строка 12:
 
<tex> E = 0 </tex>
 
<tex> E = 0 </tex>
 
   
 
   
Самое длинное кодовое слово здесь имеет длину 4. Пусть мы хотим, чтобы слова в нашем коде были не длиннее трех бит. Тогда алгоритм, который будет описан ниже, генерирует такой код:
+
Заметим, что самое длинное кодовое слово имеет длину 4. Пусть мы хотим, чтобы слова в нашем коде были не длиннее трех бит. Тогда алгоритм, который будет описан ниже, генерирует такой код:
  
 
<tex> A = 000 </tex>
 
<tex> A = 000 </tex>
Строка 25: Строка 24:
 
<tex> E = 100 </tex>
 
<tex> E = 100 </tex>
  
Важно заметить следующий факт. В худшем случае все кодовые слова будут иметь длину L бит. Тогда мы можем закодировать <tex> 2^L </tex> символов. Таким образом, нельзя получить описанный выше код, если <tex> n > 2^L </tex>.
+
При этом очевидно, что если <tex> n > 2^L </tex>, то перекидного кода с длиной слова не более <tex> L </tex> бит не существует.
 +
 
 +
== Задача о банкомате. ==
 +
В вариации задаче о банкомате, которую мы рассмотрим, у вас имеется <tex>N</tex> монет. Каждая монета характеризуется двумя параметрами: номиналом и весом. При этом все номиналы являются степенями двойки и не превышают <tex>2^0</tex>. Необходимо выбрать из имеющихся монет некоторый набор так, чтобы их суммарный номинал был равен <tex>S</tex> (натуральное число), а суммарный вес минимален.
 +
 
 +
== Алгоритм решения задачи о банкомате. ==
 +
Рассмотрим алгоритм решения приведенной выше вариации задачи о банкомате, считая, что решение существует.
 +
# Разделим имеющиеся у нас монеты на списки по номиналу (свой список для каждого номинала) и упорядочим монеты по возрастанию весов внутри списков, а списки в порядке возрастания номиналов.
 +
# Рассмотрим первый список (с монетами самого низкого номинала). Разобьем в нем все монеты на пары (1 и 2, 3 и 4 и т. д.) Заменим каждую пару монет одной новой монетой, номинал и вес которой равен сумме номиналов и весов старых. Если число монет было нечетно, то последнюю монету, которая не имеет пары, исключим из рассмотрения.
 +
# Объединим первый список со вторым так, чтобы монеты в получившемся списке остались упорядочены по весу.
 +
# Будем повторять шаги 2-3 до тех пор, пока у нас не останется один список, в котором содержатся монеты номинала 1 (<tex>2^0</tex>), упорядоченные по весу. Возьмем первые <tex>S</tex> монет из списка. Это и будет ответ к задаче.
  
== Сведение задачи о рюкзаке к генерации оптимального префиксного кода с длиной кодового слова не более L бит. ==
+
== Сведение к генерации кода Хоффмана с длиной кодового слова не более L бит. ==
Пусть <tex>L</tex> ограничение на длину кодового слова, а <tex>P=\{p_{1},p_{2},...,p_{n}\}</tex> частоты символов алфавита. Алгоритм генерации кода будет следующим:
+
Пусть <tex>L</tex> - ограничение на длину кодового слова, а <tex>P=\{p_{1},p_{2},...,p_{n}\}</tex> - частоты символов алфавита.
  
 
# Отсортируем символы алфавита в порядке возрастания их частот.
 
# Отсортируем символы алфавита в порядке возрастания их частот.
# Для каждого символа создадим <tex>L</tex> предметов ценностью  <tex>2^{-1}..2^{-L}</tex>, каждый из которых имеет вес <tex>p_{i}</tex>.
+
# Для каждого символа создадим <tex>L</tex> монет номиналами <tex>2^{-1}..2^{-L}, каждая из которых имеет вес <tex>p_{i}</tex>.
# С помощью задачи о рюкзаке выберем набор предметов суммарной ценностью <tex>n - 1</tex> (<tex>n</tex> размер алфавита) с минимальным суммарным весом.  
+
# С помощью описанного выше алгоритма выберем набор монет суммарным номиналом <tex>n - 1</tex> (<tex>n</tex> - размер алфавита) с минимальным суммарным весом.  
# Посчитаем массив <tex>H=\{h_{1},h_{2},...,h_{n}\}</tex>, где <tex>h_{i}</tex> количество предметов ценностью <tex>p_{i}</tex>, которые попали в наш набор.
+
# Посчитаем массив <tex>H=\{h_{1},h_{2},...,h_{n}\}</tex>, где <tex>h_{i}</tex> - количество монет номинала <tex>p_{i}</tex>, которые попали в наш набор.
  
При этом <tex>h_{i}</tex> это длина кодового слова для <tex>i</tex>-го символа.Зная длины кодовых слов, легко восстановить и сам код.
+
При этом <tex>h_{i}</tex> - это длина кодового слова для <tex>i</tex>-го символа.Зная длины кодовых слов, легко восстановить и сам код.
  
 
== Восстановление ответа. ==
 
== Восстановление ответа. ==
# Отсортируем все символы по возрастанию длины кодового слова, которое им соответствует, а при равенстве длин в алфавитном порядке.
+
# Отсортируем все символы по возрастанию длины кодового слова, которое им соответствует, а при равенстве длин - в алфавитном порядке.
 
# Первому символу сопоставим код, состоящий из нулей, соответствующей длины.
 
# Первому символу сопоставим код, состоящий из нулей, соответствующей длины.
 
# Каждому следующему символу сопоставим следующее двоичное число. При этом если его длина меньше необходимой, то допишем нули справа.
 
# Каждому следующему символу сопоставим следующее двоичное число. При этом если его длина меньше необходимой, то допишем нули справа.
  
Заметим, что при генерации каждого следующего кодового слова, в качестве его префикса выступает последовательность, лексикографически большая, чем предыдущее кодовое слово (т.к. мы берем следующее двоичное число), а значит ни для каких двух кодовых слов одно не может быть префиксом другого. Т.е. код, сгенерированный таким образом является префиксным.
+
== Пример работы алгоритма генерации кода Хоффмана с длиной кодового слова не более L бит ==
 +
Пусть <tex>A=\{a_{1},a_{2},...,a_{n}\}</tex> — алфавит из n различных символов, <tex>P=\{p_{1},p_{2},...,p_{n}\}</tex> — соответствующий ему набор частот. Пусть <tex>L = 2</tex> - ограничение на длину кодового слова.  
 +
 
 +
Сначала создадим необходимый набор монет;
 +
<tex>(2^{-1}; 1), (2^{-2}; 1), (2^{-1}; 2), (2^{-2}; 2), (2^{-1}; 3), (2^{-2}; 3)  </tex>
 +
 
 +
Распределим их по спискам:
 +
{| class="wikitable"
 +
| Номинал = <tex> 2^{-2} </tex> ||  <tex>(2^{-2}; 1)</tex> || <tex>(2^{-2}; 2)</tex> || <tex>(2^{-2}; 3)</tex>
 +
|-
 +
| Номинал = <tex> 2^{-1} </tex> ||  <tex>(2^{-1}; 1)</tex> || <tex>(2^{-1}; 2)</tex> || <tex>(2^{-2}; 3)</tex>
 +
|}
 +
 
 +
Выполним объединение первого списка по парам и исключим последний элемент, т.к. для него нет пары:
 +
 
 +
{| class="wikitable"
 +
| Номинал = <tex> 2^{-2} </tex> ||  <tex>(2^{-1}; 3)</tex> || ||
 +
|-
 +
| Номинал = <tex> 2^{-1} </tex> ||  <tex>(2^{-1}; 1)</tex> || <tex>(2^{-1}; 2)</tex> || <tex>(2^{-2}; 3)</tex>
 +
|}
  
== Пример работы алгоритма генерации оптимального префиксного кода с длиной кодового слова не более L бит ==
+
Объединим первый список со вторым:
Пусть <tex>A=\{A,B,C\}</tex> — алфавит из трех различных символов, <tex>P=\{1,2,3\}</tex> — соответствующий ему набор частот. Пусть <tex>L = 2</tex> — ограничение на длину кодового слова.
 
  
Сначала создадим необходимый набор предметов;
 
 
{| class="wikitable"
 
{| class="wikitable"
! Символ || Частота || Предметы
+
| Номинал = <tex> 2^{-2} </tex> || || ||  
|- align = "center"
+
|-
| A || 1 || <tex> (2^{-1}; 1), (2^{-2}; 1) </tex>
+
| Номинал = <tex> 2^{-1} </tex> || <tex>(2^{-1}; 1)</tex> || <tex>(2^{-1}; 2)</tex> || <tex>(2^{-1}; 3)</tex> || <tex>(2^{-1}; 3)</tex>
|- align = "center"
 
| B || 2 || <tex>(2^{-1}; 2), (2^{-2}; 2)</tex>
 
|- align = "center"
 
| C || 3 || <tex> (2^{-1}; 3), (2^{-2}; 3)</tex>
 
 
|}
 
|}
  
Решим задачу о рюкзаке для заданного набора и выберем предметы суммарной ценностью <tex> n - 1 = 2 </tex> с минимальным суммарным весом.  В нашем случае в оптимальный набор попадут следующие предметы:
+
Выполним объединение второго списка по парам:
  
<tex>(2^{-1}; 1), (2^{-1}; 2), (2^{-1}; 3), (2^{-2}; 1), (2^{-2}; 2) </tex>
+
{| class="wikitable"
 +
| Номинал = <tex> 2^{0} </tex> ||  <tex>(2^{0}; 3)</tex> || <tex>(2^{0}; 6)</tex>  
 +
|}
  
Посчитаем массив <tex> H </tex>:
+
Теперь нам нужно набрать монеты суммарным номиналом <tex> n - 1 = 2 </tex> с минимальным суммарным весом, т.е. просто возьмем первые две монеты из итогового списка. Посчитаем массив <tex> H </tex>. Обратите внимание, что при подсчете количества монет определенного веса мы учитываем монеты, которые были даны изначально, а не те, которые получились путем слияния исходных.
  
 
<tex>H=\{2,2,1\}</tex>
 
<tex>H=\{2,2,1\}</tex>
Строка 70: Строка 94:
 
== Пример восстановления ответа. ==
 
== Пример восстановления ответа. ==
  
Итак, у нас есть <tex>A=\{A,B,C\}</tex> — алфавит из n различных символов, а также <tex>H=\{2,2,1\}</tex> соответсвующие длины кодовых слов. Отсортируем символы в соответсвии с этими длинами.
+
Итак, у нас есть <tex>A=\{A,B,C\}</tex> — алфавит из n различных символов, а также <tex>H=\{2,2,1\}</tex> - соответсвующие длины кодовых слов. Отсортируем символы в соответсвии с этими длинами.
  
 
Сопоставим первому символу код, состоящий из 1 нуля:
 
Сопоставим первому символу код, состоящий из 1 нуля:
Строка 83: Строка 107:
  
 
<tex> A = 11 </tex>
 
<tex> A = 11 </tex>
 
==См. также==
 
*[[Алгоритм_Хаффмана | Алгоритм Хаффмана]]
 
*[[Задача_о_рюкзаке | Задача о рюкзаке]]
 
  
 
==Источники информации==
 
==Источники информации==
 
*[http://en.wikipedia.org/wiki/Package-merge_algorithm Package-merge algorithm]
 
*[http://en.wikipedia.org/wiki/Package-merge_algorithm Package-merge algorithm]
 
*[http://en.wikipedia.org/wiki/Canonical_Huffman_code Canonical Huffman code]
 
*[http://en.wikipedia.org/wiki/Canonical_Huffman_code Canonical Huffman code]
 
[[Категория: Дискретная математика и алгоритмы]]
 
 
[[Категория: Алгоритмы сжатия ]]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)