Адаптивное кодирование Хаффмана
Адаптивное кодирование Хаффмана (также называемое динамическим кодированием Хаффмана ) — это метод адаптивного кодирования, основанный на кодировании Хаффмана . Это позволяет строить код по мере передачи символов, не имея начальных знаний о распространении источников, что позволяет осуществлять однопроходное кодирование и адаптацию к изменяющимся условиям в данных. [1]
Преимущество однопроходной процедуры в том, что исходный код может быть закодирован в реальном времени, однако он становится более чувствительным к ошибкам передачи, поскольку всего лишь одна потеря разрушает весь код, требуя обнаружения и исправления ошибок .
Алгоритмы
[ редактировать ]Существует ряд реализаций этого метода, наиболее заметными из которых являются алгоритм FGK ( Фаллер - Галлагер - Кнут ) и алгоритм Виттера .
Алгоритм ФГК
[ редактировать ]Это метод онлайн-кодирования, основанный на кодировании Хаффмана. Не имея начальных знаний о частотах появления, он позволяет динамически корректировать дерево Хаффмана по мере передачи данных. В дереве FGK Huffman специальный внешний узел, называемый 0-узлом , используется для идентификации нового персонажа. То есть всякий раз, когда встречаются новые данные, выведите путь к 0-узлу, за которым следуют данные. Для персонажа прошлого просто выведите путь к данным в текущем дереве Хаффмана. Самое главное, мы должны при необходимости скорректировать дерево FGK Huffman и, наконец, обновить частоту связанных узлов. По мере увеличения частоты данных родственные свойства дерева Хаффмана могут нарушаться. По этой причине срабатывает регулировка. Это достигается путем последовательной замены узлов, поддеревьев или того и другого. Узел данных заменяется узлом самого высокого порядка той же частоты в дереве Хаффмана (или поддеревом, корнем которого является узел самого высокого порядка). Все родительские узлы узла также должны обрабатываться таким же образом.
Поскольку алгоритм FGK имеет некоторые недостатки в отношении замены узлов или поддеревьев, Виттер предложил другой алгоритм для его улучшения.
Алгоритм Виттера
[ редактировать ]Некоторые важные термины и ограничения: -
- Неявная нумерация : это просто означает, что узлы нумеруются в порядке возрастания уровня и слева направо. т.е. узлы нижнего уровня будут иметь меньшее неявное число по сравнению с узлами верхнего уровня, а узлы на том же уровне нумеруются в порядке возрастания слева направо. Другими словами, когда мы построили дерево Хаффмана, при объединении двух узлов в родительский узел мы установили узел с меньшим значением в качестве левого дочернего элемента, а узел с более высоким значением — в качестве правого дочернего элемента.
- Инвариант : для каждого веса w все листья веса w предшествуют всем внутренним узлам, имеющим вес w. Другими словами, когда мы строили дерево Хаффмана, если несколько узлов имели одинаковое значение, мы отдавали приоритет слиянию листьев над внутренними узлами.
- Блоки : узлы одинакового веса и типа (т. е. листовой узел или внутренний узел) образуют блок.
- Лидер : узел с наибольшим номером в блоке.
Блоки связаны между собой по возрастанию их весов.
Листовой блок всегда предшествует внутреннему блоку того же веса, таким образом сохраняя инвариант.
NYT (Not Yet Transferred) — это специальный узел, используемый для представления символов, которые «еще не переданы» .
algorithm for adding a symbol is leaf_to_increment := NULL p := pointer to the leaf node containing the next symbol if (p is NYT) then Extend p by adding two children Left child becomes new NYT and right child is the new symbol leaf node p := parent of new symbol leaf node leaf_to_increment := Right Child of p else Swap p with leader of its block if (new p is sibling to NYT) then leaf_to_increment := p p := parent of p while (p ≠ NULL) do Slide_And_Increment(p) if (leaf_to_increment != NULL) then Slide_And_Increment(leaf_to_increment)
function Slide_And_Increment(p) is previous_p := parent of p if (p is an internal node) then Slide p in the tree higher than the leaf nodes of weight wt + 1 increase weight of p by 1 p := previous_p else Slide p in the tree higher than the internal nodes of weight wt increase weight of p by 1 p := new parent of p.
Кодер и декодер начинаются только с корневого узла, имеющего максимальное число. Вначале это наш первоначальный узел NYT.
Когда мы передаем символ NYT, мы должны передать код для узла NYT, а затем для его общего кода.
Для каждого символа, который уже есть в дереве, нам нужно передать только код его листового узла.
Пример
[ редактировать ]
Кодировка «abb» дает 01100001 001100010 11.
Шаг 1:
Начните с пустого дерева.
Для «а» передайте его двоичный код.
Шаг 2:
NYT порождает два дочерних узла: 254 и 255, оба с весом 0. Увеличьте вес для корня и 255. Код для «a», связанного с узлом 255, равен 1.
Для «b» передайте 0 (для узла NYT), а затем его двоичный код.
Шаг 3:
NYT порождает два дочерних узла: 252 для NYT и 253 для листового узла, оба с весом 0. Увеличьте веса для 253, 254 и корневого узла. Чтобы сохранить инвариант Виттера, согласно которому все листья веса w предшествуют (в неявной нумерации) всем внутренним узлам веса w, ветвь, начинающаяся с узла 254, должна поменяться местами (с точки зрения символов и весов, но не порядка чисел) с узлом 255. Код для «b» — 11.
Для второго «б» передайте 11.
Для удобства объяснения этот шаг не совсем соответствует алгоритму Виттера. [2] но эффекты эквивалентны.
Шаг 4:
Перейдите к листовому узлу 253. Обратите внимание, что у нас есть два блока с весом 1. Узел 253 и 254 — это один блок (состоящий из листьев), узел 255 — это другой блок (состоящий из внутренних узлов). Для узла 253 самое большое число в его блоке равно 254, поэтому поменяйте местами веса и символы узлов 253 и 254. Теперь узел 254 и ветвь, начинающаяся с узла 255, удовлетворяют условию SlideAndIncrement. [2] и, следовательно, должны быть заменены. Наконец увеличьте вес узлов 255 и 256.
Будущий код для «b» — 1, а для «a» теперь — 01, что отражает их частоту.
Ссылки
[ редактировать ]- ^ Цзэнянь Ли; Марк С. Дрю; Цзянчуань Лю (9 апреля 2014 г.). Основы мультимедиа . Springer Science & Business Media. ISBN 978-3-319-05290-8 .
- ^ Jump up to: а б «Адаптивное кодирование Хаффмана» . Cs.duke.edu . Проверено 26 февраля 2012 г.
- Оригинальная статья Виттера: Дж. С. Виттер, « Разработка и анализ динамических кодов Хаффмана », Журнал ACM, 34 (4), октябрь 1987 г., стр. 825–845.
- Дж. С. Виттер, «АЛГОРИТМ 673 Динамическое кодирование Хаффмана», Транзакции ACM в математическом программном обеспечении, 15 (2), июнь 1989 г., стр 158–167. Также появляется в Сборнике алгоритмов ACM.
- Дональд Э. Кнут, «Динамическое кодирование Хаффмана», Journal of Algorithm, 6 (2), 1985, стр. 163–180.
Внешние ссылки
[ редактировать ]
В этой статье использованы общедоступные материалы из Пол Э. Блэк. «адаптивное кодирование Хаффмана» . Словарь алгоритмов и структур данных . НИСТ . - Сайт Дэна Хиршберга Калифорнийского университета
- Сайт доктора Дэвида Маршалла Кардиффского университета
- C реализация алгоритма Виттера
- Отличное описание из Университета Дьюка
сжатия данных Методы | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| без потерь |
| ||||||||
| с потерями |
| ||||||||
| Аудио |
| ||||||||
| Изображение |
| ||||||||
| Видео |
| ||||||||
| Теория | |||||||||
| Сообщество | |||||||||
| Люди | |||||||||
