Адаптивное кодирование Хаффмана

Адаптивное кодирование Хаффмана (также называемое динамическим кодированием Хаффмана ) — это метод адаптивного кодирования, основанный на кодировании Хаффмана . Это позволяет строить код по мере передачи символов, не имея начальных знаний о распространении источников, что позволяет осуществлять однопроходное кодирование и адаптацию к изменяющимся условиям в данных. ^[1]

Преимущество однопроходной процедуры в том, что исходный код может быть закодирован в реальном времени, однако он становится более чувствительным к ошибкам передачи, поскольку всего лишь одна потеря разрушает весь код, требуя обнаружения и исправления ошибок .

Алгоритмы [ править ]

Существует ряд реализаций этого метода, наиболее заметными из которых являются алгоритм FGK ( Фаллер - Галлагер - Кнут ) и Виттера алгоритм .

Алгоритм ФГК [ править ]

Это метод онлайн-кодирования, основанный на кодировании Хаффмана. Не имея начальных знаний о частотах появления, он позволяет динамически корректировать дерево Хаффмана по мере передачи данных. В дереве FGK Хаффмана специальный внешний узел, называемый 0-узлом , используется для идентификации нового персонажа. То есть всякий раз, когда встречаются новые данные, выведите путь к 0-узлу, за которым следуют данные. Для персонажа прошлого просто выведите путь к данным в текущем дереве Хаффмана. Самое главное, нам нужно при необходимости скорректировать дерево ФГК Хаффмана и, наконец, обновить частоту связанных узлов. По мере увеличения частоты данных родственные свойства дерева Хаффмана могут нарушаться. По этой причине срабатывает регулировка. Это достигается путем последовательной замены узлов, поддеревьев или того и другого. Узел данных заменяется узлом самого высокого порядка той же частоты в дереве Хаффмана (или поддеревом, корнем которого является узел самого высокого порядка). Все родительские узлы узла также должны обрабатываться таким же образом.

Поскольку алгоритм FGK имеет некоторые недостатки в отношении замены узлов или поддеревьев, Виттер предложил другой алгоритм для его улучшения.

Алгоритм Виттера [ править ]

Некоторые важные термины и ограничения: -

Неявная нумерация : это просто означает, что узлы нумеруются в порядке возрастания уровня и слева направо. т.е. узлы нижнего уровня будут иметь меньшее неявное число по сравнению с узлами верхнего уровня, а узлы на том же уровне нумеруются в порядке возрастания слева направо. Другими словами, когда мы построили дерево Хаффмана, при объединении двух узлов в родительский узел мы установили узел с меньшим значением в качестве левого дочернего элемента, а узел с более высоким значением — в качестве правого дочернего элемента.
Инвариант : для каждого веса w все листья веса w предшествуют всем внутренним узлам, имеющим вес w. Другими словами, когда мы строили дерево Хаффмана, если несколько узлов имели одинаковое значение, мы отдавали приоритет слиянию листьев над внутренними узлами.
Блоки : узлы одинакового веса и типа (т. е. листовой узел или внутренний узел) образуют блок.
Лидер : узел с наибольшим номером в блоке.

Блоки связаны между собой по возрастанию их весов.

Листовой блок всегда предшествует внутреннему блоку того же веса, таким образом сохраняя инвариант.

NYT (Not Yet Transferred) — это специальный узел, используемый для представления символов, которые «еще не переданы» .

Начинается скольжение Slide_And_Increment(листовой узел). P — листовой узел.

Slide_And_Increment(листовой узел) шаг скольжения 2. Поскольку P является листовым узлом, он скользит перед узлами следующего блока равного веса.

Slide_And_Increment(листовой узел) шаг скольжения 3. Здесь мы увеличиваем текущий вес на 1.

Slide_And_Increment(листовой узел) шаг скольжения 4. Метод подходит к концу. P — новый родитель.

Начинается скольжение Slide_And_Increment(внутренний узел). P — внутренний узел.

Slide_And_Increment (внутренний узел) шаг скольжения 2. Узел P перемещается перед следующим блоком узлов листьев с весом wt+1.

Slide_And_Increment (внутренний узел), шаг скольжения 4. Теперь «P» указывает на бывшего родителя (как в случае внутреннего узла в соответствии с алгоритмом)

алгоритм  добавления  символа 
      Leaf_to_increment := NULL 
      p := указатель на листовой узел, содержащий следующий символ 

      если  (p — Нью-Йорк Таймс),  то 
          Расширьте p, добавив двух дочерних элементов. 
          Левый дочерний элемент становится новым NYT, а правый дочерний элемент – новым узлом листа символа. 
          p  := родительский элемент нового листового узла символа 
          Leaf_to_increment := Правый дочерний элемент p 
      еще 
          Поменяйте местами p с лидером своего блока. 
          если  (новый p является родственным NYT),  то 
              Leaf_to_increment := p 
              p  := родительский элемент p 

      пока  (p ≠ NULL)  делайте 
          Слайд_И_Инкремент(п) 

      если  (leaf_to_increment != NULL)  , то 
          Slide_And_Increment(leaf_to_increment)

функция  Slide_And_Increment(p  ) 
      previous_p := родительский элемент  p 

     if  (p — внутренний узел)  , то 
          Сдвиньте p в дереве выше, чем листовые узлы веса wt + 1. 
          увеличить вес  p  на 1 
          р  := предыдущий_р 
      еще 
          Сдвиньте p в дереве выше внутренних узлов веса wt. 
          увеличить вес  p  на 1 
          p  := новый родительский элемент  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 .
^ Перейти обратно: ^а ^б «Адаптивное кодирование Хаффмана» . 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 реализация алгоритма Виттера
Отличное описание из Университета Дьюка

[LiDrew2014-1] Цзэнянь Ли; Марк С. Дрю; Цзянчуань Лю (9 апреля 2014 г.). Основы мультимедиа . Springer Science & Business Media. ISBN 978-3-319-05290-8 .

[:0-2] Перейти обратно: ^а ^б «Адаптивное кодирование Хаффмана» . Cs.duke.edu . Проверено 26 февраля 2012 г.

[1]

[2]