| Title:
|
Tuning the Zhu-Takaoka string matching algorithm and experimental results (English) |
| Author:
|
Berry, Thomas |
| Author:
|
Ravindran, Somasundaram |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 |
| Volume:
|
38 |
| Issue:
|
1 |
| Year:
|
2002 |
| Pages:
|
[67]-80 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
string matching algorithm |
| Keyword:
|
efficiency |
| MSC:
|
68P10 |
| MSC:
|
68Q25 |
| MSC:
|
68W32 |
| MSC:
|
68W40 |
| idZBL:
|
Zbl 1265.68362 |
| idMR:
|
MR1899847 |
| . |
| Date available:
|
2009-09-24T19:43:54Z |
| Last updated:
|
2015-03-24 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/135446 |
| . |
| Reference:
|
[1] Apostolico A., Giancarlo R.: The Boyer–Moore–Galil string strategies revisited.SIAM J. Comput. 15 (1986), 1, 98–105 MR 0822195, 10.1137/0215007 |
| Reference:
|
[2] Baeza–Yates R. A.: Improved string searching.Software – Practice and Experience 19 (1989), 3, 257–271 10.1002/spe.4380190305 |
| Reference:
|
[3] Boyer R. S., Moore J. S.: A fast string searching algorithm.Comm. ACM 23 (1977), 5, 1075–1091 Zbl 1219.68165 |
| Reference:
|
[4] Charras C., Lecroq T.: Exact string matching, available at:http:--www.dir.univ-rouen.fr/ lecroq/string.ps (1998) |
| Reference:
|
[5] Charras C., Lecroq T.: Exact string matching animation in JAVA available at:http:--www.dir.univ-rouen.fr/ charras/string/ (1998) |
| Reference:
|
[6] Crochemore M., Czumaj A., Gasieniec L., Jarominek L., Lecroq T., Plandowski, W., Rytter W.: Speeding up two string matching algorithms.Algorithmica 12 (1994), 4, 247–267 Zbl 0942.68574, MR 1289482, 10.1007/BF01185427 |
| Reference:
|
[7] Crochemore M., Lecroq T.: Tight bounds on the complexity of the Apostolico–Giancarlo algorithm.Inform. Process. Lett. 63 (1997), 4, 195–203 MR 1477304, 10.1016/S0020-0190(97)00107-5 |
| Reference:
|
[8] Crochemore M., Rytter W.: Text Algorithms.Oxford University Press 1994 Zbl 1078.68151, MR 1307378 |
| Reference:
|
[9] 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 |
| Reference:
|
[10] Horspool R. N.: Practical fast searching in strings.Software – Practice and Experience 10 (1980), 6, 501–506 10.1002/spe.4380100608 |
| Reference:
|
[11] Hume A., Sunday D.: Fast string searching.Software – Practice and Experience 21 (1991), 11, 1221–1248 10.1002/spe.4380211105 |
| Reference:
|
[12] Knuth D. E., Jr. J. H. Morris, Pratt V. R.: Fast pattern matching in strings.SIAM J. of Comput. 6 (1980), 1, 323–350 MR 0451916 |
| Reference:
|
[13] Liu Z., Du X., Ishi N.: An improved adaptive string searching algorithm.Software – Practice and Experience 28 (1998), 2, 191–198 10.1002/(SICI)1097-024X(199802)28:2<191::AID-SPE149>3.0.CO;2-2 |
| Reference:
|
[14] 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 |
| Reference:
|
[15] Raita T.: Tuning the Boyer–Moore–Horspool string searching algorithm.Software – Practice and Experience 22 (1992), 10, 879–884 10.1002/spe.4380221006 |
| Reference:
|
[16] Smith P. D.: Experiments with a very fast substring search algorithm.Software – Practice and Experience 21 (1991), 10, 1065–1074 10.1002/spe.4380211006 |
| Reference:
|
[17] Smit G. V. de: A comparison of three string matching algorithms.Software – Practice and Experience 12 (1982), 57–66 Zbl 0466.68050, 10.1002/spe.4380120106 |
| Reference:
|
[18] Sunday D. M.: A very fast substring search algorithm.Comm. ACM 33 (1990), 8, 132–142 |
| Reference:
|
[19] Rytter W.: A correct preprocessing algorithm for Boyer–Moore string searching.SIAM J. Comput. 9 (1980), 509–512 Zbl 0446.68049, MR 0584507, 10.1137/0209037 |
| Reference:
|
[20] 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 Zbl 0641.68134 |
| . |
