Vol. 0 No Fast Traversal of Suffix Arrays for Full-Text Approximate String Matching Masao Utiyama and Hitoshi Isahara Given a text and a

Size: px

Start display at page:

Download "Vol. 0 No Fast Traversal of Suffix Arrays for Full-Text Approximate String Matching Masao Utiyama and Hitoshi Isahara Given a text and a"

みいかなかじゅく
5 years ago
Views:

1 Vol. 0 No Fast Traversal of Suffix Arrays for Full-Text Approximate String Matching Masao Utiyama and Hitoshi Isahara Given a text and an input pattern, the goal of full-text approximate string matching is to search for all parts of the text that match the pattern. Full-text approximate string matching can be performed using a suffix trie as an index of the text. A suffix trie, however, is relatively large. So, a suffix array, which is a compact representation of a suffix trie, is often used to simulate searches on a suffix trie. A binary search algorithm is used to search the array. A method is described in this paper that uses an auxiliary array to simulate searches on a suffix trie. The method does not use a binary search algorithm so that it can perform a faster simulation. Experiments showed that the proposed method is faster than one using a binary search algorithm. 1. optical 3 character reader, OCR suffix trie Communications Research Laboratory 0 translation memory 11)

2 Vol. 0 No. 0 1 suffix tree 6) Suffix trie 1),2),5),12),13),15) A B E C D suffix array 9) 1),2),12) B C E D A A $ 9 C E D A A $ B B 8 A A $ B B D E 7 B B D E A $ 6 1),2),12) D A E $ B 5 2 A $ B E 4 B E $ 2 3 E $ 2 2 $ Text A B C A B D A B E $ Fig. 1 Text and its suffix trie Σ Σ t i..n Σ n i + 2 Σ n T T = t 1 t 2... t n t i Σ T i j $ $ Σ (i j) t i..j = t i t i+1... t j T i suffix T t i..j W (T ) = preorder {X X = t i..j W (T ) T 1 2 T = abab W (T ) = {a, b, ab, ba, aba, bab, abab a, b ab T 1 W (T ) T T 2.3 n T T Σ t i, t i+1,..., t n, $ 1 ABCABDABE t i..n T [i] = t i postorder T S T 3 S[i] T S[i] t S[i]..n 17) i < j t S[i]..n

3 Text A B C A B D A B E Suffix array lcp array Suffixes denoted by S[i] 2n S[1] 1 lcp[1] 0 ABCABDABE 4n 12n S[2] 4 lcp[2] 2 ABDABE lcp S[3] 7 lcp[3] 2 ABE S[4] 2 lcp[4] 0 BCABDABE O(n 2 ) S[5] 5 lcp[5] 1 BDABE 12n S[6] 8 lcp[6] 1 BE S[7] 3 lcp[7] 0 CABDABE S[8] 6 lcp[8] 0 DABE O( Σ n) 2 S[9] 9 lcp[9] 0 E lcp[10] 0 2 lcp Fig. 2 Text, its suffix array and lcp array. 3. t S[j]..n 13) T lcp longest common prefix n + 1 lcp[i] dynamic programming 2 i n t S[i 1]..n t S[i]..n edit distance 3 lcp[1] = lcp[n + 1] = 0 2 ABCABDABE 3.1 lcp m P = p 1 p 2... p m lcp[2] = 2 t S[1]..n = ABCABDABE t S[2]..n = ABDABE lcp[i] > 0 W (T ) X P dist(p, X) t X S S[i] j 4 t S[i]+j 1 S[i] j 1 > n $ 2 X = x 1 x 2... x u Y = y 1 y 2... y v S[4] = 2 1 t S[4]+1 1 = t S[4] = t 2 = B 2 t 3 = C 3 t 4 = A [u..v] x i y j sub(x i, y j ) j u i v S[i] j 1 lcp u = 1, v = n lcp 2(n + 1) 2 [3..7] 1 ABBBC 2 [3..7] 2 BCDEA 2.4 4(n + 1) 1 Σ 256 n Σ P T t( 0) dist(x, Y ) X Y 2 O(n) 3 n T lcp 6) 4 X T 4 4n

