Изменения

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

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

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

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

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

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

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

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

== Биграммная модель ==

== Биграммная модель ==

Существует разновидность алгоритма Хаффмана, использующая контекст. В данном случае размер контекста равен единице (биграммный — два символа, триграммный — три и так далее). Это метод построения префиксного кода для моделей высших порядков, уже не источника без памяти. Он использует результат (предыдущей операции) операции над предыдущей буквой совместно с текущей буквой. Строится на основе [[Цепь Маркова|цепи Маркова]] с глубиной зависимости <math>r = 1</math>.<ref>{{Cite web|url = http://u.cs.biu.ac.il/~tomi/Postscripts/MathComp.pdf|title = Huffman Coding with Non-Sorted Frequencies|author = Shmuel T. Klein and Dana Shapira|work = |date = 2008|publisher = |access-date = 2016-01-02|archive-date = 2016-03-04|archive-url = https://web.archive.org/web/20160304110027/http://u.cs.biu.ac.il/~tomi/Postscripts/MathComp.pdf|deadlink = no}}</ref>

Существует разновидность алгоритма Хаффмана, использующая контекст. В данном случае размер контекста равен единице (биграммный — два символа, триграммный — три и так далее). Это метод построения префиксного кода для моделей высших порядков, уже не источника без памяти. Он использует результат (предыдущей операции) операции над предыдущей буквой совместно с текущей буквой. Строится на основе [[Цепь Маркова|цепи Маркова]] с глубиной зависимости <math>r = 1</math><ref>{{Cite web|url = http://u.cs.biu.ac.il/~tomi/Postscripts/MathComp.pdf|title = Huffman Coding with Non-Sorted Frequencies|author = Shmuel T. Klein and Dana Shapira|work = |date = 2008|publisher = |access-date = 2016-01-02|archive-date = 2016-03-04|archive-url = https://web.archive.org/web/20160304110027/http://u.cs.biu.ac.il/~tomi/Postscripts/MathComp.pdf|deadlink = no}}</ref>.

'''Алгоритм'''

'''Алгоритм'''