CFP last date
15 July 2024
Reseach Article

String Searching Algorithm: A Predictive Approach

Published on July 2016 by Dipendra Gurung, Udit Kr Chakraborty, Pratikshya Sharma
International Conference on Communication Computing and Virtualization
Foundation of Computer Science USA
ICCCV2016 - Number 2
July 2016
Authors: Dipendra Gurung, Udit Kr Chakraborty, Pratikshya Sharma
a47bd602-5c27-4852-bb9c-046174e58efc

Dipendra Gurung, Udit Kr Chakraborty, Pratikshya Sharma . String Searching Algorithm: A Predictive Approach. International Conference on Communication Computing and Virtualization. ICCCV2016, 2 (July 2016), 0-0.

@article{
author = { Dipendra Gurung, Udit Kr Chakraborty, Pratikshya Sharma },
title = { String Searching Algorithm: A Predictive Approach },
journal = { International Conference on Communication Computing and Virtualization },
issue_date = { July 2016 },
volume = { ICCCV2016 },
number = { 2 },
month = { July },
year = { 2016 },
issn = 2249-0868,
pages = { 0-0 },
numpages = 1,
url = { /proceedings/icccv2016/number2/920-1664/ },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Proceeding Article
%1 International Conference on Communication Computing and Virtualization
%A Dipendra Gurung
%A Udit Kr Chakraborty
%A Pratikshya Sharma
%T String Searching Algorithm: A Predictive Approach
%J International Conference on Communication Computing and Virtualization
%@ 2249-0868
%V ICCCV2016
%N 2
%P 0-0
%D 2016
%I International Journal of Applied Information Systems
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.

References
  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
Index Terms

Computer Science
Information Sciences

Keywords

String search Predictive search