今回は可逆圧縮アルゴリズムの中から、「シャノン・ファノ符号」と「ハフマン符号」という古典的なアルゴリズムを取り上げます。古典的とはいっても、ほかのアルゴリズムと簡単に組み合わせることができるため、ハフマン符号は今でも現役のアルゴリズムです。
一般に、データ圧縮アルゴリズムは「モデル化」と「符号化」という 2 つの部分に分けて考えることができます。モデルは入力された記号列から作成され、各記号の出現確率を求めます。たとえば、記号 a の確率は 1/10 で、記号 b の確率は 9/10 のように決定します。符号化は確率に基づいて符号語を割り当て、入力された記号を符号語に変換して出力します。なお、「連長圧縮 (ランレングス)」のように、このような考え方に当てはまらない圧縮アルゴリズムもあります。
モデル化にはいろいろな方法がありますが、最も単純なモデルは、各記号の出現確率を求め、それに基づいて符号語を割り当てる方法です。このような単純なモデルを「無記憶情報源モデル」といいます。情報源は記号を生成する元（発生源）と考えてください。
情報源が記号を生成するとき、以前に生成した記号との間に関係がないことを「無記憶」といいます。簡単にいえば、記号 t の次は h が出るとか、t, h と続いたら次は e が出るといった関係はなく、確率でのみ記号が生成されるということです。
たとえば、記号列 "abccddeeeeffffgggggggghhhhhhhh" はアスキーコードで 240 ビットになりますが、a, b, c, d を 4 ビット、e と f を 3 ビット、g と h を 2 ビットで表すことができれば、この記号列を 80 ビットで表現することができます。このように、出現確率の高い記号に短い符号語を割り当て、出現確率の低い記号に長い符号語を割り当てることができれば、データを圧縮することができます。
ところで、データ圧縮アルゴリズムの評価する場合、圧縮率のほかに「平均符号長」という尺度があります。これは、符号化された記号列のビット長を、入力された記号数で割った値として定義されます。たとえば、先ほどの記号列を 80 ビットで表すと、平均符号長は 80 / 30 = 2.666667 ビットになります。
無記憶情報源モデルの場合、各記号 \(a_i\) の出現確率 \(P(a_i)\) がわかると、次の式で平均符号長の下限値を求めることができます。
この値を平均情報量、またはエントロピー (Entoropy) と呼びます。ここで、平均符号長を L とすると \(H \leq L\) が成り立ちます。つまり、平均符号長 L はエントロピー H よりも短くすることはできないのです。先ほどの記号列のエントロピーを求めると次のようになります。
記号列 : abccddeeeeffffgggggggghhhhhhhh 記号 : 確率 : -P(x)*log P(x) ----------------------------- a : 1/30 : 0.163563 b : 1/30 : 0.163563 c : 1/15 : 0.2604594 d : 1/15 : 0.2604594 e : 2/15 : 0.3875854 f : 2/15 : 0.3875854 g : 4/15 : 0.5085042 h : 4/15 : 0.5085042 ----------------------------- エントロピー = 2.640224 30 * 2.640224 = 79.20672 bit
したがって、この記号列では平均符号長を 2.64 ビット以下にすることはできません。いいかえると、この記号列を表すには少なくても 30 * 2.640224 = 79.20672 ビット以上が必要になる、ということです。
これらのことをまとめると、シャノンの有名な定理になります。参考文献『文書データ圧縮アルゴリズム入門』より引用します。
情報源符号化定理 (Noiseless Coding Theorem)一意復号可能な平均符号長 L は、無記憶情報源のエントロピー H よりも小さくすることができない。すなわち不等式 \(H \leq L\) が成り立つ。また、平均符号長 L が \(H \leq L \lt H + 1\) を満足する瞬時に復号可能な符号が構成できる。
情報源符号化定理は、データ圧縮の限界を示したことと、限界に近づけるような符号化法があることを示した点で、データ圧縮においてとても重要な定理なのです。
ここで、ファイルのエントロピーを求めるプログラムを作ってみましょう。次のリストを見てください。
リスト : エントロピーを求める
import math
from byteio import *
def entoropy(name):
count = [0] * 256
with ByteIO(name, ROPEN) as f:
while True:
c = f.getc()
if c is None: break
count[c] += 1
total = sum(count)
e = 0.0
for x in range(256):
if count[x] == 0: continue
p = count[x] / total
e += - p * math.log(p, 2)
return e, e * total / 8
関数 entoropy() の引数 name はファイル名です。ファイルからデータをリードして、各記号の出現頻度を count に求めます。あとは、各記号の出現確率 p を求め、- p * math.log(p, 2) を計算して変数 e に加算します。これでエントロピー e を求めることができます。
それでは、実際に Canterbury Corpus で配布されているテストデータ The Canterbury Corpus のエントロピーを求めてみましょう。結果は次のようになりました。
表 : エントロピーの計算結果
ファイル名 サイズ エントロピー 下限値
----------------------------------------------
alice29.txt 152,089 4.567680 86,837
asyoulik.txt 125,179 4.808116 75,235
cp.html 24,603 5.229137 16,082
fields.c 11,150 5.007698 6,980
grammar.lsp 3,721 4.632268 2,155
kennedy.xls 1,029,744 3.573471 459,971
lcet10.txt 426,754 4.669118 249,071
plrabn12.txt 481,861 4.531363 272,936
ptt5 513,216 1.210176 77,636
sum 38,240 5.328990 25,473
xargs.1 4,227 4.898432 2,589
ファイルサイズ * エントロピー で圧縮の下限値を計算することができます。たとえば、alice29.txt の場合は、86, 837 バイトよりも圧縮することはできないということです。
ただし、この結果は無記憶情報源モデルの場合であり、モデル化によってエントロピーの値は異なることに注意してください。エントロピーをより小さくするモデルを作成することがでれきば、これよりも高い圧縮率を達成することができます。逆にいうと、圧縮率を高くするには、モデル化の工夫が必要であるということです。
あとは、具体的に符号を構成する方法が必要になります。最初に、基本的な符号化である「シャノン・ファノ符号」を説明します。次に、今でも広く用いられている「ハフマン符号」を説明しましょう。
シャノン・ファノ符号は、1948 年頃にシャノンとファノがほぼ同時に見いだした方法です。シャノン・ファノ符号は次に示すアルゴリズムで構成することができます。
このアルゴリズムを使って符号化すると、次のようになります。
記号列 abccddeeeeffffgggggggghhhhhhhh
分割の回数 1 2 3 4
──────────────────────────
記号 h, 個数 8, 符号 0 0
────────────────────── 分割２
記号 g, 個数 8, 符号 0 1
──────────────────────── 分割１
記号 f, 個数 4, 符号 1 0 0
──────────────────── 分割３
記号 e, 個数 4, 符号 1 0 1
────────────────────── 分割２
記号 d, 個数 2, 符号 1 1 0 0
────────────────── 分割４
記号 c, 個数 2, 符号 1 1 0 1
──────────────────── 分割３
記号 b, 個数 1, 符号 1 1 1 0
────────────────── 分割４
記号 a, 個数 1, 符号 1 1 1 1
平均符号長 = 80 / 30
図 1 : シャノン・ファノ符号の構成
まず、各記号の個数を数えて大きい順にソートして表を 2 分割します。この場合、記号の総数は 30 文字なので、最初は g - h と f - a の 2 つに分割します（分割 1）。そして、g - h には符号 0 を、f - a には 1 を割り当てます。あとは、分割した表に対して、この作業を繰り返して適用していきます。
g - h を 2 分割すると（分割 2）、それぞれ一つの要素しかなくなるので、g と h の符号語は 00 と 01 に決まります。f - a は、f - e と d - a に分割して符号を割り当てます（分割 2）。表には要素が複数残っているので、分割を継続します。f - e は 2 分割して（分割 3）、符号語が 100 と 101 に決定できます。d - a は、d - c と b - a に 2 分割し（分割 3）、さらに分割を行うと符号語を決定できます（分割 4）。
このように、シャノン・ファノ符号では表を分割していくたびに 0 と 1 の符号を割り当て、分割できなくなったところで符号語が決定されます。二分木でいえば、根から葉に向かって枝を延ばして符号を構成していくトップダウンの方法と考えることができます。これを符号木で表すと次のようになります。
○
／ ＼
0／ ＼1
／ ＼
○ ○
0／ ＼1 ／ ＼
ｈ ｇ 0／ ＼1
00 01 ／ ＼
○ ○
0／ ＼1 0／ ＼1
ｆ ｅ ／ ＼
100 101 ○ ○
0／ ＼1 0／ ＼1
ｄ ｃ ｂ ａ
1100 1101 1110 1111
図 2 : シャノン・ファノ符号の符号木
なお、d - a を分割するときに、d と c - a に分割することも考えられます。この場合の符号語は次のようになります。
記号 h, 個数 8, 符号 0 0 記号 g, 個数 8, 符号 0 1 記号 f, 個数 4, 符号 1 0 0 記号 e, 個数 4, 符号 1 0 1 記号 d, 個数 2, 符号 1 1 0 記号 c, 個数 2, 符号 1 1 1 0 記号 b, 個数 1, 符号 1 1 1 1 0 記号 a, 個数 1, 符号 1 1 1 1 1
このように、シャノン・ファノ符号は分割の仕方によって異なる符号が得られます。しかしながら、どちらの符号についても、出現頻度の高い記号には短い符号語を、低い記号には長い符号語を割り当てることになります。結局、どちらの符号を使っても記号列は 80 ビットに圧縮することができます。
それでは、シャノン・ファノ符号のプログラムを作りましょう。ここでは「ファイルの圧縮」は行わないで、符号木を作成するプログラムを作ります。最初に二分木の節を定義します。
リスト : 符号木の節
class Node:
def __init__(self, code, count = 0, left = None, right = None):
self.code = code
self.count = count
self.left = left
self.right = right
節を表すクラスはいつものように Node としました。インスタンス変数 code は記号を格納します。記号を格納するのは「葉」だけで、他の節は None を格納します。この値で葉と節を区別します。インスタンス変数 count は記号の個数をカウントします。
次は符号木を作る関数 make_tree() を作ります。
リスト : 符号木の生成
def make_tree(sym_table, low, high, total):
if low >= high:
node = sym_table[high]
else:
half = total // 2
c = 0
for i in range(low, high + 1):
p = c
c += sym_table[i].count
if c >= half:
if half - p < c - half:
c = p
i -= 1
break
node = Node(None)
node.left = make_tree(sym_table, low, i, c)
node.right = make_tree(sym_table, i + 1, high, total - c)
return node
シャノン・ファノ符号は、再帰を使うと簡単に実現できます。make_tree() の引数 sym_table は Node オブジェクトを格納した配列で、記号数の多い順にソートされています。low と high は sym_table の区間を表していて、total はその区間にある記号の総数です。
make_tree() は start から end の区間を総数 total の半分になるように 2 分割します。low が high 以上になったら区間の個数は 1 つしかないので、sym_table[high] の Node オブジェクトを返します。
そうでなければ、half に目標値となる total // 2 をセットします。次の for ループで、分割する位置を決定します。sym_table には出現頻度の大きい順に記号が並んでいるので、先頭位置 start から各記号の出現頻度を変数 c に加えていき、その値が half に達した位置で分割します。
ただし、c が half をオーバーする場合もあるので、一つ前の値を覚えておいて、half に近い値を選ぶように工夫します。変数 p に c の値をセットします。c に出現頻度の値を加算して、half 以上になったかチェックします。そして、half - p が c - half より小さければ、一つ前の値 p が half に近いので、その位置で区間を分割します。
for ループを抜けたあと、Node(None) で新しい節を生成し、make_tree を再帰呼び出しして左右の子をセットします。low から i までの区間が左の子になり、i + 1 から high までの区間が右の子になります。最後に node を返します。
それでは、ここで簡単なテストを行ってみましょう。次のリストを見てください。
リスト : シャノン・ファノ符号のテスト
def print_node(node, n):
if node is not None:
print_node(node.left, n + 1)
print(' ' * n, end='')
if node.code is None:
print('*')
else:
print(node.code)
print_node(node.right, n + 1)
sym_table = [Node(c, n) for c, n in [(7, 8), (6, 8), (5, 4), (4, 4),
(3, 2), (2, 2), (1, 1), (0, 1)]]
root = make_tree(sym_table, 0, 7, 30)
print_node(root, 0)
make_tree() で符号木を作って print_node() で表示します。実行結果は次のようになります。
7
*
6
*
5
*
4
*
3
*
2
*
1
*
0
正常に動作していますね。
ところで、記号がアスキーコード (8 bit) で表現されている場合、平均符号長と圧縮率には次の関係があります。
圧縮率 = 平均符号長 / 8
つまり、圧縮率を小さくすることと平均符号長を短くすることは同じことになります。したがって、データ圧縮における最適な符号は、各記号を符号化するときに、その符号長の平均が最小になるような符号のことです。このような符号を「コンパクト符号」といいます。シャノン・ファノ符号はコンパクト符号ではありません。次に説明する「ハフマン符号」がコンパクト符号になります。
ハフマン符号は 1952 年に D. Huffman 氏が考案した、平均符号長を最小にすることができる符号化法です。シャノン・ファノ符号は平均符号長が最小になることは保証されていないので、ハフマン符号の方が圧縮率は優れていることになります。このため、実際にシャノン・ファノ符号が使われることはほとんどありません。
ハフマン符号の構成は、シャノン・ファノ符号と同様に符号木を作ることで行いますが、葉から根に向かって木を構成していくところが大きく異なります。つまり、ボトムアップの方法になります。ハフマン符号を構成するアルゴリズムを以下に示します。
それでは、記号列 abccddeeeeffffgggggggghhhhhhhh を入力したときの、ハフマン符号化の具体的な構成例を示しましょう。
(８) (８) (４) (４) (２) (２) ─→(１) (１)
ｈ ｇ ｆ ｅ ｄ ｃ ｂ ａ
1. ａとｂを取り出す。
N1
(８) (８) (４) (４) (２) (２) (２)
ｈ ｇ ｆ ｅ ｄ ｃ ／ ＼
(１) (１)
ｂ ａ
2. 新しい節 N1 を作りａとｂを格納する。
N1
(８) (８) (４) (４) (２) (２) (２)
ｈ ｇ ｆ ｅ ／ ＼ ｄ ｃ
(１) (１)
ｂ ａ
3. N1 を登録する。
図 3 : ハフマン符号の構成 (その１)
まず、各記号の出現頻度を求めて「節」の集合を構成します。この集合の中から、出現頻度の小さい方から 2 つ取り出して、新しい節に格納します。最初は、a と b を取り出して N1 に格納します。このとき、N1 の出現頻度は a と b を足した値をセットします。そして、この節 N1 を節の集合に登録します。この時点で節の集合は、{ c, d, N1, e, f, g, h } となります。あとは、この操作を節が一つになるまで繰り返します。
N2 N1
(８) (８) (４) (４) (４) (２)
ｈ ｇ ／ ＼ ｆ ｅ ／ ＼
(２) (２) (１) (１)
ｄ ｃ ｂ ａ
4. ｄとｃを取り出して新しい節 N2 を作る。
N4 N3
(８) (８) (８) (６)
／ ＼ ｈ ｇ ／ ＼
(４) (４) (２) (４)
／ ＼ ｆ ／ ＼ ｅ
(２) (２) (１) (１)
ｄ ｃ ｂ ａ
5. N1 とｅを取り出して新しい節 N3 を作る。
6. N2 とｆを取り出して新しい節 N4 を作る。
図 4 : ハフマン符号の構成 (その２)
同様に、節の集合の中から d と c を取り出して、新しい節 N2 にセットして集合に登録します。節の集合は {N1, e, f, N2, g, h} となり、この中から頻度 2 の N1 と頻度 4 の e を取り出して N3 を登録します。すると、節の集合は {f, N2, N3, g, h} となり、その中から頻度 4 の N2 と f を取り出して N4 を登録します。
ROOT:N7 左の枝を 0 とすると
／ ＼
／ ＼ a : 1101
N6(16) (14)N5 b : 1100
／ ＼ ／ ＼ c : 0001
(８) (８)(８) (６) d : 0000
／ ＼ ｈ ｇ ／ ＼ e : 111
(４) (４) (２) (４) f : 001
／ ＼ ｆ ／ ＼ ｅ g : 10
(２) (２) (１) (１) h : 01
ｄ ｃ ｂ ａ 平均符号長 = 80 / 30
7. N3 とｇを取り出して新しい節 N5 を作る。
8. N4 とｈを取り出して新しい節 N6 を作る。
9. N5 と N6 を取り出して新しい節 N7 を作る。
10. 節が N7 の一つしかなくなったので終了。
図 5 : ハフマン符号の構成 (その３)
この時点で節の集合は {N3, g, h, N4} の 4 つあります。小さい方から N3 と g を取り出して N5 を登録します。次に、h と N4 を取り出して N6 を登録します。節の集合は {N5, N6} となり、この 2 つを一つにまとめてハフマン木が完成します。
各記号の符号語は、ハフマン木の ROOT から葉に向かってたどっていくことで求めることができます。左右の枝にラベル 0 と 1 を割り当てることにすると、記号 a は「右、右、左、右」と枝をたどって葉に到達するので、符号語は 1101 となります。ほかの記号も同様に求めることができます。
なお、シャノン・ファノ符号のときにも説明しましたが、ハフマン符号も「葉」の組み合わせ方によって、異なる符号が得られます。しかしながら、どのハフマン符号でも同一の平均符号長が得られるので、圧縮率は同じになります。
それでは、ハフマン符号のプログラムを作りましょう。ここでは「ファイルの圧縮」は行わないで、ハフマン木を作成するプログラムを作ります。最初に二分木の節を定義します。
リスト : 符号木の節
class Node:
def __init__(self, code, count = 0, left = None, right = None):
self.code = code
self.count = count
self.left = left
self.right = right
def __gt__(x, y): return x.count > y.count
def __le__(x, y): return x.count <= y.count
節を表すクラスは Node としました。定義するインスタンス変数はシャノン・ファノ符号と同じです。ハフマン符号の場合、プライオリティキュー (ヒープ) を使うと簡単にプログラムを作ることができます。拙作のページ「二分木とヒープ」で作成したプライオリティーキュー (PQueue) を利用するため、特殊メソッド __gt__() と __le__() を定義します。
次は符号木を作る関数 make_tree() を作ります。
リスト : ハフマン木の生成
from pqueue import *
def make_tree(sym_table):
q = PQueue()
for x in sym_table:
if x.count > 0: q.push(x)
while True:
n1 = q.pop()
if q.isEmpty():
# 修正 (2007/10/06)
if n1.code is not None:
for x in sym_table:
if x.count == 0: return Node(None, 0, n1, x)
return n1
n2 = q.pop()
q.push(Node(None, n1.count + n2.count, n1, n2))
最初にプライオリティキュー (PQueue) を生成して変数 q にセットします。次に、sym_table から Node オブジェクトを取り出して、記号があるオブジェクトだけをメソッド push でキューに追加します。それから、while ループでキューからデータを取り出して、ハフマン木を構成します。
キューからメソッド pop でデータを取り出して変数 n1 と n2 にセットします。データを一つ取り出したあとキューが空になった場合は、ハフマン木が完成したので n1 を返します。そうでなければ、新しい Node オブジェクトを生成してキューに追加します。このとき、n1 と n2 を左右の子にセットし、count は n1.count + n2.count に設定します。これで、ハフマン木を構成することができます。
それでは、ここで簡単なテストを行ってみましょう。次のリストを見てください。
リスト : ハフマン符号のテスト
sym_table = [Node(c, n) for c, n in [(7, 8), (6, 8), (5, 4), (4, 4),
(3, 2), (2, 2), (1, 1), (0, 1)]]
root = make_tree(sym_table)
print_node(root, 0)
make_tree() で符号木を作って print_node() で表示します。実行結果は次のようになります。
3
*
5
*
4
*
2
*
1
*
0
*
7
*
6
ハフマン木の形は例題とは異なりますが、これでも同じ平均符号長 (80 / 30) になります。
シャノン・ファノ符号とハフマン符号でファイルを圧縮する場合、問題点が一つあります。ファイルを圧縮する場合、記号の出現頻度を調べて符号木を構成しますが、符号化されたファイルを復号する場合も、符号化した時に構成した符号木が必要になります。このため、圧縮ファイルには符号木の情報を付加しなければならず、圧縮率が低下することになります。
いちばん単純な方法は、各記号の出現頻度をそのままファイルに付加することです。ファイルを復号するときは、出現頻度から符号木を再構成すればいいのです。出現頻度を 4 バイトで格納すると 1024 byte 必要になりますが、2 バイトで収まるように工夫すると 512 byte で済みます。
また別な方法として、符号木をそのまま付加する方法があります。ファイルに書き込むときは、符号木を「行きがけ順」 [*1] で巡回します。途中の節ではフラグ 0 を出力して左右の枝をたどり、葉に到達したらフラグ 1 と記号 (8 bit) を出力します。ファイルから符号木を読み込むときは、フラグが 0 ならば節を作って左右の枝をたどっていき、1 ならば 8 bit 読み込んで記号を復号して葉にセットします。
(０)
／ ＼
／ ＼
(１) (８)
／ ＼ ／ ＼
(２) (７)(９) (10)
／ ＼ ｈ ｇ ／ ＼
(３) (６) (11) (14)
／ ＼ ｆ ／ ＼ ｅ
(４) (５) (12) (13)
ｄ ｃ ｂ ａ
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
---------------------------------------------------------
0 0 0 0 1 d 1 c 1 f 1 h 0 1 g 0 0 1 b 1 a 1 e
【注意】括弧内の数値は節を訪れる順番を表す
図 6 : ハフマン符号の表現方法
たとえば、説明で用いたハフマン木を行きがけ順で巡回すると、上図に示した順番で全ての節を出力することができます。そして、このデータからハフマン木を再構成できるのです。フラグ 0 と 1 を 1 ビットで表すと、記号の種類は最大 256 種類で、節の総数は 256 * 2 - 1 = 511 になるので、この場合 256 * 8 + 511 (bit) となり 320 byte で済みます。今回はこの方法を採用することにしましょう。
プログラムは再帰を使うと簡単に作成することができます。次のリストを見てください。
リスト : 符号木の入出力
from bitio import *
# 符号木の書き出し
def write_tree(node, fout):
if node.code is not None:
# 葉
fout.putbit(1)
fout.putbits(8, node.code)
else:
fout.putbit(0)
write_tree(node.left, fout)
write_tree(node.right, fout)
# 符号木の読み込み
def read_tree(fin):
if fin.getbit() == 1:
# 葉
node = Node(fin.getbits(8))
else:
node = Node(None)
node.left = read_tree(fin)
node.right = read_tree(fin)
return node
関数 write_tree() は符号木を行きがけ順でたどってビットストリーム (BitIO のオブジェクト) fout に出力します。node.code が None でなければ「葉」に到達したので、putbit() で 1 を出力して、putbits() で記号を出力します。枝をたどるときは、putbit() で 0 を出力してから、write_tree() を再帰呼び出しします。
関数 read_tree() は、ビットストリーム fin からデータをリードして符号木を再構成します。fin から getbit() で 1 ビット読み込みます。その値が 1 ならば「葉」なので、getbits() で記号を読み込み、Node でオブジェクトを生成して返します。そうでなければ、read_tree() を再帰呼び出しして木をたどります。Node で新しいオブジェクトを生成して、左右の子に read_tree() の返り値をセットします。
それでは、シャノン・ファノ符号のプログラムを作りましょう。メインルーチンは前回作成したランレングスのプログラムと同じで、符号化と復号をオプション -e と -d で指定します。ビット入出力を行うクラス BitIO を使うので、元のファイルサイズをファイルの先頭にセットします。したがって、圧縮ファイルの構造は次のようになります。
ファイルサイズ (4 byte) + 符号木 (不定長) + 圧縮データ (不定長)
符号化を行う関数 encode() は次のようになります。
リスト : 符号化処理
# ファイルの読み込み
def read_file(fin):
while True:
c = fin.getc()
if c is None: break
yield c
# 符号化
def encode(fin, fout):
# 出現頻度表の作成
sym_table = [Node(x) for x in range(CHAR)]
for x in read_file(fin):
sym_table[x].count += 1
# 符号木の生成
sym_table.sort(key = lambda x: x.count, reverse = True)
total = 0
x = 0
while x < CHAR:
if sym_table[x].count == 0: break
total += sym_table[x].count
x += 1
# 修正 (2007/10/06)
if x < 2:
root = Node(None, 0, sym_table[0], sym_table[1])
else:
root = make_tree(sym_table, 0, x - 1, total)
# 符号語の生成
make_code(root, 0, 0)
# 符号木の出力
write_tree(root, fout)
# 符号化
fin.stream.seek(0) # 巻き戻し
for x in read_file(fin):
fout.putbits(*code_table[x])
encode() の引数 fin が入力ファイル (ByteIO のオブジェクト)、fout が出力ファイル (BitIO のオブジェクト) です。最初に記号の出現頻度表 sym_table を作成します。sym_table には Node のオブジェクトをセットします。CHAR (256) は記号の種類を表します。そして、read_file() でファイルから記号を読み込み、Node オブジェクトの count を +1 します。
次に符号木を生成します。sort() で sym_table をソートします。このとき、キーワード引数 key に lambda x: x.count を、キーワード引数 reverse に True を指定します。これで count を基準に sym_table を降順でソートすることができます。
出現していない記号は sym_table の後ろに集まります。次の while ループで、出現している記号の範囲を求めます。このとき、記号の総数もカウントしています。そして、make_tree() で符号木を生成します。
次に、関数 make_code() で符号木から符号語と符号長を求めて、配列 code_table にセットします。code_table はグローバル変数として定義します。それから、write_tree() で符号木を出力します。最後に、fin.stream.seek(0) でファイルを巻き戻して、記号 x に対応する符号語を putbits() で出力します。
次は符号木から符号語を作る関数 make_code() を作ります。
リスト : 符号語の生成
# 符号長と符号語を格納するテーブル
code_table = [None] * CHAR
# 符号語の生成
def make_code(node, n, code):
if node.code is not None:
# 葉
code_table[node.code] = (n, code)
else:
make_code(node.left, n + 1, code << 1) # left is 0
make_code(node.right, n + 1, (code << 1) | 1) # right is 1
make_code() は符号木を巡回し、各記号の符号語と符号長を code_table にセットします。引数の node は現在いる節、n はここまでの木の高さ (符号長と同じ)、code は符号語を表します。
node.code が None でない場合は葉に到達したので、code_table[node.code] に符号長 n と符号語 code をタプルにまとめてセットします。そうでなければ、make_code() を再帰呼び出しして符号木をたどります。左の枝をたどるときは 0 なので、code を左へ 1 ビットシフトします。右の枝をたどるときは 1 なので、code を左へ 1 ビットシフトしてから最下位ビットを 1 にします。
次は復号処理を行う関数 decode() を作ります。
リスト : 復号処理
def decode(fin, fout, size):
# 符号木の読み込み
root = read_tree(fin)
# 復号
while size > 0:
node = root
# 木をたどる
while node.code is None:
if fin.getbit() == 0:
node = node.left
else:
node = node.right
# 出力
fout.putc(node.code)
size -= 1
引数 fin が入力ファイル (BitIO のオブジェクト) で、fout が出力ファイル (ByteIO のオブジェクト)、size が復号する記号の総数です。最初に read_tree() で符号木を読み込み、root にセットします。次の while ループで、size バイト分復号するまで処理を繰り返します。
2 番目の while ループで、符号木をたどります。節 node の code が None でなければ「葉」です。そうでなければ、getbit() で 1 ビット読み込み、0 であれば左の子をたどり、1 であれば右の子をたどります。葉に到達したら while ループを終了して、putc() で記号 node.code を出力します。
あとのプログラムは簡単なので、説明は割愛いたします。詳細はプログラムリスト１をお読みください。
それでは、実際に Canterbury Corpus で配布されているテストデータ The Canterbury Corpus を圧縮してみましょう。
表 : シャノン・ファノ符号の結果
ファイル名 サイズ Shannon 符号化 復号 下限値
-----------------------------------------------------------
alice29.txt 152,089 88,049 0.439 0.387 86,837
asyoulik.txt 125,179 76,081 0.476 0.318 75,235
cp.html 24,603 16,332 0.104 0.092 16,082
fields.c 11,150 7,202 0.129 0.049 6,980
grammar.lsp 3,721 2,274 0.021 0.037 2,155
kennedy.xls 1,029,744 464,925 2.652 2.000 459,971
lcet10.txt 426,754 251,234 1.363 1.036 249,071
plrabn12.txt 481,861 275,914 1.502 1.142 272,936
ptt5 513,216 106,865 0.934 0.567 77,636
sum 38,240 26,059 0.200 0.112 25,473
xargs.1 4,227 2,700 0.044 0.018 2,589
-----------------------------------------------------------
合計 2,810,784 1,317,635 7.864 5.758 1,274,965
符号化と復号の単位 : 秒
実行環境 : Python 3.8.10, Ubuntu 20.04 LTS (WSL1), Intel Core i5-6200U 2.30GHz
圧縮率は ptt5 を除いて圧縮の限界に近い値となりました。このように、シャノン・ファノ符号は性能の悪い符号化方式ではありません。シャノン・ファノ符号の場合、1 ビットよりも短い符号語は存在しません。ptt5 は記号 0 がとても多く出現するので、記号 0 に 1 ビットの符号語を割り当てても、限界に近い圧縮率を達成することはできないのです。これはハフマン符号でも同じです。
「算術符号」または「レンジコーダ (Range Coder)」を用いると、記号に 1 ビット未満の符号語を割り当てることができるので、このような場合でも限界に近い圧縮率を達成することができます。
なお、実行時間の結果は M.Hiroi のコーディング、実行したマシン、プログラミング言語などの環境に大きく依存しています。また、これらの環境だけではなく、データの種類によっても実行時間はかなり左右されます。興味のある方は、いろいろなデータをご自分の環境で試してみてください。
次はハフマン符号のプログラムを作ります。符号化を行うプログラムは次のようになります。
リスト : 符号化
# 符号化
def encode(fin, fout):
# 出現頻度表の作成
sym_table = [Node(x) for x in range(CHAR)]
for x in read_file(fin):
sym_table[x].count += 1
# ハフマン木の生成
root = make_tree(sym_table)
# 符号語の生成
make_code(root, 0, 0)
# ハフマン木の出力
write_tree(root, fout)
# 符号化
fin.stream.seek(0) # 巻き戻し
for x in read_file(fin):
fout.putbits(*code_table[x])
処理内容はシャノン・ファノ符号とほとんど同じです。符号木 (ハフマン木) を作成する make_tree() には sym_table をそのまま渡せばいいので、シャノン・ファノ符号のプログラムよりも簡単になります。
復号処理はシャノン・ファノ符号と同じです。あとのプログラムは簡単なので、説明は割愛いたします。詳細はプログラムリスト２をお読みください。
それでは、実際に Canterbury Corpus で配布されているテストデータ The Canterbury Corpus を圧縮してみましょう。
表 : ハフマン符号の結果
ファイル名 サイズ Huff 符号化 復号
------------------------------------------------
alice29.txt 152,089 87,785 0.450 0.372
asyoulik.txt 125,179 75,895 0.425 0.310
cp.html 24,603 16,310 0.096 0.070
fields.c 11,150 7,143 0.042 0.034
grammar.lsp 3,721 2,269 0.138 0.038
kennedy.xls 1,029,744 462,856 2.619 2.069
lcet10.txt 426,754 250,673 1.286 1.127
plrabn12.txt 481,861 275,690 1.447 1.155
ptt5 513,216 106,754 0.948 0.565
sum 38,240 25,968 0.144 0.117
xargs.1 4,227 2,698 0.023 0.017
-------------------------------------------------
合計 2,810,784 1,314,041 7.690 5.874
符号化と復号の単位 : 秒
全てのファイルでシャノン・ファノ符号よりも高い圧縮率になりました。ハフマン符号は優れた符号化方式であることがわかります。
なお、実行時間の結果は M.Hiroi のコーディング、実行したマシン、プログラミング言語などの環境に大きく依存しています。また、これらの環境だけではなく、データの種類によっても実行時間はかなり左右されます。興味のある方は、いろいろなデータをご自分の環境で試してみてください。
#
# shannon.py : シャノン・ファノ符号
#
# Copyright (C) 2007-2022 Makoto Hiroi
#
import argparse, os.path, time
from bitio import *
# 定数
CHAR = 256
# 符号木の節
class Node:
def __init__(self, code, count = 0, left = None, right = None):
self.code = code
self.count = count
self.left = left
self.right = right
# 符号を格納するテーブル
code_table = [None] * CHAR
# 符号の生成
def make_code(node, n, code):
if node.code is not None:
# 葉
code_table[node.code] = (n, code)
else:
make_code(node.left, n + 1, code << 1) # left is 0
make_code(node.right, n + 1, (code << 1) | 1) # right is 1
# 符号木の出力
def write_tree(node, fout):
if node.code is not None:
# 葉
fout.putbit(1)
fout.putbits(8, node.code)
else:
fout.putbit(0)
write_tree(node.left, fout)
write_tree(node.right, fout)
# 符号木の読み込み
def read_tree(fin):
if fin.getbit() == 1:
# 葉
node = Node(fin.getbits(8))
else:
node = Node(None)
node.left = read_tree(fin)
node.right = read_tree(fin)
return node
# 符号木の生成
def make_tree(sym_table, low, high, total):
if low >= high:
node = sym_table[high]
else:
half = total // 2
c = 0
for i in range(low, high + 1):
p = c
c += sym_table[i].count
if c >= half:
if half - p < c - half:
c = p
i -= 1
break
#
node = Node(None)
node.left = make_tree(sym_table, low, i, c)
node.right = make_tree(sym_table, i + 1, high, total - c)
return node
# ファイルの読み込み
def read_file(fin):
while True:
c = fin.getc()
if c is None: break
yield c
# 符号化
def encode(fin, fout):
# 出現頻度表の作成
sym_table = [Node(x) for x in range(CHAR)]
for x in read_file(fin):
sym_table[x].count += 1
# 符号木の生成
sym_table.sort(key = lambda x: x.count, reverse = True)
total = 0
x = 0
while x < CHAR:
if sym_table[x].count == 0: break
total += sym_table[x].count
x += 1
# 修正 (2007/10/06)
if x < 2:
root = Node(None, 0, sym_table[0], sym_table[1])
else:
root = make_tree(sym_table, 0, x - 1, total)
# 符号語の生成
make_code(root, 0, 0)
# 符号木の出力
write_tree(root, fout)
# 符号化
fin.stream.seek(0) # 巻き戻し
for x in read_file(fin):
fout.putbits(*code_table[x])
# 符号化
def encode_file(name1, name2):
with ByteIO(name1, ROPEN) as fin, BitIO(name2, WOPEN) as fout:
size = os.path.getsize(name1)
fout.putbits(32, size)
if size > 0: encode(fin, fout)
# 復号
def decode(fin, fout, size):
# 符号木の読み込み
root = read_tree(fin)
# 復号
while size > 0:
node = root
# 木をたどる
while node.code is None:
if fin.getbit() == 0:
node = node.left
else:
node = node.right
# 出力
fout.putc(node.code)
size -= 1
# 復号
def decode_file(name1, name2):
with BitIO(name1, ROPEN) as fin, ByteIO(name2, WOPEN) as fout:
size = fin.getbits(32)
if size > 0: decode(fin, fout, size)
# オプション解析
parser = argparse.ArgumentParser(description='シャノン・ファノ符号')
parser.add_argument('name1', help='入力ファイル')
parser.add_argument('name2', help='出力ファイル')
parser.add_argument('-e', '--encode', action='store_true', help='符号化')
parser.add_argument('-d', '--decode', action='store_true', help='復号')
args = parser.parse_args()
# 実行
s = time.time()
if args.encode and not args.decode:
encode_file(args.name1, args.name2)
elif args.decode:
decode_file(args.name1, args.name2)
else:
print('option error')
e = time.time()
print('{:.3f}'.format(e - s))
#
# huffman.py : ハフマン符号
#
# Copyright (C) 2007-2022 Makoto Hiroi
#
import argparse, os.path, time
from bitio import *
from pqueue import *
# 定数
CHAR = 256
# ハフマン木の節
class Node:
def __init__(self, code, count = 0, left = None, right = None):
self.code = code
self.count = count
self.left = left
self.right = right
def __gt__(x, y): return x.count > y.count
def __le__(x, y): return x.count <= y.count
# 符号を格納するテーブル
code_table = [None] * CHAR
# 符号の生成
def make_code(node, n, code):
if node.code is not None:
# 葉
code_table[node.code] = (n, code)
else:
make_code(node.left, n + 1, code << 1) # left is 0
make_code(node.right, n + 1, (code << 1) | 1) # right is 1
# ハフマン木の出力
def write_tree(node, fout):
if node.code is not None:
# 葉
fout.putbit(1)
fout.putbits(8, node.code)
else:
fout.putbit(0)
write_tree(node.left, fout)
write_tree(node.right, fout)
# ハフマン木の読み込み
def read_tree(fin):
if fin.getbit() == 1:
# 葉
node = Node(fin.getbits(8))
else:
node = Node(None)
node.left = read_tree(fin)
node.right = read_tree(fin)
return node
# ハフマン木の生成
def make_tree(sym_table):
q = PQueue() # ヒープの生成
for x in sym_table:
if x.count > 0: q.push(x)
while True:
n1 = q.pop()
if q.isEmpty():
# 修正 (2007/10/06)
if n1.code is not None:
for x in sym_table:
if x.count == 0: return Node(None, 0, n1, x)
return n1
n2 = q.pop()
q.push(Node(None, n1.count + n2.count, n1, n2))
# ファイルの読み込み
def read_file(fin):
while True:
c = fin.getc()
if c is None: break
yield c
# 符号化
def encode(fin, fout):
# 出現頻度表の作成
sym_table = [Node(x) for x in range(CHAR)]
for x in read_file(fin):
sym_table[x].count += 1
# ハフマン木の生成
root = make_tree(sym_table)
# 符号語の生成
make_code(root, 0, 0)
# ハフマン木の出力
write_tree(root, fout)
# 符号化
fin.stream.seek(0) # 巻き戻し
for x in read_file(fin):
fout.putbits(*code_table[x])
# 符号化
def encode_file(name1, name2):
size = os.path.getsize(name1)
with ByteIO(name1, ROPEN) as fin, BitIO(name2, WOPEN) as fout:
fout.putbits(32, size)
if size > 0: encode(fin, fout)
# 復号
def decode(fin, fout, size):
# ハフマン木の読み込み
root = read_tree(fin)
# 復号
while size > 0:
node = root
# 木をたどる
while node.code is None:
if fin.getbit() == 0:
node = node.left
else:
node = node.right
# 出力
fout.putc(node.code)
size -= 1
# 復号
def decode_file(name1, name2):
with BitIO(name1, ROPEN) as fin, ByteIO(name2, WOPEN) as fout:
size = fin.getbits(32)
if size > 0: decode(fin, fout, size)
# オプション解析
parser = argparse.ArgumentParser(description='ハフマン符号')
parser.add_argument('name1', help='入力ファイル')
parser.add_argument('name2', help='出力ファイル')
parser.add_argument('-e', '--encode', action='store_true', help='符号化')
parser.add_argument('-d', '--decode', action='store_true', help='復号')
args = parser.parse_args()
# 実行
s = time.time()
if args.encode and not args.decode:
encode_file(args.name1, args.name2)
elif args.decode:
decode_file(args.name1, args.name2)
else:
print('option error')
e = time.time()
print('{:.3f}'.format(e - s))