データ圧縮は、対象とするデータに
偏りがあることを利用
して行います。
データに含まれる値の出現頻度に偏りがある
(0などの特定の値が多く使われる)とか、
同じ値(パターン)が連続して現れるとか、
近くに似た値が現れやすい、とか、
です。
例えばまた、偏りの少ない/得られにくいデータの場合でも、別の性質や規則性を利用し、いったん
00 00 00 00 00 12 12 12
という 8バイトを 5個 の 00 と 3個の 12 と表現すれば
05 00 03 12
と 4バイトにできたりします。
あるいは 00 と 12 の２種しかないようならば８バイトをビット情報として
00000111
のようにまとめ、
00 12 07
と3バイトにできたりします。
偏りの現れやすいデータに変換する／ 似たような値が続きやすいように並べ替えることで圧縮しやすくする場合もあります。
例えば
60 61 62 63 64 78 72 73
を左隣の値との差に書き直すと、
60 01 01 01 01 14 -6 01
のようになります。
01 が増えた(あるいは小さい値が増えた)状態として別の圧縮をさらにかけやすそうです。
データ圧縮に関わるアルゴリズムとしては、データの偏りを元に圧縮する類だけでなく、 データが圧縮されやすいようにデータを偏らせるだけの類もある、ということです。
前者のアルゴリズムとしては、ランレングス法や辞書法、
ハフマン法、算術圧縮法、レンジコーダー法、等々があり、
後者としては、既出のデータや予測値と差分(やxor)を取ったりする方法やブロックソート法、
画像等でのdctやwavletを用いた方法等々があります。
（この前者/後者の分け方は正確な分類じゃないので、大雑把な感じ程度に:-)
実際にはいくつかの方法を組み合わせて使う場合が多いでしょう。
ところで、すべてに万能の圧縮方法はない、です。
一般に圧縮率と展開/圧縮速度は相反する課題で、
データの性質や利用目的、リソース(cpu速度,メモリ量)の都合に合わせて
方法(アルゴリズム)を選ぶ/作ることになります。
先の最初の例はランレングス法で低スペックな環境でも使える単純なものですが、 同様の方法（繰り返し数とデータ）で、
01 55 72 24 08 13 08 13
という比較的バラバラな値の8バイトを変換すると
01 01 01 55 01 72 01 24 01 08 01 13 01 08 01 13
と16バイトに膨れてしまいます。
データの性質が適合すれば使える方法となりますし、適合しなければ害ということにもなります。
場合によっては、画像(jpeg)や音声(mp3)などのように、元と全く同じには復元できないけれど
非常に圧縮率の高い不可逆圧縮を行うこともあります。
（完全に元に戻せる場合は可逆圧縮）
人間が見る分には/聴く分には少々違っていても問題ない、という場合に、
精度を落として(細かい部分のデータを捨てて)本来のデータ量を減らすわけです。
(16色,256色画像なんかも、色数を限定することでサイズを抑えているのでフルカラーに対して圧縮状態です)
より圧縮率を高くしよう/より速度を速くしよう、と考えるならば、 対象となるデータの性質を（調査したり実験したりして）見い出す、 ということが必要になってきます。
なお(圧縮に限らずプログラム全般にいえることですが)、
圧縮関係のアルゴリズムでは、特許の問題がいろいろあるようです。
lzw法(gifやtiffで使われていたもの...去年期限切れ)や、
算術圧縮法等、メジャーなアルゴリズムが、
プログラム特許が成立する以前に普及していたせいもあり、
サブマリン特許が成立してしまい、
利用が困難な状態が発生したりしています。
(JPG2000も制定後にサブマリン特許が問題になっていた模様...)
オンラインで読める圧縮方法の入門/概説としては、
というページがあり、お勧めです。
その他、
あたりも参考になるでしょう。
- 奥村晴彦氏のデータ圧縮 (lha のアルゴリズム作者の一人)
- DO++ (PPMやブロックソートの解説等)
- Wikipedia 主な圧縮アルゴリズム
- 続・サルでも書けるＣプログラム講座 ファイルの圧縮
※2005年現在、ろくに圧縮関係の頁は探していないので今はもっといい頁ができてるかも、です。
(4,5年前にあった他のいい頁はなくなってしまっていたりしますが)
入門/参考書としては、奥村晴彦『C言語によるアルゴリズム辞典』は 役にたつと思います。あと画像ですが、越智宏+黒田英夫 『JPEG&MPEG図解でわかる画像圧縮技術』も参考になりそうです。
下記は、大雑把な圧縮方法の考え方の自分用のメモ書きみたいなものです。
正直、助長で正確ともいえない部分もあり、下記をみるよりも
上記の"基礎"のサイトをまずみたほうがよういと思いますが、
何かのヒントにはなるかも、で、残しておきます。
■上記で例にも出したように単純な方法で、昔から使われています。
同じ値が続けて出現するなら、その値と長さを組にして記録することで、
全体のサイズを減らすわけです。同じ値が連続してよく現れるデータを対象と
しており、そうでないデータに使うと逆に太りやすいです。
単純な画像ならば同じ値が続くので、bmpやtgaの画像圧縮などでも使われています。
有効なデータが限られ高圧縮も望めないですし、 CPU速度やRAM容量の事情がよくなってるので 他の方法を採用することのほうが多いでしょうが、 展開/圧縮ともに簡単なルーチンで、遅いCPUやRAM少量あるいは リアルタイム性(圧縮の場合もある)といった条件下なら 使う場合もあるでしょう。
■ところで、上記の例での、倍に太るようなやり方は普通はやらないです（たぶん）。 下記のようにすると思います。
■別に１バイト単位の繰り返しだけでなく、対象とするデータの性質によって、 2バイト単位だったり 4バイト単位だったり、1ビット単位だったりと、いろいろありえます。 長さ情報も１バイトでない場合もあるでしょう。長さの値も説明のためにそのまま に書きましたが、実際には最小の長さ(1なり2なり)が0になるように調整して値が0〜255ならば 長さは2〜257というようなことをする場合もあります。
辞書法とか他の方法でも同様ですが、 速度や圧縮率などの兼ね合いで、細々といろいろな要素/事情を考えて データフォーマットを設定することになります。
■LZ77系(LZSS),LZ78系(LZW)等いろいろあるようです。
■入力＆出力の過程で、最近入力したデータに関する情報を一定量(辞書/表に)蓄えていき (古いデータは捨てる）、 もし、すでに辞書/表に登録してあるデータを入力したらば、辞書中の位置（とサイズ）を 出力、でなければ元データを出力、という感じです。
もちろん、辞書位置情報と元データを区別する方法(データ)が必要ですし、 辞書に登録するデータは、置き換えられる位置情報よりも大きくないと無意味となります。 辞書の登録の仕方や、辞書サイズ、位置&長さ情報、データ区別の情報の持ち方などは、 アルゴリズムやプログラムごとに工夫されることになります。
■スライド辞書法(LZ77,LZSS)は、ZIPやLHa(やその前身のLarc)等で 用いられる方法です。
これは、データ中の、今、注目する文字列（データ列）が、n文字前に現れた長さm文字の 文字列(データ列)と一緒、なら、その位置/長さを、でなければ、元データ を出力、といった感じです（複数一致するならば、最長に一致するものを 選ぶ）。
たとえば、
TEST1-TEST2
ならば
TEST1-<6,4>2
といったふうです（ <6,4>は6文字戻って4文字取ってくるという意味の値とします）。
辞書範囲があるので、 画像やテキスト/表などのように、ある注目点の近くに似たようなデータが 現れる傾向があるデータに対して、よく効くようです。
仮にデータ化してみると、まず、圧縮後の1文字が生か符合化情報かの
区別をビットで表現すると(調度8個データがある状態なので) 2進数 1111101 となり16進数 0xFD、
n戻ってmコピーという符合を n 4ビット m 4ビットとすると 0x64 と表現できるので、
54 45 53 54 31 2D 54 45 53 54 32 TEST1-TEST2
は
FD 54 45 53 54 31 2D 64 32 TEST1-<6,4>2
のように 11 バイトだったものが、9バイトに圧縮されることになります。
※ビットストリームを用いない場合の、実際的な圧縮では n戻ってmコピーは
n:8〜12ビット m:8〜4ビットの計16ビット=２バイト
になるようにするのが多いと思われます。
生データ/辞書位置の判定に関しては上記例のように別途フラグ情報を用いたり(8個=8bit=1バイトごとに出力)、あるいは、 戻る数が0なら長さの分だけ生データが続く、というやりかたもあるでしょう。
また、圧縮の下段にハフマン法(や算術圧縮法)など
ビットストリームで扱う場合は、
実データと辞書位置をひとまとめにした符号を用いて、
区別用のフラグを不用にできたりもします。
0〜255 と n戻るをまとめて、例えばn=9bit=512ならば、
0〜767(255+512) の値を１つの値として、ハフマン(算術圧縮法)化したり
するわけです。("戻る"値の場合はさらにいくつ続くかが別途、後に続く)
データの性質によっては、以前と同じ値はよく現れるけどもあまり連続しない、と言う場合は いっそ連を1に限定して連を記録しない手もあります （n戻る、という情報が取り出す１データよりもビット数が少ない時に有効。 インターバル法/BSTW法になるのかな）。
展開は、辞書/表のためのRAM(メモリ)を必要せず、
読込バッファや展開済みのデータからのコピーで済みプログラムも
比較的単純なので、ランレングスと同様、扱い安いです。
※ 1つ戻って m 続く、というデータは、実質ランレングスと同じ動作で、
速度アップのため専用にルーチンを用意することもあります。
そこそこの圧縮率でお手軽なのでランレングスより使われ安いと思います。
ただ圧縮のときは、過去に現れたデータで最長に一致するものを探す、と いう処理が重く、圧縮ソフトなどはこの辺はいろいろな工夫をされている ようです。
■ハフマン法、算術圧縮法、レンジコーダー法、などがあります。
■基本的に、出現頻度の高い値は、ビット数が短く符号を、出現頻度の 低い値にはビット数の長い符号を割り当てることで、データ量を減らします。
例えば、A,B,C,D ４つの文字からなるデータがあって、
A (00) 50% B (01) 25% C (10) 12.5% D (11) 12.5%という使用頻度のとき、
A 0 (1ビット長) B 10 (2ビット長) C 110 (3ビット長) D 111 (3ビット長)と符号化することにします （符号化は、当然、１ビットづつ取り出していったときに、 一意に判別できる値にしとくわけです）
例えばこののA,B,C,D で、ABCDABADADABA を符号化すると、
A B C D A B A D A D A B A 0 10 110 111 0 10 0 111 0 111 0 10 0となり、バイトにしてみると、
0101 1011 1010 0111 0111 0100 5 B A 7 7 4ということで、5B A7 74 の 3バイトのデータになります。
また、元が2ビット 4種のデータが 4096個あったとすると、
4096*2 = 8192ビットとなりますが、上記で符合化すると
4096*0.50*1 + 4096*0.25*2 + 4096*0.125*3 + 4096*0.125*3 = 7168ビットのように圧縮されます。
で、実のところ上記例はかなり作為的な頻度を選んでいますが、実際はもっと単純でない状況です。
具体的にどのように頻度と符合化(ビット長)を行うかは、各アルゴリズムによります。
詳しくは、書籍や他のサイトに当たってください(^^;)。
上記の例はハフマン法 寄りの話で、
算術圧縮などは少し違ってきます。
（正数ビットでなく実数になる。確率によっては1ビット以下にも符号化できる）
重い処理だけど理論上の限界に近い符号化は算術圧縮法で、
リーズナブルなのはハフマン法といったところ……
ですが、最近はハフマン並に速く算術圧縮並(若干落ちる)の圧縮率の
レンジコーダー法が流行のようです。
（算術圧縮の特許を回避した変種のようで、 浮動小数点演算だった部分を シフトを使った整数演算にして速度を上げれるようにした感じ）
■この系統の圧縮は、普通のＣＰＵが扱いやすいバイトやワードのような 単位でなく、ビット単位でデータを扱うことになります （ビットストリームと言ったりします）。
プログラム的には少々めんどくさく、処理時間もかかる重い処理になりやすい傾向があります。
例えば展開ルーチンで値を取り出す部分をCで書くと、
/// ビットストリームバッファより、1ビットの値を取得
int bs_get1(void) {
int b = (*bs_ptr >> bs_cnt) & 1;
if (++bs_cnt >= 8) {
bs_cnt = 0;
bs_ptr++;
}
return b;
}
/// ビットストリームバッファより、nビットの値を取得
int bs_get(int n) {
int c = 0;
while (n--) {
c = (c << 1) | bs_get1();
}
return c;
}
のようなルーチンを用意することになります。
他の要素もありますが、ビットストリームでない処理に比べ一桁二桁違ってくるかもしれません。
※ 単純に c = *(unsigned char)bs_ptr; で1バイト取得するのと、
c = bs_get(8); で取得するのとで、処理量を比べてみれば……
C/C++レベルでも上記以外の書き方や
値をうまく制限することで処理速度をあげる工夫もできますが、
CPU 自体にビット処理向けの命令が備わっていたりすることがあるので、
コンパイラによってはインライン命令として用意されていたり、
あるいはアセンブラ(マシン語)で記述することで大幅な速度アップを
行える可能性があります。
■値と符合の対応表が必要になりますが、この表を一定データ量ごとに
作る静的なやり方と、一つ入力するたびに更新する動的なやりかたがあります。
（上記の例だと
Aの値 00 → 1ビットの 0
Bの値 01 → 2ビットの 10
Cの値 10 → 3ビットの 110
Dの値 11 → 3ビットの 111
という情報の対応表をどうやって用意するか、ということ）
動的な方法ならば、対応表を出力する必要はありませんが、毎回更新するため 速度的に不利になります。
静的ならば、速度的に有利ですが、対応表を別途用意/出力する分、
圧縮率が落ちることになります。
( LZH では、初期は動的ハフマンでしたが、対象データの大容量化と速度の
兼ね合いから追加のモードでは静的ハフマンが採用されています）
■ビットストリームを用いた符合化の方法で、ハフマンや算術圧縮の
ような本格的なのでなく、値の性質を用いて、表を用いずに行う
変換もあります。
これは、(画像の)連や差分情報などで、 0の出現確立が一番高く、次に1の出現確立が高く、次に2……の ように値と出現確立がだいたい合うようなデータの場合、
0 0 00 1 100 01 2 101 1000 3 11000 1001 4 11001 1010 5 11010 1011 6 11011 110000 7 1110000 110001 8 1110001 110010 9 1110010 110011のような符合化を行えば、変換を表引でなく計算で求め ることができます。
※このレベルならば、うまくアセンブル化できれば毎フレームの処理でも 採用できる用途もあるかも?
■直接、圧縮するわけではありませんが、データを圧縮されやすい形に する方法として、既出の値や予測値との、差分 や XOR を取る、と いうのがあります。
差分 や XOR をすることにより、値が 0 が続いたり、0 付近の小さい 値ばかりになる、というのを期待しているわけです。
音声の ADPCM なんかがそのようなものですし、画像圧縮でも １ラインや２ライン上の値との差分/XORを取る、というのもあります。
たとえば、
80 81 82 83 84 84 84 88
を隣の値との差に書き直すと
80 01 01 01 01 00 00 04
のようになります。
また、単純な既出値との差分でなく、既出の値より何某かの
ルールを用いて次に現れそうな値を計算し予測値とし、
その予測値との差を用いる、という場合もあります。
（画像の場合、注目点の横や上などの周辺のいくつかの既出の点から予測したり）
予測精度が高ければ高いほど、差となる値は小さくなり、 圧縮されやすくなるわけです。
■Move-To-Front法 は、今、注目する値が最近いつ（いく種類前に）現れたか、を
記録する方法で、最近現れた値ほど、(0に近い)小さい値になります。
（最近現れた値ほど次に現れやすい、だろうと予測(というか期待)しているわけです)
バイト値ならば、まず 0〜255 の値の中での出現順番と
いうことで、tbl[256] のような配列テーブルを用意してその中に 0〜255
全ての値を並べて置きます。
対象のデータから１つ値を入力したら、tblテーブル中にある同じ値を検索して
その添字番号を出力、
と同時にその値を tbl[] の先頭に移動する
（空いた隙間が埋まるように配列をずらす/メモリの移動を行う）、
という処理をします。
最近現れた文字ほどtbl[]の最初のほうにあるので添字番号が小さくなる、と いうわけです。
例えば A=0 B=1 C=2 D=3 の4種(４値)の値の集まりとし（256個は大変なので^^;）、
変換用テーブルを
tbl[]={0,1,2,3}
で初期化しておきます。
今回の入力データが
DDBDD (3 3 1 3 3)
とするとき、まず 最初の D(3) は、tbl中の[3]にあるので
3
を出力します。そして tbl[] 中の 3 を 先頭に移動してずらして、
tbl[]={3,0,1,2}
になります。次の値 D(3) は、tbl[] の先頭にあるので出力は 0で、
3 0
となります。tbl[]の更新は必要ないので、そのまま次の値を入力して B(1)で、
値 1 は今の tbl では [2] に入っているので 2を出力して
3 0 2
テーブルは
tbl[]={1,3,0,2}
となります。同様に次の D(3) と、その次のD(3)を処理すると
3 0 2 1 0
テーブルは
tbl[]={3,1,0,2}
と、いう具合になります。(元のデータのままのほうが圧縮しやすそうだけど^^;
値が小さくなる、という意味のサンプルなので..)
値が 0〜255 ならば tbl[256] として同様な処理をすることになります。
ちなみに pi という16色/256色画像フォーマットでは、 これを応用した方法が採用されており、 あるピクセル(色)の次に特定のピクセル(色)が来る確立が高いだろうとして（予想して）、 直前のピクセル(色)ごとに変換テーブルを用意する （変換するときに直前のピクセル(色)をみて変換テーブルを切り替える）、 ということをしています。
16色なら tbl[16][16]を 256色画像ならtbl[256][256]を用意して tbl[直前のピクセル番号][?] を対象として処理する、 という具合です。
隣あった値に依存関係があるならば、 テーブルが一本のみに比べ 0に近い値を出力する割合が増えるわけです。
※ テーブルは単純な配列で実装するとメモリ移動(コピー)時間が
無視できない場合もあるので、
状況によっては、双方向リンク等、別の構造の採用も考えられます。
が、近い/小さい値が合われる頻度が高いなら、単純なメモリコピーの
ほうが結局速い可能性も高いです。
扱う値が1バイト数でなくさらに大きい値の場合(例えばRGB値とか)、 変換テーブルに値全てを収めるのでなく最近のn個を収める/キャッシュする、 というやり方もあります。 もっともこうなると Move To Flont 法でなく辞書法の一種になるでしょうが:-)
■ブロックソート法は、
bzip2やgsa等の最近の高圧縮な圧縮ツールで採用されている
アルゴリズムの一つで、これは、
あるルールに則り
データを並べ替える(ソートする)
ことにより似たようなデータが近くに固まって現れるようにすることで、
圧縮されやすい状態を作る方法です。
原理は比較的シンプルな構造（といってもかなり難物）ですが、 原理のままだと圧縮するデータの２乗のメモリが必要なので、 コーディングでいろいろな工夫が必要になります。
(具体的な方法等は他の解説サイトを見てください)
■ppm (Prediction by Partial Matching) 法も、最近の高圧縮ソフトで
採用されているアルゴリズムの一つで、"予測"を用いた方法のようです。
発展途上のようで、いろいろ工夫もある模様。
具体的な方法等は他の解説サイトを見てください。
■7zip(lzma) は lz系を発展改良した高圧縮ソフトらしいです。
Cマガ2006-01号に解説あり。