4 Vol. 0 No. 0 3 x i del(x i ) y j ins(y j ) X Y φ a c d f b d f 0 φ dist(x, Y ) x 1..i y 1..j 1 a D[i, j] dist(x, Y ) = D[u, v] 2 d D[i, j] 3 f D[0, 0] = 0, 4 d 2 D[i, 0] = D[i 1, 0] + del(x i ), 3 13) Table 2 D[0, j] = D[0, j 1] + ins(y j ), Fig. 3 Distance calculation with cut-off. Modification of D[i 1, j 1] + sub(x i, y j ) a part of Table 2 in 13). D[i, j] = min D[i 1, j] + del(x i ). D[i, j 1] + ins(y j ) 1 i u 1 j v C[j] + 2 sub(x i, y j ), del(x i ), ins(y j ) 0 x i = t y j sub(x i, y j ) = 0 D t + 1 D[0, 0] i D[i, 0] X = adfd del(x 1 k i k) x 1..i Y = acdfbdf 1 (y 1 1 x 1..i D[0, j] 3 ins(y 1 l j l) x 1 3 = y 1..j y 1..j x 1 +1=2 j = 0 D[0, 0] = 0, D[1, 0] = D[i, j] x 1..i 1 1, D[2, 0] = 2 D[2, 0] > 1 y 1..j 1 C[0] = 1 j = 1 x i y j C[0] + 1 = 2 D[0, 1] = 1, D[1, 1] = x i y j x i 0, D[2, 1] = 1 C[1] = 2 y j x 1..i C[2] = 2, C[3] = 2, C[4] = 3 j = 5 D[i, j] 1 C[5] = 0 D[4, 5] > 1 D[4, 7] > P T t t P T 14) 1 0 C[j] ) C[0] D[i, 0] t 13) j 0 v v D[i, j] v D[i, j] t i C[j] i D[i, j] > t v C[j] = 0 j + 1

