CFP last date
22 April 2024
Call for Paper
May Edition
IJCA solicits high quality original research papers for the upcoming May edition of the journal. The last date of research paper submission is 22 April 2024

Submit your paper
Know more
The week's pick
Responsive image
Enhancing Privacy Preservation: Multi-Attribute Protection with P-Sensitive K-Anonymity

Twinkle Patel Kiran Amin
Random Articles
Reseach Article

Comparative Study between Various Pattern Matching Algorithms

Published on September 2016 by Pranit Chettri, Chinmoy Kar
journal_cover_thumbnail

International Conference on Computing and Communication
Foundation of Computer Science USA
ICCC2016 - Number 1
September 2016
Authors: Pranit Chettri, Chinmoy Kar
3b0bf298-15cf-4381-b19d-be471c0f0336

Pranit Chettri, Chinmoy Kar . Comparative Study between Various Pattern Matching Algorithms. International Conference on Computing and Communication. ICCC2016, 1 (September 2016), 26-30.

@article{
author = { Pranit Chettri, Chinmoy Kar },
title = { Comparative Study between Various Pattern Matching Algorithms },
journal = { International Conference on Computing and Communication },
issue_date = { September 2016 },
volume = { ICCC2016 },
number = { 1 },
month = { September },
year = { 2016 },
issn = 0975-8887,
pages = { 26-30 },
numpages = 5,
url = { /proceedings/iccc2016/number1/26155-cc56/ },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Proceeding Article
%1 International Conference on Computing and Communication
%A Pranit Chettri
%A Chinmoy Kar
%T Comparative Study between Various Pattern Matching Algorithms
%J International Conference on Computing and Communication
%@ 0975-8887
%V ICCC2016
%N 1
%P 26-30
%D 2016
%I International Journal of Computer Applications
Abstract

Present paper describes the details of the study of the work that has been done in the field of text searching, a sub-division of Natural Language Processing (NLP) till date. The work in this project includes the study and analysis of some of the algorithms devised under this topic, finding the faults or loop-holes and trying to increase the efficiency of these algorithms devised, taking forward the range of work done on it. Experiment is done on the various text search algorithms that have been devised namely Knuth-Morris Pratt Algorithm, Naïve Search Algorithm and Boyer-Moore Algorithm by providing text input of various sizes and analyzing their behavior on these variable inputs. After analyzing and doing the study on these algorithms the results states that Boyer-Moore's Algorithm worked quite well and efficiently than the rest of them when dealing with larger data sets. When working on larger alphabets the Knuth-Morris Pratt Algorithm works quite well. These algorithms do have drawbacks as their efficiency depends upon the alphabet/pattern size. And also this paper describes new pattern matching algorithm that uses delimiter for shifting the pattern while matching.

References
  1. Natural language processing,online: http://en. wikipedia. org/wiki/Natural_language_processing, Access Date: 23th May,2015.
  2. Koloud Al-Khamaiseh, Shadi ALShagarin"A Survey of String Matching ", Int. Journal of Engineering Research and Applications, ISSN : 2248-9622, Vol. 4, Issue 7( Version 2), pp. 144-156,July 2014.
  3. Pandiselvam. P,Marimuthu. T ,Lawrance. R,"A Comparative Study On String Matching Algorithms Of Biological Sequences"Deptt of Computer Applications,Ayya Nadar Janaki Ammal College, India,jan 2014.
  4. Hussain I. , Kausar S. , Hussain L. , and Asifkhan M. ",Improved Approach for Exact Pattern Matching, International", Journal of Computer Science Issues, Vol. 10, Issue 3, No. 1,2013.
  5. Jain P. , Pandey S. , "Comparative Study on Text Pattern Matching for Heterogeneous System", International Journal of Computer Science and Engineering Technology, ISSN: 2229-3345, Vol. 3 No. 11 Nov 2012.
  6. Singla N. , Garg D. ,"String Matching Algorithms and their Applicability in various Applications", International Journal ofSoft Computing and Engineering, ISSN: 2231-2307, VolumeI,Issue-6, January 2012.
  7. R. S. Boyer and J. S. Moore, "A Fast String Searching Algorithm", SRI International, 1977.
  8. Donald Knuth, James H. Morris and Jr. Vaughan Pratt, "Fast pattern matching in strings", SIAM Journal on Computing, 1977.
  9. Richard M. Karp, Michael O. Rabin, "Efficient randomized pattern-matching algorithms", IBM Journal of Research and Development, 1987.
Index Terms

Computer Science
Information Sciences

Keywords

Nlp Kmp Algorithm Naive Search Bm Algorithm.