喜田 拓也，竹田 正幸，篠原 歩 九州大学大学院システム情報科学府 情報理学専攻 圧縮テキスト上の近似文字列照合問題 喜田 拓也，竹田 正幸，篠原 歩 九州大学大学院システム情報科学府 情報理学専攻 発表者：竹田研究室 博士課程３年　喜田 拓也

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

圧縮テキストに対する文字列照合問題 目標２ 目標１ 復号 文字列照合 アルゴリズム 転送 文字列照合 アルゴリズム 転送 転送 二次記憶装置上 テキスト データ 主記憶装置上 文字列照合 アルゴリズム 転送 目標１ 二次記憶装置上 圧縮テキスト 主記憶装置上 文字列照合 アルゴリズム 復号 転送 主記憶装置上 二次記憶装置上 圧縮テキスト 転送 主記憶装置上 圧縮文字列照合 アルゴリズム

本分野における研究 圧縮方法 照合アルゴリズム Run-length Eilam-Tzoreff & Vishkin (1988) 圧縮方法 照合アルゴリズム Run-length Eilam-Tzoreff & Vishkin (1988) Run-length (two dim) Amir et al. (1992, 1997); Amir & Benson (1992) LZ77 family Farach & Thorup (1995); Gąsieniec, et al. (1996); Klein & Shapira (2000) LZ78 family Amir et al. (1996); Kida et al. (1998, 1999); Navarro & Tarhio (2000); Kärkkäinen et al. (2000); LZ family Navarro et al. (1999) Straight-line programs Karpinski et al. (1997); Miyazaki et al. (1997); Hirao et al. (2000) Huffman Fukamachi et al. (1998); Klein & Shapira (2001); Miyazaki et al. (1998) Finite state encoding Takeda (1997) Word based encoding Moura et al. (1998) Pattern substitution Manber (1994); Shibata et al. (1998) Antidictionary based Shibata et al. (1999)

実験結果（非圧縮テキスト上のアルゴリズムとの対比） パタンの長さ 0.0 0.3 0.4 0.5 0.8 0.1 0.2 0.6 0.7 CPU時間（秒） AlphaStation XP1000 (Alpha21264: 667MHz) Tru64 UNIX V4.0F Medline（英文テキスト） 60.3Mbyte 世界最高速 非圧縮テキストをKMPで照合 BPE圧縮テキストに対する Boyer-Moore型のアルゴリズム を用いた照合（Shibataら[2000]） BPE圧縮テキストに対する照合 非圧縮テキストをAgrepで照合 5 10 15 20 25 30 * BPEはByte Pair Encoding圧縮法 * KMPはKnuth-Morris-Pratt法 * AgrepはWu&Manberが開発した検索ツール

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

近似文字列照合問題 MARRIAGE MASS AGE テキスト中のパタンとの編集距離が k 以内の文字列の出現を求める問題 編集距離 文字列 x に文字の挿入・削除・置換の操作を施して文字列 y へ変換するために要する最小操作回数 d MARRIAGE MASSAGE CARRIAGE d=1 MARRIAGE MASS AGE 削除 置換 k=2 d=3

近似文字列照合アルゴリズム 動的計画法 オートマトンに基づく手法 ビットパラレル手法 フィルタリング手法 L はマシン依存 Sellers (1980) O(mN) 時間 O(m) 領域 Ukkonen (1985) 平均O(kN) 時間 O(m) 領域 オートマトンに基づく手法 Ukkonen (1985) O( min(3m, m(2m||)k) ) 個の状態数 ビットパラレル手法 Wu & Manber (1992) O( k m/L N) 時間領域 Baeza-Yates & Navarro (1996) O( k(m-k)/L N) 時間領域 Myers (1998) O( m/L N) 時間領域 フィルタリング手法 Wu and Manber (1992) L はマシン依存 N はテキストの長さ m はパタンの長さ k は許容するエラーの数 詳しい人 G. Navarro A Guided Tour to Approximate String Matching ACM Computing Surveys, 33(1):31-88,2001

圧縮テキスト上の近似文字列照合 Kärkkäinenら(2000)のアルゴリズム 提案アルゴリズム r はパタンの出現個数 動的計画法を使った近似文字列照合アルゴリズムに基づく 最悪時 O(mkn+r ) 時間、平均 O(k2n+r ) 時間 LZ78圧縮テキスト上で動作 提案アルゴリズム 非決定性オートマトンの動作をビットパラレル手法で模倣するBaeza-Yates & Navarro (1999) のアルゴリズムを拡張 最悪時 O(mk3n / L) 時間 制限されたCollage system上で動作 → LZ78/LZW上で動作 n は圧縮テキストの長さ m はパタンの長さ r はパタンの出現個数

