文字列照合アルゴリズム

1
北海道大学
Hokkaido University
情報エレクトロニクス学科共通科目・２年次・第１学期〔必修科目〕
講義「情報理論」
第9回
第5章情報源符号化法
5.4 ひずみが許される場合の情報源符号化
2015/05/29
情報理論講義資料
北海道大学 Hokkaido University
2
ひずみが許される場合とは？

ある程度ひずみを許しても、1情報源記号あたりの平均符号長
を小さくしたい！（つまり、より小さくデータを圧縮したい）
テキストの場合
ひずみを許す
符号化
0011010
1110111
６時にスタバでね。ちゃんと来いよ。
0001・・・
復号
６時にスタバでねーちゃんと来いよ。
非常にまずい！
画像の場合
ほとんど問題ない
ひずみを許す符号
ビットマップファイル
（.bmp; 288 KB)
2015/05/29
jpegファイル
（.jpg; 17.5 KB）
情報理論講義資料
北海道大学 Hokkaido University
3
情報源符号化におけるひずみ

通信路でひずみが入るのではなく、符号化時にひずみを入れる
ることを許す
ひずみ
ひずみ
情報源
S
x
符号化
coding
通信路
Communication
理想的に伝達されると仮定
channel
復号
decoding
y
あて先
destination
図：情報源出力 x と情報源復号結果 y

ひずみ測度： x と y の相違を評価する関数 d(x, y)
– 関数 d(x, y) が大きいほど、ひずみが大きい。また次の性質を持つ。
d(x, y)≧0
x＝y のとき d(x, y)＝0
– ひずみ測度の平均値を平均ひずみと呼び、d で表す。
d＝∑∑d(x, y)P(x, y)
x y
2015/05/29
情報理論講義資料
北海道大学 Hokkaido University
4
ひずみ測度の例

例1 情報源アルファベットを A＝{0, 1} とし、ひずみ測度を
d(x, y) ＝0 ; x＝y
1 ; x≠y
とする。このとき、平均ひずみは
d ＝∑∑d(x, y)P(x, y)＝P(1, 0)＋P(0, 1)
P(1, 0)：入力 1 → 出力 0
P(0, 1)：入力 0 → 出力 1
x y
となる。これは、要するに、符号器の出力が元の情報源出力
と異なる確率であり、通常ビット誤り率と呼ばれる。

例2 情報源アルファベットを有限個の整数または実数の集合
としよう。このとき、ひずみ測度を
d(x, y) ＝ | x－y |2
とすれば、平均ひずみは2乗平均誤差（mean square error）と
呼ばれる量となる。ひずみの評価量として非常によく用いられる。
2015/05/29
情報理論講義資料
北海道大学 Hokkaido University
5
ひずみが許される場合、情報源符号化定理はどうなるか？
［情報源符号化定理］
情報源S は、任意の正数εに対して、1情報源記号あたりの平均符号長Lが
H(S) ≦ L ＜ H(S) +ε
となるような2元瞬時符号に符号化できる。
H(S)が限界！
しかし、どのような一意復号可能な2元符号を用いても、
平均符号長がH(S)より小さくなるような符号化はできない。

ひずみを許せば、どのくらい平均符号長の限界を下げられるか？
S：記憶の無い定常情報源、X:任意の時点においてSから出力される情報源記号
– 1情報源記号あたりの平均符号長の下限＝情報量H(S)=H(X)
– ひずみを許した場合、出力Yの値を知っても、元の入力Xに関して、
なお平均 H(X |Y ) のあいまいさが残る。
ひずみを許した
– 伝えられる情報の量は I(X;Y )＝H(X)－H(X |Y )
場合の限界！
2015/05/29
情報理論講義資料
北海道大学 Hokkaido University
6
ひずみが許される場合の情報源符号化定理


相互情報量I(X;Y ) が同じでも、平均ひずみ d は同じとは限らない
⇔ 平均ひずみ d が同じであっても、I(X;Y )は符号化の仕方で異なる
ある与えられた値 D に対し、平均ひずみ d が
d≦D
を満たす条件の下で、あらゆる情報源符号化法を考えたときの
相互情報量 I(X;Y ) の最小値を考え、これを R(D) と表す。すなわち、
R(D) ＝ min {I(X;Y )}
d≦D
これを情報源S の速度・ひずみ関数（rate-distortion function）と呼ぶ。
［ひずみが許される場合の情報源符号化定理］
平均ひずみ d を D 以下に抑えるという条件の下で、任意の正数εに対して、
情報源S を1情報源記号あたりの平均符号長Lが
R(D) ≦ L ＜ R(D) +ε
となるような2元符号へ符号化できる。しかし、どのような符号化を行っても、
d ≦ D である限り、LをR(D)より小さくすることはできない。
2015/05/29
情報理論講義資料
北海道大学 Hokkaido University
7
速度-ひずみ関数(1)


