算術圧縮

読み:さんじゅつあっしゅく
品詞:さ変名詞

圧縮アルゴリズムの一つで、エントロピー符号に属する。

目次

ハフマン符号での圧縮のビット列は、一つの文字に対して割り当てられるビットが整数個であるとは限らない。

つまり、圧縮後のデータ全体が非常に長い小数を表わしているとも解釈できるため、ここから算術圧縮という名前が付けられた。

由来

生起確率を0〜1の小数で表わし、それを用いて全体を符号化する。

そもそも、ハフマン符号ではを用いて文字に符号を割り当てるが、木のは常に整数である。このため生起確率が1/3や1/5のように整数にならない符号に対しても整数ビット分の符号を割り当てざるをえない。この問題が、圧縮率の低下を招いていた。

一方、もしデータを生起確率を元に分数で表現したとすると、その分数を表現するために必要なビット数はエントロピー限界に漸近する。

そこで、確率を整数で扱うことをやめ浮動小数点数で扱うことで圧縮率を高めたのが、算術符号である。

改良

浮動小数点数による計算はコストが高く、処理が遅い。

そこで、精度を多少犠牲にして、計算を整数のみ、つまり固定小数点で扱う方法が考えられた。これがJones符号であり、生起確率区間は0以上の整数とする。

また、このJones符号を変形したものとしてRangeCoderが作られた。算術圧縮は生起確率区間を下端〜上端で表わしたが、RangeCoderはこれを下端と区間幅で表わし、式を変更した。

RangeCoderは特許がとられておらず安全である。一応、算術符号とは式が違うため算術符号の特許には抵触しないとされているが、かなりグレーではある。

用語の所属
圧縮アルゴリズム
関連する用語
生起確率
LZARI
RangeCoder

コメントなどを投稿するフォームは、日本語対応時のみ表示されます


KisoDic通信用語の基礎知識検索システム WDIC Explorer Version 7.04a (27-May-2022)
Search System : Copyright © Mirai corporation
Dictionary : Copyright © WDIC Creators club