Код Хаффмана с длиной кодового слова не более L бит — различия между версиями
| Строка 45: | Строка 45: | ||
== Пример работы алгоритма генерации кода Хоффмана с длиной кодового слова не более L бит == | == Пример работы алгоритма генерации кода Хоффмана с длиной кодового слова не более L бит == | ||
| − | Пусть <tex>A=\{ | + | Пусть <tex>A=\{A,B,C\}</tex> — алфавит из трех различных символов, <tex>P=\{1,2,3\}</tex> — соответствующий ему набор частот. Пусть <tex>L = 2</tex> — ограничение на длину кодового слова. |
Сначала создадим необходимый набор предметов; | Сначала создадим необходимый набор предметов; | ||
| Строка 51: | Строка 51: | ||
! Символ || Частота || Предметы | ! Символ || Частота || Предметы | ||
|- | |- | ||
| − | | | + | | A || 1 || |
|- | |- | ||
| − | | | + | | B || 2 || |
| + | |- | ||
| + | | C || 3 || | ||
|} | |} | ||
<tex>(2^{-1}; 1), (2^{-2}; 1), (2^{-1}; 2), (2^{-2}; 2), (2^{-1}; 3), (2^{-2}; 3) </tex> | <tex>(2^{-1}; 1), (2^{-2}; 1), (2^{-1}; 2), (2^{-2}; 2), (2^{-1}; 3), (2^{-2}; 3) </tex> | ||
Версия 19:53, 18 декабря 2014
Код Хаффмана с длиной слова не более L бит — это вариация классического кода Хоффмана с дополнительным ограничением: длина каждого кодового слова не должна превышать заданной константы. Здесь будет приведен алгоритм, решающий эту задачу за время , где — максимальная длина кодового слова, — размер алфавита, c помощью сведения задачи к задаче о рюкзаке.
Данный алгоритм бывает полезен, когда нам нужно ограничить максимальную длину кодового слова, а при использовании алгоритма Хаффмана самому редко встречающемуся символу соответствует слишком длинное кодовое слово. Например, пусть дан алфавит из 5 символов , а частоты символов являются степенями двойки: . Тогда классический код Хоффмана будет выглядеть следующим образом:
Самое длинное кодовое слово здесь имеет длину 4. Пусть мы хотим, чтобы слова в нашем коде были не длиннее трех бит. Тогда алгоритм, который будет описан ниже, генерирует такой код:
Важно заметить следующий факт. В худшем случае все кодовые слова будут иметь длину L бит. Тогда мы можем закодировать символов. Таким образом, нельзя получить описанный выше код, если .
Содержание
Сведение к генерации кода Хоффмана с длиной кодового слова не более L бит.
Пусть — ограничение на длину кодового слова, а — частоты символов алфавита. Алгоритм генерации кода будет следующим:
- Отсортируем символы алфавита в порядке возрастания их частот.
- Для каждого символа создадим предметов ценностью , каждый из которых имеет вес .
- С помощью задачи о рюкзаке выберем набор предметов суммарной ценностью <ex>n - 1</tex> ( — размер алфавита) с минимальным суммарным весом.
- Посчитаем массив , где — количество предметов ценностью , которые попали в наш набор.
При этом — это длина кодового слова для -го символа.Зная длины кодовых слов, легко восстановить и сам код.
Восстановление ответа.
- Отсортируем все символы по возрастанию длины кодового слова, которое им соответствует, а при равенстве длин — в алфавитном порядке.
- Первому символу сопоставим код, состоящий из нулей, соответствующей длины.
- Каждому следующему символу сопоставим следующее двоичное число. При этом если его длина меньше необходимой, то допишем нули справа.
Заметим, что при генерации каждого следующего кодового слова, в качестве его префикса выступает последовательность, лексикографически большая, чем предыдущее кодовое слово (т.к. мы берем следующее двоичное число), а значит ни для каких двух кодовых слов одно не может быть префиксом другого. Т.е. код, сгенерированный таким образом является префиксным.
Пример работы алгоритма генерации кода Хоффмана с длиной кодового слова не более L бит
Пусть — алфавит из трех различных символов, — соответствующий ему набор частот. Пусть — ограничение на длину кодового слова.
Сначала создадим необходимый набор предметов;
| Символ | Частота | Предметы |
|---|---|---|
| A | 1 | |
| B | 2 | |
| C | 3 |
Решим задачу о рюкзаке для заданного набора и выберем предметы суммарной ценностью с минимальным суммарным весом. В нашем случае в оптимальный набор попадут следующие предметы:
Посчитаем массив :
Итак, мы получили длины кодовых слов для символов. Осталось восстановить ответ.
Пример восстановления ответа.
Итак, у нас есть — алфавит из n различных символов, а также — соответсвующие длины кодовых слов. Отсортируем символы в соответсвии с этими длинами.
Сопоставим первому символу код, состоящий из 1 нуля:
Сопоставим следующему символу следующее двоичное число. Т.к. длина кода увеличилась на один, то припишем справа ноль:
Сопоставим следующему символу следующее двоичное число.