R(D) は、d ≦ D を満たす、あらゆる情報源符号化法を考えたときの
I(X;Y ) の最小値。では実際、これをどのようにして求めるのか？
情報源符号化法を変えると、条件付確率 P( y| x) が変わる！
→ I(X;Y ) の最小化は、d ≦D の条件の下で P( y| x) を変えることで行う＊
→ 下図のような通信路を考え、この通信路の特性を変えることで I(X;Y )
の最小化を計ると解釈できる。この仮想的通信路を試験通信路と呼ぶ。
情報源S
P(x)
x
試験通信路
P( y | x)
y
あて先
I(X;Y )最小化
d≦D
図: 試験通信路による速度・ひずみ関数R(D) の解釈
＊任意の条件付確率 P( y| x) を与えるような情報源符号化・復号法が存在する
2015/05/29
情報理論講義資料
北海道大学 Hokkaido University
8
速度-ひずみ関数(2)

条件付確率 P( y| x) を用いれば、相互情報量 I(X;Y ) は
P(x, y)
I(X;Y )＝∑∑P(x, y)log2
P(x)P(y)
x y
P(y|x)
＝∑P(x)∑P(y|x) log2
①
P(y)
y
x
と表せる。ここに P(y) は
P(x, y)＝P(x)P(y|x)
P(y) ＝∑P(x) P(y | x)
x
により計算できる。また、d ≦D という条件は
d ＝∑P(x)∑P(y
| x) d(x, y) ≦ D
x
y
②
P(y|x) が変数
他は既知
と表せる。また、条件付確率は
P(y | x) ≧ 0
∑P(y | x) ＝ 1 for each x
y
を満たさなければならない。

③
④
一般には難しい
式②～④の条件の下に、式①のI(X;Y )を最小化すればよい！
2015/05/29
情報理論講義資料
北海道大学 Hokkaido University
9
[例]記憶のない２元情報源の場合(1/3)




1, 0 を確率 p, 1－p で発生する記憶のない2元情報源Sを考える。
また、ひずみ測度としては
0 ; x＝y
d(x, y) ＝
1 ; x≠y
を用いるものとする。このとき、平均ひずみ d はビット誤り率となる。
この情報源に対して、0≦D≦0.5 が与えられたとき、
d≦D の元での速度・ひずみ関数 R(D)を求めよう。
相互情報量I(X;Y )＝H(X)－H(X |Y )
H(X)＝ H(p) なので、
誤り源
H(X|Y) を最大化すればよい。
ここで、Y は左図のように、
1の発生確率が d である
ような誤り源の出力E と X
の排他的論理和で表せる。
2015/05/29
D>0.5 の場合は
誤る確率の方が
大きいことを意味する
PE(1)＝d
情報源S
PX(1)＝p
X
E
⊕
Y＝X  E
試験通信路
図： 2元情報源に対する試験通信路
情報理論講義資料
北海道大学 Hokkaido University
10
[例]記憶のない２元情報源の場合(2/3)


Y＝X ⊕ E であるから、X＝Y ⊕ E となる。したがって、
H(X | Y)＝H(Y ⊕ E | Y)＝H(E | Y)
が得られる。
H(E | Y) は Y の値を知ったときの E のあいまいさであるから、何
も知らないときの E のあいまいさ H(E) より大きくなることはない。
さらに、誤り源に記憶がなく定常であれば、H(E)＝ H( d ) である
が、そうでなければ、H(E)＜H( d ) であるから、
H(E | Y) ≦ H(E) ≦ H( d )
H(Y)
となる。それゆえ
H(X | Y) ≦H( d )
H(E)
H(E | Y) I(E;Y )
H(Y | E)
を得る。d≦D≦1/2 なので、さらに
H( d ) ≦H(D)
となる。したがって、相互情報量 I(X;Y ) は、
I(X;Y )＝H(X)－H(X |Y )≧ H(p)－H(D)
2015/05/29
H(E, Y)
情報理論講義資料
北海道大学 Hokkaido University
11
[例]記憶のない２元情報源の場合(3/3)
d=Dで誤り源が無記憶定常で情報源Sと独立であるとき、等号が成立
(I(X;Y )＝ H(p)－H(D)) するので、
記憶のない定常2元情報源S の速度・ひずみ関数は
R(D)＝ H(p)－H(D)
で与えられることが導けた。
 左図で分かるように、速度・ひずみ
関数は、Dに関して単調減少であり、
下に凸な関数である。一般の速度・
p=0.5
ひずみ関数も同様な性質を持つこと
が証明されている。
p=0.2
p
 記憶のある情報源の場合にも、
