Адаптивное кодирование Хаффмана - Adaptive Huffman coding

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

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

Алгоритмы

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

Алгоритм FGK

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

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

Алгоритм Виттера

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

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

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

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

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

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 (внутренний узел), шаг скольжения 3. Теперь мы увеличиваем вес до 9. Таким образом , сохраняется инвариант, поскольку текущий узел является внутренним узлом и должен располагаться перед листовыми узлами с равным весом, поскольку мы увеличили вес.

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

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:

Начните с пустого дерева.

Для "a" передайте его двоичный код.

Шаг 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.

Для удобства объяснения этот шаг не совсем соответствует алгоритму Виттера, но эффекты эквивалентны.

Шаг 4:

Перейдите к листовому узлу 253. Обратите внимание, что у нас есть два блока с весом 1. Узлы 253 и 254 - это один блок (состоящий из листьев), узел 255 - это другой блок (состоящий из внутренних узлов). Для узла 253 наибольшее число в его блоке - 254, поэтому поменяйте местами веса и символы узлов 253 и 254. Теперь узел 254 и ветвь, начинающаяся с узла 255, удовлетворяют условию SlideAndIncrement и, следовательно, должны быть поменяны местами. Наконец увеличьте вес узла 255 и 256.

Будущий код для «b» - 1, а для «a» теперь - 01, что отражает их частоту.

Рекомендации

• Оригинальная статья Виттера: JS Vitter, « Design and Analysis of Dynamic Huffman Codes », Journal of the ACM, 34 (4), October 1987, pp 825–845.
• Дж. С. Виттер, "АЛГОРИТМ 673 Динамическое кодирование Хаффмана", Транзакции ACM в математическом программном обеспечении, 15 (2), июнь 1989 г., стр. 158–167. Также появляется в Сборнике алгоритмов ACM.
• Дональд Э. Кнут, «Динамическое кодирование Хаффмана», Журнал алгоритмов, 6 (2), 1985, стр. 163–180.

Внешние ссылки

•  Эта статья включает материалы, являющиеся общественным достоянием  из  документа NIST :  Блэк, Пол Э. «Адаптивное кодирование Хаффмана» . Словарь алгоритмов и структур данных .
• Сайт Калифорнийского университета Дэна Хиршберга
• Кардиффский университет Сайт доктора Дэвида Маршалла
• C реализация алгоритма Виттера
• Отличное описание от Университета Дьюка