1

北海道大学
Hokkaido University

情報知識ネットワーク特論「情報検索とパターン照合」
情報科学研究科 コンピュータサイエンス専攻
情報知識ネットワーク研究室

喜田拓也

2005/11/15

情報知識ネットワーク特論 講義資料

第６回
圧縮テキスト上のパターン照合
データ圧縮について
本研究の動機と目標
Huffman符号化テキストに対する照合
LZW圧縮テキストに対する照合
統一的枠組み： Collage system
圧縮による照合の高速化という視点： BPE圧縮

北海道大学 Hokkaido University3

データ圧縮について
可逆圧縮（lossless compression）
エントロピー符号

非ユニバーサル符号

Runlength

非可逆圧縮（lossy compression）

ハフマン
符号

JPEG

算術
符号化
MPEG

ユニバーサル符号
文法圧縮
辞書式

LZ78
LZ77

Sequitur

LZW BPE

統計型

PPM

sort-based

BWT

MP3

映像や音声のデータに用いられる※参考文献： Managing Gigabytes: Compressing and Indexing Documents and Images, I. H. Witten, A. Moffat, T. C. Bell, Morgan Kaufmann Pub, 1999.

2005/11/15

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

4

本研究の目的
普通のパターン照合機械

オリジナル
オリジナル
テキスト
テキスト

普通の
パターン照合機械

展開
圧縮テキスト
圧縮テキスト

圧縮テキスト
圧縮テキスト
2005/11/15

オリジナル
オリジナル
テキスト
テキスト

圧縮テキストに対するパターン照合機械

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

5

本研究の応用例
小型のコンピュータ（携帯電話やPDA等）にできるだけ多くのデータを詰め込みたい！
 メモリが小さいので、索引データ構造は作りたくない！
 しかし、検索は高速に行いたい！


趣味的データベース

メモ

メール

名刺データ

住所録
予定表

電子書籍

英和・和英辞典

広辞苑※写真はsharp mi110と東芝V601T

2005/11/15

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University6

圧縮されたテキストに対する照合の難しさ
文書ファイル群

ハードディスクやメモリの容量が十分に大きくなってきた今日、
ハードディスクやメモリの容量が十分に大きくなってきた今日、
コンピュータを個人的に利用する範疇において「容量を減らす
コンピュータを個人的に利用する範疇において「容量を減らすためにテキストデータを圧縮して保存する」ということはほとん
ためにテキストデータを圧縮して保存する」ということはほとん
どないでしょう。
どないでしょう。 Windowsにはフォルダごとに圧縮をかけて容Windowsにはフォルダごとに圧縮をかけて容量を小さくする機能がありますが、私はこの機能を使ったこと量を小さくする機能がありますが、私はこの機能を使ったことがありません。画像や音声データのようなマルチメディア・がありません。画像や音声データのようなマルチメディア・
データならば圧縮して保存するのが当然ですが、テキスト
データならば圧縮して保存するのが当然ですが、テキストデータを圧縮することは百害あって一利なしと思われるでしょデータを圧縮することは百害あって一利なしと思われるでしょう。しかし、例えば大量のログファイルや過去のメールデータ
う。しかし、例えば大量のログファイルや過去のメールデータなどは削除せずに圧縮保存しておくほうが得策です。つまりなどは削除せずに圧縮保存しておくほうが得策です。つまり

2005/11/15

圧縮文書ファイル群

011110000111100111111101011010001
011110000111100111111101011010001
010101001111010001011100110101111
010101001111010001011100110101111
011000111011111101001101011111001
011000111011111101001101011111001
101001110011011000001111110101101
101001110011011000001111110101101
011111111100000101001001010011010
011111111100000101001001010011010

1. 符号語の開始位置がわからない
2. 文字列の表現がユニークでない
情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

7

本研究の目標「展開しながら」法「展開してから」法

目標： これらより速い！

「展開しないで」法※ 上図イラストは竹田正幸先生の作；出版物初出「情報処理」2002年, Vol.43, No.7, p.764(図-１)
2005/11/15

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

