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

Опубликовано: 1 Декабря, 2021

Предварительные требования: кодирование Хаффмана, декодирование Хаффмана
Адаптивное кодирование Хаффмана также известно как динамическое кодирование Хаффмана. Реализация выполняется с использованием алгоритма Виттера.

Кодирование

Адаптивное кодирование Хаффмана для строки, содержащей алфавиты:
Пусть m будет общим количеством алфавитов. Итак, m = 26.
Для алгоритма Виттера найдите такие параметры e & r, что

m = 2 e + r и 0 ≤ r ≤ 2 e
Следовательно, для m = 26 получаем e = 4 & r = 10

Существует два типа кода NYT Code и Fixed Code.

Код NYT = Переход по дереву от корневого узла к этому конкретному узлу NYT.

Для фиксированного кода он может быть рассчитан из следующих двух условий:

  1. Если 0 ≤ k ≤ 2r, тогда буква Sk кодируется как двоичное представление (k-1) в (e + 1) битах. (где k - позиция алфавита в отсортированном порядке)
  2. В противном случае буква Sk кодируется как двоичное представление (kr-1) в e битах.

Обновление дерева
Обновление дерева в алгоритме Виттера следует за неявной нумерацией. В неявной нумерации

  • Узлы нумеруются в порядке возрастания, т. Е. По уровню и слева направо.
  • Узлы с одинаковым весом и типом вместе образуют блок.
  • Блоки связаны друг с другом как по возрастанию их веса.
  • Внутренний узел представлен овальной формой. Вес внутренних узлов = Сумма весов дочерних узлов
  • Внешний узел представлен квадратной формой. Вес внешних узлов = Первоначально 1, при повторении затем увеличивал вес на 1

Шаги по обновлению дерева:

  1. Инициализируйте дерево с помощью узла NYT
  2. Поскольку символ распознается впервые, исходный узел NYT далее делится на узел NYT, и новый узел инициализируется этим символом и имеет вес = 1.
  3. Назначьте сумму веса дочерних узлов родительскому узлу
  4. Если встречается повторяющийся символ, то веса обновляются до этого символа.

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

Пример

code = "трубкозуб"
Окончательный код, который мы получаем:
00000 1 010001 0000011 0001011 0 10 110001010
  трубкозуб

Объяснение:
Для строкового кода = «муравьед», e = 5, r = 10
Как показано на изображении выше, дерево инициализируется узлом NYT с весом 0.

  1. Для символа «а» k = 1.
    NYT Code = "" (изначально дерево пусто)
    

    Для фиксированного кода: поскольку k <2r, т. Е. 1 <2 * 10, удовлетворяет условию (1)
    Итак, фиксированный код - это двоичное представление (k-1) = 0 в виде 5-битного представления.

     Фиксированный код = "00000"
     Код Хаффмана для символа "a" - "00000".
  2. Для символа «а», который уже существует в дереве. Пройдя по дереву до символа «a», мы получим code = «1».
     Код Хаффмана для символа "a" - "1".
  3. Для символа 'r' k = 18.
     Код NYT = "0" (переход до узла NYT)

    Для фиксированного кода: поскольку k> 2r, т.е. 18> 2 * 10, удовлетворяйте условию (2)
    Итак, фиксированный код - это двоичное представление (k-1 = 17) как 5-битное представление



     Фиксированный код = "10001"
     Код Хаффмана для символа "r" - "010001".
  4. Для символа d k = 4.
     Код NYT = "000" (переход до узла NYT)

    Для фиксированного кода: поскольку k <2r, т. Е. 4 <2 * 10, удовлетворяют условию (1)
    Итак, фиксированный код - это двоичное представление (k-1 = 3) как 5-битное представление

     Фиксированный код = «00011»
     Код Хаффмана = "00000011"
  5. Для символа «v» k = 22.
     Код NYT = "000" (переход до узла NYT)

    Для фиксированного кода: поскольку k> 2r, т.е. 22> 2 * 10, удовлетворяйте условию (2)
    Итак, фиксированный код - это двоичное представление (kr-1 = 11) в виде 4-битного представления.

     Фиксированный код = "1011"
     Код Хаффмана = "0001011"
  6. Поменяйте местами узел левого поддерева и правого, поскольку дерево нарушает свойство
  7. Для символа «а», который уже существует в дереве. Пройдя по дереву до символа «а», мы получим код = «0».
     Код Хаффмана для символа 'a' равен "0"
  8. Для символа «r», который уже существует в дереве. Пройдя по дереву до символа «а», мы получим код = «10».
     Код Хаффмана для символа 'r' - "10".
  9. Для символа «k» k = 11.
     Код NYT = "1100" (переход до узла NYT)

    Для фиксированного кода: поскольку k <2r, т. Е. 11 <2 * 10, удовлетворяет условию (1)
    Итак, фиксированный код - это двоичное представление (k-1 = 10) как 5-битное представление

     Фиксированный код = "01010"
     Код Хаффмана для символа "r" - "110001010".

