データ圧縮の基礎

●はじめに

　データ圧縮に関する情報を広く浅く解説する文章を目指しています。比較的新しいアルゴリズムも取り上げています。間違いや不明な点がありましたら、遠慮なくメールや掲示板に書き込んでください。この文章を読んで、一人でも多くの日本人が圧縮アルゴリズムに興味を持ってくれたら幸いです。

　データ圧縮には大きく２種類の圧縮方式があります。１つは、データの内容を省いて圧縮する方式。（データを省くので、完全に元の状態には戻らない方式。）もう一つは、データの内容を省かずに完全に圧縮する方式（完全に元の状態に戻る方式）です。

　データの内容を省くというのは、主に、画像や音声データのように、人の目や耳では判別不可能なデータを省くことをいいます。具体的な圧縮ファイルには JPEG や MP3 があります。
　これらのデータを省くタイプを「非可逆」や「ロッシー(Lossy)」と呼び、逆に、完全に圧縮/復元するタイプを「可逆」や「ロスレス(Lossless)」と呼んでいます。可逆タイプの具体的な圧縮ファイルには、LZH や ZIP があります。
　以下、データ圧縮の基礎では、圧縮アルゴリズムの基本ともいえる可逆（ロスレス）タイプについて解説します。非可逆タイプは、この可逆タイプの応用になると思ってください。まずは基本の可逆タイプをおさえましょう。

＊ yz1 と yz2 は可逆タイプです。LZH や ZIP と同じです。画像や音声などのノイズの多いデータの圧縮には不向きです。

　可逆タイプの（非可逆でも）圧縮アルゴリズムは、一般的に２段ロケット形式です。ここでは、一段目を「モデル化」。二段目を「符号化」と呼びます。

　一段目の「モデル化」では、データの特徴を抽出するデータ変換を行います。この段階でデータ量を減らします。一般に人の作成したデータには不必要なデータが多く含まれています。例えば、空白（スペース）であったり、同じ言葉の繰り返しであったり、データの種類にもよりますが、必ずといえるほどそういうデータが含まれています。この不必要なデータを「モデル化」の部分でコンパクトにまとめるデータ変換を行うのです。「モデル化」の具体的なアルゴリズム名では、LZ77, LZ78 や BlockSorting などがあります。ランレングスなども、このモデル化に入ると思います。

　二段目の「符号化」では、一段目で変換したデータを bit データにします。この段階では情報量は減りません。本来の情報量に近づけるわけです。本来の情報量とは、例えば、あなたが「お茶を飲みますか？」という問いの答えがほしかったとします。この時の答えは「飲む」か「飲まない」の２通りしか考えられません。この時の情報量は２通りなので、１bit （２進数で１桁）であらわすことができます。これを本来の情報量といいます。この情報量の bit 化のことをエントロピー符号とも言います。「符号化」の具体的なアルゴリズム名では、Huffman符号や、算術符号が有名です。最近では RangeCoder が注目されています。

＊ LZH や ZIP は LZ77 + Huffman符号の２段構成です。yz1 も同じですが、yz2 では LZ77 + RangeCoder の２段構成です。

　まずは、一般的に圧縮の後段階である、符号化について説明します。

　この順番に説明します。
　前段階の「モデル化」を行わなくても、この符号化だけでも多少のデータの圧縮は可能です。ですが、効率的な圧縮を行うにはどうしても「モデル化」と「符号化」をペアで組み合わせる必要があります。
　ただ、「符号化」どうしを複数組み合わせても意味がありません。むしろデータ量は増えるでしょう。エントロピー符号とは、情報の隙間を削り、ほぼランダムに等しいデータに変換する作業なのですから、２度目の符号化にはデータの隙間はありません。エントロピー符号は最後に１度だけ通すものなのです。

