APPLYING A Q-GRAM BASED MULTIPLE STRING MATCHING ALGORITHM FOR APPROXIMATE MATCHING

Robert Susik

rsusik@kis.p.lodz.pl
Lodz University of Technology (Poland)

Abstract

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 proposed algorithm achieves relatively good results in practical use.


Keywords:

text processing, approximate string matching, string algorithms, q-gram

Baeza-Yates R.A., Navarro G.: New and faster filters for multiple approximate string matching. Random Structures and Algorithms 20(1), 2011, 23–49.
  Google Scholar

Baeza-Yates R., Navarro G.: New and Faster Filters for Multiple Approximate String Matching. Random Structures and Algorithms 20/2002, 23–49.
  Google Scholar

Burkhardt S., Kärkkäinen J.: Better filtering with gapped q-grams. Fundam. Inform. 56(1-2)/2003, 51–70.
  Google Scholar

Fredriksson K., Navarro G.: Average-optimal single and multiple approximate string matching. ACM J. Exp. Alg. 9(1.4)/2004, 1–47.
  Google Scholar

Fredriksson K.: Shift–or string matching with super-alphabets. Information Processing Letters 87(1)/2003, 201–204.
  Google Scholar

Grossi R., Luccio F.: Simple and efficient string matching with k mismatches. Information Processing Letters 33(3)/1989, 113–120.
  Google Scholar

Jokinen P., Ukkonen E.: Two algorithms for approximate string matching in static texts. Proc. MFCS 16/1991, 240–248.
  Google Scholar

Landau G.M., Vishkin U.: Fast string matching with k differences. Journal of Computer and System Sciences 37(1)/1988, 63–78.
  Google Scholar

Susik R., Grabowski S., Fredriksson K.: Multiple Pattern Matching Revisited. Proceedings of PSC 2014, 59–70.
  Google Scholar

Ukkonen E.: Approximate string-matching with q-grams and maximal matches. Theoretical Computer Science 92/1992, 191–211.
  Google Scholar

Download


Published
2017-09-30

Cited by

Susik, R. (2017). APPLYING A Q-GRAM BASED MULTIPLE STRING MATCHING ALGORITHM FOR APPROXIMATE MATCHING. Informatyka, Automatyka, Pomiary W Gospodarce I Ochronie Środowiska, 7(3), 47–50. https://doi.org/10.5604/01.3001.0010.5214

Authors

Robert Susik 
rsusik@kis.p.lodz.pl
Lodz University of Technology Poland

Statistics

Abstract views: 169
PDF downloads: 118