エントロピー、それが問題だ

配列解析アルゴリズム特論 渋谷 配列解析アルゴリズム特論 渋谷

圧縮

渋谷

東京大学医科学研究所ヒトゲノム解析センター （兼）情報理工学系研究科コンピュータ科学専攻 http://www.hgc.jp/~tshibuya

配列解析アルゴリズム特論 渋谷 本日の話題

¦

通信路符号化入門

¦

文字列圧縮アルゴリズムのいろいろ

¿統計的手法 uHuffman code uTunstall uGolomb uArithmetic code uPPM ¿辞書的手法 uLZ77, LZ78, LZW u文法圧縮

配列解析アルゴリズム特論 渋谷 圧縮とは

¦

2種類の戦略

¿Lossless圧縮： 完全に復元可能 （本講義） ¿Lossy圧縮: 画像などで、完全に復元できなくてもよい。

¦

何を圧縮するか？

¿本講義では文字列が対象 ¿情報源のモデルを考える必要性

¦

何故圧縮できるか？

¿情報に「重複」があるから ¿情報源のエントロピー ATGCCGTAATAACGATCAATACTAGCC... A 32% C 22% G 15% T 31% モデル 出力例

配列解析アルゴリズム特論 渋谷 エントロピーとは （復習？） ¦ 情報「量」にあるべき性質 ¿ 非負 ¿ 確率が小さい事象が発生すると「びっくり度」が大きい ¿ 足し算できる

u I(p·q) = I(p) + I(q)

¦ そんなわけで情報量は ¿ I(p) = − log₂(p) ¿ 単位は「ビット」 u 確率 0.5 の事象は１ビットで表現可能！ ¦ エントロピー ¿ 情報量の期待値 u H(p1, p2, p3, ... , pn) = − Σpilog pi ¿ 性質 u pi=1ならばH=0 u 一番Hが高いのはp_i=1/nのとき ¦ 情報源に対する圧縮率の期待値の下限 ¿ 圧縮率はエントロピーに近づくと嬉しい ¿ 「正しい」情報源のモデルを考えることも重要 u モデルによってはエントロピーの計算自体が難しいことも ４割打者がヒット vs １割打者がヒット 比較：どのくらい驚く？ ２つの事象に対する エントロピー 0 片方の確率 ₁ エントロピー 1

配列解析アルゴリズム特論 渋谷 関連した２つの情報源のエントロピーの解析

¦

同時に２つの事象

A, Bがあるとする

¿H(A,B) = −Σp(a_i,b_i) log p(a_i, b_i)

¦

するとその性質

¿H(A,B) = H(B,A)

¿H(A), H(B) ≤ H(A,B) ≤ H(A) + H(B)

u関連のある質問を２つするのは損 { }n i a ∈ { }n i b ∈ ATGCCT... CTTGGA... こんなかんじ A: ヒットを打った T/F B: 桶屋が儲かった T/F A: ヒットを打った T/F B: 得点した T/F ほぼ関係ないのでH(A,B) ~H(A)+H(B) 情報としては同じなので H(A,B) = H(A) = H(B) A: ヒットを打った T/F B: ヒットを打たなかった T/F その中間

配列解析アルゴリズム特論 渋谷 条件付エントロピー

¦

Aがa

_i

の時の

Bのエントロピー

¿H(B|a_i) = −Σ_jp(ｂ_j|a_i) log p(ｂ_j|a_i) ¿相関しているならば 0

¦

条件付エントロピーはその期待値

¿H(B|A) = −Σ_i,jp(a_i,b_j) log p(ｂ_j|a_i)

¦

性質

¿H(A,B) = H(A) + H(B|A) ¿H(B|A) ≥ 0

¿H(B) ≥ H(B|A)

u下２つは H(A), H(B) ≤ H(A,B) ≤ H(A) + H(B) というエントロピーの性質から導くことができる

¦

相互情報量

¿I(A;B) = H(B) − H(B|A) = H(A) − H(A|B)

uどれくらい情報に重なりがあるか？ I(A;B) H(B|A) H(A|B) H(B) H(A) H(A,B)

配列解析アルゴリズム特論 渋谷

Relative Entropy (Kullback-Leibler Distance)