8

本分野における研究
圧縮方法

照合アルゴリズム

Run-length
Run-length (two dim.)
LZ77 family

Eilam-Tzoreff & Vishkin (1988)
Amir et al. (1992, 1997); Amir & Benson (1992)
Farach & Thorup (1995); Gąsieniec, et al. (1996);
Klein & Shapira (2000)
Amir et al. (1996); Kida et al. (1998, 1999);
Navarro & Tarhio (2000); Kärkkäinen et al. (2000);Navarro et al. (1999)
Karpinski et al. (1997); Miyazaki et al. (1997);
Hirao et al. (2000)
Fukamachi et al. (1998); Klein & Shapira (2001);
Miyazaki et al. (1998)
Takeda (1997)
Moura et al. (1998)
Manber (1994); Shibata et al. (1998)
Shibata et al. (1999)

LZ78 family
LZ family
Straight-line programs
HuffmanFinite state encoding
Word based encoding
Pattern substitution
Antidictionary based
2005/11/15

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

9

Huffman符号化テキスト上の照合
Huffman tree
0

0

0

0

A

2005/11/15

1

1

1

B

C

D

1

パターン P = DEC

E

Huffman符号化したパターン E(P) = 011001

テキスト T = ABECA・・・
Huffman符号化したテキスト E(T) = 0000000110010000・・・
誤った出現！

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

10

同期を取る方法


素朴な方法– ビットを読むごとにHuffman treeを（根から順に）たどりながら符号語の先頭位置を判別し、任意のPrefix型アルゴリズムでパターン照合を行う– 符号語の先頭かどうかを判定する手間がかかるので、遅い



フィルタリング＋検査– Shmuel T. Klein, D. Shapira:Pattern Matching in Huffman Encoded Texts. DCC2001: 449-458.
– E(T)からE(P)を任意のパターン照合アルゴリズムを用いて検索し、ヒットした位置が正しい出現かどうかを調べる– Huffman符号語の場合、符号語の途中から復号しても、ある程度のビットを読めば自動的に同期が回復する。よって、ヒットした位置から定数Kビットだ
け手前に戻ってからヒットの語頭位置を検査する
 Kはだいたい100もとれば、十分に語検出は抑えられる パターンが長くなればなるほど語検出しにくくなる

実験的に実証同期型KMP（AC）オートマトン– M. Miyazaki, S. Fukamachi, M. Takeda:
Speeding up the pattern matching machine for compressed texts(in Japanese), Trans. IPSJ, Vol. 39, No. 9, pp.2638-2648, 1998.

2005/11/15

情報知識ネットワーク特論 講義資料

11

同期つきオートマトンによる解決

北海道大学 Hokkaido University

M. Miyaaki, S. Fukamachi, M. Takeda: Speeding up the pattern matching machine for compressed texts(in Japanese), Trans. IPSJ, Vol. 39, No. 9, pp.2638-2648, 1998.

Huffman tree

パターン P = DEC
0

0
0
0

A

1

1
1

∑

E

0

1

C

0

B

0
0
0

1

0

0

1

同期なしKMPオートマトン

D1

Huffman符号化したパターン E(P) = 011001

1

0

1

1

0

0

1

1
1

1

同期つきKMPオートマトン

テキストT = ABECA・・・ Huffman符号化テキストE(T) = 0000000110010000・・・
2005/11/15

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

12

Lempel-Ziv-Welch (LZW)圧縮法

T. A. Welch: A technique for high performance data compression, IEEE Comput., Vol.17, pp.8-19, 1984.

テキスト T:a b ab ab ba b c aba bc abab

圧縮テキスト E(T): 1 2 4

a
b
a
b

6

11

1
4

b
a

b
7

b

0
2

c
c

5

9

8

12

a

3

a

10

4

5 23

6

9

11

辞書木に登録されている文字列の集合をDとする
D = {a, b, c, ab, ba, bc, ca,aba, abb, bab, bca, abab}
Dは適応的に構築される

