Алгоритм построения оптимального префиксного кода

Предположим, у* и z* — две буквы S с наименьшими частотами (с произвольной разбивкой «ничьих»). Утверждение (4.31) важно, так как оно сообщает важную информацию о местонахождении у* и z* в оптимальном решении; оно говорит, что при анализе решениях их можно «держать вместе», потому что мы знаем, что они станут одноранговыми узлами под общим родителем.
Получается, что этот общий родитель становится «метабуквой», частота которой равна сумме частот у* и z*.

Отсюда напрямую следует идея алгоритма: у* и z* заменяются этой метабуквой с получением алфавита, уменьшенного на одну букву. Затем рекурсивно вычис- ляется префиксный код для сокращенного алфавита, метабуква снова «раскрыва- ется» на у* и z* с получением префиксного кода для S. Эта рекурсивная стратегия изображена на рис. 4.17.

Рис. 4.17. Существует оптимальное решение, в котором две буквы с наименьшими частотами используются для пометки одноранговых листьев; если удалить их и пометить родительский узел новой буквой с суммарной частотой, это порождает экземпляр задачи с сокращенным

алфавитом


Ниже приводится формальное описание алгоритма.

Построение префиксного кода для алфавита S с заданными частотами:

Если S состоит из двух букв

Закодировать одну букву 0, а другую 1 Иначе

Пусть у* и z* - две буквы с наименьшими частотами Образовать новый алфавит S': удалить у* и z* и заменить их новой буквой ω с частотой f* + f*

Рекурсивно сконструировать префиксный код γ' для S', с деревом T'

Определить префиксный код для S следующим образом:

Начать с T'

Взять лист с меткой ω и добавить под ним два дочерних узла с метками у* и z*

Конец Если

Эта процедура будет называться алгоритмом Хаффмана, а префиксный код, создаваемый ею для заданного алфавита, соответственно, будет называться кодом Хаффмана. В общем случае очевидно, что выполнение алгоритма всегда завершает- ся, потому что он рекурсивно вызывает себя для алфавита, уменьшенного на одну букву.

Более того, с (4.31) нетрудно доказать, что алгоритм действительно создает оптимальный префиксный код. Но перед этим стоит сделать пару замечаний по поводу алгоритма.

Для начала рассмотрим поведение алгоритма на примере с S ={a, b, c, d, e} и ча- стотами

f = 0,32, f = 0,25, f = 0,20, f = 0,18, f = 0,05.

Ja ’ ’ Jb’ ’ J с’ ’ d ’ ’ J e ’

Алгоритм объединяет d и e в одну букву — обозначим ее (de) — с частотой 0,18 + 0,05 = 0,23. Теперь мы имеем экземпляр задачи с четырехбуквенным ал- фавитом S' = {a, b, c, (de)}. Двумя буквами S' с наименьшей частотой являются буквы c и (de), поэтому на следующем шаге они объединяются в одну букву (cde) с частотой 0,20 + 0,23 = 0,43; образуется трехбуквенный алфавит {a, b, (cde)}. Далее объединяются буквы a и b с получением алфавита из двух букв, и в этой точке акти- визируется база рекурсии. Развернув результат по цепочке рекурсивных вызовов, мы получим дерево, изображенное на рис. 4.16, c.

Интересно, как жадное правило, заложенное в основу алгоритма Хаффмана (слияние букв с двумя наименьшими частотами), укладывается в структуру алго- ритма в целом. Фактически на момент слияния двух букв мы не знаем точно, какое место они займут в общем коде. Вместо этого мы просто считаем их дочерними узлами одного родителя, и этого хватает для построения новой эквивалентной за- дачи, сокращенной на одну букву.

Кроме того, алгоритм образует естественный контраст с более ранним решени- ем, приводящим к субоптимальным кодам Шеннона-Фано. Этот метод базиро- вался на нисходящей стратегии, которая прежде всего обращала внимание на раз- биение верхнего уровня в бинарном дереве, а именно на два подузла, находящиеся непосредственно под корнем. С другой стороны, алгоритм Хаффмана использует восходящий метод: он находит листья, представляющие две буквы с самой низкой частотой, а затем продолжает работу по рекурсивному принципу.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Алгоритм построения оптимального префиксного кода:

  1. Глава 6 ПОНИМАНИЕ ГОЛОСОВОГО КОДА АНАЛИЗ ГОЛОСОВОГО КОДА
  2. Глава 6 ПОНИМАНИЕ ГОЛОСОВОГО КОДА АНАЛИЗ ГОЛОСОВОГО КОДА
  3. Глава 5 ПОНИМАНИЕ РЕЧЕВОГО КОДА АНАЛИЗ РЕЧЕВОГО КОДА
  4. Глава 5 ПОНИМАНИЕ РЕЧЕВОГО КОДА АНАЛИЗ РЕЧЕВОГО КОДА
  5. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  6. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  7. АЛГОРИТМ
  8. АЛГОРИТМ УДАЧИ
  9. Алгоритм исцеления:
  10. Алгоритм избавления от боли
  11. Оптимальные условия
  12. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  13. Алгоритм обработки результатов.
  14. АКТИВАЦИЯ: УРОВЕНЬ ОПТИМАЛЬНЫЙ
  15. ПОРОГ РАЗЛИЧЕНИЯ ОПТИМАЛЬНОГО
  16. 2. Специфика и алгоритмы работы с источниками.
  17. 6.2.4. Поиск оптимальной финансовой модели СМИ
  18. 1.1.4. Оптимальная модель социальной сферы современного общества
  19. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
  20. 2.3. Принципі оптимального поєднання централізованого і локального правового регулювання