Адаптивное кодирование и декодирование Хаффмана
Предварительные требования: кодирование Хаффмана, декодирование Хаффмана
Адаптивное кодирование Хаффмана также известно как динамическое кодирование Хаффмана. Реализация выполняется с использованием алгоритма Виттера.
Кодирование
Адаптивное кодирование Хаффмана для строки, содержащей алфавиты:
Пусть 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.
Для фиксированного кода он может быть рассчитан из следующих двух условий:
- Если 0 ≤ k ≤ 2r, тогда буква Sk кодируется как двоичное представление (k-1) в (e + 1) битах. (где k - позиция алфавита в отсортированном порядке)
- В противном случае буква Sk кодируется как двоичное представление (kr-1) в e битах.
Обновление дерева
Обновление дерева в алгоритме Виттера следует за неявной нумерацией. В неявной нумерации
- Узлы нумеруются в порядке возрастания, т. Е. По уровню и слева направо.
- Узлы с одинаковым весом и типом вместе образуют блок.
- Блоки связаны друг с другом как по возрастанию их веса.
- Внутренний узел представлен овальной формой. Вес внутренних узлов = Сумма весов дочерних узлов
- Внешний узел представлен квадратной формой. Вес внешних узлов = Первоначально 1, при повторении затем увеличивал вес на 1
Шаги по обновлению дерева:
- Инициализируйте дерево с помощью узла NYT
- Поскольку символ распознается впервые, исходный узел NYT далее делится на узел NYT, и новый узел инициализируется этим символом и имеет вес = 1.
- Назначьте сумму веса дочерних узлов родительскому узлу
- Если встречается повторяющийся символ, то веса обновляются до этого символа.
Примечание: во время обновления в дереве, если вес левого поддерева больше, чем правого поддерева, то узлы необходимо поменять местами.
Пример
code = "трубкозуб" Окончательный код, который мы получаем: 00000 1 010001 0000011 0001011 0 10 110001010 трубкозуб
Объяснение:
Для строкового кода = «муравьед», e = 5, r = 10
Как показано на изображении выше, дерево инициализируется узлом NYT с весом 0.
- Для символа «а» k = 1.
NYT Code = "" (изначально дерево пусто)
Для фиксированного кода: поскольку k <2r, т. Е. 1 <2 * 10, удовлетворяет условию (1)
Итак, фиксированный код - это двоичное представление (k-1) = 0 в виде 5-битного представления.Фиксированный код = "00000"
Код Хаффмана для символа "a" - "00000".
- Для символа «а», который уже существует в дереве. Пройдя по дереву до символа «a», мы получим code = «1».
Код Хаффмана для символа "a" - "1".
- Для символа 'r' k = 18.
Код NYT = "0" (переход до узла NYT)
Для фиксированного кода: поскольку k> 2r, т.е. 18> 2 * 10, удовлетворяйте условию (2)
Итак, фиксированный код - это двоичное представление (k-1 = 17) как 5-битное представлениеФиксированный код = "10001"
Код Хаффмана для символа "r" - "010001".
- Для символа d k = 4.
Код NYT = "000" (переход до узла NYT)
Для фиксированного кода: поскольку k <2r, т. Е. 4 <2 * 10, удовлетворяют условию (1)
Итак, фиксированный код - это двоичное представление (k-1 = 3) как 5-битное представлениеФиксированный код = «00011»
Код Хаффмана = "00000011"
- Для символа «v» k = 22.
Код NYT = "000" (переход до узла NYT)
Для фиксированного кода: поскольку k> 2r, т.е. 22> 2 * 10, удовлетворяйте условию (2)
Итак, фиксированный код - это двоичное представление (kr-1 = 11) в виде 4-битного представления.Фиксированный код = "1011"
Код Хаффмана = "0001011"
- Поменяйте местами узел левого поддерева и правого, поскольку дерево нарушает свойство
- Для символа «а», который уже существует в дереве. Пройдя по дереву до символа «а», мы получим код = «0».
Код Хаффмана для символа 'a' равен "0"
- Для символа «r», который уже существует в дереве. Пройдя по дереву до символа «а», мы получим код = «10».
Код Хаффмана для символа 'r' - "10".
- Для символа «k» k = 11.
Код NYT = "1100" (переход до узла NYT)
Для фиксированного кода: поскольку k <2r, т. Е. 11 <2 * 10, удовлетворяет условию (1)
Итак, фиксированный код - это двоичное представление (k-1 = 10) как 5-битное представлениеФиксированный код = "01010"
Код Хаффмана для символа "r" - "110001010".
Расшифровка
Шаги для декодирования:
- Прочитать двоичную строку
- Если встречается листовой узел, это NYT
- Прочитать следующие е биты
- Если значение бита e <r, то для получения необходимого символа преобразуйте (e + 1) бит в десятичное значение (e + 1) бит + 1
- Если значение 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.