¦

2つの確率事象の差異を見る指標

¿本当の情報源はPなのに、何を間違えたかQだと思ったとき に（そう思って圧縮したときに）損をする量 uP, Qを逆にした時の値は異なる ’ 対象性が必要な場合に、両者の平均を距離として扱うこともある » ただし、そこに理論的な正当性があるわけではないことに注意 u必ず正の値をとる ’ 情報源の推定を間違えないことが、最高の圧縮率を達成する条件

∑

=

x

q

x

x

p

x

p

q

p

D

)

(

)

(

log

)

(

)

||

(

配列解析アルゴリズム特論 渋谷 通信路・圧縮超入門

¦

圧縮

¥

通信路符号化

0 1 0 1 情報の出し手 情報の受け手 情報量の少ない文章（０ばっかり、など） を送るのはもったいない 0.1 0.9 0 1 0 1 情報の出し手 情報の受け手 0.9 0.9 0.1 0.1 間違いが起こる通信路でできる だけ正確に情報を送るには？ 情報量が1000ビットであれば、1000ビット送るだけでよい筈！→Huffman符号など 両サイドの相互情報量分のビット数は送ることができる筈！→Hamming符号など

配列解析アルゴリズム特論 渋谷 最も単純な通信路符号化：反復符号（repetitive coding）

¦

k 回ビットを繰り返し送るだけ

¿で、多数決で01を決定 ¿k ビット中 i 個の誤りが起こる確率： u_{𝑃𝑃(𝑖𝑖, 𝑘𝑘) = 𝑘𝑘𝑖𝑖 𝑝𝑝}𝑖𝑖_{(1 − 𝑝𝑝)} 𝑘𝑘−𝑖𝑖

0100110 → 000 111 000 000 111 111 000

→ 0

1

0 11

0

000

1

00 111 111

1

0

1

error

P(3,3)+P(2,3) ≂ 3p

2

New Error Rate:

配列解析アルゴリズム特論 渋谷 反復符号の空間的表現

¦

Error correcting space

001 011 010 000 100 101 111 110

配列解析アルゴリズム特論 渋谷 注意： 誤り発見と誤り復号は違う 001 011 010 000 100 101 111 110

¦

パリティチェック符号

¿00→000, 01→011, 10→101, 11→110 ¿誤りは見つけられるが、復号できない

Repetitive coding Parity-check coding

001 011 010 000 100 101 111 110

?

配列解析アルゴリズム特論 渋谷 一般化

¦

(m, n)-符号: length-n word → length-m code word

¿n/m: 通信レート

¿コードはなるべく互いに異なるものを

00000 _01101001011 00001

00010

配列解析アルゴリズム特論 渋谷 理想的ケース

00000

00001

00010

nH

(B|A) bit noise

Need to be

Disjoint

nH(B) bit data in total

There are at most 2nH(B)_/2nH(B|A) ₌ 2nI(A;B) _words that can be distinguished (i.e., r ≤ n·I(A;B)) Ignorable

B

A

r+nH(B|A=00000) bit information

配列解析アルゴリズム特論 渋谷 意味するところ

¦

通信路

𝐴𝐴 → 𝐵𝐵では 𝑛𝑛 · 𝐼𝐼(𝐴𝐴; 𝐵𝐵) bit 以上のデータ

は送れない

¿i.e., The rate R of any code is at most its channel capacity C

そして、

Cより小さければどのようなレートRに

対しても、それを達成する符号が存在する

(Shanon)

- 十分長い符号を考える - いくらでも小さな（でも０ではない）誤り確率は許す (= 𝜀𝜀)

𝐶𝐶 = max 𝐼𝐼(𝐴𝐴; 𝐵𝐵)

配列解析アルゴリズム特論 渋谷 パリティチェック符号を用いた復号

¦

Parity Checking

¿ 𝑥𝑥₁, 𝑥𝑥₂, … , 𝑥𝑥_𝑛𝑛 → (𝑥𝑥₁, 𝑥𝑥₂, … , 𝑥𝑥_𝑛𝑛 , 𝑝𝑝(∑_𝑖𝑖 𝑥𝑥_𝑖𝑖))

¿It can detect all the EXISTENCE of 1-bit error

¦

More parity bits?

¿ 𝑥𝑥₁, 𝑥𝑥₂, … , 𝑥𝑥_𝑛𝑛 → (𝑥𝑥₁, 𝑥𝑥₂, … , 𝑥𝑥_𝑛𝑛 , 𝑓𝑓₁({𝑥𝑥_𝑖𝑖}), 𝑓𝑓₂({𝑥𝑥_𝑖𝑖}), … , 𝑓𝑓_𝑚𝑚({𝑥𝑥_𝑖𝑖}))

¿What code is decodable even if there exists a 1-bit error?

An example of a decodable (6,3)-code for 1-bit error

000 → 000 0 0 0 001 → 001 0 1 1 010 → 010 1 1 1 011 → 011 1 0 0 100 → 100 1 0 1 101 → 101 1 1 0 110 → 110 0 1 0 111 → 111 0 0 1 p(x₁+x₂) p(x₂+x₃) p(x₁+x₂+x₃)

配列解析アルゴリズム特論 渋谷

1-bit Error-Tolerant (6,3)-Code with Parities

c

w

000 → 000 0 0 0 001 → 001 0 1 1 010 → 010 1 1 1 011 → 011 1 0 0 100 → 100 1 0 1 101 → 101 1 1 0 110 → 110 0 1 0 111 → 111 0 0 1 p(x₁+x₂) p(x₂+x₃) p(x₁+x₂+x₃) Hamming distance > 2

any pair Errorless case

Coding

1-bit error case

𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐(𝑤𝑤) = 𝑤𝑤 � 10 0 0 1 0 0 0 1 1 1 0 0 1 1 1 1 1 𝑡𝑡𝑐𝑐𝑡𝑡𝑡𝑡(𝑐𝑐) = 𝑐𝑐 � 1 1 0 1 0 0 0 1 1 0 1 0 1 1 1 0 0 1 = 0 0 0 mod 2 mod 2 𝑡𝑡𝑐𝑐𝑡𝑡𝑡𝑡 𝑐𝑐 = 𝑐𝑐 + 𝑐𝑐_𝑖𝑖 � 𝐻𝐻𝑇𝑇 _{= ℎ} 𝑖𝑖 ≠ 0 mod 2 Decodable ! Parities 𝑐𝑐₃ = 0 0 1 0 0 0 An example of an error:

Error occurred at the i-th position

Parity check matrix 𝐻𝐻𝑇𝑇

配列解析アルゴリズム特論 渋谷

(m − 1)/2 -bit Error Tolerable (2m − 1, 2m − m − 1)-Hamming Code

¦

Parity Check Matrix

All the different 2

m

− 1 length-m non-0 vectors

¦

Codes

¿

All

c that 𝑐𝑐 � 𝐻𝐻

𝑇𝑇

= 𝟎𝟎 (𝑐𝑐 ≠ 𝟎𝟎)

u2m_{−m − 1 such words exists (as the rank of H is m)}

𝐻𝐻 =

0

0

1

1

0

1

0

1

0

1

1

0

0

1

1

1

1

0

0

1

1

0

1

0

1

0

1

1

1

1

0

0

1

1

0

1

1

1

1

0

1

1

1

1

1

0

0

0

0

1

0

0

0

0

1

0

0

0

0

1

ただしこれはシャノン限界にはまだ遠い

→ 符号理論

m 2m _{− 1}

配列解析アルゴリズム特論 渋谷 ２種類の圧縮戦略

¦

統計的手法

¿文字の使用頻度の偏りに基づく uHuffman code uTunstall uGolomb uArithmetic code uPPM u...

¦

辞書的手法

¿「よく出てくる語」を辞書化する uLZ77, LZ78, LZW uBlock sorting u文法圧縮

配列解析アルゴリズム特論 渋谷 接頭符号 (Prefix Code)

¦

電話番号の原理

¿

どの符号も他の符号を

接頭辞として含まない

u含んでしまうと、途中ま で読んだ時に、どちらの 符号か区別できなくなっ てしまう

¿

出現率の高い文字を

短いコードであらわす

ことができれば、テキス

トは圧縮できる（はず）

A B C D E F G H I J 0 ₁ 1 1 ₁ 1 1 1 1 1 0 0 0 0 0 0 0 0 Cを000、Gを001と表す

配列解析アルゴリズム特論 渋谷 接頭符号による圧縮

¦

考え方

¿確率の高い事象は短いコードで表す ¿文字のビット数は変更可能

A

12.5%

C

12.5%

G

25%

T

50%

Model

100

101

11

0

Code 期待値としては1文字あたり 1.75ビットで表現される →圧縮できた （しかもこの数字はエントロ ピーに等しく理想的） 4文字なので普通に 表現すれば2ビットで 1文字を表現できる entropy = 1.75bit 理想的な場合

配列解析アルゴリズム特論 渋谷 接頭符号の性質

¦

情報源と符号

¿p_i : i 番目の文字の出現率 （∑_𝑖𝑖 𝑝𝑝_𝑖𝑖 = 1） ¿l_i : i 番目の文字のコード長

¦

Kraftの不等式

¿∑_𝑖𝑖 2−𝑙𝑙𝑖𝑖 ≤ 1 が必ず成り立つ ¿逆に、∑_𝑖𝑖 2−𝑙𝑙𝑖𝑖 ≤ 1が成り立つならば、その ような符号長の接頭符号を作ることがで きる A B C D E F G H I J 0 ₁ 1 1 ₁ 1 1 1 1 1 0 0 0 0 0 0 0 0

配列解析アルゴリズム特論 渋谷 最適な接頭符号はどの程度の性能を出せるか？

¦

符号長の期待値：

𝐸𝐸 = ∑

_𝑖𝑖

𝑝𝑝

_𝑖𝑖

� 𝑙𝑙

_𝑖𝑖 ¿l_iが∑_𝑖𝑖 2−𝑙𝑙𝑖𝑖 ≤ 1を満たす任意の正実数だとするならば、 𝑙𝑙_𝑖𝑖 = − log 𝑝𝑝_𝑖𝑖 のときに E は最小値 H = − Σp_i log p_i をとる ¿すなわち、いかなる接頭符号であっても、符号長の期待 値がエントロピー H よりもよくなることはない

¦

𝑙𝑙

_𝑖𝑖

= − log 𝑝𝑝

_𝑖𝑖

となる符号は作成可能

¿∑_𝑖𝑖 2−𝑙𝑙𝑖𝑖 ≤ 1が成り立つため ¿このときの符号長の期待値は H+1 未満となる u_{∑𝑖𝑖𝑝𝑝𝑖𝑖 = 1 なので} uただし、この符号が最適であるとは限らない

¦

結論：

¿最適な符号の符号長の期待値 E は 𝐻𝐻 ≤ 𝐸𝐸 < 𝐻𝐻 + 1 を 満たす

配列解析アルゴリズム特論 渋谷 最適な接頭符号の性質 （１）

¦

必要条件１

¿

内部節点は必ず子供を

２つ持つ

uもし子が一つだけの内部 節点があれば、除去する ことでコード長の期待値 を短くできる A C D E G I 0 ₁ 1 1 1 1 1 0 0 0 0 0 B F H J 1 1 1 0 0 0 0 このような内部節点 は意味がない

配列解析アルゴリズム特論 渋谷 最適な接頭符号の性質 （２）

¦

定義

¿「節点の確率」 uその節点以下の文字（＝子 孫の葉）が現れる確率の総 和

¦

必要条件２

¿任意の節点の確率はそ れより浅いところにあるど の節点の確率よりも低い u入れ替えるとコード長の期 待値が長くなってしまう 1.0 節点以下の 文字が現れ る確率 A B C D E F G H I J 0 ₁ 1 1 ₁ 1 1 1 1 1 0 0 0 0 0 0 0 0 0.59 0.41 0.29 0.30 0.19 0.22 0.15 0.12 0.10 0.15 0.06 0.09 0.11 0.18 0.08 0.04 0.03 0.03

配列解析アルゴリズム特論 渋谷 最適な接頭符号の性質 （３）

¦

ただし、この二つの必要条件だけでは最適性の十分条

件はまだ満たさない

0.1 0.4 0.2 0.3 0.5 0.5 0.1 0.4 0.2 0.3 0.6 0.3

こちらの方がよい

２条件を満たす異なる２つの木の例

最適ではない

配列解析アルゴリズム特論 渋谷 最適な接頭符号の性質 （４）

¦

最適な符号は一意ではない

（兄弟性）

¿同じレベルであれば節点（子 孫はまるごとつけたまま）を入 れ替えても符号長の期待値 は変わらない u0/1ラベルのつけ方を変えること もこれに含まれる 1.0 A B C D E F G H I J 0 ₁ 1 1 ₁ 1 1 1 1 1 0 0 0 0 0 0 0 0 0.59 0.41 0.29 _{0.30 0.19 0.22} 0.15 0.12 0.10 0.15 0.06 0.09 0.11 0.18 0.08 0.04 0.03 0.03

配列解析アルゴリズム特論 渋谷 最適な接頭符号の性質 （５） ¦ 内部ノードの子が２つ（必要条件１）、ということ は、一番深いレベルの葉の数は２つ以上、とい うこと ¦ 符号木の一番深いレベルには、必ず、最も小 さい出現確率の文字xとその次に小さい出現 確率の文字yが存在する ¿ もしそうでなければ、先の必要条件２を満たさない ¦ 最適な接頭符号の中には、そのxとyが符号木 の中で共通の親を持つような木Tが存在する ¿ 兄弟性の性質から ¦ xとyをzに変換した情報源S（zの出現率はxとy の出現率の和とする）を考える。このとき、T中 のxとyを除去し、その親にzを割り当てた木は、 Sに対する最適な符号木となっているはず ¦ これは再帰的に（ボトムアップに）計算可能 ¿ ２つしか文字がない場合の最適符号は自明（一意）

→ Huffman符号

A K 1 0 B C D E F G H I J 0 ₁ 1 1 ₁ 1 1 1 1 1 0 0 0 0 0 0 0 0

配列解析アルゴリズム特論 渋谷 Huffman Code (1) 155 128 118 36 21 49 47 44 85 91 57 106 176 205 224 283 507 381 888 頻度 A B C D E F G H I J 0 ₁ 1 1 ₁ 1 1 1 1 1 0 0 0 0 0 0 0 0 一番頻度の低い２つをまとめる

¦

計算時間：

O(s log s)

¿s: アルファベットサイズ ¿ヒープを用いて計算 ① ② 1952

配列解析アルゴリズム特論 渋谷 Huffman Code (2)

¦

性質

¿最適な接頭符号（の一つ） uよって H(X)≦L＜H(X)+1 を満たす

¦

k 文字まとめれば、(k 字拡大情報源）

¿H(X)≦L＜H(X)+1/k

AAAA

0.47%

AAAC

0.37%

AAAG

0.35%

AAAT

0.41%

AACA

0.32%

...

配列解析アルゴリズム特論 渋谷 cf. Shanon-Fano 符号

¦

トップダウンで作る

¿出現頻度でソート ¿できるだけ半分に近いように分割し、片方に０、もう片方に１ を割り当てる

¦

H(X)≦L＜H(X)+1 を満たす

¿ハフマン符号と異なり、最適とは限らない 0.7 0.11 0.1 0.07 0.02 A T G C N 1948

→ しかし、後の算術符号の原点となる

配列解析アルゴリズム特論 渋谷

Adaptive Coding (Feller-Gallager-Knuth)

¦

ハフマン符号はそのままでは一度全テキストは見ないと

文字の出現頻度がわからない

¦

出現頻度表を更新しながら圧縮する

¿初出の文字に対応する頻度０の葉を一つ用意する ¿更新はルートから該当ノードまでのパス長に比例した時間で可 能 ¿デコードも同様に表を更新しながらデコードする new new 頻度１の新しいノード 0 0 00を出力 形を調整

配列解析アルゴリズム特論 渋谷 Huffman Codingの欠点

¦

出現確率に大きな偏りがあるとうまく扱えない

¿

H(S)≦平均長＜H(S)+p+0.086 （p: 最大出現確率）

¿

ほとんどが０、といったコードなどではあまり圧縮で

きない

配列解析アルゴリズム特論 渋谷 Tunstall Code

¦

逆にソース側の長さを可変とする方法もある

a _b a b a b a b a b a b a b 001 000 010 011 100 101 110 111 さらにHuffman 符号と組み合わせることも可能

配列解析アルゴリズム特論 渋谷 0がたくさん続くような01列の圧縮

¦

Run-length coding

¿ＦＡＸ画像など ０１０１０００１１０００００１０１００００００００１００１０００１０００１ １ １ ３ ０ ５ １ ８ ２ ３ ３

¥

Golombコード

０００００ １２１ ０００１ ４５ ００１ ２１ ０１ １５ １ １０ ソース 頻度 Huffman符号化

配列解析アルゴリズム特論 渋谷 算術符号（Arithmetic Code） (1)

¦

[0,1)の2進小数を考える

¦

区間[0,1)内の幅

w（0<w<1)の任意の区間[a, a+w) に

は

− log 𝑤𝑤 ビット以下で表現可能な 2進小数が含ま

れる

（1次元版鳩ノ巣原理モドキ）

0.0 幅0.125 (= 1/2 1.0 3₎ 01 011 0 1 11 001 101 111 0001 0011 0101 0111 1001 1011 1101 1111 幅0.25 (= 1/22) 幅0.0625 (= 1/24)

配列解析アルゴリズム特論 渋谷 算術符号（Arithmetic Code） (2) ¦ 考え方 ¿ 文字列の長さ k の接頭辞の出現分布を考える uなんらかのモデルが必要 ’ 最も単純な算術符号＝単純な１文字ずつ独立した情報源とするモデルを仮定する ¿ その接頭辞を[0,1)中の部分区間に対応させる u範囲の大きさが文字列の出現確率に相当するようにする u異なる文字列は重ならないように。辞書順に0から1へ。 ¿ その間に含まれる最小ビット数の小数を文字列のコーディングだと考える uどんなに長い文字列であっても、そのたった一つの小数がその文字列のコーディング ¿ 文字列長も記憶しておく uひとつの小数に対応する文字列は、無限に存在する（いかなる文字列長の文字列で も対応する文字列が１つある） 0.0 1.0 a b aa ab aba abb abab abaa 0110111

配列解析アルゴリズム特論 渋谷 算術符号（Arithmetic Code） (3)

¦

性質

¿

（そのモデルにおいて）出現確率の高い文字列は大きい

範囲を占めるため、ビット数の少ない小数が含まれる

（＝高圧縮）

uその確率を𝑝𝑝とすると − log 𝑝𝑝 ビット以下

¿

すなわちその圧縮長の期待値は

𝑝𝑝 � − log 𝑝𝑝

u1文字ずつ独立に文字が出力される情報源であれば、 𝑝𝑝 � − log 𝑝𝑝 < 𝑛𝑛 � 𝐻𝐻 + 1が成り立つ ’ すなわち、 n 字拡大情報源に対するハフマン符号と同じ上界を 持つ！ 0.0 1.0 a b aa ab aba abb abab abaa 0110111

配列解析アルゴリズム特論 渋谷

Decoding Arithmetic Codes

¦

３つのステップ

¿比較 ¿文字出力 ¿スケーリング（対象となる区間を[0.1)に拡大する） 0.0 1.0 a b aa ab aba abb abab abaa 0110111

配列解析アルゴリズム特論 渋谷 算術符号の特性

¦

様々な情報源モデルに対応できる

¿

要は次の文字を確率付きで予測できるようなモデル

さえあればなんでも適用可能！

uオンラインでの予測→Adaptive arithmetic coding

uマルコフモデルによる予測→ＰＰＭ圧縮 u画像の次の画素の予測→画像圧縮

¦

実装の問題

¿小数の表現をどうするか u非常に長いビット列（桁数）で表される浮動小数の演算を効率よく、か つ誤差なく計算する必要性

配列解析アルゴリズム特論 渋谷

Adaptive Arithmetic Coding

¦

最初はすべての文字を等確率、とおき、2文

字目以降はそれを更新していく、ということが

簡単に可能

¿

デコードも可能

1 2 1 1 1 2 2 1 1 3 2 1 A C G T

配列解析アルゴリズム特論 渋谷

PPM (Prediction with Partial Matching)

¦ 長さm以下の部分文字列に対し、次に来る文字を予測 ¿ 新しい「出現」時は、より短い部分文字列からの予測率を用いる u区別するための記号(ESC)を用意 uESCの頻度はすでに表れたことのある文字の種類の数 ’ いろんなバリエーションが存在：例えばPPMAでは単に１とおく ¿ 初めての出現文字の並びの場合にはすべての文字が等確率に出現、と 仮定 ¿ 頻度表はデコード時にも作成できるので、記憶する必要はない 頻度表を作成する ATGCG A:2 C:1 ATGCT A:7 C:4 G:21 T:3 ATGGA G:2 次の文字の頻度 直前の文字 ESC: 2 ESC: 4 ESC: 1

配列解析アルゴリズム特論 渋谷

JBIG1: Binary imageの圧縮

¦

直前の10bitの「画像」から予測

1 2 4 5 6 7 9 10 3 8

Arithmetic Coding

配列解析アルゴリズム特論 渋谷 LZ77 (Ziv-Lempel '77)

¦

辞書法

¿一度出てきた単語はまた出てくることが多い ¿出てきた文字列で一番長く一致する部分をみつけ、その 場所と長さでコーディング

¦

計算方法

¿接尾辞木を使えば線形時間！ uただしメモリは多く必要

とてもまともなとまとももともとまともなとまとではなかった

４，７ ４，２ １２，２ さらにHuffman符号と組み合わせる→LZH,zip,PNG Shanon-Fano符号と組み合わせる→gzip

配列解析アルゴリズム特論 渋谷 LZ78 (Ziv-Lempel '78)

¦

すべての位置から探すのは大変なので、コードとして

既に使われたものを用いる

¿すでにコードされたもの＋１文字でコード ¿位置ではなく位置の差分で

とてもまともなとまとももともとまともなとまとではなかった

4, も 6, ま 3, も 4, と 6, と 8, な 5, と 9, か 以前に出てきた場所との差＋1文字でコード

配列解析アルゴリズム特論 渋谷 LZW (Welch)

¦

先に1文字だけの辞書を用意し、さらに、辞書を先に

作成しておけば、場所だけの記憶でコードできる

¿辞書はエンコード時に作成できるので、特に覚える必要 はない ¿高速だが圧縮率はさほど高くない 事前に作成してあるアルファベット表 １：と ２：て ３：も ４：ま ５：な ６：で ７：は ８：た ９：か １０：っ

とてもまともなとまとももともとまともなとまとではなかった

1 2 3 4 1 3 5 1 14 3 3 15 18 15 17 14 6 7 5 9 10 8 11 13 15 17 19 21 23 25 27 29 31 12 14 16 18 20 22 24 26 28 30 gif や tiffで使用 暗黙的な コ ー ド

配列解析アルゴリズム特論 渋谷 文法圧縮

¦

文脈自由文法で表す＝圧縮になっている

¿表したものをさらに算術符号（等）で圧縮する

¿実はLZ78, LZWも文法圧縮の一種！ （LZ77は違う）

¿しかし最小の文法はNP-hard [Lehman, Shelat, 2002]

u現実的にはヒューリスティックな文法で！ とてもまともなとまとももともとまともなとまとではなかった Ｓ → とてもＤＢＣＣＤAではなかった Ｄ → Ｂなと Ｃ → もと Ｂ → Ａも Ａ → まと 変換した文字列： とてもＤ（B(A（まと）も）なと）ＢＣ（もと）ＣＤＡではなかった さらに算術符号等で圧縮

配列解析アルゴリズム特論 渋谷

Re-Pair [Larsson, Moffat 2000]

¦

最も頻出する2文字ペアを置換することを繰り返す

¿O(n)で計算可能 T = a b c b b c a b c b a b c c a X₁ b X₁ a X₁ b a X₁ c X₂ b X₁ X₂ b X₂ c X₃ X₁ X₃ X₂ c

X

₁

→ bc

X

₂

→ a X

₁

X

₃

→ X

₂

b

圧縮テキスト 辞書

配列解析アルゴリズム特論 渋谷 まとめ

¦ 文字列圧縮アルゴリズムのいろいろ

¦ 次回