String Matching in Lempel

論文紹介
String Matching in Lempel-Ziv
Compressed Strings
Algorithmica (1998) 20: 388-404
M. Farach and M. Thorup
竹田研究室修士課程2年
喜田拓也
Preliminaries
用語の説明
用語の説明
prefix, substring, suffix
プレフィクス、サブストリング、サフィクス (あるいは前、中、後)
ある文字列 w に対して、
w = xyz
プレフィクス
サフィクス
サブストリング
用語の説明
prefix, substring, suffix
プレフィクス、サブストリング、サフィクス (あるいは前、中、後)
w = nobinobita
prefix
n
no
nobi
nobinobi
nobinobita
substring
suffix
a
i
ta
bita
nob
obita
bin
nobi bita
inobita
obinobi
nobinobita
nobinobita
用語の説明
Pattern Matching
パターンマッチング－文字列照合
existence problem
all-occurrences problem
クマクマ
TEXT: テクマクマヤコンテクマクマヤコン
Pattern: クマクマ
用語の説明
Pattern Matching
パターンマッチング－文字列照合
existence problem
all-occurrences problem
クマクマ
クマクマ
TEXT: テクマクマヤコンテクマクマヤコン
Pattern: クマクマ
用語の説明
Data Compression
データ圧縮
テキストデータ
起動実験「やります。僕が乗ります」「起動確率
は0.0000000001%」セントラルドグマ「初号機、完
全に沈黙」せめて、人間らしく「僕はもうエヴァに
は乗りません」覚醒強迫観念「ダメなのね・・・も
う」シンクロ率400%「逃げちゃだめだ、逃げちゃだ
めだ・・・」アンビリカルケーブル断線「活動限界ま
で4分53秒」「私には他に何もないもの・・・」ヤシ
マ作戦決戦、第3新東京市「あんたバカァ」セカン
ドインパクト「私達は選ぶ余裕なんてないのよ。
生き残るための手段をね」強羅絶対防衛線完璧
なユニゾン「命令があればそうするわ」自己修復
中ジェリコの壁人類補完計画「とれないや。血の
匂い」「帰れ！」ディラックの海「駄目です。停止
信号受け付けません」「歌はいいねぇ。
用語の説明
Data Compression
データ圧縮
圧縮テキストデータ
aldoghqu3850pcxps;
lafdjaeqw09bjzpaf
q05z9
0rwDEVcx083nkl;p
zp99OeDfja
Goal of this paper
論文の目的
圧縮テキストに対してパターンマッチを行うには？
論文の目的
Idea
search
元のテキストデータ
圧縮テキストデータ
起動実験「やります。僕が乗ります」「起動確率
は0.0000000001%」セントラルドグマ「初号機、完
全に沈黙」せめて、人間らしく「僕はもうエヴァに
は乗りません」覚醒強迫観念「ダメなのね・・・も
う」シンクロ率400%「逃げちゃだめだ、逃げちゃだ
めだ・・・」アンビリカルケーブル断線「活動限界ま
で4分53秒」「私には他に何もないもの・・・」ヤシ
マ作戦決戦、第3新東京市「あんたバカァ」セカン
ドインパクト「私達は選ぶ余裕なんてないのよ。
生き残るための手段をね」強羅絶対防衛線完璧
aldoghqu3850pcxps;
なユニゾン「命令があればそうするわ」自己修復
lafdjaeqw09bjzpaf
中ジェリコの壁人類補完計画「とれないや。血の
匂い」「帰れ！」ディラックの海「駄目です。停止
q05z9
信号受け付けません」「歌はいいねぇ。
0rwDEVcx083nkl;p
zp99OeDfja
論文の目的
Idea
search
圧縮テキストデータ
aldoghqu3850pcxps;
lafdjaeqw09bjzpaf
q05z9
0rwDEVcx083nkl;p
zp99OeDfja
Previous studies
year
researcher
1988 Eilam-Tsoreff and Vishkin
1992 Amir, Landau, and Vishikin
1992 Amir and Benson
論文の目的
compression method
run-length
two-dimensional
run-length
1995 Farach and Thorup
1996 Gasieniec, et al.
LZ77
LZ77
1996 Amir, Benson and Farach
LZW
1997 Karpinski, et al.
1997 Miyazaki, et al.
1998 Kida
Kida, et al.
straight-line programs
straight-line programs
LZW
LZ77 Compression
LZ77 圧縮
LZ77 圧縮
contents
圧縮テキスト Z =
C1・・・Cj・・・CM (P0 ,L1)・・・(Pi ,Li)・・・(PN ,LN)
Cj : テキストで使用される文字
（アルファベットΣ上の記号. |Σ|=M）
Pi , Li : 整数
LZ77 圧縮
example
アルファベットΣ={a,b,c}
テキスト T
=ababcababcbacabab
-3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
abc ababcababcbacabab
圧縮テキスト Z
ブロック
=abc
(-3,1) (-2,1) (0,2) (-1,1) (0,5) (1,2) (4,5)
LZ77 圧縮
useful property
テキスト中の最も左の位置に現れるパターンは、
必ずブロックとブロックの境目をまたぐ。
Pattern: b a c a
T= a b a b c a b a b c b a c a b a b
Main Algorithm
圧縮テキストに対する
文字列照合アルゴリズム
メイン
アルゴリズム
Basic Idea
テキスト中の最も左の位置に現れるパターンは、
必ずブロックとブロックの境目をまたぐ。
圧縮テキストの全てを展開せずとも、ブロックの
境界付近の文字列だけをしらべれば existence
problem を解くことができる。
メイン
アルゴリズム
Basic Idea
Pi
i 番目のブロックの prefix のうち、
パターンの substring になっている
最長のもの。
Pi
テキストの先頭から i 番目のブロックの
終端まで文字列の suffix のうち、
パターンの substring になっている
最長のもの。
ある i について、 Pi Pi+1 の substring がパターン
になっていれば「Yes」と答えることができる。
メイン
アルゴリズム
Basic Idea
Pattern: b a c a
Pi
Pi+1
・・・a b c c b c b a c a c a c b a b・・・
i 番目のブロック
i+1 番目のブロック
Pi Pi+1 = b a c a c a
メイン
アルゴリズム
Winding Phase
0
1
0
1
2
2
3
3
4
4
4
5 5
5
5
6
6
6
7
7
T =a b a b c a b a b c b a c a b a b b c a b
メイン
アルゴリズム
Winding Phase
abc
0
1
0
1
7
2
2
3
3
4
7
4
5
5
6
6
7
7
メイン
アルゴリズム
Winding Phase
6
abc
0
1
0
1
7
2
2
3
3
4
7
6
4
5
5
メイン
アルゴリズム
Winding Phase
5
abc
6
0
1
5
7
0
1
2
2
3
3
4
7
6
4
メイン
アルゴリズム
Winding Phase
abc
4
7
5
0
1
0
1
4
6
6
5
7
2
2
3
3
メイン
アルゴリズム
Winding Phase
4
6
4
7
5
3
3
0
1
5
7
0
1
2
2
abc
6
メイン
アルゴリズム
Winding Phase
6
7
5
4
2
6
4
2
7
5
3
3
0
1
0
1
abc
メイン
アルゴリズム
Winding Phase
6
7
2
7
5
1
1
5
4
2
6
4
3
3
0
abc
0
メイン
アルゴリズム
Winding Phase
6
7
5
4
2
7
5
0
1
0
1
2
4
6
3
3
abc ababcababcbacababbcab
Pattern: c a = Pi Pi+1
4
3
4
2
0
i=3
メイン
アルゴリズム
Unwinding Phase
Winding の手順をそのまま逆にたぐる。
最終的に、それぞれの旗は元の位置に戻り
i
は
Pi
の情報をもつ
i
は
Pi
の情報をもつ
ようにする。
メイン
アルゴリズム
Unwinding Phase
0
1
0
1
5
3
2
2
3
4
4
5
6
6
7
7
abc ababcababcbacababbcab
Pattern: b a c a
メイン
アルゴリズム
Unwinding Phase
6
7
5
4
2
7
5
0
1
0
1
2
5
4
2
6
4
3
3
0
0
abc ababcababcbacababbcab
Pattern: b a c a
メイン
アルゴリズム
Unwinding Phase
6
7
5
4
2
6
4
2
7
5
3
3
0
1
0
1
abc ababcababcbacababbcab
Pattern: b a c a
メイン
アルゴリズム
Unwinding Phase
4
6
4
7
5 5
3
3
0
1 5 5
7
0
1
2
2
6
abc ababcababcbacababbcab
Pattern: b a c a
メイン
アルゴリズム
Unwinding Phase
7
4
4
5
6
6
0
1 5
7
0
1
3
3
2
2
abc ababcababcbacababbcab
Pattern: b a c a
メイン
アルゴリズム
Unwinding Phase
5
0
1 5
0
1
6 6
7
2
2
3
3
4
7
6
4
abc ababcababcbacababbcab
Pattern: b a c a
メイン
アルゴリズム
Unwinding Phase
6
0
1
0
1
7
2
2
3
3
5
4
7
6
4
5
abc ababcababcbacababbcab
Pattern: b a c a
メイン
アルゴリズム
Unwinding Phase
0
1
0
1
7
2
2
3
3
5
4
7
4
5
6
6
abc ababcababcbacababbcab
Pattern: b a c a
メイン
アルゴリズム
Unwinding Phase
0
1
0
1
2
2
3
3
5
4
4
5
6
6
7
7
abc ababcababcbacababbcab
Pattern: b a c a
メイン
アルゴリズム
Final operation
i
0
1
2
3
4
5
6
Pi Pi+1
a
b
b
c
c
ba
b
b
a
c
a
ba
ca
b
Complexity of Algorithm
アルゴリズムの計算量
アルゴリズム
の計算量
Winding Phase
abc
0
1
0
1
7
2
2
3
3
4
7
4
5
5
6
6
7
7
アルゴリズム
の計算量
Winding Phase
O( log | Z | )
L:
0
1
0
1
2
2
3
3
4
4
Balanced tree
5
5
6
6
7
7
アルゴリズム
の計算量
Winding Phase
O( log | Z | )
L:
0
1
0
1
2
2
7
3
3
4
4
5
5
6
7
O( 1 )
6
アルゴリズム
の計算量
Winding Phase
O( | Z | log |T | )
L:
0
1
0
1
7
2
2
7
3
3
4
7
4
5
7
Segment-Merge
5
6
6
アルゴリズム
の計算量
Winding Phase
O( | Z | log | Z | + | Z | log |T | )
= O( | Z |( log | Z |・|T | ) )
O( | Z | log2 (|T | | Z |) )
アルゴリズム
の計算量
Unwinding Phase
6
7
5
4
2
6
4
2
7
5 5
3
3
0
1 5 5
7
0
1
2
2
6
abc ababcababcbacababbcab
Pattern: b a c a
アルゴリズム
の計算量
Unwinding Phase
6
7
5
O( | Z | )
4
2
6
4
2
7
5 5
3
3
0
1 5 5
7
0
1
2
2
6
abc ababcababcbacababbcab
O( log| P | )
Pattern: b a c a
前処理
O( | P | )
アルゴリズム
の計算量
Unwinding Phase
O( P + | Z | ( | Z | + log |P | ) )
O(P+|Z|log(|T | | Z |) log|P| )
前処理
O( | P | )
final operation
i
0
1
2
3
4
5
6
Pi Pi+1
a
b
b
c
c
ba
b
b
a
c
a
ba
ca
b
アルゴリズム
の計算量
O(O(|Zlog
| log
| P| P| )| )
O( log| P | )
O( log| P | )
O( log| P | )
O( log| P | )
O( log| P | )
O( log| P | )
アルゴリズム
の計算量
Total
O( | Z | log2 (|T | | Z |) )
と
O(|P|+|Z|log(|T | | Z |) log|P| )
と
O( |Z| log| P | )
O(|P|+|Z|log(|T | | Z |)(log(|T | | Z |)+log|P|))
Conclusion
まとめ
まとめ
conclusion
LZ77圧縮されたテキストに対するパターン
マッチアルゴリズムを、初めて示した。
そのアルゴリズムの時間計算量は
O(|P|+|Z|log(|T | | Z |)
(log(|T | | Z |)+log|P|))
である。
まとめ
conclusion
実際にこのアルゴリズムが速いかどうかは
実験されていない。
パターンの長さが非常に長い場合は、圧縮
テキストを展開したほうがよさそう。

Download Report