圧縮エリア

Revised : 2006/05/06
Since : 2005/04/01


Home  連長 圧縮 | ブロックソート | 前方移動  | 算術符号 | レンジコーダ | LZ符号  | ハフマン符号

圧縮の仕組み

データの冗長性偏りを利用して圧縮する。逆に言うと、無駄がなく偏りもないデータは圧縮できない。
言いかえるとデータの持つ情報量未満には圧縮できない。

圧縮には2種類あって、可逆圧縮非 可逆圧縮である。
後者は、圧縮すると元のデータに戻せないが、その分高圧縮率になる。JPEGやMP3等がこの形式である。

圧縮の手順は大きく2つに分けられる。始めは「モデル化」そして「符号化」である。

情報量の定義(Shannonの定理)

ある事象Eが確立pで起こる時、この事象の持つ情報量を-log2pと定義する。
単位は”シャノン(shannon)”、以前は“ビット (bit)”としていた。
変更は ISO/IEC 2382-16(1996) による。
平均符号長の下限は次式で計算される「エントロピー(Entropy)」で与えられる。

H = -∑pilog2(pi) [ shannon / symbol ] (piはi番目のシンボルの生起確率)

因みに”ビット(bit)”は、ほとんどのデジタルコンピュータが扱うデータの最小単位である。
英語の binary digit (2進数字)の略であり、2進数の1けたのことである。

モデル化

「符号化」しやすいデータに変換する。複数 の「モデル化」を組み合わせることも可能である。
一般に「モデル化」だけを行っても高圧縮にはならない。
モデル化には、LZ(LZ77、LZ78、LZSS、LZW等)、ブロックソート、前方移動等がある。

符号化

モデル化したデータを、本来の情報量に近づける
本来の情報量とは、元のデータを区別するのに必要最低限の情報量のことである。
例えば、あるクラスの成績表を例にとれば、
通常は100点の可能性もあるので3桁必要であるが、クラスの最高点が9点ならば、1桁で十分である。

つまり、元のデータが本来の情報量と一致している場合、圧縮できない
(既に圧縮済みのJPEG等は、本来の情報量に近く、圧縮しにくい。)
符号化には、ハフマン符号、算術符号、レンジコーダ等がある。

連長圧縮(Run Length Encoding)

元のデータを記号と長さで表現する方法である。
同じデータが連続して出現する場合に有効である。

ブロックソート(Block Sort)

元のデータを回転させ、同じ記号が並びやすくする方法である。
データサイズは、少しだけ大きくなる。

前方移動(Move To Front)

出現文字テーブルを作成し、出現した文字コードを常に先頭に移動(登録)する方法である。
新たな文字が出現するたびにテーブルに追加する方法と、
予め出現する文字全てをテーブルに登録しておく方法がある。

算術符号(Arithmetic Code)

Elias符号をコンピュータで実装可能にしたもの。
データ全体に1つの符号を割り当てることにより、最小符号長に近くなる。

レンジコーダ(Range Coder)

算術符号とよく似ていて下端と幅で表現する方法である。
算術符号に比べ処理速度が速いが、符号化精度は低くなる。

LZ符号

辞書を用いた符号の方法。
データ値のまとまりを辞書に登録し、登録場所を出力する。
辞書の構築の仕方によってLZ77系とLZ78系に分けられる。

ハフマン符号

ハフマン木を構築し、各データに割り当てるビット列を決定する。
ハフマン木は各データを重みを持った葉とする。

1.出現頻度の少ない2つの葉(節)に小さい順に0,1と割り当てる。
2.この2つの出現頻度を加算して節(2つの葉の重みを持った新たな葉)の出現頻度とする。
3.根(出現頻度の総和)に至るまで1と2を繰り返す。
4.根→節→葉の順に0,1を並べてデータ(葉)の符合とする。

図解入門よくわかる最新データ圧縮技術の基本と仕組み 図解入門よくわかる最新データ圧縮技術の基本と仕組み
圧縮の仕組みについてわかりやすく書かれている

LHA(エルエッチエー)とZIP
日本標準LHAと世界標準ZIPの圧縮方法について書かれている
ソースコード付

圧縮アルゴリズム圧縮アルゴリズム
C言語のソースコード付、ソースが読めなくても分かりやすい一冊
ページの上部へ
容量300MB、月額125円、高性能なサーバが日本最大級のバックボーンに直結。
さくらのレンタルサーバ
ロリポップのドメインが65種類 → 85種類に!!
きっとお好みのドメインが見つかるはず!
アフィリエイトならリンクシェア