Оптимальный префиксный код с длиной кодового слова не более L бит — различия между версиями
| Строка 61: | Строка 61: | ||
Поскольку <tex>n = 2^L</tex>: | Поскольку <tex>n = 2^L</tex>: | ||
| − | <tex dpi = "160">\frac{2^L}{2^1} + \frac{2^L}{2^2} + \dots + \frac{2^L}{2^L} = 2^{L - 1} + 2 ^ {L - 2} + \dots + 2^{L - L} = 2^L - 1 = n - 1 </tex> | + | <tex dpi = "160">\frac{2^L}{2^1} + \frac{2^L}{2^2} + \dots + \frac{2^L}{2^L}</tex><tex> = 2^{L - 1} + 2 ^ {L - 2} + \dots + 2^{L - L} = 2^L - 1 = n - 1 </tex> |
Таким образом, мы набрали необходимую сумму, используя все предметы. Но так как мы рассматривали граничный случай, при бОльших значениях L данную сумму гарантированно можно набрать. | Таким образом, мы набрали необходимую сумму, используя все предметы. Но так как мы рассматривали граничный случай, при бОльших значениях L данную сумму гарантированно можно набрать. | ||
Версия 19:21, 13 января 2015
| Определение: |
Оптимальный префиксный код с длиной кодового слова не более L бит — это код, обладающий следующими свойствами:
|
Здесь будет приведен алгоритм, решающий эту задачу за время , где — максимальная длина кодового слова, — размер алфавита, c помощью сведения задачи к задаче о рюкзаке.
Содержание
- 1 Пример.
- 2 Сведение задачи о генерации оптимального префиксного кода с длиной кодового слова не более L бит к задаче о рюкзаке
- 3 Восстановление ответа.
- 4 Пример работы алгоритма генерации оптимального префиксного кода с длиной кодового слова не более L бит
- 5 Пример восстановления ответа.
- 6 См. также
- 7 Источники информации
Пример.
Данный алгоритм бывает полезен, когда нам нужно ограничить максимальную длину кодового слова, а при использовании алгоритма Хаффмана самому редко встречающемуся символу соответствует слишком длинное кодовое слово. Например, пусть дан алфавит из символов , а частоты символов являются степенями двойки: . Тогда классический код Хаффмана будет выглядеть следующим образом:
| Символ | Частота | Код |
|---|---|---|
| A | 1 | 1111 |
| B | 2 | 1110 |
| C | 4 | 110 |
| D | 8 | 10 |
| E | 16 | 0 |
Самое длинное кодовое слово здесь имеет длину . Пусть мы хотим, чтобы слова в нашем коде были не длиннее трех бит. Тогда алгоритм, который будет описан ниже, генерирует такой код:
| Символ | Частота | Код |
|---|---|---|
| A | 1 | 000 |
| B | 2 | 001 |
| C | 4 | 010 |
| D | 8 | 011 |
| E | 16 | 1 |
Важно заметить следующий факт. В худшем случае все кодовые слова будут иметь длину бит. Тогда мы можем закодировать символов. Таким образом, нельзя получить описанный выше код, если .
Сведение задачи о генерации оптимального префиксного кода с длиной кодового слова не более L бит к задаче о рюкзаке
Пусть — ограничение на длину кодового слова, а — частоты символов алфавита. Алгоритм генерации кода будет следующим:
- Для каждого символа создадим предметов ценностью , каждый из которых имеет вес .
- С помощью задачи о рюкзаке выберем набор предметов суммарной ценностью ( — размер алфавита) с минимальным суммарным весом.
- Посчитаем массив , где — количество предметов ценностью , которые попали в наш набор.
При этом — это длина кодового слова для -го символа. Зная длины кодовых слов, легко восстановить и сам код.
Из последнего утверждения и шага два легко заметить, что длина кодового слова, сгенерированного приведенным алгоритмом, действительно не превысит . Это так, потому что мы создаем ровно предметов веса (частота символа). А значит, если в худшем случае мы возьмем все предметы данного веса, то их количество не превысит .
Убедимся также, что необходимую сумму () всегда можно набрать. Зафиксируем размер алфавита равным . Теперь вспомним неравенство, которым связаны и : . Возьмем минимально возможное значение такое, что . По условию у нас есть по монет номинала , где . Попробуем посчитать суммарную стоимость имеющихся монет:
Поскольку :
Таким образом, мы набрали необходимую сумму, используя все предметы. Но так как мы рассматривали граничный случай, при бОльших значениях L данную сумму гарантированно можно набрать.
Оптимальность же кода следует из оптимальности решения задачи о рюкзаке. Действительно, частота символа - это вес предеметов, соответствующих ему. Значит, чем чаще символ встречается в тексте, тем реже он будет попадать в наш рюкзак (будет выгоднее брать предметы аналогичной ценности, но меньшего веса, соответствующие более редким символам), а значит, его код будет короче.
Восстановление ответа.
Рассмотрим процедуру восстановления ответа по заданному алфавиту и известным длинам кодовых слов.
- Отсортируем все символы по возрастанию длины кодового слова, которое им соответствует, а при равенстве длин — в алфавитном порядке.
- Первому символу сопоставим код, состоящий из нулей, соответствующей длины.
- Каждому следующему символу сопоставим следующее двоичное число. При этом если его длина меньше необходимой, то допишем нули справа.
Заметим, что при генерации каждого следующего кодового слова, в качестве его префикса выступает последовательность, лексикографически большая, чем предыдущее кодовое слово (ведь мы берем следующее двоичное число), а значит ни для каких двух кодовых слов одно не может быть префиксом другого. Значит, код, сгенерированный таким образом является префиксным.
Пример работы алгоритма генерации оптимального префиксного кода с длиной кодового слова не более L бит
Пусть — алфавит из трех различных символов, — соответствующий ему набор частот. Пусть — ограничение на длину кодового слова.
Сначала создадим необходимый набор предметов;
| Символ | Частота | Предметы |
|---|---|---|
Решим задачу о рюкзаке для заданного набора и выберем предметы суммарной ценностью с минимальным суммарным весом. В нашем случае в оптимальный набор попадут следующие предметы:
Посчитаем массив :
Итак, мы получили длины кодовых слов для символов. Осталось восстановить ответ.
Пример восстановления ответа.
Итак, у нас есть — алфавит из различных символов, а также — соответсвующие длины кодовых слов. Отсортируем символы в соответсвии с этими длинами.
Сопоставим первому символу код, состоящий из одного нуля:
Сопоставим следующему символу следующее двоичное число. Так как длина кода увеличилась на один, то припишем справа ноль:
Сопоставим следующему символу следующее двоичное число.
