圧縮テキストに対する文字列照合問題 竹田研究室 博士課程二年　喜田 拓也.

Presentation on theme: "圧縮テキストに対する文字列照合問題 竹田研究室 博士課程二年　喜田 拓也."— Presentation transcript:

1 圧縮テキストに対する文字列照合問題 竹田研究室 博士課程二年　喜田 拓也

2 発表内容 圧縮テキスト上の文字列照合問題 本研究分野の歩み 近似文字列照合アルゴリズム まとめ 発表内容

3 文字列照合問題 hanage 日本経済新聞 １１月１６日 朝刊（ジュネーブ発 西山 章宏）
日本経済新聞　１１月１６日　朝刊（ジュネーブ発　西山　章宏） スイスの保養地、ダヴォス・プラッツで１１月１０日から１１月１４まで、行われた、世界知覚認識学会（ミシェル・ポーター会長）で、北海道大学医学部の斉藤信（まこと）教授が提唱した、痛みを表す「hanage」と言う単位を、世界で共通の単位とする事が承認された。本来、痛みは、個人差が大きく、同じ刺激でも主観によって感じ方が異なるため、客観的に数値で表すことは、不可能であると思われていた。しかし、斉藤教授は、「鼻の粘膜は、人体の中で一番個人差が小さい。」事に注目し研究を進めた結果、１センチの鼻毛を、１Ｎ（ニュートン）の力で、引っ張る時に生じる痛みを、１hanageと定義出来ることを発見し、そして今学会で単位として承認された。 文字列照合問題

4 文字列照合問題 データ圧縮 ... O(テキストの長さ) 既存の手法 限界 !? 索引構造
Knuth-Morris-Pratt (1974) Boyer-Moore (1977) Karp-Rabin (1987) Bit-parallelism (1987) 既存の手法 O(テキストの長さ) 限界 !? データ圧縮 数多くのアルゴリズムが提唱されている． 細かい改良も数多くなされたが，照合スピードは頭打ちになっている． この分野での進展はもうない． 索引構造 Suffix array Inverted file 文字列照合問題

5 圧縮テキスト上の文字列照合問題 原テキスト テキスト パターン 展開 圧縮 非圧縮 圧縮テキスト 圧縮テキスト 普通の 文字列照合機械
圧縮テキストに対する 文字列照合機械 圧縮テキスト 圧縮 テキスト 非圧縮 パターン 圧縮テキスト上の文字列照合問題

6 圧縮テキスト上の文字列照合問題とは 本研究分野の歩み 圧縮テキスト上の近似文字列照合問題 まとめ 圧縮テキスト上の文字列照合問題とは 本研究分野の歩み 圧縮テキスト上の近似文字列照合問題 まとめ

7 Eliam-Tsoreff and Vishkin run-length 1992 Amir, Landau, and Vishkin
年 研究者 圧縮法 1988 Eliam-Tsoreff and Vishkin run-length 1992 Amir, Landau, and Vishkin two-dimensional run-length 1992 Amir and Benson two-dimensional run-length Amir, Benson, and Farach 1994 two-dimensional run-length 1994 Manber original compression scheme 1995 Farach and Thorup LZ77 1996 Gasieniec, et al. LZ77 1996 Amir, Benson and Farach LZW 1997 Karpinski, Rytter, and Shinohara straight-line programs 1997 Miyazaki, Shinohara, and Takeda straight-line programs 1997 Takeda finite state encoding 1998 Fukamachi, Shinohara, and Takeda Huffman encoding 1998 Kida, et al. LZW これまでの研究１

8 Dictionary based methods
年 研究者 圧縮法 1998 Kida, et al. LZW 1998 de Moura, et al. Word based encoding 1999 Kida, et al. LZW 1999 Navarro and Raffinot LZ family 1999 Shibata, et al. Antidictionaries Kida, et al. 1999 Dictionary based methods (Collage system) 1999 Shibata, et al. Byte pair encoding 2000 Shibata, et al. Collage system これまでの研究２

