Fast Pattern Matching Algorithms in Compressed Texts 竹田研究室 1999年 3月1日 文字列照合問題とは パターン: グローバル・スタンダード テキスト: 日本経済新聞 11月16日 朝刊(ジュネーブ発 西山 章宏) スイスの保養地、ダヴォス・プラッツで11月10日から11月14まで、行われ た、世界知覚認識学会(ミシェル・ポーター会長)で、北海道大学医学部の斉 Knuth-Morris-Pratt 法 (1974) 藤信(まこと)教授が提唱した、痛みを表す「hanage」と言う単位を、世界で共 通の単位とする事が承認された。本来、痛みは、個人差が大きく、同じ刺激で Boyer-Moore 法 (1977) も主観によって感じ方が異なるため、客観的に数値で表すことは、不可能で あると思われていた。しかし、斉藤教授は、「鼻の粘膜は、人体の中で一番個 Aho-Corasick 法 (1975) 人差が小さい。」事に注目し研究を進めた結果、1センチの鼻毛を、1N (ニュートン)の力で、引っ張る時に生じる痛みを、1hanageと定義出来ること Shift-And 法 (1987) を発見し、そして今学会で単位として承認された。 斉藤教授によると、足の小指を角にぶつけたときの痛みは、2~3Khanage Uratani-Takeda 法 (1992) (キロハナゲ)、お産の時の痛みは2.5~3.2Mhanage(メガハナゲ)になる テキストの長さ のだそうだ。「痛みを数値で表すことにより、正確な治療に役立つ。」(斉藤教 授)そうで、今回の発見は、大変画期的だそうだ。「日本人の提唱する単位が、 523文字目 世界で認められるのは、非常に珍しい。」(京都大学 横田昌平教授)そうで、 グローバル・スタンダード 日本発の「グローバル・スタンダード」は、驚きをもって迎えられている。 O( - 2 / 28 - ) 文字列照合問題 圧縮テキストに対する文字列照合 aldoghqu3850pc xps;lafdjaeqw0 9bjzpafq05^@62 z90w DEVcx0832nkl; pzp99OeDfj 日本経済新聞 11月16日 朝刊(ジュネーブ発 西山 章宏) a 展開 スイスの保養地、ダヴォス・プラッツで11月10日から11月14まで、行われ た、世界知覚認識学会(ミシェル・ポーター会長)で、北海道大学医学部の斉 藤信(まこと)教授が提唱した、痛みを表す「hanage」と言う単位を、世界で共 通の単位とする事が承認された。本来、痛みは、個人差が大きく、同じ刺激で ・・・本来、痛みは、個人差が大きく、同じ刺激 も主観によって感じ方が異なるため、客観的に数値で表すことは、不可能で でも主観によって感じ方が異なるため、客観 あると思われていた。しかし、斉藤教授は、「鼻の粘膜は、人体の中で一番個 的に数値で表すことは、不可能であると思わ 人差が小さい。」事に注目し研究を進めた結果、1センチの鼻毛を、1N れていた。しかし、斉藤教授は、「鼻の粘膜は、 (ニュートン)の力で、引っ張る時に生じる痛みを、1hanageと定義出来ること 人体の中で一番個人差が小さい。」事に注目 し研究を進めた結果、1センチの鼻毛・・・・ を発見し、そして今学会で単位として承認された。 斉藤教授によると、足の小指を角にぶつけたときの痛みは、2~3Khanage (キロハナゲ)、お産の時の痛みは2.5~3.2Mhanage(メガハナゲ)になる のだそうだ。「痛みを数値で表すことにより、正確な治療に役立つ。」(斉藤教 授)そうで、今回の発見は、大変画期的だそうだ。「日本人の提唱する単位が、 世界で認められるのは、非常に珍しい。」(京都大学 横田昌平教授)そうで、 523文字目 日本発の「グローバル・スタンダード」は、驚きをもって迎えられている。 文字列照合 文字列照合 - 3 / 28 - 圧縮文字列照合問題 これまでの研究 年 研究者 圧縮法 1988 1992 1992 1994 1994 1995 1996 1996 1997 1997 Eliam-Tsoreff and Vishkin Amir, Landau, and Vishkin Amir and Benson Amir, Benson, and Farach Manber Farach and Thorup Gasieniec, et al. Amir, Benson and Farach Karpinski, Rytter, and Shinohara run-length two-dimensional run-length two-dimensional run-length two-dimensional run-length Miyazaki, Shinohara, and Takeda 1997 Takeda 1998 Fukamachi, Shinohara, and Takeda 1998 Kida, et al. 1998 Shibata original compression scheme LZ77 LZ77 LZW straight-line programs straight-line programs finite state encoding Huffman encoding LZW byte pair encoding - 4 / 28 - 圧縮文字列照合におけるこれまでの研究 提案アルゴリズム • Multiple pattern matching in LZW compression (複数パターンを扱うことのできる圧縮文字列照合アルゴリズム) – 複数パターンを同時に検索可能 – パターンの出現位置をすべて報告 – O(n+m2 +|Σ|)領域、O(n+m2+|Σ|+r)時間 • Shift-And approach to pattern matching in LZW compression (高速Shift-And法を利用した圧縮文字列照合アルゴリズム) – パターンの出現位置を全て報告 – O(n+m+|Σ|)領域、 O(n+m+|Σ|+r)時間 – いくつかの拡張が可能 - 5 / 28 - 本論文の内容 Lempel-Ziv-Welch 圧縮法 (Unix の compress コマンド、 GIF形式の画像圧縮など) テキスト: a b ab ab ba b c aba bc abab 圧縮されたテキスト: 1 2 4 0 a 1 a b 4 5 a b b 6 7 b 11 3 c 9 a 10 a 8 5 23 c b 2 4 6 9 11 辞書木に登録 されている文字列 の集合 D 12 O( 圧縮テキストの長さ ) 辞書木 - 6 / 28 - LZW圧縮法 接頭辞、接尾辞、部分文字列 接頭辞(prefix)、接尾辞(suffix)、部分文字列(substring)とは ある文字列 w に対して、 ababb w = xyz 接尾辞 suffix 接頭辞 prefix 部分文字列 substring abab ab a ab bab - 7 / 28 - abb bb b Prefix, Suffix, Substring Multiple Pattern Matching in LZW Compressed Texts LZW圧縮テキストに対する 複数パターン照合アルゴリズム 提案アルゴリズム1 [Mico-M] Multiple pattern matching in LZW compression • Aho-Corasick(AC)照合機械を模倣すること により、複数パターンを同時に探索すること が可能 • 前処理にO(m2 +|Σ|)時間、 O(m2 +|Σ|)領域使 用 • 任意の個数のパターンについて、O(n+r)時 間で圧縮テキストを走査し、すべての出現位 置を報告する - 9 / 28 - アルゴリズム[Mico-M] Aho-Corasick(AC)照合機械 パターンの集合:Π={aba, ababb, abca, bb} 0 a b 1 2 c b 8 b 状態: 0 テキスト: output: a b b 3 4 {aba} 6 a 9 {bb} 7 {abca} O(m) 5 {ababb, bb} : goto 関数 : failure 関数 { } : output 1 2 3 4 3 4 5 1 abababba aba aba - 10 / 28 - bb ababb AC照合機械 Aho-Corasick(AC)照合機械 パターンの集合:Π={aba, ababb, abca, bb} 0 a b 1 2 c b 8 b 状態: 0 テキスト: 圧縮テキスト: output: a b 3 4 {aba} 6 a 9 {bb} b 7 {abca} 5 {ababb, bb} : goto 関数 : failure 関数 { } : output 1 2 3 4 3 4 5 1 abababba 1 2 4 4 5 bb aba aba ababb - 11 / 28 - 提案アルゴリズムの動き アルゴリズムのアイデア 関数 Jump(q, u) : • 文字列 u に対応する遷移の連続をO(1)時間 で模倣する 2 + |D • 定義域はQ×D O(m D|)|) O(m×| • AC照合機械の状態を返す 関数 Output(q, u) : • 状態 q に対応する文字列と u を連結した文字 列中に現れるパターンの出現位置をO(r)時間 報告する • 定義域はQ×D O(m2D+|×| |D|)Π|) O(m×| • パターンの集合を返す - 12 / 28 - -- JumpとOutput 関数 Jump(q, u) O(m3) δ( q , u) uはパターンの部分文字列 δ(ε, u) それ以外 Jump(q, u) = O(|D|) - 13 / 28 - 関数Jump 関数 Jump(q, u) O(m2) Jump(q, u) = O(m2) - - ^ Ancestor(N1(q, u ), | u |-|u|) uはパターンの部分文字列 δ(ε, u) それ以外 O(|D|) - 14 / 28 - -- m2での実現方法 関数 Output(q, u) ~ u :uの接頭辞でかつパターンの接尾辞である最長の文字列 A(u) ={〈i,π〉|π∈Π, |u|< ~i <|u|, |π|< i, and u[i-|π|+1...i ]=π} ~ ) ∪ A(u) Output(q, u) = Output(q, u O(m2) u q π1 ~ u π1 π2 - 15 / 28 - O(|D|) π2 関数Output 提案アルゴリズム1 [Mico-M] Multiple pattern matching in LZW compression • Aho-Corasick(AC)照合機械を模倣すること により、複数パターンを同時に探索すること が可能 • 前処理にO(m2 +|Σ|)時間、 O(m2 +|Σ|)領域使 用 • 任意の個数のパターンについて、O(n+r)時 間で圧縮テキストを走査し、すべての出現位 置を報告する - 16 / 28 - アルゴリズム[Mico-M] Shift-And approach to pattern matching in LZW Compressed Texts LZW圧縮テキストに対する Shift-And法 提案アルゴリズム2 [Mico-S] Shift-And approach to pattern matching in LZW compression • 高速な文字列照合アルゴリズムとして知られ るShift-And法を模倣する • 前処理にO(m+|Σ|)時間、O(m+|Σ|)領域使用 • 一つのパターンについて、O(n+r)時間で圧縮 テキストを走査し、すべての出現位置を報告 する • 拡張性に優れている – 一般化されたパターンに対する文字列照合 – k個のミスマッチを許した文字列照合 – 複数パターンへの対応 - 18 / 28 - アルゴリズム[Mico-S] Shift-And法 パターン:= aabac テキスト:= aabaacaabacaba a 1 1 0 1 1 0 1 a 0 1 0 0 1 0 0 b 0 0 1 0 0 0 0 a 0 0 0 1 0 0 0 c 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 0 &0 0 1 0 0 マスクビット列 a 1 1 0 0 0 b 0 0 1 0 0 a 1 0 0 1 0 c 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 a a b a c abc 1 0 1 0 0 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 - 19 / 28 - Shift-And法 Shift-And法 パターン:= aabac テキスト:= a a b a c aaabaacaabacab a b a a c a 1 1 0 1 1 0 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 Jump! a 1 1 0 0 0 b 0 0 1 0 0 a 1 0 0 1 0 マスクビット c 0 0 0 0 1 a 1 0 0 0 0 0 0 0 0 0 abc 1 0 1 0 0 1 1 0 0 0 0 0 0 0 1 Jump! - 20 / 28 - アルゴリズムのアイデア 関数 Jump S∈{1,・・・, m} について • 任意の a ∈Σ, u ∈Σ*, M(a) = { 1< i < m |π[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) - 21 / 28 - 関数Jump 関数 Output(S, u) 定義: Output(S, u) = { 1 < j < |u| | m∈S } U(u) = {1 < j < |u| | i < m and u[1..i]=π[m-i+1..m]} O(|D|) A(u) = {1 < j < |u| | m < i and u[1-m+1..i]=π} O(|D|) Output(S, u) =((m S)∩U(u)) ∪ A(u) q u π π - 22 / 28 - 関数Output 提案アルゴリズム2 [Mico-S] Shift-And approach to pattern matching in LZW compression • 高速な文字列照合アルゴリズムとして知られ るShift-And法を模倣する • 前処理にO(m+|Σ|)時間、O(m+|Σ|)領域使用 • 一つのパターンについて、O(n+r)時間で圧縮 テキストを走査し、すべての出現位置を報告 する • 拡張性に優れている – 一般化されたパターンに対する文字列照合 – k個のミスマッチを許した文字列照合 – 複数パターンへの対応 - 23 / 28 - アルゴリズム[Mico-S] Experiment 実験 実験 1: 圧縮テキストを展開しながらShift-And法 2: 提案アルゴリズム1[Mico-M]を用いる 3: 提案アルゴリズム2[Mico-S]を用いる 4: 原テキストに対してShift-And法 実験テキスト: Brown corpus 非圧縮時: 6.8Mb 圧縮時: 3.4Mb 実験環境: SunSPARCstation 20 実験方法: テキストの走査時間を30回計測し、 その平均を計算 - 25 / 28 - 実験 実験の結果 方法 応答時間(秒) CPU時間(秒) 展開しながらShiftAnd法で照合 6.554 3.373 Mico-Mで照合 6.130 2.914 Mico-Sで照合 5.400 2.241 11.425 0.699 原テキストをShiftAnd法で照合 - 26 / 28 - 実験の結果(テキスト走査時間) まとめ • LZW圧縮テキストを展開せずに文字列照合を行 うアルゴリズムを提案した – AC照合機械を模倣 – Shift-And 法を模倣 • 提案アルゴリズムは、圧縮テキストを展開してから 文字列照合するアルゴリズムよりも高速であること を示した - 27 / 28 - まとめ 本研究の今後の展望 • 近似文字列照合が行えるアルゴリズムの開発 • 正規表現が扱えるアルゴリズムの開発 • 高速な文字列照合を可能とする圧縮技術の開発 圧縮率が良い, 圧縮・展開速度が早い 文字列照合が高速に行える, etc.. - 28 / 28 - 今後の展望 2 3 4 5 6 7 9 10 11 12 13 14 15 文字列照合問題 圧縮文字列照合問題 圧縮文字列照合におけるこれまでの研究 本論文の内容 LZW圧縮法 Prefix, Suffix, Substring アルゴリズム[Mico-M] AC照合機械 提案アルゴリズムの動き -- JumpとOutput 関数Jump -- m2での実現方法 関数Output - 38 / 28 - 18 19 20 21 22 アルゴリズム[Mico-S] Shift-And法 アルゴリズムのアイデア 関数Jump 関数Output 25 26 27 28 実験 実験の結果(テキスト走査時間) まとめ 今後の展望 さくいん
© Copyright 2024 ExpyDoc