=0.1
I(X;Y )＝lim I(Xn;Yn)/n
R(D)

n→∞
の最小値として、速度・ひずみ関数を
定義することができる。
2015/05/29
D
図： 2元情報源の速度・ひずみ関数
情報理論講義資料
北海道大学 Hokkaido University
12
ひずみが許される場合の情報源符号化法(1)
［ひずみが許される場合の情報源符号化定理］
平均ひずみ d を D 以下に抑えるという条件の下で、任意の正数εに対して、
情報源S を1情報源記号あたりの平均符号長Lが
R(D) ≦ L ＜ R(D) +ε
となるような2元符号へ符号化できる。しかし、どのような符号化を行っても、
d ≦ D である限り、LをR(D)より小さくすることはできない。

ひずみが許される場合の情報源符号化定理は、1情報源記号あたりの平均
符号長を、速度・ひずみ関数 R(D) にいくらでも近づく符号化法の存在を示
している。では、具体的な符号化方法はあるのか？
– ひずみのない場合に比べて、はるかに難しい！




2015/05/29
ベクトル量子化
変換符号化
予測符号化
etc.
参考図書
「情報・符号・暗号の理論」
今井秀樹著、電子情報通信学会
情報理論講義資料
北海道大学 Hokkaido University
13
ひずみが許される場合の情報源符号化法(2)
x
情報源S
P(x)
CDへの符号化
x→w
dn(x, w)最小
x, w は長さ n の系列
w
ひずみのない
場合の情報源
符号化
w∈CD
図5.6 ひずみが許される場合の情報源符号化法
１）まず、情報源S の情報源アルファベットA の記号からなる長さ n の系列を
N 個選び、それを符号語とする符号CD を作っておく。
２）情報源S から発生する長さ n の系列 x＝x1x2・・・xn に対し、CDの中から、
ひずみ測度
n
d(x, y)は与えられる
dn(x, w)＝∑ d(xi, wi)
i＝1
が最小となるような符号語 w＝w1w2・・・wn ∈CD を選ぶ。
３）この符号語に対し、ひずみのない場合の情報源符号化を行う。
2015/05/29
情報理論講義資料
北海道大学 Hokkaido University
14
ひずみが許される場合の情報源符号化法(3)

図5.7 はこの符号化法の概念図
n次ベクトル空間
– 図の各点は長さ n の系列
– 2重丸（青）で示されているのが
CDの符号語
– ひずみ測度が、左図において
距離に比例するものとする。
このとき、符号化は図の矢印の
ように行われる。
– つまり、この図の例では符号語と
そのまわりの8個の系列を一つの
図： CDへの符号化の概念図
符号語で代表させてしまう。
– 符号CD は、このように符号化したときに、平均ひずみができるだけ小さ
くなるように選ぶべきである。また、平均ひずみが同じであれば、符号
語数の少ないことが望ましい。
CDの具体的構成法は
2015/05/29
知られていない
情報理論講義資料
北海道大学 Hokkaido University
15
[例]無記憶２元情報源のひずみあり符号化(1/2)

1, 0 を確率 p, 1－p で発生する記憶のない2元情報源を考える。
また、ひずみ測度としては
0 ; x＝y
d(x, y) ＝
1 ; x≠y
を用いるものとする。このとき、平均ひずみ d はビット誤り率となる。
ここで、CD として
CD＝{000, 111}
を考える。 CDへの符号化は、情報源系列とのひずみが最も小さい符号を
選ぶことにより行われる。すなわち
000
001
010
100
とすればよい。
2015/05/29
000
111
110
101
011
111
情報理論講義資料
北海道大学 Hokkaido University
16
[例]無記憶２元情報源のひずみあり符号化(2/2)
このとき、平均ひずみは1情報源記号あたり
d＝1/3 ［3p(1－p)2 ＋ 3p2(1－p)］
となる。また、CDに符号化したとき、
符号語000, 111の発生確率はそれぞれ、
H(p)
LB
3
2
2
3
(1－p) ＋3p(1－p) 、3p (1－p)＋p
d
であるから、これに対し、ひずみのない
情報源符号化を行えば、1情報源記号
あたりの平均符号長 L は
LB＝1/3［H( (1－p)3 ＋ 3p(1－p)2 )］
LI
にいくらでも近づけることができる。
 一方、d だけひずみを許すとき、平均
符号長 L の下限は
LI＝ H(p)－H( d )
p
となることが判る。
図5.8 例5.5の符号化による平均ひずみ d および
 LB は LI の2倍近い値になっている。
1情報源符号あたりの平均符号長の下限LB と LI

2015/05/29
情報理論講義資料

Download Report