Lempel-Ziv Parsing and Sublinear

Lempel-Ziv Parsing and
Sublinear-Size Index Structures
for String Matching
¨
¨
Juha Karkkainen
Esko Ukkonen
Proceedings of the Third South American Workshop on String Processing.
WSP 1996, 141-55, 1996
竹田研究室修士課程1年
喜田拓也
研究背景

文字列照合問題（パターンマッチング）
existence problem
all-occurrences problem
9
きだくんのおかあさんがりあかーをひいている
さんがりあ
研究背景

文字列照合問題（パターンマッチング）
existence problem
all-occurrences problem
KMP O(m+n)
m n
BM O(m+n)
研究背景

巨大なテキストに対する文字列照合問題
– Index を作ることで劇的に速くなる.
研究背景

現在知られている index 構造 O（n）
–
–
–
–
–
Over 10n bytes
suffix tree
suffix array
5n bytes
level-compressed trie
About 11n bytes
suffix cactus
9n bytes
suffix binary search tree
About 10n bytes
研究背景

新しい index 構造が必要
– より小さい
– 前処理をしない場合よりも検索が高速

初の sublinear-size index
LZ parsing を用いる
これがミ
ソ
O(n / log n)
LZ parsing

Lempel-Ziv 圧縮
– LZ77 （移動辞書式圧縮）

LZSS, LZH,LZR,LZB
– LZ78 （登録辞書式圧縮）

LZW,LZC,LZT,LZFG
LZ parsing = LZ76 ?
LZ parsing

LZ parse Z of string T の定義
Z = （P1,L1,C1） ... （Pi,Li,Ci） ... （PN,LN,CN）
Pi, Li
負でない整数
Ci
Σ上の記号
LZ parsing

LZ parse Z of string T の定義
Z = （P1,L1,C1） ... （Pi,Li,Ci） ... （PN,LN,CN）
U1 = 1,
Ui = Ui -1 + Li -1 + 1 for i > 1.
Pi < Ui , whenever Li > 0
For 1 ≦ i ≦ N
T［Ui…Ui+Li-1］ = T［Pi…Pi+Li-1］,
T［Ui+Li］ = Ci .
T［Pi...］と T［Ui...］の common prefix が
最大となる Pi < Ui を選ぶ.
LZ parsing

LZ parse の例
T = aaaabbaaababaaabb $
注意
Z = （0,0,a）（1,3,b）（5,1,a）（3,3,a）（6,5,b）
LZ parsing

LZ parse の例
block
T = aaaabbaaababaaabb
definition
phrase
boundary symbol
Z = （0,0,a）（1,3,b）（5,1,a）（3,3,a）（6,5,b）
LZ parsing
LZ parse の例
=
=
=
T = aaaabbaaababaaabb
U1U2
U 3 U4
U5
=
=

1 2
6
8
12
Z = （0,0,a）（1,3,b）（5,1,a）（3,3,a）（6,5,b）
LZ parsing

parse Z の特性
– どの二つの block も同一ではない
LZ parsing

parse Z の特性
– どの二つの block も同一ではない
– パターンP の最初の occurrence は,
必ず Z の boundary symbol を含む
LZ parsing

parse Z のサイズのオーダー
N を長さ n のテキストの LZ parse における
block の個数とする. また c = |Σ| とする.
N<
n
1
logc n - logc logc n - c-1
O（n / log n）
LZ parsing

N の目安
for text length n = 300000.
|Σ|
type
N
English 77 40964
DNA
4 31633
random 2 16734
random 8 14755
random 64 88748
Oh!
Let’s go
検索アルゴリズム

サーチを2種類に分類する.
これがミ
ソ
T における Pの occurrence が boundary symbol を含む.
Primary occurrence
それ以外
Secondary occurrence
検索アルゴリズム

Occurrence を2種類に分類する.
これがミ
ソ
Primary search
Existence problem
Primary occurrence
Secondary search
Secondary occurrence
Primary Search

問題の定義
P の primary occurrence を見つけ出す.
1 ･･･ u ･･････ m
T ［Ui + Li］ = Ci
Reference pair （i
, u）
Primary Search

問題の定義
P の primary occurrence を見つけ出す.
1 ･･･ u ･････････ u′･･ m
Canonical reference pair （i , u）
Primary Search

問題の定義
P の primary occurrence を見つけ出す.
O
（mN）
（i,u）が primary occurrence の
canonical reference pair であるような
i を見つけ出す.
Primary Search

Primary Search を解くための工夫
1 ･･･ u ･･････ m
T ［Ui + Li - u + 1 … Ui + Li ］ = P［1…u］
T ［Ui + Li … Ui + Li - u + m］ = P［u…m］
Primary Search

Primary Search を解くための工夫
1 ･･･ u ･･････ m
Primary Search

Two-Dimensional Prefix Matching(2DPM)
｛（Xi , Yi）｝：文字列の組の集合
（X , Y）：質問文字列
X が Xi の prefix,
Y が Yi の prefix.
愛?
（Xi i, Yi）
Primary Search

Two-Dimensional Prefix Matching(2DPM)
｛（Xi , Yi）｝：文字列の組の集合
（X , Y）：質問文字列
R
R
Xi = T［Ui…Ui+Li］ = T［Ui…Ui+1 -1］
Yi = T［Ui+Li...］ = T［Ui+1 -1...］
R
X = P［1…u］
Y = P［u…m］
Primary Search

2DPMの例
1 ･･･ u ･･････ m
1 block
Primary Search

