Download presentation
Presentation is loading. Please wait.
Published byAlexander Petersen Modified 約 6 年前
1
Proceedings of the Third South American Workshop on String Processing.
2019/1/11 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, , 1996 竹田研究室 修士課程1年 喜田 拓也
2
研究背景 9 文字列照合問題(パターンマッチング) existence problem all-occurrences problem
きだくんのおかあさんがりあかーをひいている さんがりあ
3
研究背景 KMP O(m+n) m n BM O(m+n) 文字列照合問題(パターンマッチング) existence problem
all-occurrences problem existence problem all-occurrences problem existence problem all-occurrences problem KMP O(m+n) m n BM O(m+n)
4
研究背景 巨大なテキストに対する文字列照合問題 Index を作ることで劇的に速くなる.
5
研究背景 O(n) 現在知られている index 構造 suffix tree suffix array Over 10n bytes
level-compressed trie suffix cactus suffix binary search tree O(n) Over 10n bytes 5n bytes About 11n bytes 9n bytes About 10n bytes
6
O(n / log n) 研究背景 新しい index 構造が必要 初の sublinear-size index より小さい
前処理をしない場合よりも検索が高速 初の sublinear-size index LZ parsing を用いる これがミソ O(n / log n)
7
LZ parsing Lempel-Ziv 圧縮 LZ parsing = LZ76 ? LZ77 (移動辞書式圧縮)
LZSS, LZH,LZR,LZB LZ78 (登録辞書式圧縮) LZW,LZC,LZT,LZFG LZ parsing = LZ76 ?
8
LZ parsing ... LZ parse Z of string T の定義 Z (P1,L1,C1) (Pi,Li,Ci)
= (P1,L1,C1) (Pi,Li,Ci) (PN,LN,CN) ... Pi, Li 負でない整数 Ci Σ上の記号
9
Pi < Ui , whenever Li > 0 T[Ui…Ui+Li-1] = T[Pi…Pi+Li-1],
LZ parsing LZ parse Z of string T の定義 Z = (P1,L1,C1) (Pi,Li,Ci) (PN,LN,CN) ... = 1, U1 Ui = Ui -1 + Li 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 を選ぶ.
10
LZ parsing aaaabbaaababaaabb a b a a b $ LZ parse の例 T 注意 Z (0,0,a)
2019/1/11 LZ parsing LZ parse の例 T = aaaabbaaababaaabb a b a a b $ 注意 Z = (0,0,a) (1,3,b) (5,1,a) (3,3,a) (6,5,b)
11
LZ parsing aaaabbaaababaaabb a b a a b LZ parse の例 block T definition
2019/1/11 LZ parsing LZ parse の例 block T = aaaabbaaababaaabb a b a a b definition phrase boundary symbol Z = (0,0,a) (1,3,b) (5,1,a) (3,3,a) (6,5,b)
12
LZ parsing aaaabbaaababaaabb a b a a b LZ parse の例 T U1 U5 U4 U3 U2 =
2019/1/11 LZ parsing LZ parse の例 T = aaaabbaaababaaabb a b a a b U1 U5 U4 U3 U2 = 1 2 6 8 12 Z = (0,0,a) (1,3,b) (5,1,a) (3,3,a) (6,5,b)
13
LZ parsing parse Z の特性 どの二つの block も同一ではない
14
LZ parsing parse Z の特性 どの二つの block も同一ではない
パターンP の最初の occurrence は, 必ず Z の boundary symbol を含む
15
LZ parsing n O(n / log n) parse Z のサイズのオーダー
N を長さ n のテキストの LZ parse における block の個数とする. また c = |Σ| とする. N < n logc n - logc logc n - 1 c-1 O(n / log n)
16
|Σ| LZ parsing for text length n = 300000. English DNA random 77 4 2 8
64 40964 31633 16734 14755 88748 type N |Σ|
17
Oh! Let’s go
18
T における Pの occurrence が boundary symbol を含む.
検索アルゴリズム サーチ を2種類に分類する. これがミソ T における Pの occurrence が boundary symbol を含む. Primary occurrence それ以外 Secondary occurrence
19
検索アルゴリズム Occurrence を2種類に分類する. Primary search Existence problem
これがミソ Primary search Existence problem Primary occurrence Secondary search Secondary occurrence
20
P の primary occurrence を見つけ出す.
Primary Search 問題の定義 P の primary occurrence を見つけ出す. T [Ui + Li] = Ci 1 ・・・ u ・・・・・・ m Reference pair (i , u)
21
P の primary occurrence を見つけ出す.
Primary Search 問題の定義 P の primary occurrence を見つけ出す. 1 ・・・ u ・・・・・・・・・ u′・・ m Canonical reference pair (i , u)
22
Primary Search 問題の定義 P の primary occurrence を見つけ出す. O(mN)
(i,u) が primary occurrence の canonical reference pair であるような i を見つけ出す.
23
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]
24
Primary Search Primary Search を解くための工夫 1 ・・・ u ・・・・・・ m
25
i Primary Search Two-Dimensional Prefix Matching(2DPM)
{(Xi , Yi)} : 文字列の組の集合 (X , Y) : 質問文字列 i X が Xi の prefix, Y が Yi の prefix. (Xi , Yi) 愛?
26
Xi = T[Ui…Ui+Li]R = T[Ui…Ui+1 -1]R
2019/1/11 Primary Search Two-Dimensional Prefix Matching(2DPM) {(Xi , Yi)} : 文字列の組の集合 (X , Y) : 質問文字列 Xi = T[Ui…Ui+Li]R = T[Ui…Ui+1 -1]R Yi = T[Ui+Li...] = T[Ui ] X = P[1…u]R Y = P[u…m]
27
Primary Search 2DPMの例 1 ・・・ u ・・・・・・ m 1 block
28
Primary Search 問題の定義 P の primary occurrence を見つけ出す.
2-dimensional prefix matching を解く. 2-dimensional range query を解く.
29
i Primary Search 質問区間に含まれる点 (xi , yi)を見つける. 2-dimensional range query
2019/1/11 Primary Search 2-dimensional range query {(xi , yi)} : 点の集合 ([xl , xr] , [yl , yr]) : 質問区間. 質問区間に含まれる点 (xi , yi)を見つける. i 愛?
30
Primary Search 2-dimensional range query {(xi , yi)} : 点の集合
([xl , xr] , [yl , yr]) : 質問区間. xl xr yl yr
31
Primary Search 2-dimensional range query {(xi , yi)} : 点の集合
([xl , xr] , [yl , yr]) : 質問区間. これがミソ 辞書式順序を用いる. xl = X xr = Xzzzzz... yl = Y yr = Yzzzzz... xi = Xi , yi = Yi
32
Primary Search Y 2-dimensional range query X (a,aaaabb...)
aba abazzzz... ab abzzzz... X Y (a,aaaabb...) (baaa,bbaaa...) (ab,aaabab...) (abaa,abaaa...)
33
N 点の balanced 2-d tree. (Lee, Wong 1977)
Primary Search 2-dimensional range query 2DPM N 点の balanced 2-d tree. (Lee, Wong 1977) O( N + l) 2-d tree for string. O(m N + l) O(m + N + l)
34
Primary Search Y 2-d tree の例 X a X 値で判別 b c Y 値で判別 d g e f g e c b f d
(x1 , y1) (x2 , y2) (x3 , y3) (x4 , y4) (x5 , y5) (x7 , y7) (x6 , y6) X 値で判別 Y 値で判別 X Y g e c b f d a
35
T [Ui + Li - u + 1 … Ui + Li - u + m] = P となるような canonical な i を見つける.
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)
36
T [Ui + Li - u + 1 … Ui + Li - u + m] = P となるような canonical な i を見つける.
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)
37
Ok? No!
38
Secondary Search 問題の定義 Secondary occurrence Known occurrence
これがミソ Secondary occurrence
39
Secondary Search 問題の定義 Known occurrence Secondary occurrence
(Pi , Li , Ci) Pi Pi+Li-1
40
Known occurrence O = T[v…v + m - 1] T[Ui - Pi + v…Ui -Pi + v + m - 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]
41
i Secondary Search xi ≦ x, yi ≧ y となるような すべての区間 [xi , yi] を見つける.
Interval containment problem {[xi , yi]}i=1,…,N : 区間の集合 [x , y] : 質問区間 xi ≦ x, yi ≧ y となるような すべての区間 [xi , yi] を見つける. i 愛?
42
Secondary Search xi = Pi , yi = Pi + Li - 1 x = v , y = v + m - 1
問題の定義 Secondary occurrence O = T[v…v + m - 1] 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 ]
43
トータルでは, すべての occurrenceに対して interval containment problem が行われるので
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)
44
Secondary Search binary tree の構造を持つ. 2-d heap 各ノードは区間のうちの1つを中に持つ.
区間[xi , yi]を持つノードの… 左の subtree のすべてのノードが持つ 区間の y の値は yi より小さい. 右の subtree のすべてのノードが持つ 区間の x の値は xi より大きい.
45
Secondary Search 2-d heap の例 [2,5] [3,6] [4,5] [5,7] [1,7] [4,8] [6,9]
10 11 2 4 5 6 7 3 [1,7] [4,8] [6,9] [9,12] [1,9] [7,12] [6,11] 11 9 7 8 5 6 6 7 9
46
Secondary Search 2-d heap の例 O(log N + l log N) [2,5] [3,6] [4,5]
1 [2,5] [3,6] [4,5] [5,7] 8 9 10 11 2 4 5 6 7 3 [1,7] [4,8] [6,9] [9,12] [1,9] [7,12] [6,11] [2,3] [2,3] [2,3] [2,3] O(log N + l log N) [2,3] [2,3] [2,3] 1 2 3 4 5 6 7 8 9 10 11 12
47
I saw every thing Mmmmm...
48
検索アルゴリズムのまとめ 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)
49
さいごに 18 N 新しい Index 構造の構成 bytes LZ parse Z O(N)
本当に小さいのか? 18 N bytes 1 2 新しい Index 構造の構成 LZ parse Z O(N) 2-d tree for string O(N) 2-d heap と offset O(N) Suffix array = 5n bytes n > 103 小さい
50
さいごに 本当に小さいのか? 他の index 構造よりも一般的に小さくなるだろう. 検索時間の practical な評価は? 謎
51
さいごに 一番の謎 本当に小さいのか? 検索時間の practical な評価は? 実現可能か?
他の index 構造よりも一般的に小さくなるだろう. 検索時間の practical な評価は? 実現可能か? 謎 一番の謎 これがミソ
Similar presentations
© 2024 slidesplayer.net Inc.
All rights reserved.