5 v /* */ D 3.2 C AB- P P[i] i (1<=i<=m) T(node) node CABDABE ABDABE ABE t AB /* */ main(){ AB /* */ C[0] := D[0,0] := 0 for(i:=1; i<=m; i++){ D[i,0] := D[i-1,0] + del(p[i]) if(d[i,0]<=t){c[0]:=ielse{break /* */ foreach child in {search(child, 1) search(node, j){ if (node ) return if (cutp(t(node), j)) return if (D[m,j]<=t) foreach child in (node ) { 2 search(child, j+1) cutp(textchar, j){ j t /* */ D[m,j] := t+1 j + 1 /* j */ t C[j] := 0 D[0,j] := D[0,j-1] + ins(textchar) t for(i:=1; i<=min(c[j-1]+1, m); i++){ D[i,j] := min(d[i-1,j-1]+sub(p[i],textchar), D[i-1,j]+del(P[i]), D[i,j-1]+ins(textChar)) if(d[i,j]<=t){c[j] := i C /* */ 4 if(c[j]=0){ 4 main return true else{ /* j+1 */ if(c[j]>c[j-1]){d[c[j]+1,j] := t+1 search return false search search 4 Fig. 4 Full-text approximate string matching algorithm. search(node,j) ( 1 ) node 3.3 D[m,j] ( 2 ) cutp(t(node),j) j ( 2 ) j C[j] true false ( 3 ) C[j]=0 ( 3 ) node j+1 D[m,j] t false j+1 ( 4 ) node 5 search 2 cutp(t(node),j) D[i,j+1] D[i-1,j], ( 1 ) D[m,j]:=t+1 true C[j]>C[j-1] C[j]=C[j-1]+1 D[i-1,j+1], D[i,j] j := C[j] 0 C[j-1]+1

6 Vol. 0 No. 0 5 i-1 i C[j-1] j-1 j j+1 D[i,j+1] φ A B 0 φ D C A 6 DCA AB Fig. 6 Distance matrix between DCA and AB (cutoff). C[j-1]+1 = C[j] C[j]+1 a D[C[j]+1,j+1] default value 5 Fig. 5 Handling default values for distances. j+1 0<=i<=C[j] D[i,j+1] D[C[j]+1,j+1] for 2 5 a 3.3 lcp t t+1 D[C[j]+1,j] C[j]<=C[j-1] j φ B C A 0 φ D C A 1 7 DCA BCA 5 D[0,j],..., D[C[j],j] Fig. 7 Distance matrix between DCA and BCA cutp for (success in approximate string matching). 1),2),12) 2 ABCABDABE 1 DCA AB 1 6 1),2),12) 1 BCA D[3,3]=1 BCA BCA +1=2 exact match 1 B 2 4. [4..6] 2 C [4..4] 3 A [4..4]

7 BCA 2 S[i 1] S[i] 1 BCA 2 t S[1]...n = t 1...n = ABCABDABE t S[2]...n = t 4...n = ABDABE AB AB lcp[2] = [1..3] A, [4..6] B [7..7] C, [8..8] D, [9..9] E printf("%c", T[S[i]+k]); 1 S lcp 1 * B 1 [4..6] 2 C [7..7] D [8..8] E S[1]=1, lcp[1]=0: A B C A B D A B E [9..9] S[2]=4, lcp[2]=2: * * D A B E S[3]=7, lcp[3]=2: * * E S[4]=2, lcp[4]=0: B C A B D A B E S[5]=5, lcp[5]=1: * D A B E S[6]=8, lcp[6]=1: * E S[7]=3, lcp[7]=0: C A B D A B E 4 S[8]=6, lcp[8]=0: D A B E S[9]=9, lcp[9]=0: E 1 for(i:=1; i<=n; i++){ for(k:=lcp[i]; S[i]+k<=n; k++){ for(i:=1; i<=n; i++){ 2 printf("s[%d]=%d, lcp[%d]=%d: ", i, S[i],i,lcp[i]); S[1] 1 for(k:=0; k<lcp[i]; k++){printf("* "); for(k:=lcp[i]; S[i]+k<=n; k++){ A 2 printf("%c ", T[S[i]+k]); A 1 [1..3] S[4] printf("\n"); 1 B lcp * 2 lcp lcp[i] 1 2 i=1 lcp[1]=0 2 T[S[1]+0]=T[1] T[n]=T[9] 3 ABCABDABE for i=2 lcp[2]=2 12) T[S[2]+2]=T[6] T[n]=T[9] DABE i=3

8 Vol. 0 No. 0 7 main() { /* */ ( 4 ) /* */ for(i:=1; i<=n; i++){ cut := false for(k:=lcp[i]; S[i]+k<=n; k++){ j := k + 1 if(cutp(t[s[i]+k], j)){ cut := true break if (D[m,j]<=t) if(cut){ /* */ while(lcp[i+1]>=j){i++ 8 lcp lcp[1]=0 k 0 Fig. 8 Full-text approximate string matching algorithm using a lcp array. lcp[3]=2 T[S[3]+2]=T[9] E cutp("b",2) cutp true for AB 4.3 lcp 5 while ABCABDABE DCA 8 i=1 for ABCABDABE T[S[1]+0]=T[1] A cutp("a",1) 6 1 k=1 while lcp j=2 lcp[2]=lcp[3]=2 8 ABE ABE AB 8 cutp 4 for 8 2 for i=4 S BCABDABE BCA k lcp[i] 7 BCAB lcp[i] S[i] k+1 i=5 for T[S[i]+k] k+1 j lcp[5]=1 k 1 i=4 cutp("b",1) cutp("d",2) while 1 j 1 ABCABDABE 1 i=2,3 ABD- lcp[i+1] DCA B- CA CA DA lcp[i+1]>=j m n( m) t 9) while

9 lcp 4 cutp 1 i m 1 j m + t + 1 j m + t + 1 j = m + t + 1 t 5. O(m(m + t)) i n k m + t cutp 1 i m O(n(m + t)m) CD m + t ,99 O( Σ m+t ) BNC British National Corpus cutp O(m) 2 O(log n) O(m Σ m+t log n) 7),10),16) O(t) cutp O(t) 3),4) O(t Σ t ) ) O(t Σ t log n) i i while O( Σ t )..., 1,2,3,4,5 s O(s Σ t ) Size-1,Size-2,...,Size-5 O((t + s) Σ t ) 6 s 1 BNC Size-1 9) O(log n + t) Size-5 O((t + log n) Σ t ) 14.9M M n British National Corpus lcp 8n BNC 90% 10% lcp BNC 9) lcp lcp 5.1.1

10 Vol. 0 No. 0 9 Table 1 1 Number of different units (types) and the number of total units (tokens). Size-1 Size-2 Size-3 Size-4 Size-5 4,296 4,608 4,783 4,880 4, M 29.8M 44.8M 59.7M 74.6M BNC 251, , , , , M 33.5M 50.2M 66.9M 83.6M ,12, BNC 3,6, binsearch Size (Mainichi) 18 2,4,6 BNC binsearch ,2, lcp CPU Size-1 5 Size-5 C 4.1 Fig. 9 Average search CPU time (seconds) on Mainichi 2 binsearch (graphs of Size-1 to 5 and the table of Size-5). 4.3 lcp 5.2 lcp BNC 1 CPU CPU Alpha MHz x MB OS Linux Kondara MNU/Linux release 1.1 CPU lcp binsearch lcp Av. of search time (CPU sec.) CPU 10 9 OS CPU = CPU + CPU CPU CPU CPU CPU binsearch-18-6 lcp-18-6 lcp-18-4 binsearch binsearch-18-6 binsearch 18 6 Size-5 binsearch 9 18 lcp-18-2

11 Av. of search time (CPU sec.) binsearch-9-3 lcp Size (BNC) binsearch-9-2 lcp-9-2 binsearch-9-1 lcp binsearch lcp BNC CPU Size-1 5 Size-5 Fig. 10 Average search CPU time (seconds) on BNC (graphs of Size-1 to 5 and the table of Size-5). binsearch-18-6 binsearch-12-6 t 1,t t 1 t 2 = 100 (t 1 + t 2 ) 0.5 BNC 0.49% BNC 1.08% t O(t) 1 13) t O(t) t 9 2 lcp binsearch 2 1/2 9 binsearch lcp 2,4,6 7, 16, ,2,3 22, 34, lcp lcp binsearch lcp 8 while lcp lcp 9 10 lcp lcp binsearch lcp GB lcp lcp 9 10

12 Vol. 0 No Av. of the number of skipped suffixes Size (Mainichi) lcp-18-2 lcp-18-4 lcp Size-1 5 8),16) Size-5 lcp Fig. 11 Average of the number of skipped suffixes on Mainichi (graphs of Size-1 to 5 and the table of Size-5). lcp Av. of the number of skipped suffixes Size (BNC) lcp-9-1 lcp-9-2 lcp BNC Size-1 5 Size-5 Fig. 12 Average of the number of skipped suffixes on BNC (graphs of Size-1 to 5 and the table of Size-5) ) lcp 8),16) for )

13 the 15th International Conference on Computational Linguistics (COLING 94), pp (1994). 11) Navarro, G.: A Guided Tour to Approximate String Matching, ACM Computing Surveys, Vol. 33, No. 1, pp (2001). 12) Navarro, G. and Baeza-Yates, R.: A Hybrid Indexing Method for Approximate String Matching, Journal of Discrete Algorithms, Vol. 1, No. 1, pp (2000). 13) Shang, H. and Merrettal, T. H.: Tries for Approximate String Matching, IEE Transactions on Knowledge and Data Engineering, Vol. 8, No. 4, pp (1996). 14) Ukkonen, E.: Finding Approxmate Patterns in Strings, Journal of Algorithms, Vol. 6, pp (1985). 15) Ukkonen, E.: Approximate String-Matching over Suffix Trees, Proc. of the 4th Annual Symposium on Combinatorial Pattern Matching (CPM 93), pp (1993). 16) Yamamoto, M. and Church, K. W.: Using Suffix Arrays to Compute Term Frequency and Document Frequency for All Substrings in a Corpus, Computational Linguistics, Vol. 27, No. 1, pp (2001). 1) Baeza-Yates, R. and Gonnet, G.: All-Against- All Sequence Matching, Technical report, Department of Computer Science, University of Chile (1990). 2) Baeza-Yates, R. and Gonnet, G.: A Fast Algorithm on Average for All-Against-All Sequence Matching, Proc. of the 6th Symposium on String Processing and Information Retrieval (SPIRE 99), pp (1999). 3) Baldwin, T.: Low-cost, High-performance Translation Retrieval: Dumber is Better, Proc. of the 39th Annual Meeting and 10th Conference of the Europena Chapter of the Association for Computational Linguistics (ACL- EACL 2001), pp (2001). 4) Baldwin, T. and Tanaka, H.: The Effects of Word Order and Segmentation on Translation Retrieval Performance, Proc. of the 18th International Conference on Computational Linguistics (COLING 2000), pp (2000). 5) Cobbs, A.: Fast Approximate Matching using Suffix Trees, Proc. of the 6th Annual Symposium on Combinatorial Pattern Matching (CP- M 95), pp (1995). 6) Gusfield, D.: Algorithms on Strings, Trees, and Sequences, Cambridge University Press (1997). 7) Ikehara, S., Shirai, S. and Uchino, H.: A Statistical Method for Extracting Uninterrupted and Interrupted Collocations form Very Large Corpora, Proc. of the 16th International Conference on Computational Linguistics (COL- ING 96), pp (1996). 8),, 17),,,,,,, ( ):, (1990). ( ) ( ) : ACL, 1999 LA (1999). 9) Manber, U. and Myers, G.: Suffix Arrays: A new method for on-line string searches, SIAM Journal on Computing, Vol. 22, No. 5, pp (1993). 10) Nagao, M. and Mori, S.: A New Method of N-gram Statistics for Large Number of n and Automatic Extraction of Words and Phrases from Large Text Data of Japanese, Proc. of

14 Vol. 0 No

[2] OCR [3], [4] [5] [6] [4], [7] [8], [9] 1 [10] Fig. 1 Current arrangement and size of ruby. 2 Fig. 2 Typography combined with printing

[2] OCR [3], [4] [5] [6] [4], [7] [8], [9] 1 [10] Fig. 1 Current arrangement and size of ruby. 2 Fig. 2 Typography combined with printing 1,a) 1,b) 1,c) 2012 11 8 2012 12 18, 2013 1 27 WEB Ruby Removal Filters Using Genetic Programming for Early-modern Japanese Printed Books Taeka Awazu 1,a) Masami Takata 1,b) Kazuki Joe 1,c) Received: November