Алгоритм Краскала, Прима для нахождения минимального остовного дерева

Канонические коды Хаффмана[править | править код]

Проблема обычного алгоритма сжатия по Хаффману — недетерминированность. Для похожих последовательностей могут получиться разные деревья, так и одно дерево без правильной сериализации может соответствовать разным последовательностям. Для избежания применяют канонические коды Хаффмана.
В этом алгоритме не строится дерево Хаффмана^[3].
Состоит из двух этапов:

Подсчёт длины кода для какого-то символа Составление кода.

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

Подсчёт длины[править | править код]

Составление кода[править | править код]

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