辞書木|D| = O(圧縮テキスト長)※ UNIXのcompressコマンドやGIF形式の画像圧縮などに使われている
2005/11/15

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

13

復習： Aho-Corasick照合機械の動作
パターン集合Π= {aba, ababb, abca, bb} に対するAC照合機械
0

a

b

1

2

a

c
b

8

状態： 0
テキスト：
Output：2005/11/15

9

b
a

1

b

3

6

b

4

{aba}

b

5

{ababb, bb}

7a{abca}: goto 関数: failure 関数{ } : output

{bb}

2

a

3

aba

b

4

a

3

aba

b

4

b

5

bb
ababb

a

1

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

14

アルゴリズムのアイデア

T. Kida, M. Takeda, A. Shinohara, M. Miyazaki, and S. Arikawa: Multiple pattern matching in LZW compressed text,
Proc. Data Compression Conference, pp. 103-112, IEEE Computer Society, Mar. 1998.



LZW圧縮テキスト上で、AC照合機械の動作をシミュレートしたい
0

a

b

1

2

a

c
b

8

状態： 0
テキスト：
圧縮テキスト：
Output：2005/11/15

9

b
a

1

1

b
2

3

6

b

4

{aba}

b

5

{ababb, bb}

7a{abca}: goto 関数: failure 関数{ } : output

{bb}

2

a

3
4

aba

b

4

a

3
4

aba

b

4

b

5
5

bb
ababb

a

1

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

15

アルゴリズムの核となる関数：Jump & Output


二つの関数 Jump と Output をうまく計算できないか？
–関数 Jump(q, u) ：文字列 u に対応する遷移の連続をO(1)時間で模倣する
 定義域はQ×D
O(m2+|D|)領域で単純には
 AC照合機械の状態を返す
O(m|D|)領域が実現！


必要と考えられる–関数 Output(q, u) ：状態 q に対応する文字列と u を連結した文字列中に現れるパターンの出現位置をO(r)時間で報告する
 定義域はQ×D
O(m2+|D|)領域で単純には
 パターンの集合を返す
O(m|D|)領域が実現！
必要と考えられる

2005/11/15

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University16

関数Jumpについて
δ(q,u) をもとのAC照合機械の（拡張された）状態遷移関数※とするとO(m3)領域

Jump(q, u) =δ(q, u)δ(ε, u)uがあるパターンの部分文字列のときそれ以外のときO(|D|)領域
O(m2)領域O(m2)領域※

Ancestor(N'1 (q, u'), |u'|－|u|)Jump(q, u) =uがあるパターンの部分文字列のとき

δ(ε, u)

それ以外のときO(|D|)領域※ つまりδ(q,u)は、状態qから文字列uを読み込んだとき、gotoとfailureで遷移した先の状態を返す関数※ u’ はPに対するgeneralized suffix trie上で、uの先祖で最も近いexplicitなノードに対応する文字列
2005/11/15

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University17関数Outputについて
u~ ：uの接頭辞でかつパターンの接尾辞である最長の文字列~ i <|u|, |p|< i,A(u) = ｛〈i,p〉| p∈Π, |u|<and u[i－|p|+1...i ]=p｝

状態qは、あるパターンのprefixに対応することに注意

O(|D|)領域

O(m2)領域

Output(q, u) = Output(q, u)~ ∪ A(u)qp1
2005/11/15

u
u~
p2

p1

p2
情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

18

Kida, et al. [1998]の結果


おおもとのアイデア：– A. Amir, G. Benson, and M. Farach: Let sleeping files lie: Patternmatching in Z-compressed files, J. Computer and System Sciences,
Vol.52, pp.299-307, 1996.


LZW圧縮テキスト上でKMPをシミュレート

Aho-Corasick（AC）照合機械を模倣することにより、複数パ
ターンを同時に探索することが可能
2
 前処理にO(m +|Σ|)時間・領域かかる
2
 任意の個数のパターンについて、O(n+r)時間・ O(m +|D|)領域
