Google scholar arxiv informatics ads IJAIS publications are indexed with Google Scholar, NASA ADS, Informatics et. al.

Call for Paper

-

November Edition 2021

International Journal of Applied Information Systems solicits high quality original research papers for the November 2021 Edition of the journal. The last date of research paper submission is October 15, 2021.

String Searching Algorithm: A Predictive Approach

Dipendra Gurung, Udit Kr Chakraborty, Pratikshya Sharma Published in Algorithms

IJAIS Proceedings on International Conference on Communication Computing and Virtualization
Year of Publication: 2016
© 2015 by IJAIS Journal
Download full text
  1. Dipendra Gurung, Udit Kr Chakraborty and Pratikshya Sharma. Article: String Searching Algorithm: A Predictive Approach. IJAIS Proceedings on International Conference on Communication Computing and Virtualization ICCCV 2016(2):19-24, July 2016. BibTeX

    @article{key:article,
    	author = "Dipendra Gurung and Udit Kr Chakraborty and Pratikshya Sharma",
    	title = "Article: String Searching Algorithm: A Predictive Approach",
    	journal = "IJAIS Proceedings on International Conference on Communication Computing and Virtualization",
    	year = 2016,
    	volume = "ICCCV 2016",
    	number = 2,
    	pages = "19-24",
    	month = "July",
    	note = "Published by Foundation of Computer Science, New York, USA"
    }
    

Abstract

In today's time computer systems produce large volumes of data. In order to extract valuable information from this data various new techniques are being developed and used. This has led to the increase in the importance of text processing and consequently string searching. In this paper a new string searching algorithm is presented that uses intelligent predictions based on text features to search for a string in a text. The proposed algorithm has been developed after analyzing the existing algorithms such as KMP, Boyer-Moore and Horspool. One unique feature of this algorithm is that unlike the existing algorithms, it does not require pre-processing the pattern to be searched. As a result it does not incur the overhead required in pre-processing the pattern. The algorithm searches through a given text to find the first occurrence of a pattern. It does not involve complex computations and uses simple rules during a match or mismatch of a pattern character. Based on the variety of applications coming up in areas of data and information mining, sentiment analysis, DNA pattern matching etc, this simple, elegant and intelligent algorithm will find its application.

Reference

  1. Joseph B. Sidowski, On-line computer text processing: A tutorial in: Behavior Research Methods&Instrumentation, vol. 6, no. 2, pp. 159-166, 1974.
  2. Boyer, R. S. ; Moore, J. S. A fast string searching algorithm. Commun. ACM 20, pp. 762-772, 1977.
  3. Donald E. Knuth, James H. Morris, Vaughan R. Pratt, Fast Pattern Matching In Strings in: Siam, Vol. 6, No. 2, pp. 323-350, June 1977.
  4. R. Nigel horspool, Practical fast searching in strings in: Software-Practice and Experience, vol. 10, pp. 501-506, 1980.
  5. Timo Raita, Tuning The Boyer-Moore-Horspool String Searching Algorithm in: Software-Practice And Experience, Vol. 22(10), pp. 879-884, October 1992.
  6. NimishaSingla, Deepak Garg, String Matching Algorithms and their Applicability in various Applications in: International Journal of Soft Computing and Engineering (IJSCE) ISSN: 2231-2307, Volume-I, Issue-6, pp. 156-161, January 2012.
  7. Emma Haddi, Xiaohui Liu, Yong Shi, The Role of Text Pre-processing in Sentiment Analysis: International Conference on Information Technology and Quantitative Management, pp. 234-231, 2013.
  8. SurangaHettiariachchi, Wesley Kerr: Boyer-Moore String Matching algorithm, Technical paper downloaded from http://cs. eou. edu/CSMM/surangah/research/boyer/boy. pdf
  9. Anany Levitin: Introduction to The Design and Analysis of Algorithms, 2nd edition, ISBN: 9780321358288, published by Pearson Education, Inc. , 2007.
  10. http://www. inf. fhflensburg. de/lang/algorithmen/pattern/indexen. htm
  11. http://www. boost. org/doc/libs/1_54_0/libs/algorithm/doc/html/the_boost_algorithm_library/Searching/BoyerMooreHorspool. html
  12. http://www. personal. kent. edu/~rmuhamma/Algorithms/MyAlgorithms/StringMatch/boyerMoore. htm
  13. http://cs. indstate. edu/~kmandumula/presentation. pdf
  14. http://www. cs. utexas. edu/~moore/best-ideas/string-searching/index. html

Keywords

String search, Predictive search