FSE, 산술 코딩(Arithmetic Coding)으로 압축률을 높이다!

저자는 FSE(Finite State Entropy)가 ANS(Asymmetric Numeral Systems)의 고성능 구현임을 강조하며, 상태 테이블(State Table)을 활용하여 인코딩 및 디코딩 속도를 향상시킨다고 설명한다. 특히, FSE는 고정된 확률(Fixed Probabilities)을 가진 작은 알파벳(Small Alphabets)에 적합하며, Zstd와 같은 압축기에 사용된다. 디코딩 테이블(Decoding Table)을 통해 심볼(Symbol)을 빠르게 찾아내는 방식은 FSE의 핵심적인 특징이다.

저자는 산술 코딩(Arithmetic Coding)과 ANS(Asymmetric Numeral Systems)의 기본 원리를 설명하며, 두 기술 모두 심볼 확률(Symbol Probabilities)에 따라 심볼을 표현하는 데 사용된다고 언급한다. 산술 코딩은 구간(Interval)을 유지하며, ANS는 단일 정수 상태(Single Integer State)를 추적하는 방식으로 구현된다. 특히, ANS는 머신 친화적인(Machine-Friendly) 방식으로 설계되어 FSE와 같은 고성능 구현에 적합하다.

저자는 반복 오프셋(Repeat Offsets) 기법을 통해 압축 성능을 개선하는 방법을 제시한다. 이 기법은 최근에 사용된 오프셋을 재사용하여 중복된 거리(Repeated Distances)를 표현하는 데 사용되며, FSE의 효율성을 높인다. 반복 오프셋(Repeat Offsets) 사용은 Silesia 코퍼스(Silesia Corpus)에서 압축률을 크게 향상시키는 결과를 보였다. 파서(Parser) 최적화를 통해 반복 오프셋을 인식하도록 하는 것이 중요하다고 강조한다.

저자는 enwik8 및 Silesia 코퍼스(Silesia Corpus)를 사용하여 다양한 압축 기술의 성능을 비교 분석한다. 특히, FSE를 사용한 압축기는 Huffman baseline에 비해 enwik8에서 0.2% 향상, Silesia에서 0.18% 향상을 보였다. 또한, 반복 오프셋(Repeat Offsets)을 적용한 결과, Silesia 코퍼스(Silesia Corpus)에서 압축률이 크게 개선되었다. Zstd와의 비교(Comparison)를 통해, 저자가 개발한 압축기의 성능을 객관적으로 평가한다.