　ここでは、なにも考えず（深いアルゴリズムは無し）に符号化する例を示します。一番、簡単で単純な方法です。
　まず、"AAABCAAABD" という１０文字の文字列をなにも考えずにそのまま bit 列に変換することを考えてみましょう。１bit で２種類。２bitで４種類と、bit数をｎとすると２のｎ乗の状態をあらわすことができます。この場合、使用している文字は４種類(A,B,C,D)です。ちょうど２bit であらわせます。

　この文字列を符号化すると、'00 00 00 01 10 00 00 00 01 11' と２０bit であらわすことができます。また、この対応表さえあれば、２０bit を元の１０文字に戻すこともできます。この文字列は、特に考慮しない単純な符号化では ２０bit になるデータであるとも言えます。

　エントロピー符号の基本中の基本である、Huffman符号から説明します。
Huffman 符号は「文字の出現頻度を考慮して bit を割り当てよう」という考え方です。上の例の文字列 "AAABCAAABD" の各文字の出現頻度は、

です。Huffman 符号では、出現頻度の低い文字から bit を割り当てます。出現頻度の低い２つを探し出して 0 と 1 の bit をつけて行くわけです。まず最初は C と D に、0 と 1 を割り当てます。

　次に、C と D の出現頻度は合わせて２です。次から、C と D は 出現回数２の CD というかたまりとして扱うわけです。
　で、次に出現回数が低いのは、B と CD です。B に 0、CD に 1 を割り当てます。

ここで、BCD を１つのかたまり出現度４と考え直して、最後に、A に 0、BCD に 1 を割り当てます。

これが、Huffman 符号の bit の割り当て方式（の一例）です。
また、モビールのような「木」を作る方式でも同じ結果が得られます。

木の左の枝に '0' 右の枝に '1' を割り当てて符号 bit を決定します。結果は上の割り当て方と同じです。

　この bit 対応表で "AAABCAAABD" の文字列を bit 列に変換すると、'0 0 0 10 110 0 0 0 10 111' １６bit となります。何も考えない場合（２０bit）よりも４bit も短くなりました。また、この bit 対応表があれば、この１６bit のデータを１０文字の文字列に戻すことができます。

　Huffman 符号では、必ず１文字に１bit 以上の bit を割り当てるので、どうしても 1/2, 1/4, 1/8 という bit 表現可能な出現頻度の組み合わせに近似してしまいます。具体的には 1/3 とか 2/3 という、微妙な出現頻度を符号化できないのです。
　先ほどのHuffman符号の例であっても、

と、微妙なズレがあります。
　例えば "ABA" という文字列を bit 列に変換すると、Huffman 符号でも３bit 必要になります。

　これは普通に bit を割り当てたのと同じになってしまい、出現頻度を考慮する効果が発揮されません。この微妙な出現頻度を符号化できる方式が算術符号であるともいえます。
　算術符号では、実数（以下の解説では分数）を使って計算します。また、Huffman符号のように１文字ずつ bit を割り当てるのではなく、文字列全体を考慮して bit の割り当てを行います。
　まず、"ABA" の出現頻度表を分数で作ります。

その出現頻度をグラフにすると、以下のイメージになります。

1 ---+-- 3/3 A| A| A| A| A| A| A| A| A| A| A| --A+-- 1/3 B| B| B| B| 0 --B+-- 0/3

次に、最初の文字が A だった場合の２文字目の概念もグラフ内に書き込むとこうなります。

1 ---+-- 3/3 ---+-- 9/9 
    A|         A|       
    A|         A|       
    A|         A|       
    A|         A|       
    A|         A|       
    A|       --A+-- 5/9 
    A|         B|       
    A|         B|       
  --A+-- 1/3 --B+-- 3/9 
    B|                  
    B|                  
    B|                  
    B|                  
0 --B+-- 0/3

そして、２文字目が B だった場合を追記するとこうなります。

1 ---+-- 3/3 ---+-- 9/9
    A|         A|      
    A|         A|      
    A|         A|      
    A|         A|      
    A|         A|      
    A|       --A+-- 5/9 ---+-- 15/27
    A|         B|         A|        
    A|         B|       --A+-- 11/27
  --A+-- 1/3 --B+-- 3/9 --B+--  9/27
    B|       
    B|       
    B|       
    B|       
