Open AccessAPPLYING A Q-GRAM BASED MULTIPLE STRING MATCHING ALGORITHM FOR APPROXIMATE MATCHING
Author(s) -
Robert Susik
Publication year - 2017
Publication title -
informatyka, automatyka, pomiary w gospodarce i ochronie środowiska
Language(s) - English
Resource type - Journals
eISSN - 2391-6761
pISSN - 2083-0157
DOI - 10.5604/01.3001.0010.5214
Subject(s) - string searching algorithm , pattern matching , matching (statistics) , algorithm , commentz walter algorithm , approximate string matching , computer science , string (physics) , 3 dimensional matching , string metric , blossom algorithm , pattern recognition (psychology) , mathematics , artificial intelligence , mathematical physics , statistics
We consider the application of multiple pattern matching (Multi AOSO on q-Grams) algorithm for approximate pattern matching. We propose the on-line approach which translates the problem from approximate pattern matching into a multiple pattern one (called partitioning into exact search). Presented solution allows relatively fast search multiple patterns in text with given k-differences(or mismatches). This paper presents comparison of solution based on MAG algorithm, and [4]. Experiments on DNA, English, Proteins and XML texts with up to k errors show that the new proposedalgorithm achieves relatively good results in practical use.