問題の定義
P の primary occurrence を見つけ出す.
2-dimensional prefix matching を解く.
2-dimensional range query を解く.
Primary Search

2-dimensional range query
｛（xi , yi）｝：点の集合
（［xl , xr］ , ［yl , yr］）：質問区間.
質問区間に含まれる点（xi , yi）
を見つける.
i
愛?
Primary Search

2-dimensional range query
｛（xi , yi）｝：点の集合
（［xl , xr］ , ［yl , yr］）：質問区間.
yr
yl
xl
xr
Primary Search

2-dimensional range query
｛（xi , yi）｝：点の集合
（［xl , xr］ , ［yl , yr］）：質問区間.
これがミ
ソ
辞書式順序を用いる.
xl = X
yl = Y
xr = Xzzzzz...
yr = Yzzzzz...
xi = Xi ,
yi = Yi
Primary Search

2-dimensional range query
Y
abzzzz...
ab
abazzzz...
aba
（a,aaaabb...）
（baaa,bbaaa...）
（ab,aaabab...）
（abaa,abaaa...）
X
Primary Search

2-dimensional range query
N 点の balanced 2-d tree. （Lee, Wong 1977）
O（ N + l）

2DPM
2-d tree for string.
O（m N + l）
O（m + N + l）
Primary Search

2-d tree の例
(x2 , y2)
X 値で判別
Y 値で判別
a
(x1 , y1)
b
c
(x3 , y3)
d
e
f
(x4 , y4)
(x5 , y5)
(x6 , y6)
Y
(x7 , y7)
g
e
b
d
g X 値で判別
f
c
a
X
Primary Search
T ［Ui + Li - u + 1 … Ui + Li - u + m］ = P
となるような canonical な i を見つける.
1 ･･･ u ･･････ m
O（m + N + l）
O（m2 + m N + L）
Primary Search
T ［Ui + Li - u + 1 … Ui + Li - u + m］ = P
となるような canonical な i を見つける.
1 ･･･ u ･･････ m
O（m2 + m N + L）
O（m2 +m log N + Nm log m + L）
Ok?
No!
Secondary Search

問題の定義
Secondary occurrence
Known occurrence
これがミ
ソ
Secondary occurrence
Secondary Search
問題の定義
Known occurrence

Secondary occurrence
（Pi , Li , Ci）
Pi
Pi+Li-1
Secondary Search
問題の定義
T［v…v + m - 1］

Secondary occurrence
Known occurrence O = T［v…v + m - 1］
Pi ≦ v, Pi + Li-1≧ v + m - 1 となる
すべての i をみつける.
O（N）
Secondary occurrence
T［Ui - Pi + v…Ui -Pi + v + m - 1］
Secondary Search

Interval containment problem
｛［xi , yi］｝i=1,…,N : 区間の集合
［x , y］ : 質問区間
xi ≦ x, yi ≧ y となるような
すべての区間［xi , yi］を見つける.
i
愛?
Secondary Search
問題の定義
O = T［v…v + m - 1］ Secondary occurrence

T［Pi］
T［Pi+Li-1］
xi = Pi , yi = Pi + Li - 1
x=v, y=v+m-1
offset oi = Ui - Pi
T［ x + oi … y + oi ］
Secondary Search

Interval containment problem
– Priority search tree （McCreight 1985）
O（log N + l）
– 2-d heap
O（log N + l log N）
トータルでは, すべての occurrenceに対して
interval containment problem が行われるので
O（L log N）
Secondary Search

2-d heap
binary tree の構造を持つ.
各ノードは区間のうちの1つを中に持つ.
区間［xi , yi］を持つノードの…
左の subtree のすべてのノードが持つ
区間の y の値は yi より小さい.
右の subtree のすべてのノードが持つ
区間の x の値は xi より大きい.
Secondary Search

2-d heap の例
6 11
［6,11］
9
［1,9］
7 4
［1,7］
8
1
2
3
8 5
［4,8］
9
10
7
［7,12］
6
7
6
［6,9］
9
［9,12］
11
5 ［3,6］
6 ［4,5］
7
5 ［5,7］
［2,5］
Secondary Search

2-d heap の例
［2,3］［1,9］
［2,3］［1,7］ 4
8
［6,11］［2,3］
1
2
3
［4,8］ 5 ［2,3］ 6
［6,9］
9
10
2
3
4
5
7
［9,12］
11
［2,5］［3,6］［4,5］［5,7］
［2,3］［2,3］［2,3］
1
［7,12］
6
7
O（log N + l log N）
8
9
10 11 12
I saw every thing
Mmmmm...
検索アルゴリズムのまとめ
parse Z により,サーチを 2 part に分割
 primary search -> 2DPM
-> 2-dimensional range query

– 2-d tree for string. O（N）領域
– search time O(m2 + m log N + Nm log m )

secondary search
> interval containment problem
– 2-d heap. O（N）領域
– search time O(L log N)
-
さいごに

本当に小さいのか？
1
2
18 N
新しい Index 構造の構成
bytes
LZ parse Z
O（N）
2-d tree for string O（N）
2-d heap と offset O（N）
Suffix array = 5n bytes
n > 103
小さい
さいごに

本当に小さいのか？
– 他の index 構造よりも一般的に小さくなるだろう.

検索時間の practical な評価は？
–謎
さいごに

本当に小さいのか？
– 他の index 構造よりも一般的に小さくなるだろう.

検索時間の practical な評価は？
–謎

実現可能か？
一番の謎
これがミ
ソ

Download Report