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