Comparison criteria between matching algorithms texts application on (horspool's and brute force algorithms)

 
 
 
  • Abstract
  • Keywords
  • References
  • PDF
  • Abstract


    The subject of matching text or search the texts is important topics in the field of computer science and is used in many programs such as Microsoft word program in correct spelling mistakes and search &replace, and other uses. The aim of this study was to learn how to trade-off texts matching algorithms, which are very much where we have the application on Horspool's and Brute Force algorithms. According to the standard number of comparisons and time of execution. The study pointed on preference Horspool's algorithm.


  • Keywords


    Space and Time Tradeoffs; Put Enhancement in String Matching; Horspool's and Brute Force Algorithms.

  • References


      [1] R. N. Horspool (1980). "Practical fast searching in strings". Software - Practice & Experience 10 (6): 501–506. doi:10.1002/spe.4380100608. (Subscription required (help)). http://dx.doi.org/10.1002/spe.4380100608.

      [2] AHO, A.V., 1990, Algorithms for finding patterns in strings. in Handbook of Theoretical Computer Science, Volume A, Algorithms and complexity, J. van Leeuwen ed., Chapter 5, pp 255-300, Elsevier, Amsterdam.

      [3] BAEZA-YATES, R.A., RÉGNIER, M., 1992, Average running time of the Boyer-Moore-Horspool algorithm, Theoretical Computer Science 92(1):19-31. http://dx.doi.org/10.1016/0304-3975(92)90133-Z.

      [4] BEAUQUIER, D., BERSTEL, J., CHRÉTIENNE, P., 1992, Éléments d'algorithmique, Chapter 10, pp 337-377, Masson, Paris.

      [5] CROCHEMORE, M., HANCART, C., 1999, Pattern Matching in Strings, in Algorithms and Theory of Computation Handbook, M.J. Atallah ed., Chapter 11, pp 11-1--11-28, CRC Press Inc., Boca Raton, FL.

      [6] HANCART, C., 1993. Analyse exacte ET en moyenne d'algorithmes de recherche d'un motif dans UN texte, Ph. D. Thesis, University Paris 7, France.

      [7] HORSPOOL R.N., 1980, Practical fast searching in strings, Software - Practice & Experience, 10(6):501-506. http://dx.doi.org/10.1002/spe.4380100608.

      [8] LECROQ, T., 1995, Experimental results on string matching algorithms, Software - Practice & Experience 25(7):727-765. http://dx.doi.org/10.1002/spe.4380250703.

      [9] STEPHEN, G.A., 1994, String Searching Algorithms, World Scientific.

      [10] http://www-igm.univ-mlv.fr/~lecroq/string/node18.html.

      [11] http://polynomialtimes.com/algorithms/space-and-time-trade-offs/horspools-algorithm/.

      [12] http://www-igm.univ-mlv.fr/~lecroq/string/node3.html#SECTION0030.

      [13] Anany Levitin, the design and analyses of algorithms, third edition,9 October 2011 from the following web sites: ftp://doc.nit.ac.ir/cee/jazayeri/Algorithms/Books/Design%20&%20Analysis%20of%20Algorithm.pdf.

      [14] http://www-igm.univ-mlv.fr/~lecroq/string/node2.html.

      [15] http://www.algorithmic-solutions.info/leda_manual/string_matching.html.


 

View

Download

Article ID: 4283
 
DOI: 10.14419/jacst.v4i1.4283




Copyright © 2012-2015 Science Publishing Corporation Inc. All rights reserved.