はじめに
それでは情報理論の圧縮技術における最も重要な考え方の一つである符号の木(Tree)を学んでいきましょう。木を用いた実装は今後の講義でも使うので、木の作り方から応用法まで習得しましょう。
符号の木
木とは根をはじめに節点と節点を枝で繋いだ図のことです。特に端にある節点のことを葉と呼びます。符号の木はそれぞれの葉を符号に見立てるものです。根以外のすべての節点に記号を割り当て、根から葉までの節点で生成される記号列を符号語と考えることができます。
次の例は、符号長{2,2,2,3,3}の符号の木です
| a | b | c | d | e |
|---|---|---|---|---|
| 00 | 01 | 10 | 110 | 111 |
符号の木によって生成される符号空間は語頭符号となります。(証明は略)
符号の木の作り方(語頭符号生成アルゴリズム)
木の作り方は、大きく分けて2つあります。1つは根から作っていく方法です。もう1つが葉から作っていく方法です。このシリーズでは葉から作っていく方法を採用します。
1. 作りたい符号空間の符号長列を用意する
符号器と復号器の設計をするうえで、符号語数とそれに対応する符号語長を用意します。
上の図では、符号語数は5。符号語長列は {2,2,2,3,3}
2. 符号語数分の葉を作る
▢が葉に対応します。それぞれにはa,b,c,d,eのシンボルを割り当てておきましょう。(ここでは、それぞれのシンボルが符号語長列の要素に対応します。a:2,b:2,c:2,d:3,e:3)
3. 符号語長が長い節点を結合し、親を作る
親(parent)とは、2つの節点を派生させる節点のことです。また、親から派生する節点を子(child)といいます。
同じ長さのものが3つ以上ある場合は２つ適当に選んで問題ありません。
4. 3を根ができるまで繰り返す。
5. 完成(各枝に符号を割り当てる。)
符号の木は完成しました。これを関数で実装するには
入力→符号語長列
出力→木の根
とすればよいです。また、節点はClassを定義しましょう。
また、枝に符号を割り当てると書きましたが、Pythonで実装する際は節点に割り当てましょう(節点Classしか作らないから)。割り当て方は自由ですが、今回は左子ノードに0、右子ノードに1を割り当てます。
)
シャノン符号
先ほど紹介したアルゴリズムは、符号長列に基づいて作りました。次に実装するシャノン符号は記号の生起確率を符号長に変換し、得た符号長列を使って符号の木を作る方法です。
なぜこのようなことをするかというと、情報源は確率分布によって記号を生成することができます。そこで、なるべく平均符号語長がエントロピーに近くなるように符号を構成したい気持ちがあるからです。
※エントロピーとは符号の良さを表す指標だと思ってください。
簡単に言うと符号長列に基づいた符号の木を作るために確率分布を符号長列に変換するということです。
シャノン符号の作り方
次の式で与えられるl(x)を符号語長として語頭符号生成アルゴリズムから語頭符号を生成しましょう。
演習問題
1. 二分木の節点を表現するNodeクラスを定義しなさい
節点を表現するためにはどんなメタデータが必要であるかを考えましょう。
※次回以降の講義でも使うので便宜的に頻度(frequency)をメタデータに追加してください。
ヒント
- ID
- 親子関係(parent,left,right)
- 葉であるか
- 深さ(長さに対応する)
- シンボル(に葉に対して記号(a,b,cなど)を割り当てる)
- (頻度)
2. nodeを要素に持つリストから最も深いnodeをポップする関数を定義せよ
pop_max_level_node
入力: ノードの配列
内部: 最も深いnodeを配列から削除
出力: 削除したnodeを返す
3. 符号長列から符号の木を生成する関数を定義せよ
make_tree_by_lengths
入力: 符号長列,シンボル配列(任意)
出力: 木のルートノード(根のことです)
上で定義したClassとポップ関数を使いましょう‼️
4. 生成した木の葉に符号を割り当てる関数を定義せよ
allocate_codes_by_tree
入力: ルートノード
出力: 符号語の配列,頻度の配列,シンボルの配列
出力でシンボルの順番が混ざることを想定しているので、それぞれの要素がセットになるように以上の出力にしてください。
5. シャノン符号を生成する関数を定義せよ
make_tree_of_shannon
入力: 確率分布,シンボル配列(任意)
出力: ルートノード
3を使いましょう
6. (4)で定義した関数の出力を元のシンボルの順に戻す関数を定義せよ
sort_c_and_f_by_symbols
入力: (4)の出力のTuple, 元のシンボルの順番を持った配列
出力: 符号語の配列,頻度の配列,シンボルの配列
7. 次のプログラムを作りなさい
- 標準入力から符号語数を受け取る
- それぞれの符号語の正規確率を受け取る
- 確率分布からシャノン符号を生成し、出力でそれぞれの確率に対する符号語を出力せよ
例
alphabet size> 4
p_1> 0.4
p_2> 0.3
p_3> 0.2
p_4> 0.1
cw for p_1: 00
cw for p_2: 01
cw for p_3: 100
cw for p_4: 1010
解説
1
class Node:
def __init__(self):
self.parent = None #親ノード
self.left = None #左子ノード
self.right = None #右子ノード
self.leaf = False #葉かどうか
self.id = None #ID
self.level = None #深さ
self.frequency = 0 #頻度
self.symbol = None #シンボル
2
def pop_max_level_node(nodes):
if not nodes:
return None
max_index = max(range(len(nodes)), key=lambda i: nodes[i].level)
return nodes.pop(max_index)
3
def make_tree_by_lengths(lengths, symbols=None):
if symbols is None:
symbols = [[]] * len(lengths) #シンボルが指定されていない場合、空のリストを生成
nodes = [Node() for _ in range(len(lengths))] #葉の生成
c = 0
#リーフの定義
for i, length in enumerate(lengths):
nodes[i].id = i
nodes[i].leaf = True
nodes[i].level = length #符号長を階層として設定
nodes[i].symbol = symbols[i]
c = i
#ノードが一つになるまで結合していく(最終的にルートノード唯一つにする)
while len(nodes) > 1:
c += 1
#一番深い階層にあるノード2つ結合する(2つを子ノードとして親ノードを作る)
left = pop_max_level_node(nodes)
right = pop_max_level_node(nodes)
if (left.level != right.level): #右ノードと左ノードの階層が違う場合は右ノードを空ノードとして結合する
nodes.append(right) #右ノードを戻す
right = Node()
right.id= c
right.leaf=False
right.level=left.level
c += 1
parent = Node() #親ノードの作成
#親ノードと子ノードの関係性
parent.left = left
parent.right = right
parent.id = c
parent.level = left.level - 1
left.parent = parent
right.parent = parent
nodes.append(parent)
nodes.sort(key=lambda n: (n.id if n.leaf else float('inf')))
#ルートノードnodes[0]のレベルが0になるまで空ノードを追加して木を高くしていく
#Why: ルートノードのレベルが0でないこと符号長はそのlevelだけ減ることを意味するため
while nodes[0].level > 0:
left = pop_max_level_node(nodes)
c += 1
#ルートノードを作るために空ノードを追加
right = Node()
right.id= c
right.leaf=False
right.level=left.level
#親ノードの作成
parent = Node()
parent.left = left
parent.right = right
c += 1
parent.id = c
parent.level = left.level - 1
left.parent = parent
right.parent = parent
nodes.append(parent)
nodes.sort(key=lambda n: (n.id if n.leaf else float('inf')))
return nodes[0] #ルートノードを返す
4
def allocate_codes_by_tree(rootnode, codes=None, frequencies = None, symbols = None, code=""):
if codes is None: # リストが指定されていない場合、新規作成
codes = []
if symbols is None:
symbols = []
if frequencies is None:
frequencies = []
if rootnode is None:
return [codes, frequencies, symbols]
if rootnode.leaf:
#葉の場合、符号、確率分布、シンボルを結果の配列に追加
codes.append(code)
frequencies.append(rootnode.frequency)
symbols.append(rootnode.symbol)
else:
allocate_codes_by_tree(rootnode.left, codes, frequencies, symbols, code + "0") #左ノードは0
allocate_codes_by_tree(rootnode.right, codes, frequencies, symbols, code + "1") #右ノードは1
return [codes, frequencies, symbols] #符号、確率分布、シンボルのリストを返す
5
def make_tree_of_shannon(frequencies,symbols = None):
lengths = []
# 確率に基づいて符号長を計算
for f in frequencies:
lengths.append(math.ceil(-1 * math.log2(f)))
# make_tree_by_lengthsを呼び出して木を生成
return make_tree_by_lengths(lengths,symbols)
6
def sort_c_and_f_by_symbols(allocated_codes, symbols_original):
codes, frequencies, symbols = allocated_codes
symbol_to_code = {symbol: (code, freq) for code, freq, symbol in zip(codes, frequencies, symbols)}
sorted_codes = []
sorted_frequencies = []
sorted_symbols = []
for symbol in symbols_original:
if symbol in symbol_to_code:
code, freq = symbol_to_code[symbol]
sorted_codes.append(code)
sorted_frequencies.append(freq)
sorted_symbols.append(symbol)
return [sorted_codes, sorted_frequencies, sorted_symbols]
7
# 標準入力
asize = int(input('alphabet size> '))
frequencies = []
symbols = []
for i in range(asize):
p = float(input(f'p_{i+1}> '))
frequencies.append(p)
symbols.append(f'p_{i+1}')
# シャノンの符号化の木を生成
tree = make_tree_of_shannon(frequencies,symbols)
# 生成した木に符号を割り当て、ソートした結果を取得する
result = sort_c_and_f_by_symbols(allocate_codes_by_tree(tree),symbols)
# 標準出力
for i in range(asize):
print(f"cw for {result[2][i]}: {result[0][i]}")
次のステップ
今回の演習は難しかったと思います。講義の内容で扱った語頭符号生成アルゴリズムを再現するにはNodeクラスをうまく設計する必要がありました。わからないところはprintで一つ一つ理解するのも良いかもしれません。特に木を生成する関数はとても重要です。今後、ハフマン符号と呼ばれる確率分布で木を生成するアルゴリズムも紹介するのでよく理解してから次に進みましょう。