圧縮テキスト上の近似文字列照合問題

圧縮テキスト上の近似文字列照合問題
喜田拓也，竹田正幸，篠原歩
九州大学大学院システム情報科学府情報理学専攻
発表者：竹田研究室博士課程３年喜田拓也
文字列照合問題


テキストT中に含まれるパタンの出現を求める問題
KMP法[Knuthら(1974)]， BM法[BoyerとMoore (1977)]
ビットパラレル手法[Abrahamson(1987)][Baeza-YatesとGonnet(1992)]
パタン hanage
テキストT
日本経済新聞１１月１６日朝刊（ジュネーブ発西山章宏）
スイスの保養地、ダヴォス・プラッツで１１月１０日から１１月１４まで、行われた、世
界知覚認識学会（ミシェル・ポーター会長）で、北海道大学医学部の斉藤信（まこと）
教授が提唱した、痛みを表す「hanage」と言う単位を、世界で共通の単位とする事
が承認された。本来、痛みは、個人差が大きく、同じ刺激でも主観によって感じ方が
異なるため、客観的に数値で表すことは、不可能であると思われていた。しかし、斉
藤教授は、「鼻の粘膜は、人体の中で一番個人差が小さい。」事に注目し研究を進
めた結果、１センチの鼻毛を、１Ｎ（ニュートン）の力で、引っ張る時に生じる痛みを、
１hanageと定義出来ることを発見し、そして今学会で単位として承認された。
圧縮テキストに対する文字列照合問題
目
テキスト
標
データ
文字列照合
アルゴリズム
転送
２
二次記憶装置上
主記憶装置上
圧縮テキスト
目
標転送
１
二次記憶装置上
文字列照合
アルゴリズム
復号
主記憶装置上
主記憶装置上
圧縮テキスト
転送
二次記憶装置上
主記憶装置上
圧縮文字列照合
アルゴリズム
本分野における研究
圧縮方法
照合アルゴリズム
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
Huffman
Finite state encoding
Word based encoding
Pattern substitution
Antidictionary based
実験結果（非圧縮テキスト上のアルゴリズムとの対比）
0.8
AlphaStation XP1000
(Alpha21264: 667MHz)
Tru64 UNIX V4.0F
CPU時間（秒）
0.7
Medline（英文テキスト）
60.3Mbyte
0.6
0.5
非圧縮テキストをKMPで照合
0.4
BPE圧縮テキストに対する照合
0.3
非圧縮テキストをAgrepで照合
0.2
BPE圧縮テキストに対する
Boyer-Moore型のアルゴリズム
を用いた照合（Shibataら[2000]）
0.1
0.0
5
10
15
20
25
パタンの長さ
30
* BPEはByte Pair Encoding圧縮法
* KMPはKnuth-Morris-Pratt法
* AgrepはWu&Manberが開発した検索ツール
近似文字列照合問題
CARRIAGE
MARRIAGE
MASSAGE
近似文字列照合問題


テキスト中のパタンとの編集距離が k 以内の文字列の
出現を求める問題
編集距離
 文字列 x に文字の挿入・削除・置換の操作を施して
文字列 y へ変換するために要する最小操作回数 d
CARRIAGE
d=1
MARRIAGE
k=2
MARRIAGE
置換
MASSAGE
d=3
削除
MASS AGE
近似文字列照合アルゴリズム

動的計画法



オートマトンに基づく手法


Ukkonen (1985) O( min(3m, m(2m||)k) ) 個の状態数
ビットパラレル手法




Sellers (1980) O(mN) 時間 O(m) 領域
Ukkonen (1985)
平均O(kN) 時間 O(m) 領域
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)のアルゴリズム




動的計画法を使った近似文字列照合アルゴリズムに基づく
最悪時 O(mkn+r ) 時間、平均 O(k2n+r ) 時間
LZ78圧縮テキスト上で動作
提案アルゴリズム



非決定性オートマトンの動作をビットパラレル手法で模倣する
Baeza-Yates & Navarro (1999) のアルゴリズムを拡張
最悪時 O(mk3n / L) 時間
制限されたCollage system上で動作 → LZ78/LZW上で動作
n は圧縮テキストの長さ
m はパタンの長さ
r はパタンの出現個数
LZW圧縮法に対する実験結果
80
Intel Pentium III 550MHz
(RAM: 64Mb; Linux)
Wall Street Journal の記事
（英文テキスト）10Mbyte
パタンの長さ＝10
CPU時間（秒）
70
60
50
40
提案アルゴリズム
30
20
Kärkkäinenらのアルゴリズム
10
復号後に[Myers98]で照合
0
1
2
3
4
5
許容される最大の編集距離 k
圧縮テキストに対する近似文字列照合の高速化

フィルタリング手法（Filtration technique; Wu and Manber, 1992）



パタンを k+1 個の小片に分割
各小片を複数パタン文字列照合アルゴリズムで照合
小片が出現した近辺を通常用いられる近似文字列照合アルゴリ
ズムを用いて検査
k = 2 の場合
パタン:
TAAATCACGGCATACT
分割後の小片: TAAAT, CACGG, CATACT
テキスト:

ACCCTGTTTAGATCACGGCACTACTGTAAAC
圧縮テキストに対してフィルタリング手法を適用

圧縮テキスト上の複数パタン文字列照合アルゴリズムが必要

圧縮テキストを部分的に復号する必要がある
圧縮テキスト上の複数パタン照合アルゴリズム
圧縮テキスト上の複数パタン照合アルゴリズム

Aho-Corasick型




Boyer-Moore型



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) 領域
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圧縮法における実験結果
Intel Pentium III 550MHz
(RAM: 64Mb; Linux)
Wall Street Journal の記事
（英文テキスト）10Mbyte
パタンの長さ＝10
CPU時間（秒）
7
6
5
復号後にフィルタリング手法で照合
4
復号後に[Myers98]で照合
3
圧縮テキストにフィルタリング/AC
圧縮テキストにフィルタリング/BM
2
圧縮テキストにフィルタリング/BP
1
1
2
3
4
5
許容される最大の編集距離 k
* ACはAho-Corasick型の圧縮テキスト上の
複数パタン文字列照合アルゴリズム
* BPはBit-parallel型のアルゴリズム[Navarro+99]
* BMはBoyer-Moore型のアルゴリズム[Navarro+00]
LZW圧縮法における実験結果
CPU時間（秒）
7
圧縮テキストにフィルタリング/AC
6
復号後にフィルタリング手法で照合
5
4
圧縮テキストにフィルタリング/BM
圧縮テキストにフィルタリング/BP
3
復号後に[Myers98]で照合
2
Intel Pentium III 550MHz
(RAM: 64Mb; Linux)
Wall Street Journal の記事
（英文テキスト）10Mbyte
パタンの長さ＝30
1
0
1
5
10
15
許容される最大の編集距離 k
LZW圧縮法における実験結果
CPU時間（秒）
8
Intel Pentium III 550MHz
(RAM: 64Mb; Linux)
DNA塩基配列 10Mbyte
パタンの長さ＝30
7
6
5
圧縮テキストにフィルタリング/BM
4
復号後にフィルタリング手法で照合
3
復号後に[Myers98]で照合
2
圧縮テキストにフィルタリング/AC
1
0
圧縮テキストにフィルタリング/BP
1
5
10
15
許容される最大の編集距離 k
* ACはAho-Corasick型の圧縮テキスト上の
複数パタン文字列照合アルゴリズム
* BPはBit-parallel型のアルゴリズム[Navarro+99]
* BMはBoyer-Moore型のアルゴリズム[Navarro+00]
まとめ

Download Report