The Performance of the Character-Access on the Checking Phase in String Searching Algorithms

Authors: Mahmoud M. Mhashi

Abstract:

A new algorithm called Character-Comparison to Character-Access (CCCA) is developed to test the effect of both: 1) converting character-comparison and number-comparison into character-access and 2) the starting point of checking on the performance of the checking operation in string searching. An experiment is performed; the results are compared with five algorithms, namely, Naive, BM, Inf_Suf_Pref, Raita, and Circle. With the CCCA algorithm, the results suggest that the evaluation criteria of the average number of comparisons are improved up to 74.0%. Furthermore, the results suggest that the clock time required by the other algorithms is improved in range from 28% to 68% by the new CCCA algorithm

Keywords: Pattern matching, string searching, charactercomparison, character-access, and checking.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1335454

References:

[1] D. E. Knuth, J. H. Morris, and V. R Pratt., Fast pattern matching in strings, SIAM J. Comput. Vol. 6, no. 2, pp. 323-350, 1977.
[2] RS. Boyer, and JS. Moore, A fast string searching algorithm. Communications of the ACM Vol. 20, no. 10, pp. 762-772, 1977.
[3] A. Apostolico, and R. R.Giancarlo, "The Boyer-Moore-Galil string searching strategies revisited", SIAM J. Comput. Vol. 15, no. 1, pp. 98- 105, 1986.
[4] G. De, V. Smit, A comparison of three string matching algorithms, Software-Practice and Experience Vol. 12, pp. 57-66, 1982.
[5] A. Blumer, J. Blumer, A. Ehrenfeucht, D. Haussler, M. T. Chen, J. Seiferas, The smallest automaton recognizing the subwords of a text, Theoret. Comput. Sci., Vol. 40, pp. 31-55, 1985.
[6] M. Crochemore, Transducers and repetitions, Theoret. Comput. Sci., Vol. 45, pp. 63-86, 1986.
[7] M. Crochemore, D. Perrin, Two-way string-matching, J. ACM, Vol. 38, pp. 651-675, 1991.
[8] L. Colussi, Correctness and efficiency of the pattern matching algorithms, Information and Computation, Vol. 95, pp. 225-251, 1991.
[9] Z. Galil, R. Giancarlo, On the exact complexity of string matching: upper bounds, SIAM J. Comput. Vol. 21, pp. 407-437, 1992.
[10] P. D. Smith, Experiments with a very fast substring search algorithm, Software-Practice and Experience Vol. 21, no. 10, pp. 1065-1074, 1991.
[11] D. M. Sunday, A very fast substring search algorithm, Communications of the ACM Vol. 33, no. 8, pp. 132-142, 1990.
[12] Z. Liu, X. Du, N. Ishii, An improved adaptive string searching algorithm, Software-Practice and Experience Vol. 28, no. 2, pp. 191- 198, 1998.
[13] P. Fenwick, Fast string matching for multiple searches, Software- Practice and Experience Vol. 31, no. 9, pp. 815-833, 2001.
[14] M. Mhashi, A Fast String Matching Algorithm using Double-Length Skip Distances. Dirasat Journal, University of Jordan, Jordan Vol. 30, no. 1, pp. 84-92, 2003.
[15] P. Fenwick, Some perils of performance prediction: a case study on pattern matching. Software-Practice and Experience Vol. 31, no. 9, pp. 835-843, 2001.
[16] A. Al-jaber, M. Mhashi, A modified double skip algorithm in string searching, AMSE(Association for the advancement of modelling & Simulation Techniques in Enterprises) Periodicals Vol.8, no. 4, pp. 1-16, 2003.
[17] M. Mhashi, The effect of multiple reference characters on detecting matches in string searching algorithms, to appear in Software-Practice and Experience 2005.