9 Amirらのアイデア 3 4 5 1 2 3 4 3 4 5 1 abababba a b a b a b b パターン 7 1 2 4 5
: goto 関数 : failure 関数 Knuth-Morris-Pratt(KMP) automaton a 1 2 4 5 b 3 -1 3 4 5 1 2 3 4 3 4 5 1 状態 テキスト abababba 圧縮テキスト X1 X2 X3 X4 Amirらのアイデア

10 我々の改良 Amir et al. 我々[DCC’98] KMP照合機械 Aho-Corasick照合機械 単一のパターンのみ
もっと速くしたいなぁ… Amir et al. 我々[DCC’98] KMP照合機械 Aho-Corasick照合機械 単一のパターンのみ 複数パターンに対応 最初の出現のみ報告 すべての出現位置を報告 O(n + m2)時間領域 O(n log m + m )時間 O(n+m)領域 O(n + m2)時間領域 実験結果なし 実装＆実験済み 我々の改良[DCC’98]

11 Bit-parallelism ababb a b a b b b a a abababba a b パターン 1 2 4 5 3 1 2
 a 1 2 4 5 b 3 a b a b b b a a abababba テキスト 1 2 3 4 5 1 Bit-parallelism

12 Ri = (Ri-1<<1 | 1) & M(T[i])
Bit-parallelism ababb マスクビット列M ab 1 a b パターン abababba テキスト 1 2 3 4 5 1 & Ri = (Ri-1<<1 | 1) & M(T[i]) Shift-And法の計算式

13 拡張のアイデア ababb abababba ab 1 1 a b パターン テキスト 2 3 4 5 Jump! Jump!
a b パターン abababba テキスト 1 2 3 4 5 Jump! Jump! 圧縮テキスト上のShift-And法

14 実験結果 （CPU時間） Time (sec) Pattern length uncompress+AC 0.2 0.4 0.6 0.8
0.2 0.4 0.6 0.8 1.0 1.2 1.4 5 10 15 20 25 30 Pattern length Time (sec) uncompress+agrep gunzip+AC gunzip+agrep uncomAC gunzipAC AC on LZW Bit-parallel on LZW AlphaStation XP1000 (Alpha21264: 667MH) Tru64 UNIX V4.0F Genbank(DNA sequence) 17.1Mbyte 実験結果

15 Medline(348,566 references) 60.3Mbyte
実験結果 （実時間） Medline(348,566 references) 60.3Mbyte method Local Remote 原テキストに agrep 2.39 9.03 uncomAC 4.10 6.93 gunzipAC 3.38 6.49 AC on LZW 3.29 5.51 Bit-parallel on LZW 3.01 5.49 データ転送速度 24.9Mbyte/sec データ転送速度 6.57Mbyte/sec Local Remote 実験結果

16 Dictionary based methods
年 研究者 圧縮法 1998 Kida, et al. LZW 1998 de Moura, et al. Word based encoding 1999 Kida, et al. LZW 1999 Navarro and Raffinot LZ family ショック！ ショック！ 1999 Shibata, et al. Antidictionaries Kida, et al. 1999 Dictionary based methods (Collage system) 1999 Shibata, et al. Byte pair encoding 2000 Shibata, et al. Collage system これまでの研究３

17 反撃のSPIRE’99 統一的枠組み 統一的枠組みに対する 照合アルゴリズム 従来
T. Kida, M. Takeda, A. Shinohara, Y. Shibata, and S. Arikawa. A Unifying Framework for Compressed Pattern Matching. In 6th International Symposium on String Processing and Information Retrieval, pp IEEE Computer Society, 1999. 統一的枠組みに対する 照合アルゴリズム 圧縮方法C 圧縮方法B 圧縮方法A 統一的枠組み 従来 照合アルゴリズムC 圧縮方法C 照合アルゴリズムB 圧縮方法B 照合アルゴリズムA 圧縮方法A Collage systemによる統一

