Изменения
Перейти к навигации
Перейти к поиску
Строка 65:
Строка 65: + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
Добавил про канонические коды.
После перестановки операция увеличения веса узлов продолжается дальше. Следующий узел, вес которого будет увеличен алгоритмом, — это новый родитель узла, увеличение веса которого вызвало перестановку.
После перестановки операция увеличения веса узлов продолжается дальше. Следующий узел, вес которого будет увеличен алгоритмом, — это новый родитель узла, увеличение веса которого вызвало перестановку.
== Канонические коды Хаффмана ==
Проблема обычного алгоритма сжатия по Хаффману — недетерминированность. Для похожих последовательностей могут получиться разные деревья, так и одно дерево без правильной сериализации может соответствовать разным последовательностям. Для избежания применяют канонические коды Хаффмана.
В этом алгоритме не строится дерево Хаффмана.
Состоит из двух этапов:
{|
|
# Подсчёт длины кода для какого-то символа
# Составление кода.
|}
=== Подсчёт длины ===
{|
|
# Посчитаем частоту для каждого символа
# Отсортируем их в лексикографическом порядке.
# В массив запишем частоту каждой буквы.
# Слева приписываем массив той же длины, но с порядковыми номерами из правого массива. Левый массив получается списком указателей на элементы правой части.
# В левой части делаем не [[Двоичная куча|возрастающую пирамиду]]. Но heap будет не по значению элементов массива, а по значению на ссылаемый элемент массива.
# Самый левый элемент указывает на символ из правого массива с наименьшей частотой. Его можно удалить следующим образом:
## Правую половину не трогаем
## Первый элемент массива заменяем на самый правый элемент левого массива, якобы сдвигая границу разделения.
## Проверяем условия правильности пирамиды, если что-то не так, то надо повторить «хипизацию».
## Убирается первый элемент левой части массива и объединяется ранее убранным. Сумма их частот записывается в границу между левым и правым массивом.
## На место удалённого элемента в левой части записывается индекс массива куда добавили сумму частот на прошлом шаге.
## Из-за того объединили два элемента нужно изменить значения этих элементов массива ссылкой на родителя, куда их положили.
# Повторяем, в куче слева не останется 1 элемент.
# В правой части массива получились ссылки на элементы, объеднияющие 2 символа. Поэтому идём по массиву по ссылкам, инкрементируя уровень погружения.
# Количество переходов по ссылкам будет длина кода Хаффмана.
|}
=== Составление кода ===
{|
|
# Расположим элементы в лексикографическом порядке.
# Составим таблицу, состоящую из блоков, начиная с самой большой длины кода. Каждый блок будет содержать элементы с одинаковой длиной кода.
# Самый первый символ таблицы кодируется нулями.
# В каждом блоке символы будут находиться в лексикографическом порядке.
# Коды в блоке будут иметь двоичный вид и отличаться на 1.
# При переходе в следующий блок, биты кода самого последнего символа отсекаются и добавляется 1.
|}
== Биграммная модель ==
== Биграммная модель ==