【第3章　ハフマン符号化】

3.1 可変長符号の種類

第1章で説明しましたように、ハフマン符号は固定長符号に可変長符号を割り当てるFV符号の代表的なものです。 ハフマン符号の詳しい説明をする前に、可変長符号の種類について少し説明しておきましょう。 ４つの記号「ａ」、「ｂ」、「ｃ」、「ｄ」に対して、左表のような内容の符号を割り当てることを考えてみます。

最初の固定長符号は、現在のコンピュータで用いられている固定長符号と原理的に同じものです。 このような符号の場合、符号化されたビット列から元の記号を一意に(ただ一通りの方法で)復元できます。

それに対して符号１では、符号化されたビット列から元の記号を一意に復元できるとは限りません。 例えば「010001」というビット列は、

など、色々な復元法が可能です。 このような符号を「一意復号不可能な符号」といい、固定長符号のような符号を「一意復号可能な符号」といいます。

一意復号可能な符号でなければ圧縮には利用できませんから、符号１を一意復号可能にすることを考えますと、すぐに思いつくのが符号１の前に符号長を付け加える方法と、符号の最後に目印となるビットを付け加える方法です。 符号２は符号１の前に(符号長−１)を表す１ビットを付け加えたもので、第1章のハフマン符号の解説中で説明したものと原理的に同じものです。 符号３は符号の最後に値０のビットを付け加えて、終了目印にしたものです。

これらの符号とは異なり、符号のビット内容そのもので一意復号可能にするように工夫したものが符号４と符号５です。 例えば符号４で「001011111」というビット列は、

と一意に復号され、符号５で「0100101110」というビット列は、

と一意に復号されます。

しかし符号４では、「001011111」のうちの最初の７ビット「0010111」を読み込んだ段階では、

という３通りの復号が可能で、符号列を最後まで読み込まないと正しく復号できません。 それに対して符号５では、最初の「0」を読み込んだ段階で「ａ」が決まり、次の「100」を読み込んだ段階で「ｂ］が決まり、次の「101」を読み込んだ段階で「ｃ］が決まり、最後の「110」を読み込んで「ｄ」が決まります。

このように、１つの記号に対する符号を読み込んだ瞬間に復号することのできる符号を「瞬時に復号可能な符号」といい、符号４のように先まで読まなければ正確に復号することができない符号を「瞬時に復号不可能な符号」といいます。 一般に、ある符号が瞬時に復号可能な符号であるためには、「ある記号に対する符号の末尾の何ビットかを除いたビット列が、別の符号と一致してはならない」という条件を満足していなければなりません。 この条件のことを「語頭条件」といい、これを満足する符号のことを「接頭符号(prefix code)」といいます。

例えば符号４では、ｃに対する符号「011」の最後の１を除いた「01」はｂに対する符号と一致し、さらにまた１を除いた「0」はａに対する符号と一致してしまい、接頭符号とはなりません。 それに対して符号５では、どの符号の末尾の何ビットかを除いても別の符号と一致するものはなく接頭符号となります。 前表の符号では符号２、符号３、符号５が接頭符号であり、瞬時に復号可能な符号です。

3.2 シャノン・ファノ符号とハフマン符号

データ圧縮に用いる可変長符号は、次のような条件を満たすものが理想です。

1. 一意復号可能な符号で、できれば瞬時に復号可能な符号であること。
2. 頻繁に出てくる記号には短いビット数の符号が対応し、あまり出てこない記号には長いビット数の符号が対応すること。
3. 平均符号長が小さいこと。

この条件を比較的良く満たす符号として最初に発明されたのが「シャノン・ファノ符号(Shannon ＆ Fano code)」です。 この符号は、1948年頃、ベル研究所のシャノンとMIT(マサチューセッツ工科大学)のファノによって独立に開発されました。

