Алгоритм построения оптимального префиксного кода
Отсюда напрямую следует идея алгоритма: у* и 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.
Интересно, как жадное правило, заложенное в основу алгоритма Хаффмана (слияние букв с двумя наименьшими частотами), укладывается в структуру алго- ритма в целом. Фактически на момент слияния двух букв мы не знаем точно, какое место они займут в общем коде. Вместо этого мы просто считаем их дочерними узлами одного родителя, и этого хватает для построения новой эквивалентной за- дачи, сокращенной на одну букву.
Кроме того, алгоритм образует естественный контраст с более ранним решени- ем, приводящим к субоптимальным кодам Шеннона-Фано. Этот метод базиро- вался на нисходящей стратегии, которая прежде всего обращала внимание на раз- биение верхнего уровня в бинарном дереве, а именно на два подузла, находящиеся непосредственно под корнем. С другой стороны, алгоритм Хаффмана использует восходящий метод: он находит листья, представляющие две буквы с самой низкой частотой, а затем продолжает работу по рекурсивному принципу.
Еще по теме Алгоритм построения оптимального префиксного кода:
- Глава 6 ПОНИМАНИЕ ГОЛОСОВОГО КОДА АНАЛИЗ ГОЛОСОВОГО КОДА
- Глава 6 ПОНИМАНИЕ ГОЛОСОВОГО КОДА АНАЛИЗ ГОЛОСОВОГО КОДА
- Глава 5 ПОНИМАНИЕ РЕЧЕВОГО КОДА АНАЛИЗ РЕЧЕВОГО КОДА
- Глава 5 ПОНИМАНИЕ РЕЧЕВОГО КОДА АНАЛИЗ РЕЧЕВОГО КОДА
- Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
- Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
- АЛГОРИТМ
- АЛГОРИТМ УДАЧИ
- Алгоритм исцеления:
- Алгоритм избавления от боли
- Оптимальные условия
- § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
- Алгоритм обработки результатов.
- АКТИВАЦИЯ: УРОВЕНЬ ОПТИМАЛЬНЫЙ
- ПОРОГ РАЗЛИЧЕНИЯ ОПТИМАЛЬНОГО
- 2. Специфика и алгоритмы работы с источниками.
- 6.2.4. Поиск оптимальной финансовой модели СМИ
- 1.1.4. Оптимальная модель социальной сферы современного общества
- СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
- 2.3. Принципі оптимального поєднання централізованого і локального правового регулювання