Revised : 2020/07/25
Since : 2005/04/01
データの冗長性や偏り
を利用して圧縮する。逆に言うと、無駄がなく偏りもないデータは圧縮できない。
言いかえるとデータの持つ情報量未満には圧縮できない。
圧縮には２種類あって、可逆圧縮と非
可逆圧縮である。
後者は、圧縮すると元のデータに戻せないが、その分高圧縮率になる。JPEGやMP3等がこの形式である。
圧縮の手順は大きく2つに分けられる。始めは「モデル化」そして「符号化｣である。
ある事象Ｅが確立ｐで起こる時、この事象の持つ情報量を－ｌｏｇ2ｐと定義する。
単位は”シャノン(shannon)”、以前は“ビット (bit)”としていた。
変更は ISO/IEC 2382-16(1996) による。
平均符号長の下限は次式で計算される「エントロピー（Entropy）」で与えられる。
H = -∑ｐiｌｏｇ2（ｐi） [ shannon /
symbol ] （ｐiはｉ番目のシンボルの生起確率）
因みに”ビット(bit)”は、ほとんどのデジタルコンピュータが扱うデータの最小単位である。
英語の binary digit （2進数字）の略であり、2進数の1桁のことである。
「符号化」しやすいデータに変換する。複数
の「モデル化」を組み合わせることも可能である。
一般に「モデル化」だけを行っても高圧縮にはならない。
モデル化には、LZ（LZ77、LZ78、LZSS、LZW、LZMA等）、ブロックソート、前方移動等がある。
モデル化したデータを、本来の情報量に近づける。
本来の情報量とは、元のデータを区別するのに必要最低限の情報量のことである。
例えば、あるクラスの成績表を例にとれば、
通常は100点の可能性もあるので3桁必要であるが、クラスの最高点が9点ならば、1桁で十分である。
つまり、元のデータが本来の情報量と一致している場合、圧縮できない。
（既に圧縮済みのJPEG等は、本来の情報量に近く、圧縮しにくい。）
符号化には、ハフマン符号、算術符号、レンジコーダ等がある。
元のデータを記号と長さで表現する方法である。
同じデータが連続して出現する場合に有効である。
元のデータを回転させ、同じ記号が並びやすくする方法である。
データサイズは、少しだけ大きくなる。
出現文字テーブルを作成し、出現した文字コードを常に先頭に移動（登録）する方法である。
新たな文字が出現するたびにテーブルに追加する方法と、
予め出現する文字全てをテーブルに登録しておく方法がある。
Ｅｌｉａｓ符号をコンピュータで実装可能にしたもの。
データ全体に１つの符号を割り当てることにより、最小符号長に近くなる。
算術符号とよく似ていて下端と幅で表現する方法である。
算術符号に比べ処理速度が速いが、符号化精度は低くなる。
辞書を用いた符号の方法。
データ値のまとまりを辞書に登録し、登録場所を出力する。
辞書の構築の仕方によってＬＺ77系とＬＺ78系に分けられる。
ハフマン木を構築し、各データに割り当てるビット列を決定する。
ハフマン木は各データを重みを持った葉とする。
１．出現頻度の少ない２つの葉（節）に小さい順に0,1と割り当てる。
２．この２つの出現頻度を加算して節（２つの葉の重みを持った新たな葉）の出現頻度とする。
３．根（出現頻度の総和）に至るまで１と２を繰り返す。
４．根→節→葉の順に0,1を並べてデータ(葉）の符合とする。
