高速な算術圧縮を実現する「Range Coder」

はじめに 本記事では、全体のサイズが最小となる算術圧縮を高速に実現するRange Coder（以下RC）を紹介します。 算術圧縮は、各文字の出現確率が分かっている場合にそのデータを最小長で表現可能な符号法です。各文字に固定の符号を割り当てるHuffman法とは違い、符号化を状態更新とみなし、すべての文字を符号し終わった後の状態を保存することで符号化を実現します。これにより1文字単位の符号長を1bitより細かく調整することが可能となります。 算術符号は圧縮率が高い反面、ビット単位の演算処理が大量に発生するため、符号化、復号化ともにHuffman符号に比べ遅いという問題点があります。今回紹介するRCは、算術符号の処理をバイト単位で行うことで高速な処理を可能にします。 また、算術圧縮については概要から説明します。 対象読者 C++の利用者を対象としています。データ圧縮の基礎を知っていることが望ま

[taki0313]

メモ．実装してみたい．

[tomhiro]

RangeCorderをC++で実装

[hirokist]

RangeCorderをC++で実装

[hiromark]

Range Coder の解説。わかりやすい。

[yaotti]

算術符号化

[starsky5]

データ圧縮

[abars]

レンジコーダ

[TAKESAKO]

レンジコーダーは pathtraq の URL 圧縮に使われています