Изменения

Один из первых алгоритмов эффективного кодирования информации был предложен Д. А. Хаффманом в 1952 году. Идея алгоритма состоит в следующем: зная вероятности появления символов в сообщении, можно описать процедуру построения кодов переменной длины, состоящих из целого количества битов. Символам с большей вероятностью ставятся в соответствие более короткие коды. Коды Хаффмана обладают свойством [[Префиксный код|префиксности]] (то есть ни одно кодовое слово не является префиксом другого), что позволяет однозначно их декодировать.

Один из первых алгоритмов эффективного кодирования информации был предложен Д. А. Хаффманом в 1952 году. Идея алгоритма состоит в следующем: зная вероятности появления символов в сообщении, можно описать процедуру построения кодов переменной длины, состоящих из целого количества битов. Символам с большей вероятностью ставятся в соответствие более короткие коды. Коды Хаффмана обладают свойством [[Префиксный код|префиксности]] (то есть ни одно кодовое слово не является префиксом другого), что позволяет однозначно их декодировать.

Классический алгоритм Хаффмана на входе получает таблицу частот встречаемости символов в сообщении. Далее на основании этой таблицы строится дерево кодирования Хаффмана (Н-дерево).<ref>Д. Мастрюков. [http://www.compression.ru/download/articles/huff/mastrukov_1993_huffman.pdf Монитор 7-8.93]</ref>

Классический алгоритм Хаффмана на входе получает таблицу [[частотность|частотностей]] символов в сообщении. Далее на основании этой таблицы строится дерево кодирования Хаффмана (Н-дерево).<ref>Д. Мастрюков. [http://www.compression.ru/download/articles/huff/mastrukov_1993_huffman.pdf Монитор 7-8.93]</ref>

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

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

# Выбираются два свободных узла дерева с наименьшими весами.

# Выбираются два свободных узла дерева с наименьшими весами.

# Шаги, начиная со второго, повторяются до тех пор, пока в списке свободных узлов не останется только один свободный узел. Он и будет считаться корнем дерева.

# Шаги, начиная со второго, повторяются до тех пор, пока в списке свободных узлов не останется только один свободный узел. Он и будет считаться корнем дерева.

Допустим, у нас есть следующая таблица частот:

Допустим, у нас есть следующая таблица абсолютных частотностей:

{| class="wikitable"

{| class="wikitable"

!Символ

!Символ

!Д

!Д

|-

|-

!Частота

!Абсолютная частотность

| 15 || 7 || 6 || 6 || 5

| 15 || 7 || 6 || 6 || 5

|}

|}

Поскольку ни один из полученных кодов не является префиксом другого, они могут быть однозначно декодированы при чтении их из потока. Кроме того, наиболее частый символ сообщения А закодирован наименьшим количеством бит, а наиболее редкий символ Д — наибольшим.

Поскольку ни один из полученных кодов не является префиксом другого, они могут быть однозначно декодированы при чтении их из потока. Кроме того, наиболее частый символ сообщения А закодирован наименьшим количеством бит, а наиболее редкий символ Д — наибольшим.

При этом общая длина сообщения, состоящего из приведённых в таблице символов, составит 87 бит (в среднем 2,2308 бита на символ). При использовании равномерного кодирования общая длина сообщения составила бы 117 бит (ровно 3 бита на символ). Заметим, что [[Информационная энтропия|энтропия]] источника, независимым образом порождающего символы с указанными частотами, составляет ~2,1858 бита на символ, то есть [[Избыточность информации|избыточность]] построенного для такого источника кода Хаффмана, понимаемая как отличие среднего числа бит на символ от энтропии, составляет менее 0,05 бит на символ.

При этом общая длина сообщения, состоящего из приведённых в таблице символов, составит 87 бит (в среднем 2,2308 бита на символ). При использовании равномерного кодирования общая длина сообщения составила бы 117 бит (ровно 3 бита на символ). Заметим, что [[Информационная энтропия|энтропия]] источника, независимым образом порождающего символы с указанными частотностями, составляет ~2,1858 бита на символ, то есть [[Избыточность информации|избыточность]] построенного для такого источника кода Хаффмана, понимаемая как отличие среднего числа бит на символ от энтропии, составляет менее 0,05 бит на символ.

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

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

== Адаптивное сжатие ==

== Адаптивное сжатие ==

{|

{|

|

|

# Посчитаем частоту для каждого символа

# Посчитаем частотность для каждого символа

# Отсортируем их в лексикографическом порядке.

# Отсортируем их в лексикографическом порядке.

# В массив запишем частоту каждой буквы.

# В массив запишем частотность каждой буквы.

# Слева приписываем массив той же длины, но с порядковыми номерами из правого массива. Левый массив получается списком указателей на элементы правой части.

# Слева приписываем массив той же длины, но с порядковыми номерами из правого массива. Левый массив получается списком указателей на элементы правой части.

# В левой части делаем не [[Двоичная куча|возрастающую пирамиду]]. Но heap будет не по значению элементов массива, а по значению на ссылаемый элемент массива.

# В левой части делаем не [[Двоичная куча|возрастающую пирамиду]]. Но heap будет не по значению элементов массива, а по значению на ссылаемый элемент массива.

# Самый левый элемент указывает на символ из правого массива с наименьшей частотой. Его можно удалить следующим образом:

# Самый левый элемент указывает на символ из правого массива с наименьшей частотностью. Его можно удалить следующим образом:

## Правую половину не трогаем

## Правую половину не трогаем

## Первый элемент массива заменяем на самый правый элемент левого массива, якобы сдвигая границу разделения.

## Первый элемент массива заменяем на самый правый элемент левого массива, якобы сдвигая границу разделения.

## Проверяем условия правильности пирамиды, если что-то не так, то надо повторить «хипизацию».

## Проверяем условия правильности пирамиды, если что-то не так, то надо повторить «хипизацию».

## Убирается первый элемент левой части массива и объединяется ранее убранным. Сумма их частот записывается в границу между левым и правым массивом.

## Убирается первый элемент левой части массива и объединяется ранее убранным. Сумма их частотностей записывается в границу между левым и правым массивом.

## На место удалённого элемента в левой части записывается индекс массива куда добавили сумму частот на прошлом шаге.

## На место удалённого элемента в левой части записывается индекс массива куда добавили сумму частотностей на прошлом шаге.

## Из-за того объединили два элемента нужно изменить значения этих элементов массива ссылкой на родителя, куда их положили.

## Из-за того объединили два элемента нужно изменить значения этих элементов массива ссылкой на родителя, куда их положили.

# Повторяем, в куче слева не останется 1 элемент.

# Повторяем, в куче слева не останется 1 элемент.

'''Пример'''

'''Пример'''

Допустим, сообщение, которое надо закодировать '''«abcabcabc»'''. Нам заранее известна таблица частот символов (на основе других данных, например, статистических данных по словарю).

Допустим, сообщение, которое надо закодировать '''«abcabcabc»'''. Нам заранее известна таблица частотностей символов (на основе других данных, например, статистических данных по словарю).

{| class="wikitable" style="text-align:center"

{| class="wikitable" style="text-align:center"

!

!

В процессе работы алгоритма сжатия вес узлов в дереве кодирования Хаффмана неуклонно растет. Первая проблема возникает тогда, когда вес корня дерева начинает превосходить вместимость ячейки, в которой он хранится. Как правило, это 16-битовое значение и, следовательно, не может быть больше, чем 65535. Вторая проблема, заслуживающая ещё большего внимания, может возникнуть значительно раньше, когда размер самого длинного кода Хаффмана превосходит вместимость ячейки, которая используется для того, чтобы передать его в выходной поток. Декодеру все равно, какой длины код он декодирует, поскольку он движется сверху вниз по дереву кодирования, выбирая из входного потока по одному биту. Кодер же должен начинать от листа дерева и двигаться вверх к корню, собирая биты, которые нужно передать. Обычно это происходит с переменной типа «целое», и, когда длина кода Хаффмана превосходит размер типа «целое» в битах, наступает переполнение.

В процессе работы алгоритма сжатия вес узлов в дереве кодирования Хаффмана неуклонно растет. Первая проблема возникает тогда, когда вес корня дерева начинает превосходить вместимость ячейки, в которой он хранится. Как правило, это 16-битовое значение и, следовательно, не может быть больше, чем 65535. Вторая проблема, заслуживающая ещё большего внимания, может возникнуть значительно раньше, когда размер самого длинного кода Хаффмана превосходит вместимость ячейки, которая используется для того, чтобы передать его в выходной поток. Декодеру все равно, какой длины код он декодирует, поскольку он движется сверху вниз по дереву кодирования, выбирая из входного потока по одному биту. Кодер же должен начинать от листа дерева и двигаться вверх к корню, собирая биты, которые нужно передать. Обычно это происходит с переменной типа «целое», и, когда длина кода Хаффмана превосходит размер типа «целое» в битах, наступает переполнение.

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

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

== Масштабирование весов узлов дерева Хаффмана ==

== Масштабирование весов узлов дерева Хаффмана ==