18 （一文字代入，連結，繰り返し，切り落とし）
Collage system 直線的プログラム＋αの表現力 （一文字代入，連結，繰り返し，切り落とし） 圧縮テキストを抽象的に表現 （辞書部分と符号化列を分離: 〈D, S 〉） 辞書式圧縮法を統一的に扱える 一文字代入，連結，繰り返し，切り落とし 辞書部分と符号化列を分離: 〈D, S 〉 S X3 , X6 , X4 , X7 X1 = a ; X2 = b ; X7 = X6・X4 ; X6 = [ 3 ]X5 ; X5 = ( X3 )3 ; X4 = X2・X1 ; X3 = X1・X2 ; D S ここで、 X3 からX7 まではそれぞれ、このような文字列に対応しています。 すなわちこのS は下の文字列を表現していることになります。 これが原テキストで、S が圧縮テキストです。 abbabbababba Collage system

19 O( (||D||+|S|) ・height(D) + m2 + r ) 時間
Collage systemから得られた知見 O( (||D||+|S|) ・height(D) + m2 + r ) 時間 O( ||D|| + |S| + m2 + r ) 時間 LZ77 LZSS LZ78 Run length 切り取り操作がある BPE Huffman LZW 切り取り操作がない O( ||D|| + m2 ) 領域 Collage systemによる知見

20 Dictionary based methods
年 研究者 圧縮法 ほんと、速いよ。 1998 Kida, et al. LZW 1998 de Moura, et al. Word based encoding 1999 Kida, et al. LZW 1999 Navarro and Raffinot LZ family 1999 Shibata, et al. Antidictionaries Kida, et al. 1999 Dictionary based methods (Collage system) 1999 Shibata, et al. Byte pair encoding BMタイプ！ 2000 Shibata, et al. Collage system これまでの研究４（柴田登場）

21 BPE圧縮法 ABABCDEBDEFABDEABC AB G GGCDEBDEFGDEGC DE H GGCHBHFGHGC GC I
ペア表 A B C D E F G H I Code Pair AB DE GC テキスト ABABCDEBDEFABDEABC G AB GGCDEBDEFGDEGC H DE GGCHBHFGHGC I GC GIHBHFGHI BPE圧縮法

22 実験結果 Time (sec) Pattern length 0.00 0.05 0.10 0.15 0.20 0.25 5 10 15
30 Pattern length Time (sec) AlphaStation XP1000 (Alpha21264: 667MH) Tru64 UNIX V4.0F Genbank(DNA sequence) 17.1Mbyte KMP Agrep Bit-parallel on BPE BM on BPE 実験結果

23 目標の変遷 理論的興味のみ 照合を高速化する圧縮法の開発 展開時間 ＋ 照合時間 ＜ 原テキストの照合時間
照合時間　＜ 照合時間　＜　原テキストの照合時間 照合を高速化する圧縮法の開発 目標の変遷

24 圧縮テキスト上の文字列照合問題とは 本研究分野の歩み 圧縮テキスト上の近似文字列照合問題 まとめ 圧縮テキスト上の文字列照合問題とは 本研究分野の歩み 圧縮テキスト上の近似文字列照合問題 まとめ

25 近似文字列照合 CARRIAGE MARRIAGE MASSAGE 近似文字列照合問題

26 編集距離（レヴェンシュタイン距離） 1 3 文字列 x[1...n] を文字列 y[1...n] へ変換する ために要する最小コスト d
置換 = 削除 = 挿入 = 1 各操作のコスト CARRIAGE 1 MARRIAGE k = 2 MASSAGE 3 編集距離

27 非決定性オートマトンによる解法 POKEMON PIKACHU パターン 1 2 3 テキスト エラー数     N P O K E
  N P O K E M   N P O K E M   N P O K E M   1 2 3 PIKACHU テキスト 非決定オートマトンによる解法

28 R. Baeza-Yates and G. Navarro
Bit-parallelismの利用 R. Baeza-Yates and G. Navarro N P O K E M   1111 0011 0111 0000 0000 状態 S (mk+1)(k+1) サイズ Bit-parallelismの適用

