Изменения

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

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

Существует разновидность алгоритма Хаффмана, использующая контекст. В данном случае размер контекста равен единице (биграммный — два символа, триграммный — три и так далее). Это метод построения префиксного кода для моделей высших порядков, уже не источника без памяти. Он использует результат (предыдущей операции) операции над предыдущей буквой совместно с текущей буквой. Строится на основе [[Цепь Маркова|цепи Маркова]] с глубиной зависимости <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|url-status = live}}</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>.

В 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 |url-status=live }}</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 |url-status=live }}</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 |url-status=live }}</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 |url-status=live }}</ref>.

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

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