A comparative analysis of string searching algorithms

Jacek Widuch

Abstract


One of the text processing problems is the pattern matching problem. The goal of the problem is to find all places where one text or string, called pattern, is found within the given text. In this paper, a comparative analysis of existing string matching algorithms is presented, and the comparison criterion is the time of searching the pattern in the text. The results of the tests are also presented.

Keywords


text; pattern; alphabet; string searching; prefix; suffix; prefix function

Full Text:

PDF (Polski)

References


Abu–Alhaj M. M., Halaiyqah M., Abu–Hashem M. A., Hnaif A. A., Abouabdalla O., Manasrah A. M.: An innovative platform to improve the performance of exact string matching algorithms. International Journal of Computer Science and Information Security, Vol. 7, No. 1, 2010, s. 280÷283.

Adjeroh D., Bell T., Mukherjee A.: The Burrows–Wheeler Transform: Data Compression, Suffix Arrays, and Pattern Matching. Springer, 2008.

Atallah M. J.: Algorithms and Theory of Computation Handbook. CRC-Press, 1st edition, 1998.

Boyer R. S., Moore J. S.: A Fast String Searching Algorithm. Communications of the ACM, Vol. 20, No. 10, 1977, s. 762÷772.

Charras Ch., Lecroq T.: Handbook of Exact String Matching Algorithms. College Publications, 2004.

Cormen T. H., Leiserson Ch. E., Rivest R. L.: Wprowadzenie do algorytmów. WNT, Warszawa 2000.

Crochemore M., Rytter W.: Jewels of Stringology. World Scientific Pub Co Inc, 1st edition, 2002.

Gusfield D.: Algorithm on strings, trees, and sequences. Cambridge University Press, 1997.

Hancart C.: Une analyse en moyenne de l'algorithme de Morris et Pratt et de ses raffinements. Théorie des Automates et Applications, Actes des 2e Journées Franco–Belges, D. Krob ed., Rouen, France, 1992, s. 99÷110.

Hancart C.: Analyse exacte et en moyenne d'algorithmes de recherche d'un motif dans un texte, Thése de doctorat de l'Université de Paris , France, 1993.

Horspool R. N.: Practical fast searching in strings. Software – Practice and Experience, Vol. 10, No. 6, 1980, s. 501÷506.

Karp R. M., Rabin M. O.: Efficient randomized pattern–matching algorithms. Technical Report TR–31–81 , Aiken Computation Laboratory, Harvard University, 1981.

Knuth D., Morris Jr. J. H., Pratt V.: Fast pattern matching in strings. SIAM Journal on Computing, Vol. 6, No. 2, 1977, s. 323÷350.

Manber U., Myers E.W.: Suffix Arrays: A New Method for On-Line String Searches. SIAM Journal of Computing, Vol. 22, No. 5, 1993, s. 935÷948.

Raita T.: Tuning the Boyer–Moore–Horspool string searching algorithm. Software – Practice & Experience, Vol. 22, No. 10, 1992, s. 879÷884.

Smith s. D.: Experiments with a very fast substring search algorithm. Software – Practice and Experience, Vol. 21, No. 10, 1991, s. 1065÷1074.

Sunday D. M.: A very fast substring search algorithm. Communications of the ACM, Vol. 33, No. 8, s. 132÷142, 1990.




DOI: http://dx.doi.org/10.21936/si2013_v34.n1.4