Fast Pattern Matching Algorithms in Compressed Texts 竹田研究室 1999年 3月1日

O(テキストの長さ) 文字列照合問題とは パターン： グローバル・スタンダード テキスト： 日本経済新聞　１１月１６日　朝刊（ジュネーブ発　西山　章宏） スイスの保養地、ダヴォス・プラッツで１１月１０日から１１月１４まで、行われた、世界知覚認識学会（ミシェル・ポーター会長）で、北海道大学医学部の斉藤信（まこと）教授が提唱した、痛みを表す「hanage」と言う単位を、世界で共通の単位とする事が承認された。本来、痛みは、個人差が大きく、同じ刺激でも主観によって感じ方が異なるため、客観的に数値で表すことは、不可能であると思われていた。しかし、斉藤教授は、「鼻の粘膜は、人体の中で一番個人差が小さい。」事に注目し研究を進めた結果、１センチの鼻毛を、１Ｎ（ニュートン）の力で、引っ張る時に生じる痛みを、１hanageと定義出来ることを発見し、そして今学会で単位として承認された。 斉藤教授によると、足の小指を角にぶつけたときの痛みは、２～３Ｋhanage（キロハナゲ）、お産の時の痛みは２．５～３．２Ｍhanage（メガハナゲ）になるのだそうだ。「痛みを数値で表すことにより、正確な治療に役立つ。」（斉藤教授）そうで、今回の発見は、大変画期的だそうだ。「日本人の提唱する単位が、世界で認められるのは、非常に珍しい。」（京都大学　横田昌平教授）そうで、日本発の「グローバル・スタンダード」は、驚きをもって迎えられている。 テキスト： Knuth-Morris-Pratt 法 (1974) Boyer-Moore 法 (1977) Aho-Corasick 法 (1975) Uratani-Takeda 法 (1992) Shift-And 法 (1987) O(テキストの長さ) 523文字目 グローバル・スタンダード 文字列照合問題

圧縮テキストに対する文字列照合 展開 文字列照合 文字列照合 523文字目 日本経済新聞 １１月１６日 朝刊（ジュネーブ発 西山 章宏） aldoghqu3850pcxps;lafdjaeqw09bjzpafq05^@62:vzZIAPF’(90rwDEVcx0832nkvl;pzp99OPF:eDfja 圧縮文字列照合問題 圧縮テキストに対する文字列照合 日本経済新聞　１１月１６日　朝刊（ジュネーブ発　西山　章宏） スイスの保養地、ダヴォス・プラッツで１１月１０日から１１月１４まで、行われた、世界知覚認識学会（ミシェル・ポーター会長）で、北海道大学医学部の斉藤信（まこと）教授が提唱した、痛みを表す「hanage」と言う単位を、世界で共通の単位とする事が承認された。本来、痛みは、個人差が大きく、同じ刺激でも主観によって感じ方が異なるため、客観的に数値で表すことは、不可能であると思われていた。しかし、斉藤教授は、「鼻の粘膜は、人体の中で一番個人差が小さい。」事に注目し研究を進めた結果、１センチの鼻毛を、１Ｎ（ニュートン）の力で、引っ張る時に生じる痛みを、１hanageと定義出来ることを発見し、そして今学会で単位として承認された。 斉藤教授によると、足の小指を角にぶつけたときの痛みは、２～３Ｋhanage（キロハナゲ）、お産の時の痛みは２．５～３．２Ｍhanage（メガハナゲ）になるのだそうだ。「痛みを数値で表すことにより、正確な治療に役立つ。」（斉藤教授）そうで、今回の発見は、大変画期的だそうだ。「日本人の提唱する単位が、世界で認められるのは、非常に珍しい。」（京都大学　横田昌平教授）そうで、日本発の「グローバル・スタンダード」は、驚きをもって迎えられている。 展開 文字列照合 ・・・本来、痛みは、個人差が大きく、同じ刺激でも主観によって感じ方が異なるため、客観的に数値で表すことは、不可能であると思われていた。しかし、斉藤教授は、「鼻の粘膜は、人体の中で一番個人差が小さい。」事に注目し研究を進めた結果、１センチの鼻毛・・・・ 文字列照合 523文字目 圧縮文字列照合問題

これまでの研究 年 研究者 圧縮法 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 1998 Shibata byte pair encoding 圧縮文字列照合におけるこれまでの研究

提案アルゴリズム 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)時間 いくつかの拡張が可能 本論文の内容

