Код Хаффмана с длиной кодового слова не более L бит — различия между версиями

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

Текущая версия на 18:27, 23 октября 2019

Оптимальный префиксный код с длиной кодового слова не более L бит — это код, в котором длина каждого кодового слова не должна превышать заданной константы. Здесь будет приведен алгоритм, решающий эту задачу за время [math] O(nL) [/math], где [math]L[/math] — максимальная длина кодового слова, [math]n[/math] — размер алфавита, c помощью сведения задачи к задаче о рюкзаке.

Данный алгоритм бывает полезен, когда нам нужно ограничить максимальную длину кодового слова, а при использовании алгоритма Хаффмана самому редко встречающемуся символу соответствует слишком длинное кодовое слово. Например, пусть дан алфавит из 5 символов [math]A=\{A,B,C,D,E\}[/math], а частоты символов являются степенями двойки: [math]P=\{1,2,4, 8, 16\}[/math]. Тогда классический код Хоффмана будет выглядеть следующим образом:

[math] A = 1111 [/math]

[math] B = 1110 [/math]

[math] C = 110 [/math]

[math] D = 10 [/math]

[math] E = 0 [/math]

Самое длинное кодовое слово здесь имеет длину 4. Пусть мы хотим, чтобы слова в нашем коде были не длиннее трех бит. Тогда алгоритм, который будет описан ниже, генерирует такой код:

[math] A = 000 [/math]

[math] B = 001 [/math]

[math] C = 010 [/math]

[math] D = 011 [/math]

[math] E = 100 [/math]

Важно заметить следующий факт. В худшем случае все кодовые слова будут иметь длину L бит. Тогда мы можем закодировать [math] 2^L [/math] символов. Таким образом, нельзя получить описанный выше код, если [math] n \gt 2^L [/math].

Сведение задачи о рюкзаке к генерации оптимального префиксного кода с длиной кодового слова не более L бит.[править]

Пусть [math]L[/math] — ограничение на длину кодового слова, а [math]P=\{p_{1},p_{2},...,p_{n}\}[/math] — частоты символов алфавита. Алгоритм генерации кода будет следующим:

  1. Отсортируем символы алфавита в порядке возрастания их частот.
  2. Для каждого символа создадим [math]L[/math] предметов ценностью [math]2^{-1}..2^{-L}[/math], каждый из которых имеет вес [math]p_{i}[/math].
  3. С помощью задачи о рюкзаке выберем набор предметов суммарной ценностью [math]n - 1[/math] ([math]n[/math] — размер алфавита) с минимальным суммарным весом.
  4. Посчитаем массив [math]H=\{h_{1},h_{2},...,h_{n}\}[/math], где [math]h_{i}[/math] — количество предметов ценностью [math]p_{i}[/math], которые попали в наш набор.

При этом [math]h_{i}[/math] — это длина кодового слова для [math]i[/math]-го символа.Зная длины кодовых слов, легко восстановить и сам код.

Восстановление ответа.[править]

  1. Отсортируем все символы по возрастанию длины кодового слова, которое им соответствует, а при равенстве длин — в алфавитном порядке.
  2. Первому символу сопоставим код, состоящий из нулей, соответствующей длины.
  3. Каждому следующему символу сопоставим следующее двоичное число. При этом если его длина меньше необходимой, то допишем нули справа.

Заметим, что при генерации каждого следующего кодового слова, в качестве его префикса выступает последовательность, лексикографически большая, чем предыдущее кодовое слово (т.к. мы берем следующее двоичное число), а значит ни для каких двух кодовых слов одно не может быть префиксом другого. Т.е. код, сгенерированный таким образом является префиксным.

Пример работы алгоритма генерации оптимального префиксного кода с длиной кодового слова не более L бит[править]

Пусть [math]A=\{A,B,C\}[/math] — алфавит из трех различных символов, [math]P=\{1,2,3\}[/math] — соответствующий ему набор частот. Пусть [math]L = 2[/math] — ограничение на длину кодового слова.

Сначала создадим необходимый набор предметов;

Символ Частота Предметы
A 1 [math] (2^{-1}; 1), (2^{-2}; 1) [/math]
B 2 [math](2^{-1}; 2), (2^{-2}; 2)[/math]
C 3 [math] (2^{-1}; 3), (2^{-2}; 3)[/math]

Решим задачу о рюкзаке для заданного набора и выберем предметы суммарной ценностью [math] n - 1 = 2 [/math] с минимальным суммарным весом. В нашем случае в оптимальный набор попадут следующие предметы:

[math](2^{-1}; 1), (2^{-1}; 2), (2^{-1}; 3), (2^{-2}; 1), (2^{-2}; 2) [/math]

Посчитаем массив [math] H [/math]:

[math]H=\{2,2,1\}[/math]

Итак, мы получили длины кодовых слов для символов. Осталось восстановить ответ.

Пример восстановления ответа.[править]

Итак, у нас есть [math]A=\{A,B,C\}[/math] — алфавит из n различных символов, а также [math]H=\{2,2,1\}[/math] — соответсвующие длины кодовых слов. Отсортируем символы в соответсвии с этими длинами.

Сопоставим первому символу код, состоящий из 1 нуля:

[math] C = 0 [/math]

Сопоставим следующему символу следующее двоичное число. Т.к. длина кода увеличилась на один, то припишем справа ноль:

[math] B = 10 [/math]

Сопоставим следующему символу следующее двоичное число.

[math] A = 11 [/math]

См. также[править]

Источники информации[править]