**Finite State Entropy** (FSE) – алгоритм [энтропийного кодирования][1], чем-то похожий и на [алгоритм Хаффмана][2], и на [арифметическое кодирование][3]. При этом он взял лучшее от них обоих: работает так же быстро, как хаффмановский, и со степенью сжатия как у арифметического кодирования.

FSE принадлежит семейству кодеков ANS ([Asymmetric Numeral Systems][4]),  изобретённых [Яреком Ду́дой][5]. На основе его исследований [Ян Коллет][6] разработал оптимизированный вариант алгоритма, впоследствии названный FSE.

В [заметках][7] Яна Коллета непросто разобраться, поэтому я изложу объяснение в несколько ином порядке, более удобном для понимания, на мой взгляд.

[![][8]][9]
[Читать дальше →][10]

[1]: https://ru.wikipedia.org/wiki/%D0%AD%D0%BD%D1%82%D1%80%D0%BE%D0%BF%D0%B8%D0%B9%D0%BD%D0%BE%D0%B5_%D0%BA%D0%BE%D0%B4%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5
[2]: https://habrahabr.ru/post/144200/
[3]: https://habrahabr.ru/post/130531/
[4]: https://en.wikipedia.org/wiki/Asymmetric_Numeral_Systems
[5]: http://arxiv.org/abs/1311.2540
[6]: https://github.com/Cyan4973
[7]: http://fastcompression.blogspot.ru/2014/01/fse-decoding-how-it-works.html
[8]: https://habrastorage.org/getpro/habr/post_images/cf4/ca6/008/cf4ca6008e7097320a48f37be6a64335.png
[9]: https://habrahabr.ru/company/playrix/blog/324116/
[10]: https://habrahabr.ru/post/324116/?utm_source=habrahabr&utm_medium=rss&utm_campaign=feed_posts#habracut