Изменения

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

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

Классический алгоритм Хаффмана на входе получает таблицу [[частотность|частотностей]] символов в сообщении. Далее на основании этой таблицы строится дерево кодирования Хаффмана (Н-дерево).<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] {{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 = }}</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>

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

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

== Модификации ==

== Модификации ==

В 2013 году была предложена модификация алгоритма Хаффмана, позволяющая кодировать символы дробным количеством бит — ANS<ref>http://chaos.if.uj.edu.pl/ZOA/files/semianria/chaos/28.04.2014.pdf</ref><ref>http://arxiv.org/pdf/1311.2540.pdf</ref>. На базе данной модификации реализованы алгоритмы сжатия [[Zstandard]] (Zstd, Facebook, 2015—2016)<ref>[http://www.opennet.ru/opennews/art.shtml?num=45058 Facebook опубликовал реализацию алгоритма сжатия Zstandard 1.0] / Opennet.ru, 01.09.2016</ref> и {{нп5|LZFSE|LZFSE|fr|LZFSE}} (Apple, OS X 10.11, iOS 9, 2016)<ref>[https://www.opennet.ru/opennews/art.shtml?num=44746 Компания Apple открыла реализацию алгоритма сжатия без потерь LZFSE] / Opennet.ru, 07.07.2016 </ref><ref>[https://www.infoq.com/news/2016/07/apple-lzfse-lossless-opensource Apple Open-Sources its New Compression Algorithm LZFSE<!-- Заголовок добавлен ботом -->]</ref><ref>[https://developer.apple.com/library/mac/documentation/Performance/Reference/Compression/ Data Compression<!-- Заголовок добавлен ботом -->]</ref><ref>[https://github.com/lzfse/lzfse GitHub — lzfse/lzfse: LZFSE compression library and command line tool<!-- Заголовок добавлен ботом -->]</ref>.

В 2013 году была предложена модификация алгоритма Хаффмана, позволяющая кодировать символы дробным количеством бит — ANS<ref>{{Cite web |url=http://chaos.if.uj.edu.pl/ZOA/files/semianria/chaos/28.04.2014.pdf |title=Архивированная копия |access-date=2016-01-02 |archive-date=2016-03-05 |archive-url=https://web.archive.org/web/20160305212234/http://chaos.if.uj.edu.pl/ZOA/files/semianria/chaos/28.04.2014.pdf |deadlink=no }}</ref><ref>{{Cite web |url=http://arxiv.org/pdf/1311.2540.pdf |title=Архивированная копия |access-date=2016-01-02 |archive-date=2016-09-11 |archive-url=https://web.archive.org/web/20160911213547/http://arxiv.org/pdf/1311.2540.pdf |deadlink=no }}</ref>. На базе данной модификации реализованы алгоритмы сжатия [[Zstandard]] (Zstd, Facebook, 2015—2016)<ref>[http://www.opennet.ru/opennews/art.shtml?num=45058 Facebook опубликовал реализацию алгоритма сжатия Zstandard 1.0] {{Wayback|url=http://www.opennet.ru/opennews/art.shtml?num=45058 |date=20160902142935 }} / Opennet.ru, 01.09.2016</ref> и {{нп5|LZFSE|LZFSE|fr|LZFSE}} (Apple, OS X 10.11, iOS 9, 2016)<ref>[https://www.opennet.ru/opennews/art.shtml?num=44746 Компания Apple открыла реализацию алгоритма сжатия без потерь LZFSE] {{Wayback|url=https://www.opennet.ru/opennews/art.shtml?num=44746 |date=20160911053312 }} / Opennet.ru, 07.07.2016</ref><ref>{{Cite web |url=https://www.infoq.com/news/2016/07/apple-lzfse-lossless-opensource |title=Apple Open-Sources its New Compression Algorithm LZFSE<!-- Заголовок добавлен ботом --> |access-date=2016-09-01 |archive-date=2016-09-11 |archive-url=https://web.archive.org/web/20160911215307/https://www.infoq.com/news/2016/07/apple-lzfse-lossless-opensource |deadlink=no }}</ref><ref>[https://developer.apple.com/library/mac/documentation/Performance/Reference/Compression/ Data Compression<!-- Заголовок добавлен ботом -->]</ref><ref>{{Cite web |url=https://github.com/lzfse/lzfse |title=GitHub — lzfse/lzfse: LZFSE compression library and command line tool<!-- Заголовок добавлен ботом --> |access-date=2016-09-01 |archive-date=2020-11-28 |archive-url=https://web.archive.org/web/20201128185751/https://github.com/lzfse/lzfse |deadlink=no }}</ref>.

== Примечания ==

== Примечания ==