Редактирование: Код Хаффмана с длиной кодового слова не более 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,D,E\}</tex>, а частоты символов являются степенями двойки: <tex>P=\{1,2,4, 8, 16\}</tex>. Тогда классический код Хоффмана будет выглядеть следующим образом:
+
Данный алгоритм бывает полезен, когда нам нужно ограничить максимальную длину кодового слова, а при использовании алгоритма Хаффмана самому редко встречающемуся символу соответствует слишком длинное кодовое слово. Например, пусть дан алфавит из 5 символов <tex>A=\{A,B,C, C, D\}</tex>, а частоты символов являются степенями двойки: <tex>P=\{1,2,4, 8, 16\}</tex>. Тогда классический код Хоффмана будет выглядеть следующим образом:
  
 
<tex> A = 1111 </tex>
 
<tex> A = 1111 </tex>
Строка 27: Строка 27:
 
Важно заметить следующий факт. В худшем случае все кодовые слова будут иметь длину L бит. Тогда мы можем закодировать <tex> 2^L </tex> символов. Таким образом, нельзя получить описанный выше код, если <tex> n > 2^L </tex>.
 
Важно заметить следующий факт. В худшем случае все кодовые слова будут иметь длину L бит. Тогда мы можем закодировать <tex> 2^L </tex> символов. Таким образом, нельзя получить описанный выше код, если <tex> n > 2^L </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> размер алфавита) с минимальным суммарным весом.  
+
# С помощью задачи о рюкзаке выберем набор предметов суммарной ценностью <ex>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>-го символа.Зная длины кодовых слов, легко восстановить и сам код.
  
 
== Восстановление ответа. ==
 
== Восстановление ответа. ==
# Отсортируем все символы по возрастанию длины кодового слова, которое им соответствует, а при равенстве длин в алфавитном порядке.
+
# Отсортируем все символы по возрастанию длины кодового слова, которое им соответствует, а при равенстве длин - в алфавитном порядке.
 
# Первому символу сопоставим код, состоящий из нулей, соответствующей длины.
 
# Первому символу сопоставим код, состоящий из нулей, соответствующей длины.
 
# Каждому следующему символу сопоставим следующее двоичное число. При этом если его длина меньше необходимой, то допишем нули справа.
 
# Каждому следующему символу сопоставим следующее двоичное число. При этом если его длина меньше необходимой, то допишем нули справа.
Строка 44: Строка 44:
 
Заметим, что при генерации каждого следующего кодового слова, в качестве его префикса выступает последовательность, лексикографически большая, чем предыдущее кодовое слово (т.к. мы берем следующее двоичное число), а значит ни для каких двух кодовых слов одно не может быть префиксом другого. Т.е. код, сгенерированный таким образом является префиксным.
 
Заметим, что при генерации каждого следующего кодового слова, в качестве его префикса выступает последовательность, лексикографически большая, чем предыдущее кодовое слово (т.к. мы берем следующее двоичное число), а значит ни для каких двух кодовых слов одно не может быть префиксом другого. Т.е. код, сгенерированный таким образом является префиксным.
  
== Пример работы алгоритма генерации оптимального префиксного кода с длиной кодового слова не более L бит ==
+
== Пример работы алгоритма генерации кода Хоффмана с длиной кодового слова не более L бит ==
Пусть <tex>A=\{A,B,C\}</tex> — алфавит из трех различных символов, <tex>P=\{1,2,3\}</tex> — соответствующий ему набор частот. Пусть <tex>L = 2</tex> ограничение на длину кодового слова.  
+
Пусть <tex>A=\{a_{1},a_{2},...,a_{n}\}</tex> — алфавит из n различных символов, <tex>P=\{p_{1},p_{2},...,p_{n}\}</tex> — соответствующий ему набор частот. Пусть <tex>L = 2</tex> - ограничение на длину кодового слова.  
  
 
Сначала создадим необходимый набор предметов;
 
Сначала создадим необходимый набор предметов;
{| class="wikitable"
+
<tex>(2^{-1}; 1), (2^{-2}; 1), (2^{-1}; 2), (2^{-2}; 2), (2^{-1}; 3), (2^{-2}; 3) </tex>
! Символ || Частота || Предметы
 
|- align = "center"
 
| 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> с минимальным суммарным весом.  В нашем случае в оптимальный набор попадут следующие предметы:
 
Решим задачу о рюкзаке для заданного набора и выберем предметы суммарной ценностью <tex> n - 1 = 2 </tex> с минимальным суммарным весом.  В нашем случае в оптимальный набор попадут следующие предметы:
Строка 62: Строка 54:
 
  <tex>(2^{-1}; 1), (2^{-1}; 2), (2^{-1}; 3), (2^{-2}; 1), (2^{-2}; 2) </tex>
 
  <tex>(2^{-1}; 1), (2^{-1}; 2), (2^{-1}; 3), (2^{-2}; 1), (2^{-2}; 2) </tex>
  
Посчитаем массив <tex> H </tex>:
+
Посчитаем массив <tex> H </tex>. Обратите внимание, что при подсчете количества монет определенного веса мы учитываем монеты, которые были даны изначально, а не те, которые получились путем слияния исходных.
  
 
<tex>H=\{2,2,1\}</tex>
 
<tex>H=\{2,2,1\}</tex>
Строка 70: Строка 62:
 
== Пример восстановления ответа. ==
 
== Пример восстановления ответа. ==
  
Итак, у нас есть <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: Строка 75:
  
 
<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]
 
[[Категория: Дискретная математика и алгоритмы]]
 
 
[[Категория: Алгоритмы сжатия ]]
 

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

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

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