で圧縮テキストを走査し、すべての出現位置を報告する
※ 初出は、「T. Kida, M. Takeda, A. Shinohara, M. Miyazaki, and S. Arikawa: Multiple pattern matching in
LZW compressed text, Proc. Data Compression Conference, pp. 103-112, IEEE Computer Society, Mar.
1998. 」だが、Journal版が2000年にある：「T. Kida, M. Takeda, A. Shinohara, M. Miyazaki, and S. Arikawa:
Multiple Pattern Matching in LZW Compressed Text, Journal of Discrete Algorithms, 1(1), pp. 133-158,
Hermes Science Publishing, Dec. 2000.」
2005/11/15

情報知識ネットワーク特論 講義資料

19

Bit-parallel化のアイデア

北海道大学 Hokkaido University

T. Kida, M. Takeda, A. Shinohara, and S. Arikawa: Shift-And approach to pattern matching in LZW compressed text,
Proc. CPM'99, LNCS1645, pp. 1-13, Springer-Verlag, Jul. 1999.

パターンP:=

aabac

テキストT:=

a a b a a c a a b a c a b
1 1 0 1 1 0 1 1 0 1 0 1 0
0 1 0 0 1 0 0 1 0 0 0 0 0
0 0 1 0 0 0 0 0 1 0 0 0 0
0 0 0 1 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 1 0 0

a
a
b
a
c

Jump!
2005/11/15

マスクビット

a b c
1 0 0
1 0 0
0 1 0
1 0 0
0 0 1

Jump!
情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

20

拡張した状態更新関数f’

任意の a∈Σ, u∈Σ*, S∈{1,…, m} について以下のように定義する– M(a) = { 1< i < m | P[i] = a }– f(S, a) = ((S ⊕ 1)∪{1}) ∩ M(a)– f’(S,ε) = S and f’(S, ua) = f’( f(S, u), a)– M’(u) = f’({1,・・・, m}, u)O(|D|)時間・領域



このとき、任意のu∈Σ*, S∈{1,・・・, m} について–f’(S, u) = ((S ⊕ |u|)∪{1,・・・, |u|}) ∩ M’(u)O(1)時間2005/11/15

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University21

関数OutputのBit-parallel版


定義：
O(|D|)時間・領域–Output(S, u) = { 1 < j < |u| | m∈S }–U(u) = {1 < j < |u| | i <m かつ u[1..i] =P[m-i+1..m] }–A(u) = {1 < j < |u| | m < i かつ u[1-m+1..i]=P }–Output(S, u) =((m ⊖ S)∩U(u)) ∪ A(u)qP
2005/11/15

O(|D|)時間・領域

u(m ⊖ S)∩U(u)P

A(u)
情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

22

Kida, et al. [1999]の結果
Shift-And法に基づいたBit-parallel手法を適用して、状態遷移関数とOutput関数の処理を高速化
 前処理にO(m+|Σ|)時間・領域を使用
 一つのパターンについて、O(n+r)時間・O(m+|D|)領域で圧縮テ
キストを走査し、すべての出現位置を報告する
 Shift-And法と同様、拡張性に優れている– 一般化されたパターンに対する文字列照合– k個のミスマッチを許した文字列照合– 複数パターンへの対応

2005/11/15

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University23

目標の達成！

CPU時間（秒）1.4
1.2

AlphaStation XP1000(Alpha21264: 667MHz)
Tru64 UNIX V4.0F

1.0

Genbank（DNA塩基配列）
17.1Mbyte

0.8「展開しながら」法

0.6

compress(LZW)+KMP
gunzip(LZ77)+KMP

0.4「展開しないで」法

0.2
02005/11/15

T. Kidaら[1998]
ビットパラレルによる高速化[1999]

510

15 20 25
パタンの長さ30
情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University24

論文の衝突！


第一次ショック！ (at CPM’99)– T. Kida, et al., Shift-And Approach to Pattern Matching in LZWCompressed Text
– G. Navarro and M. Raffinot, A General Practical Approach to Pattern
Matching over Ziv-Liempel Compressed Text



