Finite State Entropy (FSE) – алгоритм энтропийного кодирования, чем-то похожий и на алгоритм Хаффмана, и на арифметическое кодирование. При этом он взял лучшее от них обоих: работает так же быстро, как хаффмановский, и со степенью сжатия как у арифметического кодирования.
FSE принадлежит семейству кодеков ANS (Asymmetric Numeral Systems), изобретённых Яреком Ду́дой. На основе его исследований Ян Коллет разработал оптимизированный вариант алгоритма, впоследствии названный FSE.
В заметках Яна Коллета непросто разобраться, поэтому я изложу объяснение в несколько ином порядке, более удобном для понимания, на мой взгляд.
Читать дальше →
FSE кодирование
Source: habrahabr