シャノン(C.E.Shannon)は情報量や情報のエントロピーといった概念を定義し、情報理論の基礎を築いた有名なコンピュータ研究者で、コンピュータが普及する以前の1948年に、すでにデータ圧縮法を開発していた先見性には驚かされます。

シャノン・ファノ符号が開発されてから４年後の1952年、ハフマン(D.A.Huffman)が1.と2.の条件を満たし、しかも平均符号長を最小にするような符号を開発しました。 このため現在では、実際のデータ圧縮にはハフマン符号が用いられることが多く、シャノン・ファノ符号は歴史的意義しか持たなくなりました。 シャノン・ファノ符号とハフマン符号は非常に良く似ているので、ここではシャノン・ファノ符号の解説は省略し、ハフマン符号についてだけ解説することにします。

3.3 符号の木

ハフマン符号化では「符号の木」と呼ばれる木構造を利用して符号を構成します。 符号の木では各線分を「枝」と呼び、枝の両端の点を「節点」と呼びます。 通常の木と違い符号の木は上から下に向かって伸びていて、一番上の節点を「根(下図の一番上の○印)」、上下に枝がついている節点を「内部節点(下図の○印)」、下に枝がついていない節点を「葉(下図の□印)」といいます。 １つの節点から下に伸びる枝は最大で２本あり、それぞれビット０とビット１が対応付けられています。 そして葉には１つの記号が対応付けられていて、根から葉まで枝をたどっていった時、枝に付けられたビットを順番に並べていくと、その記号に対応する符号となります。

符号の木から構成されるハフマン符号
a：0　b：100　c：101　d：110　e：1110　f：1111

例えば上図の木で記号「ｃ］に対応する符号を調べますと、次のようになります。

1. 根から右の枝(ビット１)をたどる　→　符号：１
2. 次の内部節点から左の枝(ビット０)をたどる　→　符号：１０
3. 次の内部節点から右の枝(ビット１)をたどる　→　符号：１０１
4. 「ｃ」の葉に到達　→　符号：１０１で確定

１つの葉に到達する経路は１通りしかありませんので、ある可変長符号系列を符号の木で表現することができるのなら、その符号は一意復号可能でかつ瞬時に復号可能な符号となります。

上図の符号の木は3.1節の符号表の符号５と同じ符号系列ですから、ちゃんとした符号の木で表現できましたが、一意復号不可能な符号である同表中の符号１と、瞬時に復号不可能な符号である符号４を符号の木で表現してみますと下図のようになります。

上図より、ある符号が瞬時に復号可能な符号つまり接頭符号であるための語頭条件「ある記号に対する符号の末尾の何ビットかを除いたビット列が、別の符号と一致してはならない」は、符号の木では「記号は葉にだけ対応付けられ、内部節点に対応付けられてはならない」という、ごく自然で直観的な条件になることがわかります。 したがってある符号が接頭符号であることと、正しい符号の木で表現できることは同じ意味になります。

符号の木は記号を符号化する時だけでなく、符号化されたデータを元の記号に復号する場合にも利用することができます。 例えば前述の符号の木を用いて符号列「0100101110」を復号しますと、次のようになります。

1. 最初の１ビット「0」について、根からビットに対応する枝をたどると、
   根→左枝(0)→葉「a」に到達
   となり、記号「ａ」を復号。
2. 次の３ビット「100」について、同様に根からビットに対応する枝をたどると、
   根→右枝(1)→左枝(0)→左枝(0)→葉「ｂ」に到達
   となり、記号「ｂ」を復号。
3. 次の３ビット「101」で葉「ｃ］に到達→記号「ｃ」を復号。
4. 最後の３ビット「110」は葉「ｄ］に到達→記号「ｄ」を復号。

以上より、最終的には次のように復号します。

最終更新日：2001年7月2日 　第2章へ 第4節へ

　webmaster@snap-tck.com 　Copyleft (C) 2000 SNAP(Sugimoto Norio Art Production)