0 --B+-- 0/3 

　ここが重要なのですが、このグラフから読み取れることは、11/27 〜 15/27 という範囲はすべて "ABA" という文字列の情報を示しているということです。これは、11/27 〜 15/27 の範囲内の数値は "ABA" という文字列と相互変換できるということなのです。
　11/27 〜 15/27 の範囲には、1/2 が含まれます。1/2 は 0.5 なので、なんと１bit であらわすことができます。

    :          :
    A|         A|      
    A|       --A+-- 5/9 ---+-- 15/27 = 0.555..
    A|         B|         A|  
   [A]        [B]        [A]       ←  1/2 = 0.5  (1bit)
    A|         B|         A|  
    A|         B|       --A+-- 11/27 = 0.407407..
    A|         B|         B|  
  --A+-- 1/3 --B+-- 3/9 --B+--  9/27
    B|
　  :

　0.5 (1/2) という情報を受け取った場合、それを "ABA" という文字列に変換できるのです。
　出現頻度が高い文字は、それだけ数値の範囲が広がります。範囲が広いと言うことは、それだけ短い bit 数で表現できる確率が上がると解釈することもできます。
　同じように、"AAB" や "BAA" の bit をあらわすと、

0 ---+-- 3/3 ---+-- 9/9 ---+-- 27/27 = 1.0
    A|         A|         A|  
    A|         A|         A|  
    A|         A|         A|  
    A|         A|         A|  
    A|         A|         A|  
    A|         A|         A|  
    A|         A|         A|  
    A|         A|       --A+-- 19/27 = 0.703703..
    A|         A|         B|  
   [A]        [A]        [B]       ←  5/8 = 0.625 (3bit)
    A|         A|         B|  
    A|       --A+-- 5/9 --B+-- 15/27 = 0.555..
    A|         B|       
    A|         B|       
    A|         B|       
    A|         B|       
    A|         B|       
  --A+-- 1/3 --B+-- 3/9 ---+-- 9/27  = 0.333..
    B|         A|         A|  
   [B]        [A]        [A]       ← 1/4 = 0.25 (2bit)
    B|         A|         A|  
    B|         A|       --A+-- 5/27  = 0.185185..
    B|         A|         B|  
    B|        -A+ - 1/9 --B+--
    B|         B|       
    B|         B|       
0 --B+-- 0/3 --B+-- 0/9 

　最近、もっとも注目されているエントロピー符号化方式が、この RangeCoder です。
　考えかたは算術符号とほぼ同じなので、圧縮率も高く、アルゴリズムも簡単なので Huffman 符号と同等かそれ以上の処理速度が発揮できます。
　さらに、RangeCoder の発案者は「特許を取らない」と言っている（らしい）ので、自由に使うことができます（ここが重要）。ただ、本当に特許が取られていないことが証明されているわけではありません（みんながそう言っていて、みんながそう信じているということ）。しかし、これだけのメリットがあれば、RangeCoder が注目されるのも無理も無い話でしょう。
　符号化の考え方は、算術符号も、RangeCoder もほとんど同じだと思います。両者の違いはとても微妙で、算術符号のほうは 0.0〜1.0 の幅から、実数で分割して行くのに対して、RangeCoder では 0〜100000000000 （大きな整数）の幅から、「整数で」分割して行きます。整数を使うと、いくら大きな数であっても、処理を繰り返すうちにいつか分割できない数値になってしまいます。そこで、RangeCoder では、一定の数値を下回らないように、数値を補正していきます。単純には１０倍するとか、２倍するという方法です。また、算術符号であらわしている「範囲」という概念も、「上の値と下の値」であらわすのではなく、「下の値と幅（Range)」であらわしています。その他には、一般的に出力単位と精度の違いがあります。同じ bit 数を使っていても、算術符号のほうが RangeCoder より符号化の精度が高くなります。しかし、処理速度の面では、8bit単位に出力する RangeCoder が有利になっています。

