Адаптивное кодирование Хаффмана
Метод сжатия данных

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

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

Алгоритмы

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

Алгоритм FGK

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

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

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

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

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

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

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

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

Slide_And_Increment(листовой узел) начинается скольжение. P — листовой узел.
Slide_And_Increment(leaf node) шаг скольжения 2. Поскольку P является листовым узлом, он скользит перед следующими блочными узлами равного веса.
Slide_And_Increment(leaf node) скользящий шаг 3. Здесь мы увеличиваем текущий вес на 1.
Slide_And_Increment(leaf node) скользящий шаг 4. Метод завершается. P — новый родительский узел.
Slide_And_Increment(внутренний узел) начинается скольжение. P — внутренний узел.
Slide_And_Increment(внутренний узел) шаг скольжения 2. Узел P скользит перед следующим блоком узлов-листьев с весом wt+1.
Slide_And_Increment(внутренний узел) скользящий шаг 3. Теперь мы увеличиваем вес до 9. Таким образом, инвариант сохраняется, поскольку текущий узел является внутренним узлом и должен располагаться перед конечными узлами равного веса, поскольку мы увеличили вес.
Slide_And_Increment(внутренний узел) шаг скольжения 4. Теперь «P» указывает на бывшего родителя (как в случае внутреннего узла согласно алгоритму)
Алгоритм добавления символа : лист_для_приращения := NULL p := указатель на конечный узел, содержащий следующий символ если (p — NYT), то Расширить p, добавив двух потомков Левый потомок становится новым NYT, а правый потомок — новым конечным узлом символа. p  := родительский узел нового символа leaf_to_increment := Правый потомок p еще Поменять p с лидером его блока если (новый p является родственным NYT), то лист_для_приращения := p p  := родитель p пока (p ≠ NULL) делать Слайд_И_Инкремент(p) если (leaf_to_increment != NULL) тогда Скольжение_и_увеличение(leaf_to_increment)
функция Slide_And_Increment(p) — это previous_p := parent p если (p — внутренний узел), то Сдвиньте p в дереве выше листовых узлов веса wt + 1 увеличить вес p на 1 p  := previous_p иначе Сдвиньте 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, что отражает их частоту.

Ссылки

  1. ^ Ze-Nian Li; Mark S. Drew; Jiangchuan Liu (9 апреля 2014 г.). Основы мультимедиа. Springer Science & Business Media. ISBN 978-3-319-05290-8.
  2. ^ ab "Адаптивное кодирование Хаффмана". Cs.duke.edu . Получено 2012-02-26 .
  • Оригинальная статья Виттера: JS Vitter, «Проектирование и анализ динамических кодов Хаффмана», Journal of the ACM, 34(4), октябрь 1987 г., стр. 825–845.
  • JS Vitter, "ALGORITHM 673 Dynamic Huffman Coding", ACM Transactions on Mathematical Software, 15(2), июнь 1989 г., стр. 158–167. Также появляется в Collected Algorithms of ACM.
  • Дональд Э. Кнут, «Динамическое кодирование Хаффмана», Журнал алгоритмов, 6(2), 1985, стр. 163–180.
Взято с "https://en.wikipedia.org/w/index.php?title=Адаптивное_кодирование_Хаффмана&oldid=1188793083"