ｽﾗｲﾄﾞﾀｲﾄﾙなし

LZW 圧縮テキストに対する
高速文字列照合アルゴリズム
喜田拓也竹田正幸篠原歩
九州大学大学院システム情報科学研究科
はじめに
• 文字列照合問題 (Pattern Matching Problem)
パターン :
ヲトコ
テキスト : ヲモイコンダラシレンノミチヲイクガヲトコノ・・・
Knuth-Morris-Pratt 法 (1974)
Boyer-Moore 法 (1977)
Aho-Corasick 法 (1975)
Uratani-Takeda 法 (1992)
・
・
・
O( テキストの長さ + パターンの長さ )
目的
文書ファイル群
起動実験「やります。僕が乗ります」「起
動確率は0.0000000001%」セントラルドグ
マ「初号機、完全に沈黙」せめて、人間ら
しく「僕はもうエヴァには乗りません」覚醒
強迫観念「ダメなのね・・・もう」シンクロ率
400%「逃げちゃだめだ、逃げちゃだめ
だ・・・」アンビリカルケーブル断線「活動限
界まで4分53秒」「私には他に何もないも
の・・・」ヤシマ作戦決戦、第3新東京市
「あんたバカァ」セカンドインパクト「私達は
選ぶ余裕なんてないのよ。生き残るため
の手段をね」強羅絶対防衛線完璧なユニ
ゾン「命令があればそうするわ」自己修復
中ジェリコの壁人類補完計画「とれない
や。血の匂い」「帰れ！」ディラックの海
「駄目です。停止信号受け付けません」
「歌はいいねぇ。リリスの生み出した文化
目的
圧縮文書ファイル群
aldoghqu385
0pcxps;lafd
jaeqw09bjz
pafq05^@62:
z9
0rwDEVcx083
2nkl;pzp9
9O:eDfja
Previous studies
year
researcher
1988 Eliam-Tsoreff and Vishkin
1992 Amir, Landau, and Vishkin
1992 Amir and Benson
1995
1996
1996
1997
1997
compression method
run-length
two-dimensional
run-length
two-dimensional
run-length
Farach and Thorup
LZ77
Gasieniec, et al.
LZ77
Amir, Benson and Farach
LZW
Karpinski, et al.
straight-line programs
Miyazaki, Takeda, Shinohara straight-line programs
Kida, Takeda, Shinohara,
1998 Miyazaki, Arikawa
LZW
Lempel-Ziv-Welch 圧縮法
(Unix の compress コマンド、 GIF形式の画像圧縮など)
テキスト:
a b ab ab ba b c aba bc abab
圧縮されたテキスト: 1 2 4
4
5 23
O(辞書木の大きさ)
4
O( 圧縮テキストの長さ )
5
a
b b
6
7
b
11
2
11
c
b
a
b
9
0
a
1
6
3
c
9
10
a
8
a
12
辞書木: D
アルゴリズムの概要
(KMP法による文字列照合の場合)
パターン : ヲトコ
テキスト : ヲモイコンダラシレンノミチヲイクガヲトコノ・・・
探索の状態
0
ヲ
1
ト
2
コ
3
1. テキストから文字を読み込む。
2. 状態を更新する。
3. パターンが出現したかどうかを判断する。
4. 「1.」へ戻る。
アルゴリズムの概要
(LZW圧縮されたテキスト上の文字列照合の場合)
パターン : ヲトコ
テキスト : ヲモイコンダラシレンノミチヲイクガヲトコノ・・・
探索の状態
0
ヲ
1
ト
2
コ
3
1. 圧縮テキストから数字（文字列）を読み込む。
2. 辞書木と状態を更新する。
3. パターンが出現したかどうかを判断する。
4. 「1.」へ戻る。
アルゴリズムの概要
(LZW圧縮されたテキスト上の文字列照合の場合)
探索の状態
0
ヲ
1
ト
2
コ
3
・・・ヲトコノドコンジヨウ・・・
状態: 2
状態: 0
パターンの出現を検知する関数が必要
Output( 現在の状態, 圧縮テキストの整数一個 )
O(とりうる状態の個数×辞書木の大きさ)
O(辞書木の大きさ)
実験の結果
CPU time (s)
T. Kida, M. Takeda, A Shinohara, M.miyazaki, and S. Arikawa.
Multiple pattern matching in LZW compressed text. In J. A. Atorer and M. Cohn eds.,
Proceedings of Data Compression Conference ’98, pp. 103-112.
IEEE Computer Society, March 1998
テキストを一時ファイルに展開後検索
30
25
テキストを展開しながら検索
20
15
10
テキストを展開せずに検索
5
0
0
5
10
15
20
25
Occurrence rate ( % )
(number of pattern occurrences / original text length)
Shift-And 法
(Abrahamson 1987, Wu-Manber 1992)
パターン:= a a b a c
マスクビット
テキスト:= aabaacaabacab
a
a
b
a
c
1
0
0
0
0
1
1
0
0
0
0
0
1
0
0
0
0
1
0
0
1
0
0
1
0
1
1
0
0
0
0
0
0
0
0
1
1
0
1
0 &0
1
1
0
0
1
0
0
0
0
1
1
0
0
0
0
0
1
0
0
1
0
0
1
0
1
0
0
1
0
0
0
0
0
1
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
O( テキスト長 )
で照合可能
実験の結果（テキスト約 6.5Mb, 圧縮時約 3.4Mb）
CPU時間(s)
(Shift-And 法を利用したアルゴリズム)
展開後Shift-And法
4.0
3.5
Kida, et al. 1998
3.0
2.5
2.0
1.5
今回のアルゴリズム
1.0
0.5
Sun SPARCstation20
0
0.000 0.001 0.014 0.066 0.151 0.498 1.460
パターンの出現回数（出現 / テキスト長） (%)
まとめ
• 提案アルゴリズムの計算量
– O(圧縮テキストの長さ+パターンの長さ+出現回数) 時間
– O( 辞書木の大きさ ) 領域
• 展開後検索を行うよりも約 1.5 倍高速である。
またAho-Corasick法を利用したアルゴリズムより 1.3
倍高速である。
• 一般化した文字列照合問題やミスマッチを許した文字
列照合も扱うことができる。
今後の課題
• 近似(文字の挿入・削除・置換を許す)文字列照合への対応
1 NATTO
2
例: NATO
GTO NAGOYA
1
KATO
3
一般化された文字列照合問題
Σ を文字の有限集合, Δ= { X ⊆Σ| X ≠φ} とする。
パターン P = X1 ... Xm (Xi ∈Δ) と
テキスト T = T [1 : n] が与えられたとき、
T [ j : j+m-1 ] ⊆ P となるような j を求めよ。
例: (a+b)cde(f+g+h)i
092-627-72XX ( X は 0～9 の数字 )
＊＊えもん ( ＊は任意の文字 )
ミスマッチを許した文字列照合
パターン文字列のうち、 k 個以下の文字が
置き換わった文字列もパターンと一致する
とみなした検索。
例:
Pattern : ムーミン, k = 1 とした場合
正
誤
ユーミン
ノーミン
ムーラン
ラーメン
ローソン
ノーシン

Download Report