Код Хаффмана с длиной кодового слова не более L бит — различия между версиями
м (rollbackEdits.php mass rollback) |
|||
(не показана 51 промежуточная версия 4 участников) | |||
Строка 1: | Строка 1: | ||
− | ''' | + | '''Оптимальный префиксный код с длиной кодового слова не более 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> A = 1111 </tex> | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | == Сведение к генерации кода | + | <tex> B = 1110 </tex> |
− | Пусть <tex>L</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>L</tex> предметов ценностью <tex>2^{-1}..2^{-L}</tex>, каждый из которых имеет вес <tex>p_{i}</tex>. |
− | # С помощью | + | # С помощью задачи о рюкзаке выберем набор предметов суммарной ценностью <tex>n - 1</tex> (<tex>n</tex> — размер алфавита) с минимальным суммарным весом. |
− | # Посчитаем массив <tex>H=\{h_{1},h_{2},...,h_{n}\}</tex>, где <tex>h_{i}</tex> | + | # Посчитаем массив <tex>H=\{h_{1},h_{2},...,h_{n}\}</tex>, где <tex>h_{i}</tex> — количество предметов ценностью <tex>p_{i}</tex>, которые попали в наш набор. |
− | При этом <tex>h_{i}</tex> | + | При этом <tex>h_{i}</tex> — это длина кодового слова для <tex>i</tex>-го символа.Зная длины кодовых слов, легко восстановить и сам код. |
== Восстановление ответа. == | == Восстановление ответа. == | ||
− | # Отсортируем все символы по возрастанию длины кодового слова, которое им соответствует, а при равенстве длин | + | # Отсортируем все символы по возрастанию длины кодового слова, которое им соответствует, а при равенстве длин — в алфавитном порядке. |
# Первому символу сопоставим код, состоящий из нулей, соответствующей длины. | # Первому символу сопоставим код, состоящий из нулей, соответствующей длины. | ||
# Каждому следующему символу сопоставим следующее двоичное число. При этом если его длина меньше необходимой, то допишем нули справа. | # Каждому следующему символу сопоставим следующее двоичное число. При этом если его длина меньше необходимой, то допишем нули справа. | ||
− | == Пример работы алгоритма генерации кода | + | Заметим, что при генерации каждого следующего кодового слова, в качестве его префикса выступает последовательность, лексикографически большая, чем предыдущее кодовое слово (т.к. мы берем следующее двоичное число), а значит ни для каких двух кодовых слов одно не может быть префиксом другого. Т.е. код, сгенерированный таким образом является префиксным. |
− | Пусть <tex>A=\{ | + | |
+ | == Пример работы алгоритма генерации оптимального префиксного кода с длиной кодового слова не более L бит == | ||
+ | Пусть <tex>A=\{A,B,C\}</tex> — алфавит из трех различных символов, <tex>P=\{1,2,3\}</tex> — соответствующий ему набор частот. Пусть <tex>L = 2</tex> — ограничение на длину кодового слова. | ||
+ | |||
+ | Сначала создадим необходимый набор предметов; | ||
+ | {| class="wikitable" | ||
+ | ! Символ || Частота || Предметы | ||
+ | |- 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>(2^{-1}; 1), (2^{-1}; 2), (2^{-1}; 3), (2^{-2}; 1), (2^{-2}; 2) </tex> | ||
+ | |||
+ | Посчитаем массив <tex> H </tex>: | ||
+ | |||
+ | <tex>H=\{2,2,1\}</tex> | ||
+ | |||
+ | Итак, мы получили длины кодовых слов для символов. Осталось восстановить ответ. | ||
+ | |||
+ | == Пример восстановления ответа. == | ||
+ | |||
+ | Итак, у нас есть <tex>A=\{A,B,C\}</tex> — алфавит из n различных символов, а также <tex>H=\{2,2,1\}</tex> — соответсвующие длины кодовых слов. Отсортируем символы в соответсвии с этими длинами. | ||
+ | |||
+ | Сопоставим первому символу код, состоящий из 1 нуля: | ||
+ | |||
+ | <tex> C = 0 </tex> | ||
+ | |||
+ | Сопоставим следующему символу следующее двоичное число. Т.к. длина кода увеличилась на один, то припишем справа ноль: | ||
+ | |||
+ | <tex> B = 10 </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] | ||
+ | |||
+ | [[Категория: Дискретная математика и алгоритмы]] | ||
− | + | [[Категория: Алгоритмы сжатия ]] |
Текущая версия на 19:15, 4 сентября 2022
Оптимальный префиксный код с длиной кодового слова не более L бит — это код, в котором длина каждого кодового слова не должна превышать заданной константы. Здесь будет приведен алгоритм, решающий эту задачу за время задаче о рюкзаке.
, где — максимальная длина кодового слова, — размер алфавита, c помощью сведения задачи кДанный алгоритм бывает полезен, когда нам нужно ограничить максимальную длину кодового слова, а при использовании алгоритма Хаффмана самому редко встречающемуся символу соответствует слишком длинное кодовое слово. Например, пусть дан алфавит из 5 символов
, а частоты символов являются степенями двойки: . Тогда классический код Хоффмана будет выглядеть следующим образом:
Самое длинное кодовое слово здесь имеет длину 4. Пусть мы хотим, чтобы слова в нашем коде были не длиннее трех бит. Тогда алгоритм, который будет описан ниже, генерирует такой код:
Важно заметить следующий факт. В худшем случае все кодовые слова будут иметь длину L бит. Тогда мы можем закодировать
символов. Таким образом, нельзя получить описанный выше код, если .Содержание
- 1 Сведение задачи о рюкзаке к генерации оптимального префиксного кода с длиной кодового слова не более L бит.
- 2 Восстановление ответа.
- 3 Пример работы алгоритма генерации оптимального префиксного кода с длиной кодового слова не более L бит
- 4 Пример восстановления ответа.
- 5 См. также
- 6 Источники информации
Сведение задачи о рюкзаке к генерации оптимального префиксного кода с длиной кодового слова не более L бит.
Пусть
— ограничение на длину кодового слова, а — частоты символов алфавита. Алгоритм генерации кода будет следующим:- Отсортируем символы алфавита в порядке возрастания их частот.
- Для каждого символа создадим предметов ценностью , каждый из которых имеет вес .
- С помощью задачи о рюкзаке выберем набор предметов суммарной ценностью ( — размер алфавита) с минимальным суммарным весом.
- Посчитаем массив , где — количество предметов ценностью , которые попали в наш набор.
При этом
— это длина кодового слова для -го символа.Зная длины кодовых слов, легко восстановить и сам код.Восстановление ответа.
- Отсортируем все символы по возрастанию длины кодового слова, которое им соответствует, а при равенстве длин — в алфавитном порядке.
- Первому символу сопоставим код, состоящий из нулей, соответствующей длины.
- Каждому следующему символу сопоставим следующее двоичное число. При этом если его длина меньше необходимой, то допишем нули справа.
Заметим, что при генерации каждого следующего кодового слова, в качестве его префикса выступает последовательность, лексикографически большая, чем предыдущее кодовое слово (т.к. мы берем следующее двоичное число), а значит ни для каких двух кодовых слов одно не может быть префиксом другого. Т.е. код, сгенерированный таким образом является префиксным.
Пример работы алгоритма генерации оптимального префиксного кода с длиной кодового слова не более L бит
Пусть
— алфавит из трех различных символов, — соответствующий ему набор частот. Пусть — ограничение на длину кодового слова.Сначала создадим необходимый набор предметов;
Символ | Частота | Предметы |
---|---|---|
A | 1 | |
B | 2 | |
C | 3 |
Решим задачу о рюкзаке для заданного набора и выберем предметы суммарной ценностью
с минимальным суммарным весом. В нашем случае в оптимальный набор попадут следующие предметы:
Посчитаем массив
:
Итак, мы получили длины кодовых слов для символов. Осталось восстановить ответ.
Пример восстановления ответа.
Итак, у нас есть
— алфавит из n различных символов, а также — соответсвующие длины кодовых слов. Отсортируем символы в соответсвии с этими длинами.Сопоставим первому символу код, состоящий из 1 нуля:
Сопоставим следующему символу следующее двоичное число. Т.к. длина кода увеличилась на один, то припишем справа ноль:
Сопоставим следующему символу следующее двоичное число.