(Unix の compress コマンド、 GIF形式の画像圧縮など) Lempel-Ziv-Welch 圧縮法 (Unix の compress コマンド、 GIF形式の画像圧縮など) aba 6 a b ab ab ba b c aba bc abab テキスト: 圧縮されたテキスト: 1 2 3 4 5 6 9 11 辞書木 b a c 1 2 3 4 5 6 7 9 8 12 10 11 辞書木に登録 されている文字列 の集合 D O( 圧縮テキストの長さ ) LZW圧縮法

Prefix, Suffix, Substring 接頭辞、接尾辞、部分文字列 接頭辞(prefix)、接尾辞(suffix)、部分文字列(substring)とは ある文字列 w に対して、 w = xyz a b a b b 接頭辞 prefix 接尾辞 suffix 部分文字列 substring a b a b a b a a b b b b b b a b Prefix, Suffix, Substring

Multiple Pattern Matching in LZW Compressed Texts 複数パターン照合アルゴリズム それではこのLZ77圧縮テキストに対するパターンマッチングアルゴリズムの説明に入ります。

Multiple pattern matching in LZW compression 提案アルゴリズム1 ［Mico-M］ Multiple pattern matching in LZW compression Aho-Corasick（AC）照合機械を模倣することにより、複数パターンを同時に探索することが可能 前処理にO(m2 +|Σ|)時間、 O(m2 +|Σ|)領域使用 任意の個数のパターンについて、O(n+r)時間で圧縮テキストを走査し、すべての出現位置を報告する アルゴリズム[Mico-M]

1 2 3 4 3 4 5 1 abababba a b c O(m) aba aba bb ababb Aho-Corasick(AC)照合機械 パターンの集合：Π={aba, ababb, abca, bb} a 1 2 3 4 5 6 7 9 8 b c {bb} {abca} {aba} {ababb, bb} : goto 関数 : failure 関数 { } : output O(m) 状態： 1 2 3 4 3 4 5 1 テキスト： abababba output: aba aba bb ababb AC照合機械

1 1 2 3 4 5 2 4 4 1 abababba a b c 1 2 4 4 5 aba bb ababb aba Aho-Corasick(AC)照合機械 パターンの集合：Π={aba, ababb, abca, bb} a 1 2 3 4 5 6 7 9 8 b c {bb} {abca} {aba} {ababb, bb} : goto 関数 : failure 関数 { } : output 状態： 1 1 2 3 4 5 2 4 4 1 テキスト： abababba 1 2 4 4 5 圧縮テキスト： aba bb ababb output: aba 提案アルゴリズムの動き

O(m2 + |D|) O(m×|D|×|Π|) O(m×|D|) アルゴリズムのアイデア 関数 Jump(q, u) ： 文字列 u に対応する遷移の連続をO(1)時間で模倣する O(m2 + |D|) O(m×|D|×|Π|) O(m×|D|) 定義域はQ×D AC照合機械の状態を返す 関数 Output(q, u) ： 状態 q に対応する文字列と u を連結した文字列中に現れるパターンの出現位置をO(r)時間報告する 定義域はQ×D パターンの集合を返す -- JumpとOutput

O(m3) O(|D|) 関数 Jump(q, u) δ( q , u) uはパターンの部分文字列 Jump(q, u) = δ(ε, u) それ以外 O(|D|) 関数Jump

Ancestor(N1(q, u ), | u |－|u|) 関数 Jump(q, u) O(m2) O(m2) uはパターンの部分文字列 Ancestor(N1(q, u ), | u |－|u|) ＾ － Jump(q, u) = δ(ε, u) それ以外 O(|D|) -- m2での実現方法

：uの接頭辞でかつパターンの接尾辞である最長の文字列 関数 Output(q, u) u ~ ：uの接頭辞でかつパターンの接尾辞である最長の文字列 A(u) =｛〈i,π〉|π∈Π, |u|< i <|u|, |π|< i, and u[i－|π|+1...i ]=π｝ ~ Output(q, u) = Output(q, u ) ∪ A(u) ~ O(m2) O(|D|) q u π1 π2 ~ 関数Output

Multiple pattern matching in LZW compression 提案アルゴリズム1 ［Mico-M］ Multiple pattern matching in LZW compression Aho-Corasick（AC）照合機械を模倣することにより、複数パターンを同時に探索することが可能 前処理にO(m2 +|Σ|)時間、 O(m2 +|Σ|)領域使用 任意の個数のパターンについて、O(n+r)時間で圧縮テキストを走査し、すべての出現位置を報告する アルゴリズム[Mico-M]

