Microsoft Word - 1 刘洪磊_new_.doc

Size: px

Start display at page:

Download "Microsoft Word - 1 刘洪磊_new_.doc"

豆尘钱
4 years ago
Views:

1 ISSN CODEN JKYTA8 Journal of Frontiers of Computer Science and Technology /2011/05(09) Tel: DOI: /j.issn * 刘洪磊, 杨晓春 +, 王斌, 金蓉, Approximate Substring Query Algorithms Supporting Local Optimal Matching * LIU Honglei, YANG Xiaochun +, WANG Bin, JIN Rong College of Information Science and Engineering, Northeastern University, Shenyang , China + Corresponding author: yangxc@mail.neu.edu.cn LIU Honglei, YANG Xiaochun, WANG Bin, et al. Approximate substring query algorithms supporting local optimal matching. Journal of Frontiers of Computer Science and Technology, 2011, 5(9): Abstract: The algorithms of approximate string query based on edit distance have usually a given threshold k, and report those strings whose edit distances with the query are not bigger than k. However, when talking about approximate substring query, many answers got in this way have overlap, thus meaningless. So this paper proposes a concept of local optimal matching only computing those answers which are both not higher than k and local optimal, thus eliminating the overlapped answers and cutting the time cost. It also presents a definition of approximate substring query supporting local optimal matching along with a query algorithm based on gram index. Moreover, it analyzes the generality of the matching process, and studies the methods of filtering and limiting the boundary based on local optimal matching. Finally, it proposes an algorithm of local optimal approximate substring query with filtering, so that the efficiency of matching is promoted. Key words: substring query; fuzzy query; gram index; edit distance 基于编辑距离的字符串近似查询算法一般是先给定阈值 k, 然后计算那些与查询串的编辑距离小于或等于 k 的结果但是对于近似子串查询, 结果中有很多是交叠的, 并且是无意义的, 于是提出了一种局 *The National Natural Science Foundation of China under Grant No , , ( ); the Fundamental Research Funds for the Central Universities under Grant No. N , N , N ( ). Received , Accepted

2 770 Journal of Frontiers of Computer Science and Technology 2011, 5(9) 部最优化匹配的概念, 只计算那些符合阈值条件, 并且是局部最优的结果, 这样不仅避免了结果的交叠, 而且极大节省了时间开销给出了支持局部最优化匹配的近似子串查询的定义, 相应提出了一种基于 gram 索引的局部最优化近似子串查询算法, 分析了子串近似匹配过程中的规律, 研究了基于局部最优化匹配的边界限定和过滤策略, 给出了一种过滤优化的局部最优化近似子串查询算法, 提高了查询效率子串查询 ; 模糊查询 ; gram 索引 ; 编辑距离 A TP ,,, DNA Internet,, Levenshtein 1965 (edit distance, Levenshtein distance) [1], Sankoff Kruskal 1983 Hamming distance [2], Das 1997 Episode distance [3], Needleman Wunsch 1970 longest common subsequence distance [4],, k, k,, 1 1 T= dynamicprogramming P= progrem, T P, k=2, T progr progra program programm P, P 2,,,,, program, T P, T P :, Web,, : (1),, (2) gram (3),, (4) gram, (5), : 2 ; 3 ; 4 gram ; 5, ; 6 ; 7

3 : 771 ; 8, 2,, Knuth [5] Knuth-Morris-Pratt Boyer Moore [6] Boyer-Moore ; [7] gram, [8],, DNA, gram gram, program 2-gram {pr,ro,og,gr,ra,am} [9 12] gram [10] [11 12] gram, VGRAM(variable-length grams) gram, VGRAM gram,, [13], [14], [7] gram, gram, [15] BLAST(basic local alignment search tool) 3 3.1, 1( [1] ),, 2 2 s 1 = program s 2 = progrem, s 2 s 1 e a, ed(s 1,s 2 )=1 x y, x[1,i] y[1,j] x y i j x y C, C i,j x[1,i] y[1,j] x[1,i] i, C i,0 =i, C 0,j =j : C i, j C x = y = 1 + min( C, C, C ) x y i 1, j 1 i j i 1, j i, j 1 i 1, j 1 i j ed(x,y)=c x, y C i,j : x i =y j,, C i 1,j 1 ; x i y j,, 2( ) 3 3 T= dynamicprogramming, P= progrem, P T 12, P T 14 m 1, P T program, x=p, y=t, T

