Open Access Open Access  Restricted Access Subscription or Fee Access

Implementation of ECSA for String Matching

Dinesh Kumar Bhawnani, Siddhartha Choubey

Abstract


The problems of Exact string Searching had been investigated by many studies ranging from finding the shortest common super string in DNA sequencing to searching for occurrences of a pattern occurs in text editors. In this paper, the implementation of Naïve, Boyer-Moore-Horsepool and Enhanced Checking and Skipping Algorithm (ECSA) is introduced. The ECSA algorithm enhance the classical string searching algorithms by converting the character-comparison into character-access, by using the condition type character-access rather than the number-comparison, and by starting the comparison at the latest mismatch in the previous checking, which in turn increases the probability of finding the mismatch faster if there is any. A computer program is developed to compare the performance of the ECSA algorithm against the conventional Naïve (brute force) and Boyer-Moore-Horsepool (BMH) algorithms. The results of the experiment show that the performance of the enhanced algorithm is outperform the performance of the introduced algorithms.

Keywords


Checking and Skipping, Condition Type, Multiple References, Pattern Matching and String-Searching

Full Text:

PDF

References


Ukkonen E., "A linear–time algorithm for finding approximate shortest common superstring", Algorithmica, 1990; 5:313–323.

Stephen G., "String Searching Algorithms", World Scientific, Singapore, 1994.

Apostolico, "A, Galil Z. Pattern Matching Algorithms", Oxford University Press, 1997.

Gusfield D., "Algorithms on strings, trees and sequences", Cambridge University Press, Cambridge, 1997.

Fenwick P., "Fast string matching for multiple searches", Software–Practice and Experience, 2001, 31(9):815–833.

Liu Z, Du X,and Ishii N., "An improved adaptive string searching algorithm", Software Practice and Experience, 1988, 28(2):191–198.

Sunday D., "A very fast substring search algorithm", Communications of the ACM, 1990, 33(8):132–142.

Raita T., "Tuning the Boyer-Moore-Horspool String Searching Algorithm", Software Practice and Experience, 1992, 22 (10):879-844.

Bruce W., Watson, E., "A Boyer-Moore-style Algorithm for Regular Expression Pattern Matching", Science of Computer Programming, 2003, 48: 99-117.

Ager M. S., Danvy O., and Rohde H. K., "Fast partial evaluation of pattern matching in strings", ACM/SIGPLAN Workshop Partial Evaluation and Semantic-Based Program Manipulation, San Diego, California, USA, pp. 3 – 9, 2003.W.-K. Chen, Linear Networks and Systems (Book style)., Belmont, CA: Wadsworth, 1993, pp. 123–135.

Fredriksson and Grabowski S., “Practical and Optimal String Matching”, Proceedings of SPIRE'2005, Lecture Notes in Computer Science 3772, 2005, pp. 374-385, Springer Verlag.

Hernandez, and Rosenblueth D., “Disjunctive partial deduction of a right-to-left string-matching algorithm”, Information Processing Letters, 2003, 87: 235–241.

Apostolico A., and R.Giancarlo R., “The Boyer-Moore-Galil string searching strategies revisited”, SIAM J. Comput., 1986, 15(1): 98-105.

Crochemore, “Transducers and repetitions”, Theoret. Comput. Sci., 1986; 45: 63-86.

Crochemore M., and Perrin D., “Two-way string-matching”, J. ACM, 1991, 38: 651-675.

Galil Z., and Giancarlo R., “On the exact complexity of string matching: upper bounds”, SIAM J. Comput., 1992, 21: 407-437.

Smith P. D., “Experiments with a very fast substring search algorithm”, SP&E, 1991, 21(10): 1065-1074.

Smith P., "On Tuning the Boyer-Moore-Horspool String Searching Algorithm", Short Communication, Software Practice and Experience, 1994, 24(4):435-436.

Mhashi M., "A Fast String Matching Algorithm using Double-Length Skip Distances", Dirasat Journal, University of Jordan, Jordan, 2003, 30(1):84-92.

Mhashi M., "The Effectof Multiple Reference Characters on Detecting Matches in String Searching Algorithms", Software Practice and Experience, 2005, 35(13): 1299 - 1315.

Mhashi, M., "The Performance of the Character-Access On the Checking Phase in String Searching Algorithms", Transactions on Enformatica, Systems Sciences and Engineering, 2005, 9: 38 –43.

Boyer RS., and Moore JS., "A fast string searching algorithm", Communications of the ACM, 1977, 20(10):762–772.

Horspool RN., "Practical Fast Searching in Strings", Software Practice and Experience, 1980, 10(6):501–506.


Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.