　符号/復号ともにやっている計算は非常に単純です。高速に処理できる理由も理解できるかと思います。しかし、どうしてこれが算術符号と同じような理屈になるのか、理解しがたいことであるとも思います。
　何度かグラフに書くなどしてこの動きを追いかけてみると理解が深まると思います。算術符号と照らし合わせて考えることも有効でしょう。とても有用な符号化アルゴリズムなので、ぜひ、皆さんにもマスターしていただきたいと思っています。

他の解説は DO++ さんのページ
http://member.nifty.ne.jp/DO/algorithm/rangecoder.htm
にあります。

また、yz2α でも RangeCoder を採用しています。
yz2α のコードは公開されていますので、そちらも参考にしてください。
http://www.01-tec.com/yz2/index.html

RangeCoder の詳細ページ（英語）
http://www.compressconsult.com/rangecoder/

　Huffman符号でも、算術符号でも、RangeCoder でも、どのエントロピー符号であっても同じような出現頻度表を作成します。この頻度表は圧縮時（符号化時）に作成されて、展開時（復号化時）に必要になります。
よって、頻度表の情報もなんらかの形で渡す必要があるわけです。頻度表の渡し方にもいくつかの方法があります。

　一般的に圧縮の前段階である、モデル化について説明します。

の順番に説明します。
　一般に「モデル化」だけを行ってもデータが大きく圧縮されることはありません。「モデル化」の後「符号化」を行うことで、最終的にデータが圧縮されます。「モデル化」では「符号化」しやすいデータに変換しているともいえます。
　また、複数の「モデル化」を組み合わせることもできます。どの組み合わせがよいか？はまだまだ未知の領域といえます。

　一番簡単な変換（モデル化）方法です。略して'RLE'と呼ばれることもあります。

　例えば、"AABBBCCCCDDDDD" という４種類１４文字の文字列があったとします。これに「繰り返し数」の「かける（×）」という概念を取り入れて、

と８個のデータに変換します。
　このときの情報量の変化は、４種類の情報(A,B,C,D)が１４個で（２bit×１４）約２８bit から、７種類の情報(A,B,C,D,×3,×4,×5)が８個で（３bit×８）約２４bit へ、４bit 減っています。

　（「約２４bit」と書いたのは、このモデル化の後のエントロピー符号のアルゴリズムは単純な符号化でも Huffman符号でも 算術符号でも RangeCoder でもなんでもよいわけです。「約２４bit」とは「最悪でも２４bit以下には入るでしょう」という意味です。）

　このように「繰り返し数」の概念を取り入れるのがランレングスです。同じ文字の繰り返しの多いデータには有効ですが、複雑なデータには向いていません。本格的なデータ圧縮では、あまり使われることはありません。

　これも簡単な変換（モデル化）方法です。略して'MTF'と呼ばれることもあります。

　出現文字テーブル（MTFテーブル）を作成し、出現した文字コードを常に先頭に移動（登録）する方法です。
　例をあげると "PAPAMAMA" という文字列があった場合、最初の文字は P です。

　次の文字は A です。MTFテーブルの先頭は 'A' になります。

　次の文字は P ですが、MTFテーブルにすでに登録されているので、MTFテーブル内の位置（先頭からの位置）である２を出力します。そして、MTFテーブルは P が先頭になります。

　次は A です。P と同様に２になります。MTFテーブルの先頭は 'A' です。

　これを最後まで繰り返すと・・・

となります。
　このように 2 という小さな数値（MTFテーブルの先頭付近を示す数値）が多く出てくる形に変換されます。出力コードの頻度が偏るデータに変換できると、後段の符号化で高い圧縮率が出せるという理屈です。

　LZ とはデータ圧縮で最も有名な方式です。一般に「辞書」と言われる文字列のテーブルを作成し、データを圧縮します。

