Document

Report
有限幾何学
第11回
有限幾何学 第11回
1. プレフィックスコードと根付き木
用語の説明
2. 2分木とプレフィックスコード
3. ハフマン木とハフマンコード
1.
1.1 用語の説明
根付き木:根と呼ばれる頂点が指定されている木
根から他の頂点に向けて向き付けをすることができる
根⇒
1.1 用語の説明
葉:根付き木の根以外の次数1の頂点
内点:根付き木の葉以外の頂点
根⇒
の頂点が葉
の頂点が内点
1.1 用語の説明
親と子:辺uvがuからvへの向き付けを与えられているとき,
uをvの親,vをuの子という
根⇒
u
v
1.1 用語の説明
兄弟:同じ親を持つ頂点を兄弟という
根⇒
u
w
v
⇐ vとwは兄弟
1.1 用語の説明
子孫と先祖:uからvへの有向道が存在するとき,
vをuの子孫,uをvの先祖という
根⇒
u
v
1.1 用語の説明
m分木:各頂点の子の数がm以下の根付き木
次数ではないことに注意
根⇒
3分木
1.1 用語の説明
正則m分木:m分木で全ての内点がm個の子を持つもの
根⇒
正則2分木
1.2 2分木とプレフィクスコード
符号語:0と1からなる有限列
例:01, 0110, 10010
接頭部:符号語 S=S1S2・・・Sn に対し,
S1S2・・・Sl (1 ≦ l ≦ n)で表される符号語を
Sの接頭部という
例:01は0110の接頭部
0110は011001の接頭部
1.2 2分木とプレフィクスコード
プレフィクスコード(prefix code,接頭符号):
符号語からなる集合Pで,Pに属する任意の符号語が
Pに属する他の符号語の接頭部にならないもの
例:S={ 01,001,100,0001 }はプレフィクスコード
例:プレフィクスコードSに対して,例えば01∈Sのとき,
01XXXのように表される符号語はSの要素ではない
1.2 2分木とプレフィクスコード
文字の符号化におけるプレフィクスコードの利点:
例:aを00,bを1000,cを10 に符号化した場合
({00, 1000, 10} はプレフィクスコードではない)
・baは100000,caaは100000 となるので,
100000から元の文字列を一意に復号することができない
・100000を先頭から順に見ていったときに,
10と1000どちらで読み取ればよいのかが分からないのが
一意に復号化できない理由の1つ
1.2 2分木とプレフィクスコード
文字の符号化におけるプレフィクスコードの利点:
例:aを00,bを1000,cを11 に符号化した場合
({00, 1000, 11} はプレフィクスコード)
・00,100,11からなる列は一意に復号することができる
例えば,1000000だと,1000 00 00 = baa となる
111000001100だと,11 1000 00 11 00 = cbaca となる
1.2 2分木とプレフィクスコード
2分木からプレフィクスコードを
構成する方法
任意の2分木からプレフィクスコードを構成することができる
根⇒
1.2 2分木とプレフィクスコード
2分木からプレフィクスコードを
構成する方法
次のように各辺に0と1のラベルを割り当てる
根⇒
0
1
0
0
1
⇐分岐していない所は
1
0,1どちらでもよい
1
0
1
0
1
1.2 2分木とプレフィクスコード
2分木からプレフィクスコードを
構成する方法
このようにラベル付けされた2分木をプレフィクス木と呼ぶ
根⇒
0
1
0
0
1
⇐分岐していない所は
1
0,1どちらでもよい
1
0
1
0
1
1.2 2分木とプレフィクスコード
2分木からプレフィクスコードを
構成する方法
各葉に次のように符号語を割り当てる
根⇒
0
1
0
0
000
1
001
⇐分岐していない所は
1
0,1どちらでもよい
1
0
010
1
0
011
110
1
111
1.2 2分木とプレフィクスコード
2分木からプレフィクスコードを
構成する方法
割り当てられた符号語からなる集合はプレフィクスコード
根⇒
0
1
0
0
000
1
001
⇐分岐していない所は
1
0,1どちらでもよい
1
0
010
1
0
011
110
1
111
1.2 2分木とプレフィクスコード
2分木からプレフィクスコードを
構成する方法
逆に任意のプレフィクスコードはあるプレフィクス木から
構成することができる(省略)
根⇒
0
1
0
0
000
1
001
1
0
010
1
1
0
011
110
1
111
1.3 ハフマン木とハフマンコード
t個の文字をプレフィクスコードに対応させる方法を考える
文章をコード化した際になるべく短くなるようにしたい
t個の文字の使用頻度と対応する符号語の長さ(0と1の個数)を
それぞれ w1,w2,・・・,wt と l1, l2, ・・・,lt とすると,
∑ wi li が小さいほどコード化された文章が短くなる
1≦i≦t
プレフィクス木に置き換えて考える
1.3 ハフマン木とハフマンコード
Tをt個の葉を持つ根付き木とし,
葉にそれぞれw1,w2,・・・,wt の重みが与えられているとする.
Tの根から重みwiが与えられた葉までの道の長さをliとするとき,
wt(T):=∑ wi li
辺の本数
1≦i≦t
をTの総コード長という
T2
T1
3
4
5
8
9
9
8
5
4
3
wt(T1) = 3×3 + 4×3 + 5×2 + 8×2 + 9×2 = 65 wt(T2) = 9×4 + 8×4 + 5×3 + 4×2 + 3×1 = 94
1.3 ハフマン木とハフマンコード
Tをt個の葉を持つ根付き木とし,
葉にそれぞれw1,w2,・・・,wt の重みが与えられているとする.
Tの根から重みwiが与えられた葉までの道の長さをliとするとき,
wt(T):=∑ wi li
辺の本数
1≦i≦t
をTの総コード長という
総コード長が最小となる根付き木を求めることにより,
効率のよいプレフィクスコードを得ることができる
1.3 ハフマン木とハフマンコード
ハフマンによるアルゴリズム
・ 指定された重みを割り当てられた葉を持つ根付き木で
総コード長が最小となるものを求めるアルゴリズム
・このアルゴリズムによって得られる根付き木をハフマン木という
・ハフマン木に対応するプレフィクスコードをハフマンコードという
・ハフマンコードはデータの圧縮に利用されている
・入力:重みw1,w2,・・・, wt
・出力:t個の葉を持つ根付き木で,それぞれの葉に
重みw1,w2,・・・, wtが割り当てられているもののなかで
総コード長が最小のもの
1.3 ハフマン木とハフマンコード
ハフマンによるアルゴリズム
入力
重み 3, 4, 5, 8, 9
出力
3
4
5
8
9
1.3 ハフマン木とハフマンコード
ハフマンによるアルゴリズム
根付き木Tに対し,wr(T)でTの根の重みを表すとする
1. Tvi=vi(1 ≦i ≦t)をviが根の根付き木とし,wr(Tvi)=wiとする
2. FをTvi (1 ≦i ≦t)を並べたグラフとする
3. Fの中で根の重みが最小の木をT,次に小さい木をT’とする
4. 新たに頂点r*を加え,r*とT, T’各々の根を辺で結び
r*を根とする根付き木T*を構成する.wr(T*)=wr(T)+wr(T’)とする
5. F=F-{T, T’} ∪{T*}とする
6. Fの連結成分の数が1ならば終了,2以上ならば手順3へ
1.3 ハフマン木とハフマンコード
ハフマンによるアルゴリズム
例:重み 3, 4, 5, 8, 9 に対してハフマンのアルゴリズムを適用する
3
4
5
8
9
1. Tvi=vi(1 ≦i ≦t)をviが根の根付き木とし,wr(Tvi)=wiとする
2. FをTvi (1 ≦i ≦t)を並べたグラフとする
1.3 ハフマン木とハフマンコード
ハフマンによるアルゴリズム
例:重み 3, 4, 5, 8, 9 に対してハフマンのアルゴリズムを適用する
T
3
T’
4
5
8
9
3. Fの中で根の重みが最小の木をT,次に小さい木をT’とする
1.3 ハフマン木とハフマンコード
ハフマンによるアルゴリズム
例:重み 3, 4, 5, 8, 9 に対してハフマンのアルゴリズムを適用する
7 r*
T
T’
8
4
9
5
3
4. 新たに頂点r*を加え,r*とT, T’各々の根を辺で結び
r*を根とする根付き木T*を構成する.wr(T*)=wr(T)+wr(T’)とする
5. F=F-{T, T’} ∪{T*}とする.
1.3 ハフマン木とハフマンコード
ハフマンによるアルゴリズム
例:重み 3, 4, 5, 8, 9 に対してハフマンのアルゴリズムを適用する
7
3
4
5
8
9
6. Fの連結成分の数が1ならば終了,2以上ならば手順3へ
1.3 ハフマン木とハフマンコード
ハフマンによるアルゴリズム
例:重み 3, 4, 5, 8, 9 に対してハフマンのアルゴリズムを適用する
T’
3
7
4
T
5
8
9
3. Fの中で根の重みが最小の木をT,次に小さい木をT’とする
1.3 ハフマン木とハフマンコード
ハフマンによるアルゴリズム
例:重み 3, 4, 5, 8, 9 に対してハフマンのアルゴリズムを適用する
12
T’
r*
7
T
8
4
9
5
3
4. 新たに頂点r*を加え,r*とT, T’各々の根を辺で結び
r*を根とする根付き木T*を構成する.wr(T*)=wr(T)+wr(T’)とする
5. F=F-{T, T’} ∪{T*}とする.
1.3 ハフマン木とハフマンコード
ハフマンによるアルゴリズム
例:重み 3, 4, 5, 8, 9 に対してハフマンのアルゴリズムを適用する
12
7
3
17
4
5
8
9
1.3 ハフマン木とハフマンコード
ハフマンによるアルゴリズム
例:重み 3, 4, 5, 8, 9 に対してハフマンのアルゴリズムを適用する
29
12
7
3
17
4
5
8
9
1.3 ハフマン木とハフマンコード
重みw1,w2,・・・, wt(t ≧2)に対して,
ハフマン木は総コード長が最小の2分木である
最小性
1.3 ハフマン木とハフマンコード
重みw1,w2,・・・, wt(t ≧2)に対して,
ハフマン木は総コード長が最小の2分木である
最小性
最小性の証明に次のLemmaを用いる
重みw1,w2,・・・, wt (w1≦w2≦・・・≦wt)
に対する総コード長が最小の2分木で,
重みw1,w2を持つ葉が兄弟であるのものが存在する
Lemma
1.3 ハフマン木とハフマンコード
重みw1,w2,・・・, wt (w1≦w2≦・・・≦wt)
に対する総コード長が最小の2分木で,
重みw1,w2を持つ葉が兄弟であるのものが存在する
Lemma
Lemmaの証明:
L:重み w1,w2,・・・, wt に対する総コード長が最小の2分木
rL:Lの根
注意:このときLは正則2分木となる
∵
子の数が1の内点があるとすると
こちらの方が総コード長が小さくなる
1.3 ハフマン木とハフマンコード
重みw1,w2,・・・, wt (w1≦w2≦・・・≦wt)
に対する総コード長が最小の2分木で,
重みw1,w2を持つ葉が兄弟であるのものが存在する
Lemma
Lemmaの証明:
L:重み w1,w2,・・・, wt に対する総コード長が最小の2分木
rL:Lの根
u:Lにおいて,rLより距離が最も離れた内点(注:uの子は葉)
vi, vj:uの子,割り当てられた重みをそれぞれwi,wj (wi≦wj)とする
v1,v2:それぞれ重みw1,w2が割り当てられているとする
1.3 ハフマン木とハフマンコード
重みw1,w2,・・・, wt (w1≦w2≦・・・≦wt)
に対する総コード長が最小の2分木で,
重みw1,w2を持つ葉が兄弟であるのものが存在する
rL
Lemmaの証明:
L
u
vi
vj
wi
wj
v1 v2
w2
w1
Lemma
1.3 ハフマン木とハフマンコード
重みw1,w2,・・・, wt (w1≦w2≦・・・≦wt)
に対する総コード長が最小の2分木で,
重みw1,w2を持つ葉が兄弟であるのものが存在する
Lemmaの証明:
葉に重みw1,w2,・・・, wt が割り当てられた
2分木L’を次のように構成する
V(L’) := V(L),E(L’) := E(L)
vi, vjにそれぞれ重み w1, w2 を割り当てる
v1,v2にそれぞれ重み wi, wj を割り当てる
v1,v2 vi, vj 以外の葉にはLの葉と同じ重みを割り当てる
Lemma
1.3 ハフマン木とハフマンコード
Lemma
重みw1,w2,・・・, wt (w1≦w2≦・・・≦wt)
に対する総コード長が最小の2分木で,
重みw1,w2を持つ葉が兄弟であるのものが存在する
Lemmaの証明:
rL
rL
L’
L
u
vi
u
vj
wi
wj
v1 v2
w1
w2
vi
vj
w1
w2
v1 v2
wi
wj
1.3 ハフマン木とハフマンコード
重みw1,w2,・・・, wt (w1≦w2≦・・・≦wt)
に対する総コード長が最小の2分木で,
重みw1,w2を持つ葉が兄弟であるのものが存在する
Lemma
Lemmaの証明:
このとき,
L’が重みw1,w2,・・・, wt (w1≦w2≦・・・≦wt)
に対する総コード長が最小の2分木で,
重みw1,w2を持つ葉が兄弟であるのものとなる(提出課題)
1.3 ハフマン木とハフマンコード
重みw1,w2,・・・, wt(t ≧2)に対して,
ハフマン木は総コード長が最小の2分木である
最小性
最小性の証明:
tに関する帰納法.
t=2の場合は自明.
w1≦w2≦・・・≦wtとしてよい.
Lemmaより,
重みw1,w2,・・・, wt に対する総コード長が最小の2分木 L’ で,
重みw1,w2を持つ葉が兄弟であるのものが存在する.
1.3 ハフマン木とハフマンコード
重みw1,w2,・・・, wt(t ≧2)に対して,
ハフマン木は総コード長が最小の2分木である
最小性
最小性の証明:
L’:重みw1,w2,・・・, wt に対する総コード長が最小の2分木で,
重みw1,w2を持つ葉が兄弟であるのもの
v1,v2:それぞれ重みw1,w2が割り当てられたL’の葉
L’
v1
v2
w1 w2
1.3 ハフマン木とハフマンコード
重みw1,w2,・・・, wt(t ≧2)に対して,
ハフマン木は総コード長が最小の2分木である
最小性の証明:
L*:Lからv1とv2を取り除き,
v1とv2の親uに重み w1+w2 を与えたもの
注意1:wt(L’) = wt(L*) + w1 + w2
L’
u
v1
v2
w1 w2
L*
u
w1+w2
最小性
1.3 ハフマン木とハフマンコード
重みw1,w2,・・・, wt(t ≧2)に対して,
ハフマン木は総コード長が最小の2分木である
最小性
最小性の証明:
F: 重みw1,w2,・・・, wtに対するハフマン木
F*:重みw1+w2,w3,・・・, wtに対するハフマン木
注意2:wt(F) = wt(F*) + w1 + w2
F
F*
w1+w2
w1 w2 w3 w4
w5
w3 w4
w5
1.3 ハフマン木とハフマンコード
重みw1,w2,・・・, wt(t ≧2)に対して,
ハフマン木は総コード長が最小の2分木である
最小性
最小性の証明:
帰納法の仮定より,wt(F*)≦wt(L*).
よって
注意1:wt(L’) = wt(L*) + w1 + w2,注意2:wt(F) = wt(F*) + w1 + w2より,
wt(F)≦wt(L’).
1.3 ハフマン木とハフマンコード
重みw1,w2,・・・, wt(t ≧2)に対して,
ハフマン木は総コード長が最小の2分木である
最小性
最小性の証明:
wt(F)≦wt(L’)であることと
L’は重みw1,w2,・・・, wt に対する総コード長が最小の2分木
であることから,
wt(F) = wt(L’).
よって
ハフマン木が重みw1,w2,・・・, wtに対する
総コード長が最小の2分木であることが分かる.
提出課題(6/27)
課題1:
Lemmaの証明の続き
課題2:
教科書:P.68, 3.21
提出課題(6/27)
課題1のヒント(教科書 P.67 参照) :
wt(L’) = wt(L)であることを示せばよい
l(v)を根 rL から頂点 v へ至る道の長さ とすると
L’のv1,v2 vi, vj 以外の葉には
Lの葉と同じ重みが割り当てられているので
wt(L’) - l(v1)wi - l(v2)wj - l(vi)w1 - l(vj)w2
= wt(L) - l(v1)w1 - l(v2)w2 - l(vi)wi - l(vj)wj

similar documents