Изменения

'''Код Хаффмана с длиной слова не более L бит''' - это вариация классического кода Хоффмана с дополнительным ограничением: длина каждого кодового слова не должна превышать заданной константы. Здесь будет приведен алгоритм, решающий эту задачу за время <tex> O(nL) </tex>, где <tex>L</tex> - максимальная длина кодового слова, <tex>n</tex> - размер алфавита, c помощью сведения задачи к одной из вариаций '''задачи о банкомате'''.Данный алгоритм бывает полезен, когда нам нужно ограничить максимальную длину кодового слова, а при использовании алгоритма Хаффмана самому редко встречающемуся символу соответствует слишком длинное кодовое слово. Например, пусть дан алфавит из 5 символов <tex>A=\{A,B,C, C, D\}</tex>, а частоты символов являются степенями двойки: <tex>P=\{1,2,4, 8, 16\}</tex>. Тогда классический код Хоффмана будет выглядеть следующим образом: <tex> A = 1111 </tex><tex> B = 1110 </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>