第二次ショック！ (at CPM2000)– Y. Shibata, et al., A Boyer-Moore type algorithm for compressed
pattern matching– G. Navarro and J. Tarhio, Boyer-Moore string matching over ZivLempel compressed text

2005/11/15

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

25

コラージュ・システム(Collage system)

T. Kida, et al. A Unifying Framework for Compressed Pattern Matching, In Proc. 6th International Symp. On String
Processing and Information Retrieval, pp. 89-96. IEEE Computer Society, 1999.



辞書式圧縮法によって圧縮されたテキストを統一的に表現するための形式的体系

コ

ラ

ー

ジ

ュ

シ

ス

テ

ム

LZ77圧縮テキスト
LZ78圧縮テキスト
LZW圧縮テキスト

2005/11/15

コラージュシステムで表現されたテキストに対する照合アルゴリズム

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

26

コラージュ・システムの例
X1 = a ;X2 = b ;X3 = X1・X2 ;D : X4 = X2・X1 ;X5 = ( X3 )3 ;X 6 = [ 3 ]X 5 ;（連接） a b（連接） b a（繰り返し） a b a b a b（切り落とし） b a b||D|| = 6
S : X3 X6 X4 X5 X2 X3 X1 X5 X4 X2|S| = 10abbabbaabababbabaabababbab
2005/11/15

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

27

コラージュ・システムの定義
コラージュシステムとは，組〈D, S 〉
 D : トークン割当の集合（辞書に相当）– X1 = expr1 ; X2 = expr2 ; ・・・ ; Xn = exprn
各 exprk は以下のいずれか aa ∈Σ∪{ε}一文字割当 Xi ・ Xｊ
i, j は整数で， i, j < k 連結j
 ( Xi )i, j は整数で， i < k繰り返し [ j ]Xii, j は整数で， i < k
前切り落とし[j] Xi
i, j は整数で， i < k
後切り落とし– ||D|| = n : D中のトークンの個数– X.u ： トークン X が表す文字列
S : D で割当てられたトークンの列（符号列に相当）– Xi1 Xi2 ・・・Xil( Xi は D中のトークン)– |S| = l : トークンの列の長さ

2005/11/15

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

28

照合アルゴリズムの計算量定理
コラージュシステム〈D, S 〉で表現されたテキストに対する文字列照合問題は，
O( ||D|| + |P|2 ) 領域を用いて
O( ( ||D|| + |S| )・height(D) + |P|2 + r ) 時間で解決できる．
圧縮テキスト長|P| はパタンの長さ

r はパタンの出現回数

Dが切り落とし操作を含まない場合は，O( ||D|| + |S| + |P|2 + r ) 時間で解決できる．

2005/11/15

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

29

得られた知見O( (||D||+|S|) ・height(D) + |P|2 + r ) 時間

LZ77 LZSS
切り取り操
作が

ある

O( ||D|| + |S| + |P|2 + r ) 時間

LZ78

LZW

BPE

Sequitur

切り取り
操作がな
い

O( ||D|| + |P|2 ) 領域
2005/11/15

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

30

ちょっと、ひといき・・・

ここまでのまとめ– Huffman符号化テキストに対する照合 → 同期つきオートマトン– LZW圧縮テキストに対する照合 → KMP(AC)の遷移をLZW上で模倣– 統一的枠組み： Collage system 辞書式圧縮法によって圧縮されたテキストを統一的に表現するための形式的体系
 Collage systemの枠組みに入る圧縮法に関して、その上での統一的なパターン照合アルゴリズムを得た
 切り取り操作を含まない圧縮法は、パターン照合に向いている～トリビア～
佐藤雅彦 著：「毎月新聞」より

左を見よ
正11角形

キングペンギンの雛 （旭山動物園にて ’05.3.13）
2005/11/15

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

31

圧縮文字列照合する理由は？
もし・・・

容量は十分あるのに、テキストを圧縮して保存しますか？

元のテキスト上での照合時間×

2005/11/15

目標２

×

×

＞

新たな目標
圧縮テキスト上の照合時間

×

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

32

新たな目標（目標２）

CPU時間（秒）1.4
1.2

