Tuning the Zhu-Takaoka string matching algorithm and experimental results
Thomas Berry; Somasundaram Ravindran
Kybernetika (2002)
- Volume: 38, Issue: 1, page [67]-80
- ISSN: 0023-5954
Access Full Article
top
Abstract
topHow to cite
topBerry, Thomas, and Ravindran, Somasundaram. "Tuning the Zhu-Takaoka string matching algorithm and experimental results." Kybernetika 38.1 (2002): [67]-80. <http://eudml.org/doc/33567>.
@article{Berry2002,
abstract = {In this paper we present experimental results for string matching algorithms which have a competitive theoretical worst case run time complexity. Of these algorithms a few are already famous for their speed in practice, such as the Boyer–Moore and its derivatives. We chose to evaluate the algorithms by counting the number of comparisons made and by timing how long they took to complete a given search. Using the experimental results we were able to introduce a new string matching algorithm and compared it with the existing algorithms by experimentation. These experimental results clearly show that the new algorithm is more efficient than the existing algorithms for our chosen data sets. Using the chosen data sets over 1,500,000 separate tests were conducted to determine the most efficient algorithm.},
author = {Berry, Thomas, Ravindran, Somasundaram},
journal = {Kybernetika},
keywords = {string matching algorithm; efficiency; string matching algorithm; efficiency},
language = {eng},
number = {1},
pages = {[67]-80},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Tuning the Zhu-Takaoka string matching algorithm and experimental results},
url = {http://eudml.org/doc/33567},
volume = {38},
year = {2002},
}
TY - JOUR
AU - Berry, Thomas
AU - Ravindran, Somasundaram
TI - Tuning the Zhu-Takaoka string matching algorithm and experimental results
JO - Kybernetika
PY - 2002
PB - Institute of Information Theory and Automation AS CR
VL - 38
IS - 1
SP - [67]
EP - 80
AB - In this paper we present experimental results for string matching algorithms which have a competitive theoretical worst case run time complexity. Of these algorithms a few are already famous for their speed in practice, such as the Boyer–Moore and its derivatives. We chose to evaluate the algorithms by counting the number of comparisons made and by timing how long they took to complete a given search. Using the experimental results we were able to introduce a new string matching algorithm and compared it with the existing algorithms by experimentation. These experimental results clearly show that the new algorithm is more efficient than the existing algorithms for our chosen data sets. Using the chosen data sets over 1,500,000 separate tests were conducted to determine the most efficient algorithm.
LA - eng
KW - string matching algorithm; efficiency; string matching algorithm; efficiency
UR - http://eudml.org/doc/33567
ER -
References
top- Apostolico A., Giancarlo R., 10.1137/0215007, SIAM J. Comput. 15 (1986), 1, 98–105 (1986) MR0822195DOI10.1137/0215007
- Baeza–Yates R. A., 10.1002/spe.4380190305, Software – Practice and Experience 19 (1989), 3, 257–271 (1989) DOI10.1002/spe.4380190305
- Boyer R. S., Moore J. S., A fast string searching algorithm, Comm. ACM 23 (1977), 5, 1075–1091 (1977) Zbl1219.68165
- Charras C., Lecroq T., Exact string matching, available at:http:--www, dir.univ-rouen.fr/ lecroq/string.ps (1998) (1998)
- Charras C., Lecroq T., Exact string matching animation in JAVA available at:http:--www, dir.univ-rouen.fr/ charras/string/ (1998) (1998)
- Crochemore M., Czumaj A., Gasieniec L., Jarominek L., Lecroq T., Plandowski, W., Rytter W., 10.1007/BF01185427, Algorithmica 12 (1994), 4, 247–267 (1994) Zbl0942.68574MR1289482DOI10.1007/BF01185427
- Crochemore M., Lecroq T., 10.1016/S0020-0190(97)00107-5, Inform. Process. Lett. 63 (1997), 4, 195–203 (1997) MR1477304DOI10.1016/S0020-0190(97)00107-5
- Crochemore M., Rytter W., Text Algorithms, Oxford University Press 1994 Zbl1078.68151MR1307378
- Hancart C., Analyse exacte et en moyenne d’algorithmes de recherche d’un motif dans un texte, These de doctorat de l’Universite de Paris 7, 1993
- Horspool R. N., 10.1002/spe.4380100608, Software – Practice and Experience 10 (1980), 6, 501–506 (1980) DOI10.1002/spe.4380100608
- Hume A., Sunday D., 10.1002/spe.4380211105, Software – Practice and Experience 21 (1991), 11, 1221–1248 (1991) DOI10.1002/spe.4380211105
- Knuth D. E., Jr. J. H. Morris, Pratt V. R., Fast pattern matching in strings, SIAM J. of Comput. 6 (1980), 1, 323–350 (1980) MR0451916
- Liu Z., Du X., Ishi N., 10.1002/(SICI)1097-024X(199802)28:2<191::AID-SPE149>3.0.CO;2-2, Software – Practice and Experience 28 (1998), 2, 191–198 (1998) DOI10.1002/(SICI)1097-024X(199802)28:2<191::AID-SPE149>3.0.CO;2-2
- Melichar B., Approximate string matching by finite automata, In: Computer Analysis of Images and Patterns (Lecture Notes in Computer Scince 970), Springer–Verlag, Berlin 1995, pp. 342–349 (1995)
- Raita T., 10.1002/spe.4380221006, Software – Practice and Experience 22 (1992), 10, 879–884 (1992) DOI10.1002/spe.4380221006
- Smith P. D., 10.1002/spe.4380211006, Software – Practice and Experience 21 (1991), 10, 1065–1074 (1991) DOI10.1002/spe.4380211006
- Smit G. V. de, 10.1002/spe.4380120106, Software – Practice and Experience 12 (1982), 57–66 (1982) Zbl0466.68050DOI10.1002/spe.4380120106
- Sunday D. M., A very fast substring search algorithm, Comm. ACM 33 (1990), 8, 132–142 (1990)
- Rytter W., 10.1137/0209037, SIAM J. Comput. 9 (1980), 509–512 (1980) Zbl0446.68049MR0584507DOI10.1137/0209037
- Zhu R. F., Takaoka T., On improving the average case of the Boyer–Moore string matching algorithm, J. Inform. Process. 10 (1987), 3, 173–177 (1987) Zbl0641.68134
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.