2 The result of approximate substring query supporting local optimal matching 2 Fig.

4 772 Journal of Frontiers of Computer Science and Technology 2011, 5(9) C i,j P[1,i] T T j, Ci, j min ed( P[1, i], T[ k, j]) = k j C 0,j =0, 1 3 T P P T program 1,, Fig.2 The result of approximate substring query supporting local optimal matching 2 Fig.1 The matrix for calculating edit distance 1 3.2, m i T i P, 1, k, m i k, 1 1, k=2, T progr progra program programm, program, 3 ( ) T P, R : R T, T R R P, R P T 2 1, 4( ) T P, R, R P k, R 4 2, k=2, 4,,, program,, 4 gram 4, 3.1 T,,, O(mn), m n P T

5 : 773,, Naïve, gram, [9,16] gram gram gram,, gram q-gram q, k, gram,, gram q k program 2-gram {pr,ro,og,gr,ra,am}, progrem 2-gram {pr,ro,og,gr,re,em}, 4 gram s 1 s 2, ed(s 1,s 2 ) k, s 1 s 2 k, max{ s 1, s 2 }+1 (k+1) q q-gram R={r 1,r 2,,r n }, ed(p,r i ) k, 1 k, r i P +k r 1 ed(p,r i ) k, r 1 P k, k r 1 P, k, k 2 r i P +1 (k+1) q q-gram P, q-gram P +1 q k, k q gram, k, P +1 (k+1) q q-gram 5 5 T= dynamicprogramming, P= progrem, k=2, q=2, 2, P 2 2-gram gram, gram, gram, :, gram 4.2, T,, 1, P +k, P +k, 2, P gram, gram, 5(gram ) P gram T gram, P T 3, gram P g p, T g t,, gram g end : gend = gt+ P gp Fig.3 Gram base positions and candidate regions to verify 3 gram 6 (gram ) gram, gram, gram