AlphaStation XP1000(Alpha21264: 667MHz)
Tru64 UNIX V4.0F

1.0

Genbank（DNA塩基配列）
17.1Mbyte

0.8「展開しながら」法

0.6

compress(LZW)+KMP
gunzip(LZ77)+KMP

0.4
0.2
0

2005/11/15

非圧縮テキストをKMPで照合
こちらのほうが圧倒的に早い

5

10

15 20 25
パタンの長さ「展開しないで」法
T. Kidaら[1998]
ビットパラレルによる高速化[1999]30
情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

33

Bite Pair Encoding(BPE)圧縮法
18

テキスト

ABABCDEBDEFABDEABCG

G G C D E B D E F G DE
GC
DEG
H

GGCHBHFGHGC

辞書
G →AB
H →DE
I → GCI
置換後の文字列

GIHBHFGHI

サイズ：２５６= 1 byte分

92005/11/15

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University34

目標２の達成0.8

前の図では一番早かった

0.7

CPU時間（秒）AlphaStation XP1000(Alpha21264: 667MHz)
Tru64 UNIX V4.0F
Medline（英文テキスト）
60.3Mbyte

0.6

非圧縮テキストをKMPで照合

0.5「展開しないで」法

0.4

BPE圧縮テキストに対する照合(KMP)

0.3

非圧縮テキストをAgrepで照合

0.2「展開しないで」法

0.1
0.0
2005/11/15

5

10 15 20 25
パタンの長さ30

BPE圧縮テキストに対する照合(BM)Shibata, et al. (2000)

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

35以上の話をまとめると…
普通の2

非圧縮テキスト
LZSS専用

4

GOAL

GOAL

圧縮率は高いLZSS圧縮テキスト
LZW専用

GOAL

3

圧縮率はまあまあ

LZW圧縮テキスト
BPE専用

1
BPE圧縮テキスト

2005/11/15

GOAL

圧縮率は低いでも文字列照合には適している
情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

36

パラダイムシフト
圧縮技術を応用して様々な処理の困難さの壁を打ち破る

データを圧縮することで文字列照合を高速化できる！

保存コストや転送コストを低減するためにデータ圧縮技術を用いる

2005/11/15

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

37

圧縮技術で・・・する

長大な二つの文字列どうしの類似度を《圧縮技術で》高速化する– “A Sub-quadratic Sequence Alignment Algorithm for Unrestricted Cost
Matrices”,

M. Crochemore, G. M. Landau, and M. Ziv-Ukelson, Proceeding of 13th Symposium on Discrete
Algorithm, pp.679-688, 2002



巨大なグラフ構造を《圧縮技術で》オンメモリに載せて処理する– 中野眞一（群馬大学） 「クエリサポート付きグラフ圧縮」
極大平面グラフを2m+o(n) bitで、かつクエリサポートXML（半構造データ）に対する問い合わせを《圧縮技術で》高速化する– 舞田哲哉、坂本比呂志（九州工業大学）

2005/11/15

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

38

その他の結果

文法圧縮テキスト上のパターン照合– S. Mitarai, et al., Compressed Pattern Matching for SEQUITUR, In Proc.
Data Compression Conference 2001, pp. 469-478, IEEE Computer
Society, 2001.



圧縮テキストに対する近似文字列照合– T. Matsumoto, T. Kida, et al., Bit-parallel approach to approximate string
matching in compressed texts, In Proc. 7th International Symp. On String
Processing and Information Retrieval, pp.221-228, IEEE Computer
Society, 2000.
– G. Navarro, T. Kida, et al., Faster Approximate String Matching overCompressed Text, In Proc. Data Compression Conference 2001, pp. 459468, IEEE Computer Society, 2001.



BWT圧縮に関するパターン照合– A. Firth, T. Bell, A. Mukherjee, and D. Adjeroh: A comparison of BWT
approaches to string pattern matching, Software—Practice & Experience,
Vol.35(13), pp.1217-1258, 2005.

2005/11/15

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

39

第６回 まとめ