Shift-And approach to pattern matching in LZW Compressed Texts

Shift-And approach to pattern matching in LZW compression 提案アルゴリズム2 ［Mico-S］ Shift-And approach to pattern matching in LZW compression 高速な文字列照合アルゴリズムとして知られるShift-And法を模倣する 前処理にO(m+|Σ|)時間、O(m+|Σ|)領域使用 一つのパターンについて、O(n+r)時間で圧縮テキストを走査し、すべての出現位置を報告する 拡張性に優れている 一般化されたパターンに対する文字列照合 k個のミスマッチを許した文字列照合 複数パターンへの対応 アルゴリズム[Mico-S]

Shift-And法 aabac aabaacaabacab テキスト:= パターン:= abc 1 a b c 1 & a b c 1 1 マスクビット列 a b c 1 & a b c 1 1 1 a b c 1 1 1 1 Shift-And法

Shift-And法 aabac Jump! Jump! パターン:= テキスト:= a aabaacaabacab a b a c b マスクビット テキスト:= a aabaacaabacab a b a c b abc a b c 1 1 1 1 1 1 Jump! Jump! アルゴリズムのアイデア

O(|D|) O(1) 関数 Jump S∈{1,・・・, m} • M(a) = { 1< i < m |π[i] = a } 任意の a ∈Σ, u ∈Σ*, S∈{1,・・・, m} • について 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) 関数Jump

O(|D|) q u 関数 Output(S, u) Output(S, u) = { 1 < j < |u| | m∈S } 定義： Output(S, u) = { 1 < j < |u| | m∈S } U(u) = {1 < j < |u| | i < m and u[1..i]=π[m-i+1..m]} 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 π π 関数Output

Shift-And approach to pattern matching in LZW compression 提案アルゴリズム2 ［Mico-S］ Shift-And approach to pattern matching in LZW compression 高速な文字列照合アルゴリズムとして知られるShift-And法を模倣する 前処理にO(m+|Σ|)時間、O(m+|Σ|)領域使用 一つのパターンについて、O(n+r)時間で圧縮テキストを走査し、すべての出現位置を報告する 拡張性に優れている 一般化されたパターンに対する文字列照合 k個のミスマッチを許した文字列照合 複数パターンへの対応 アルゴリズム[Mico-S]

Experiment 実験 それではこのLZ77圧縮テキストに対するパターンマッチングアルゴリズムの説明に入ります。

実験環境： SunSPARCstation 20 圧縮テキストを展開しながらShift-And法 1: 提案アルゴリズム1［Mico-M］を用いる 2: 提案アルゴリズム2［Mico-S］を用いる 3: 原テキストに対してShift-And法 4: 実験テキスト：　Brown corpus 非圧縮時： 6.8Mb 圧縮時： 3.4Mb 実験環境：　SunSPARCstation 20 実験方法：　テキストの走査時間を30回計測し、 その平均を計算 実験

実験の結果 方法 応答時間（秒） CPU時間（秒） 展開しながらShift- And法で照合 6.554 3.373 Mico-Mで照合 6.130 2.914 Mico-Sで照合 5.400 2.241 原テキストをShift- And法で照合 11.425 0.699 実験の結果(テキスト走査時間)

まとめ LZW圧縮テキストを展開せずに文字列照合を行うアルゴリズムを提案した AC照合機械を模倣 Shift-And 法を模倣 提案アルゴリズムは、圧縮テキストを展開してから文字列照合するアルゴリズムよりも高速であることを示した まとめ

本研究の今後の展望 近似文字列照合が行えるアルゴリズムの開発 正規表現が扱えるアルゴリズムの開発 高速な文字列照合を可能とする圧縮技術の開発 圧縮率が良い, 圧縮・展開速度が早い 文字列照合が高速に行える, etc.. 今後の展望

2 文字列照合問題 圧縮文字列照合問題 圧縮文字列照合におけるこれまでの研究 本論文の内容 LZW圧縮法 Prefix, Suffix, Substring アルゴリズム[Mico-M] 　AC照合機械 　提案アルゴリズムの動き 　　-- JumpとOutput 　関数Jump 　　-- m2での実現方法 　関数Output 3 4 5 6 7 9 18 アルゴリズム[Mico-S] 　Shift-And法 　アルゴリズムのアイデア 　関数Jump 　関数Output 実験 　実験の結果(テキスト走査時間) まとめ 今後の展望 10 19 11 20 12 21 13 22 14 15 25 26 27 28 さくいん