Расшифровка

Шаги для декодирования:

  1. Прочитать двоичную строку
  2. Если встречается листовой узел, это NYT
    • Прочитать следующие е биты
      1. Если значение бита e <r, то для получения необходимого символа преобразуйте (e + 1) бит в десятичное значение (e + 1) бит + 1
      2. Если значение e бита> r, то для получения необходимого символа преобразуйте e битов в десятичное значение e бит + r + 1

Пример:

code = "00000101000100000110001011010110001010"
Получаем окончательный декодированный код как
 00000 1 0 10001 00 00011 000 1011 0 10 1100 01010
   aa NYT r NYT d NYT var NYT k

Объяснение:

  • Начните декодирование с чтения первых e битов. Итак, первые 4 бита - 0000, что означает десятичное значение = 0.
    Теперь значение 0 <r, т.е. 0 <10 удовлетворяет условию (1).
    Теперь согласно условию (1) преобразуйте первый бит e + 1 = 5 в десятичный и прибавьте к нему 1.
     00000 = 0
    0 + 1 = 1, что является значением для алфавита a.
    

    Обновите дерево и добавьте в дерево узел для символа 'a'

  • Прочтите следующий бит в данном коде и пройдите по дереву. Мы достигаем внешнего листового узла «а». Итак, следующий декодированный символ - это «а».
  • Прочтите следующий набор бит данного кода и пройдитесь по дереву. У нас 0 как узел NYT. Достигнув узла NYT, считайте e битов, которые равны 1000. Преобразуйте 1000 в десятичное значение 8. Поскольку 8 <r удовлетворяет условию (1).
    Теперь преобразуйте бит e + 1 в десятичное и прибавьте к нему 1.
    10001 = 17
    17 + 1 = 18, что является значением для алфавита r.
    

    Обновите дерево и добавьте в него узел для символа «r».

  • При чтении следующего набора битов и обходе Дерева мы достигаем узла NYT в 00. Считываем биты e, которые равны 0001. Преобразование 0001 в десятичное число равно 1. Поскольку 1 <r удовлетворяет условию (1).
    Теперь преобразуйте бит e + 1 в десятичное и прибавьте к нему 1.
    00011 = 3
    3 + 1 = 4, что является значением алфавита d.
    

    Обновите дерево и добавьте в него узел для символа «d».

  • Читая следующий набор битов и проходя по дереву, мы достигаем узла NYT в 000. Считываем биты e, которые равны 1011. Преобразование 1011 в десятичное число равно 11. Поскольку 11> r удовлетворяет условию (2).
    Теперь преобразуйте k + r + 1 бит в десятичное и расшифруйте символ.
    10110 = 22, что соответствует алфавиту v.
    

    Обновите дерево и добавьте в дерево узел для символа «v».

  • Читая следующий набор битов и проходя по дереву, мы получаем символ «а» в 0. Обновите дерево и добавьте в дерево узел для символа «а».
  • Читая следующий набор битов и проходя по дереву, мы получаем символ «r» на уровне 10. Обновим дерево и добавим в дерево узел для символа «a».
  • Читая следующий набор битов и проходя по дереву, мы достигаем узла NYT на 1100. Считываем e битов, которые равны 0101. Преобразование 0101 в десятичное число равно 9. Поскольку 9 <r удовлетворяет условию (1).
    Теперь преобразуйте бит e + 1 в десятичное и прибавьте к нему 1.
    01000 = 8, 
    8 + 1 = 9. что является значением для алфавита k.
    

    Обновите дерево и добавьте в дерево узел для символа «v».

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по доступной для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.