Код Хаффмана с длиной кодового слова не более L бит
Версия от 13:35, 17 декабря 2014; Ruslan.tkhakokhov (обсуждение | вклад)
Код Хаффмана с длиной слова не более L бит - это вариация классического кода Хоффмана с дополнительным ограничением: длина каждого кодового слова не должна превышать заданной константы. Здесь будет приведен алгоритм, решающий эту задачу за время
, где - максимальная длина кодового слова, - размер алфавита, c помощью сведения задачи к одной из вариаций задачи о банкомате.Задача о банкомате.
В вариации задаче о банкомате, которую мы рассмотрим, у вас имеется
монет. Каждая монета характеризуется двумя параметрами: номиналом и весом. При этом все номиналы являются степенями двойки и не превышают . Необходимо выбрать из имеющихся монет некоторый набор так, чтобы их суммарный номинал был равен (натуральное число), а суммарный вес минимален.Алгоритм решения задачи о банкомате.
Рассмотрим алгоритм решения приведенной выше вариации задачи о банкомате.
- Разделим имеющиеся у нас монеты на списки по номиналу (свой список для каждого номинала) и упорядочим монеты по возрастанию весов внутри списков.