6 774 Journal of Frontiers of Computer Science and Technology 2011, 5(9) 3, k,, gram, gram i, max( g + q 1, g k) i g + k t end 1 P gram T, 2 gram,, P +k gram, P 2 1, P +k 1,, 4.3 1, gram (gram-based local optimal approximate substring query algorithm, GASQ) end 7. for (each pos in FR){ 8. count=count(pos); // pos 9. if (count is greater than lowerbound){ 10. region=[pos P k+1,pos]; // 11. Verify(region); // Naïve 12. }// if 13. }// for 14. }// while 6 4, P= AGTC, T= GAAGGTCTCA, k=1, gram 1 P gram,, ; gram, gram, AG T 3, P 1 gram 6; gram,, gram 1, , 5 GASQ : P gram, gram ; gram gram T, gram gram, gram ; gram,,, 5,, 1 gram : P, T, gram G, k : 1. P gram 2. G L 3. L gram L 4. while ( L is not empty){ 5. smallest=mergheap(l ); // 6. FR=Fuzzy(smallest); //gram Fig.4 The flow of the algorithm 4 5 6,, P k 4,,,

7 : 775 LOB(local optimal boundary constraint) LOF(local optimal filtering), 5.1 4, 2, i, m i < m i 1 m i m i+1 T i, 2,, i 1 i,, T i P P k, 3 T i, T i T i : T P[ P k, P ] i 2, 3 2 5, T i, 3, T i P j, M (mismatch zone),,, M, i, M 4 i, 5 M T P, Ti [ + 1, i+ P j] Pj [ + 1, P ] = 3 4 T P k, M P P,, M 7 6, , 5 G k, 4, 6 T C, 5 Σ, Σ, P k Σ, 毎,,,,, ;,,,,, M,, 2 Fig.5 The matching process of extreme value point 5 : i, MTable : 1. Σ ETable; 2. Q; 3. while (T i exists in ETable){ 4. Q.pop();

8 776 Journal of Frontiers of Computer Science and Technology 2011, 5(9) 5. ETable ; 6. }// while 7. MTable T i C; 8. C ETable ; 9. Q.push(T i ); 10. if (length of Q is greater than M ){ 11. pos=q.front(); 12. pos region; 13. return region; 14. }// if P +k, 4, 6, R, 3 R P j, 5, ed(r,p) M, M ed(r,p) k, ed(r,p[1,j]) k M 1 R P +k 2 M, 5 P + k 2 M, i, P +k 2 M 1 8 6, 7, C, M=0, P +k 1, 4 6 gram, (gram-based local optimal approximate substring query algorithm with filtering, FGASQ ) FGASQ GASQ,, 3 : P, T, gram G, k : 1. GASQ IsEx=Filter(pos); // 11. if (IsEx is true){ // 12. region=[pos P k+2 M +1,pos]; 13. Verify(region);// Naïve 14. }// if GASQ FGASQ 6, 4,, 6 7 8, 5 6, 4 Fig.6 The difference between FGASQ and GASQ 6 FGASQ GASQ 7 : (1) Ubuntu(Linux) 10.04; (2) Virtualbox, Pentium Dual-Core CPU E5200@2.5GHz, 1 GB RAM DNA (10M) T, T 150 P 100 P

9 : 777 7( ) Naïve, : 被验证的区域大小的总和验证区域比例 = 被查询长串的长度, 7.1 GASQ FGASQ, 7,,, FGASQ GASQ, 25%, 8 7, gram q,, q, gram Fig.8 Comparison between GASQ and FGASQ when P =150 and q=13 8 GASQ FGASQ P =150 q=13 Fig.7 Comparison between GASQ and FGASQ when P =150 and q=9 7 GASQ FGASQ P =150 q=9 7.2 q gram q, q GASQ FGASQ

10 778 Journal of Frontiers of Computer Science and Technology 2011, 5(9) 9, q, q P gram,,, q,, 9(a) k=9, q=13, 9(b) q=13, q=13, gram, Fig Effects of different q on FGASQ when P =150 FGASQ P =150 q 8 Fig.9 Effects of different q on GASQ when P =150 9 GASQ P =150 q 10 9, 9, FGASQ GASQ,, gram,, gram,,,

: 779 References: [1] Levenshtein V I. Binary codes capable of correcting spurious insertions and deletions of ones[j]. Problems of Information Transmission, 1965, 1(1): 8 17.

11 : 779 References: [1] Levenshtein V I. Binary codes capable of correcting spurious insertions and deletions of ones[j]. Problems of Information Transmission, 1965, 1(1): [2] Sankoff D, Kruskal J. Time warps, string edits, and macromolecules: the theory and practice of sequence comparison[m]. Reading, UK: Addison-Wesley Publication, [3] Das G, Fleisher R, Gasieniek L, et al. Episode matching[c]// LNCS 1264: Proceedings of the 8th Annual Symposium on Combinatorial Pattern Matching (CPM 97), Aarhus, Denmark, June 30-July 2, [S.l.]: Springer, 1997: [4] Needleman S, Wunsch C. A general method applicable to the search for similarities in the amino acid sequences of two proteins[j]. Journal of Molecular Biology, 1970, 48(3): [5] Knuth D E, Morris J H, Pratt V R. Fast pattern matching in strings[j]. SIAM Journal on Computing, 1977, 6(2): [6] Boyer R S, Moore J S. A fast string searching algorithm[j]. Communications of the ACM, 1977, 20(10): [7] Kim Y, Woo K G, Park H, et al. Efficient processing of substring match queries with inverted q-gram indexes[c]// Proceedings of the IEEE 26th International Conference on Data Engineering (ICDE 10). Washington, DC, USA: IEEE Computer Society, 2010: [8] Navarro G. A guided tour to approximate string matching[j]. ACM Computing Surveys, 2001, 33(1): [9] Kim M S, Whang K Y, Lee J G, et al. n-gram/2l: a space and time efficient two-level n-gram inverted index structure[c]//proceedings of the 31st International Conference on Very Large Data Bases (VLDB 05), 2005: [10] Zobel J, Moffat A. Inverted files for text search engines[j]. ACM Computing Surveys, 2006, 38(2). [11] Yang Xiaochun, Wang Bin, Li Chen. Cost-based variablelength-gram selection for string collections to support approximate queries efficiently[c]//proceedings of the 2008 ACM SIGMOD International Conference on Management of Data (SIGMOD 08). New York, NY, USA: ACM, 2008: [12] Li Chen, Wang Bin, Yang Xiaochun. VGRAM: improving performance of approximate queries on string collections using variable length grams[c]//proceedings of the 33rd International Conference on Very Large Data Bases (VLDB 07), 2007: [13] Li Chen, Lu Jiaheng, Lu Yiming. Efficient merging and filtering algorithms for approximate string searches[c]// Proceedings of the IEEE 24th International Conference on Data Engineering (ICDE 08). Washington, DC, USA: IEEE Computer Society, 2008: [14] Krauthgamer R, Mehta A, Raman V, et al. Greedy list intersection[c]//proceedings of the IEEE 24th International Conference on Data Engineering (ICDE 08). Washington, DC, USA: IEEE Computer Society, 2008: [15] Altschul S F, Gish W, Miller W, et al. Basic local alignment search tool[j]. Journal of Molecular Biology, 1990, 215(3): [16] Behm A, Ji Shengyue, Li Chen, et al. Space-constrained gram-based indexing for efficient approximate string search[c]//proceedings of the IEEE 25th International Conference on Data Engineering (ICDE 09). Washington, DC, USA: IEEE Computer Society, 2009: LIU Honglei was born in He is a master candidate at Northeastern University. His research interests include approximate string query and bioinformatics. (1988 ),,,,,

780 Journal of Frontiers of Computer Science and Technology 2011, 5(9) YANG Xiaochun was born in 1973.

Now she is a professor and doctoral supervisor at Northeastern University, and the senior member of CCF.

(1973 ),,, 2001,, CCF,,, WANG Bin was born in 1972. He is a lecturer at Northeastern University.

(1972 ),,,,, JIN Rong was born in 1988. She is a master candidate at Northeastern University.

12 780 Journal of Frontiers of Computer Science and Technology 2011, 5(9) YANG Xiaochun was born in She received her Ph.D. degree in Computer Software and Theory from Northeastern University in Now she is a professor and doctoral supervisor at Northeastern University, and the senior member of CCF. Her research interests include theory and technology of database, data quality analysis and data privacy, etc. (1973 ),,, 2001,, CCF,,, WANG Bin was born in He is a lecturer at Northeastern University. His research interests include distributed database management and system structure. (1972 ),,,,, JIN Rong was born in She is a master candidate at Northeastern University. Her research interest is approximate text search. (1988 ),,,, 2012, 16, 96, 30, , ( ) , 16, 248, , 38.5, , ( ) : (010)

7 2 2012 26 (1) ( ) : (3), (12) (7) (10)

1 2 3.4 1* 3* (Case-based reasoning) (15) 2012 7(2) 25-45 1 2 3 4 168 (05)2720411 ~ 33110, : naiwei@cs.ccu.edu.tw (05)2648000-5542 :yehlinlo@gmail.com 7 2 2012 25 7 2 2012 26 (1) ( ) : (3), (12) (7) (10)