データ圧縮されたテキスト上でのパターン照合アルゴリズム– Huffman符号化テキストに対する照合 → 同期つきオートマトン– LZW圧縮テキストに対する照合 → KMP(AC)の遷移をLZW上で模倣



統一的枠組み： Collage system– 辞書式圧縮法によって圧縮されたテキストを統一的に表現するための形式的体系– どのような圧縮法がパターン照合に適しているかを明確にした

圧縮による照合の高速化という視点– BPE圧縮： 圧縮率は低いが、パターン照合を高速化する– もとのテキストに対してパターン照合するよりも高速に照合できた

大きなパラダイムシフト– データ圧縮技術は、単にデータを小さくするだけではない使い道がある次回（「情報検索とパターン照合」最終回）のテーマ– これまでの講義でできなかったトピックスについて、いろいろ

2005/11/15

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

40

Kida, et al.[1998]のアルゴリズムの擬似コード
PMonLZW (E(T) = u1u2…un, Π:パターン集合)
1 Construct AC machine and generalized suffix trie for Π;
2 Initialize the dictionary trie for E(T);
3 Preprocess Jump(q,u) and Output(q,u)
for any q and u∈{あるパターンπ∈Πのfactor}
4 l ← 0;5 q ← q0;
6 for i ← 1…n do
7for each 〈d ,π〉∈Output(q, ui) do
8report pattern π occurs at position l+d;9q ← Jump(q, ui);10l ← l + |ui|;
11
Update the dictionary trie;/* ノードui+1に対する文字列がDに登録される */12
Update variables for Jump(q, ui+1) and Output(q, ui+1);/* δ(ε,ui+1) やA(ui+1)、ui+1’、|ui+1|等が親ノードを用いて計算される */13
end of for
14 end of for2005/11/15

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

41

付録： 文脈自由文法について

４つ組G=(N,Σ,P,S)によって定義される。
– N：非終端アルファベットと呼ばれる空でない有限集合。
– Σ ：終端アルファベットと呼ばれる空でない有限集合。
– P：N×(N∪Σ)*の有限部分集合。
Pの要素(A, α)は生成規則と呼ばれ、A→α と書かれる。
– S：S∈Nで、開始記号という。



BNF(Backus Naur Form)は文脈自由文法の表記法の一つ。
Chomsky階層の４言語族

句構造言語（0型）

FSL

文脈依存言語（1型）
文脈自由言語（2型）

CSL
CFL

正規言語（3型） RGL
2005/11/15

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

42

付録： 文脈自由文法の例（１）
文脈自由文法G=(N,Σ,P,S)
N={S}, Σ ={a,b}, P={S→ab, S→aSb}
S ⇒ aSb ⇒ aaSbb ⇒ aaabbb
L(G)={anbn | n は 1以上の整数}
S
構文木：

S
S

a a a b b b
2005/11/15

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

43

付録： 文脈自由文法の例（２）
文脈自由文法G=(N,Σ,P,S)
N={S,A,B}, Σ ={a,b},
P={S→AA, A→aaB, B→bb}
S ⇒ AA ⇒ aaBaaB ⇒ aabbaabb
L(G)={aabbaabb}
構文木：

S
A

A
B

B

a a b b a a b b
2005/11/15

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

44

付録： 文法変換に基づく圧縮の考え方
John C. Kieffer and En-hui Yang, 2000.

元のデータ（テキストデータ）
T

変換
L(GTT)={T}

文法

導出（文脈自由文法）

符号化

GT

圧縮データ
復号化
2005/11/15（ビット列）

B(GT)

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

45

付録： これまでの研究（C. Kieffer ら調べによる）[G固定：構文木を圧縮]

R. Cameron [1988]
 E. Kawaguchi and T. Endo [1980]
 E. Kourapova and B. Ryabko [1995]
[L(G)={x} となる G を圧縮]

C. Cook, A. Rosenfeld, and A. Aronson [1976]
 J. Storer and T. Szymanski [1995]
 C. Nevill-Manning and I. Witten [1997]

2005/11/15

情報知識ネットワーク特論 講義資料