LZW圧縮法に対する実験結果 CPU時間（秒） 許容される最大の編集距離 k 10 20 30 1 2 3 4 5 40 50 60 70 10 20 30 1 2 3 4 5 許容される最大の編集距離 k CPU時間（秒） 40 50 60 70 80 Intel Pentium III 550MHz (RAM: 64Mb; Linux) Wall Street Journal の記事（英文テキスト）10Mbyte パタンの長さ＝10 提案アルゴリズム Kärkkäinenらのアルゴリズム 復号後に[Myers98]で照合

圧縮テキストに対する近似文字列照合の高速化 フィルタリング手法（Filtration technique; Wu and Manber, 1992） パタンを k+1 個の小片に分割 各小片を複数パタン文字列照合アルゴリズムで照合 小片が出現した近辺を通常用いられる近似文字列照合アルゴリズムを用いて検査 テキスト: ACCCTGTTTAGATCACGGCACTACTGTAAAC 分割後の小片: TAAAT, CACGG, CATACT k = 2 の場合 パタン: TAAATCACGGCATACT 圧縮テキストに対してフィルタリング手法を適用 圧縮テキスト上の複数パタン文字列照合アルゴリズムが必要 圧縮テキストを部分的に復号する必要がある

圧縮テキスト上の複数パタン照合アルゴリズム

圧縮テキスト上の複数パタン照合アルゴリズム Aho-Corasick型 T. Kida, M. Takeda, A. Shinohara, M. Miyazaki, and S. Arikawa, Multiple pattern matching in LZW compressed text. LZW圧縮テキスト上で動作 O(m2+n+r) 時間，o(m2+n) 領域 Boyer-Moore型 G. Navarro and J. Tarhio, Boyer-Moore string matching over Ziv-Lempel compressed text. Y. Shibata, T. Matsumoto, M. Takeda, A. Shinohara, and S. Arikawa, A Boyer-Moore type algorithm for compressed pattern matching. ビットパラレル型 G. Navarro and M. Raffinot, A general practical approach to pattern matching over Ziv-Lempel compressed text. T. Kida, M. Takeda, A. Shinohara, M. Miyazaki, and S. Arikawa, Shift-And approach to pattern matching in LZW compressed text.

LZW圧縮法における実験結果 CPU時間（秒） 許容される最大の編集距離 k 1 2 3 4 5 6 7 Intel Pentium III 550MHz (RAM: 64Mb; Linux) Wall Street Journal の記事（英文テキスト）10Mbyte パタンの長さ＝10 復号後にフィルタリング手法で照合 復号後に[Myers98]で照合 圧縮テキストにフィルタリング/AC 圧縮テキストにフィルタリング/BM 圧縮テキストにフィルタリング/BP * ACはAho-Corasick型の圧縮テキスト上の 　複数パタン文字列照合アルゴリズム * BPはBit-parallel型のアルゴリズム[Navarro+99] * BMはBoyer-Moore型のアルゴリズム[Navarro+00]

LZW圧縮法における実験結果 CPU時間（秒） 許容される最大の編集距離 k 7 6 5 4 3 2 1 1 5 10 15 圧縮テキストにフィルタリング/AC 6 復号後にフィルタリング手法で照合 5 圧縮テキストにフィルタリング/BM 圧縮テキストにフィルタリング/BP CPU時間（秒） 4 復号後に[Myers98]で照合 3 2 Intel Pentium III 550MHz (RAM: 64Mb; Linux) Wall Street Journal の記事（英文テキスト）10Mbyte パタンの長さ＝30 1 1 5 10 15 許容される最大の編集距離 k

LZW圧縮法における実験結果 CPU時間（秒） 許容される最大の編集距離 k 8 7 6 5 4 3 2 1 1 5 10 15 Intel Pentium III 550MHz (RAM: 64Mb; Linux) DNA塩基配列　10Mbyte パタンの長さ＝30 7 6 5 CPU時間（秒） 圧縮テキストにフィルタリング/BM 4 復号後にフィルタリング手法で照合 3 復号後に[Myers98]で照合 2 圧縮テキストにフィルタリング/AC 1 圧縮テキストにフィルタリング/BP 1 5 10 15 * ACはAho-Corasick型の圧縮テキスト上の 　複数パタン文字列照合アルゴリズム 許容される最大の編集距離 k * BPはBit-parallel型のアルゴリズム[Navarro+99] * BMはBoyer-Moore型のアルゴリズム[Navarro+00]

まとめ