　辞書とは、文字列を登録したテーブルのことです。例えば、"ABURAKATABURA" という文字列では、"ABURA"という文字列が２回出てきています。このように、頻繁に使う文字列を辞書に登録しておくことで、文字列を辞書コードに変換できるので、情報量を減らすことができます。
　LZ には大きく LZ77 系と、LZ78 系の２種類があります。Lempel さんと Ziv さんが 1977年に発表した方式と、1978年に発表した方式という意味です。

　比較的新しいモデル化の概念で、LZよりも高い圧縮率（効率のよい変換）をします。（発案者の名前をとって、 BWT = Burrows-Wheeler Transform とも呼ばれています。）
　ただ、ソートの処理時間がデータ量に指数比例してしまうため、どの程度のデータを処理させるのかあらかじめ上限を決める必要があります。よって、データ量が多いと単純に圧縮率が上がるというわけにはなりません。

他の解説として、DO++ さんのページも参照ください
http://member.nifty.ne.jp/DO/algorithm/blocksorting.htm

BlockSorting を採用したアーカイバソフトには、GCA や BZIP2 があります。
どちらも圧縮速度は高速で、他のアーカイバソフトに負けていません。

GCA
http://www1.odn.ne.jp/synsyr/gca.html

BZIP2
http://www.linux.or.jp/JM/html/bzip2/man1/bzip2.1.html

　直訳すると「部分一致予測」です。
　PPM は「モデル化」＋「符号化」の２段構成方式とは言い難い面を持っていますが、どちらかと言えば「モデル化」の概念です。
　簡単に説明すると、複数の出現頻度表を持って、場合によって使い分けることを主な特徴としています。（符号化ではなく、PPM で頻度表を作成するところが単純に２段構成とは言い難いところ）
　例えば、英字と数字の混在する文字列を圧縮する場合、頻度表を２つ作り、

と用途を決めます。
　一般的な文字列では、英字の次に来る文字は英字である確率が高いので、英字が来た場合の出現頻度表（Ａ）の値は、英字の出現頻度が高くなります。またもう一方の、数字が来た場合の出現頻度表（Ｂ）の値は、数字の出現頻度が高くなります。
　このように、出現確率は均等ではなく、ある部分（ある状態）によって次の文字の出現確率が変化していることに着目した考え方なのです。
　この方式によって、出現頻度表が１つの符号化アルゴリズムよりも、より的確な符号化ができるようになります。
　文字の前後関係によって、出現頻度（出現確率）を変えるので、「次の文字を予測する方式」といわれます。
　この考え方を進めて行くと、'A〜Z'など、各文字単位に頻度表を作成する方法が考えられます。２５６種類の文字があるのなら、２５６個の頻度表を作るという考え方です。（この１文字分のすべての頻度表を作る考え方を Order-1 と呼んでいるようです。また２文字分の頻度表を作ると Order-2 と呼ぶそうです。Order-2 では１文字２５６種類とすると、すべての頻度表を確保するには６５５３６個分のメモリ空間が必要になりますが。）
　２５６個もの頻度表を実際に実装するには膨大なメモリ空間が必要になりますので、使用頻度の高い文字コードの頻度表から動的に作成したり、使わなそうな頻度表を破棄したりする工夫も必要になってきます。

　では、簡単な例をみてみましょう。

　例えば "ABAB1212" を変換する場合、これを１つの頻度表で符号化(Huffman符号化)したとすると、

　となり、bit に変換すると

　１６bit となります。では、英字と数字の２つの頻度表を作った場合を考えてみます。

　この２つの頻度表を Huffman符号で符号化してみます。

　この２つの頻度表から "ABAB1212" を符号化すると

　１１bit になりました。５bit 圧縮されたことになります。
　これはかなり極端な例ですが、考え方はこのような考え方であると思っていただいてよいかと思います。

　理論だけがあっても実装できなければ意味がありません。
　いままで紹介した「モデル化」と「符号化」の理論を実際に実装したアーカイバソフトを紹介します。

　より深く勉強したい人のために参考文献をあげておきます。

last update 2001/12/19
since 2001/07/17