29 基本的アイデア Jump(S, “PIK”) Output(S, “PIK”) P I     N P O K E M  N P

30 Jump (S, w) ∪ l d (i, j) , ( w S Jump ) = M(w;l, d). Ç ) ( l, d S Å
) , | min(| max( k d m w + - l 平行移動 O( k2 ) l 前処理で OK! d (i, j) Jumpのアイデア

31 Output (S, w)  Xi OMANZAIOMOROI •••PAPEPON POK EMON d=1 d=2 POKEMON
テキスト OMANZAIOMOROI •••PAPEPON POK EMON パターン d=1 d=2 POKEMON NOMEKOP Outputのアイデア

32 O( k2(||D||+|S| )+km )) 時間
理論的結果 T. Matsumoto, T. Kida, M. Takeda, A. Shinohara, and S. Arikawa. Bit-parallel approach to approximate string matching in compressed texts. In 6th International Symposium on String Processing and Information Retrieval. Simple Collage system LZ78, LZW O( k2(||D||+|S| )+km )) 時間 O( k2||D|| ) 領域 O(k2n+km)) 時間 O(k2n) 領域 ||D|| : 辞書の大きさ, m : パターン長 |S| : 符号列の長さ, k : エラーの上限 n : 圧縮テキスト長 J. Karkkainen, G. Navarro, and E. Ukkonen. Approximate string matching over Ziv-Lempel compressed text. In Proc.11th Ann. Symp. on Combinatorial Pattern Matching. J. Karkkainen, et al. O(mkn) 時間領域 動的計画法が土台 理論的結果

33 Genbank(DNA sequence)
実験結果（CPU時間） m (k =1) 8 12 16 20 24 28 32 uncompress+DP 2.572 3.638 4.578 5.513 6.504 7.466 8.375 Bit-parallel on LZW 5.364 6.233 6.475 6.633 6.829 7.021 7.269 k (m =14) 1 2 3 4 5 uncompress+DP 4.108 4.110 4.101 4.102 4.098 Bit-parallel on LZW 6.327 12.91 21.51 31.50 43.03 AlphaStation XP1000 (Alpha21264: 667MH) Tru64 UNIX V4.0F Genbank(DNA sequence) 17.1Mbyte compression ratio 26.8% 実験結果

34 圧縮テキスト上の文字列照合問題とは 本研究分野の歩み 圧縮テキスト上の近似文字列照合問題 まとめ 圧縮テキスト上の文字列照合問題とは 本研究分野の歩み 圧縮テキスト上の近似文字列照合問題 まとめ

35 まとめ 圧縮テキスト上の文字列照合は実用的な技術である． Collage systemは本研究のための強力な道具である．
辞書式圧縮法の抽象的な枠組みによる統一的手法. BPE圧縮法は，圧縮テキスト上の文字列照合に非常に適した圧縮法である． サイズ固定の静的辞書，固定長符号，単純なアルゴリズム. 文字列照合を高速化するためのデータ圧縮. 圧縮テキスト上の近似文字列照合アルゴリズムはまだ実用的でない． O( kn ) 時間？ まとめ

36 Bit-parallelismでのOutput (S, w)

37 じ も く 3 文字列照合問題 5 圧縮テキスト上の文字列照合問題 6 本研究分野の歩み 22 実験結果(CIAC&CPM2K)
7 これまでの研究１ 23 目標の変遷 8 これまでの研究2 25 圧縮テキスト上の近似文字列照合問題 9 Amirらのアイデア(KMP) 26 編集距離 10 我々の改良[DCC’98] 27 非決定オートマトンによる解法 11 Bit-parallelism[CPM’99] 28 Bit-parallelismの適用 15 実験結果(DCC&CPM--ELT) 29 基本的アイデア 14 実験結果(DCC&CPM--CPU) 30 Jumpのアイデア 17 Collage systemによる統一 31 Outputのアイデア 32 理論的結果 21 BPE圧縮法 33 実験結果 もくじ