International Journal of Information Technology and Computer Science (IJITCS)
IJITCS Vol. 9, No. 2, 8 Feb. 2017
Cover page and Table of Contents: PDF (size: 439KB)
An analysis of the Intelligent Predictive String Search Algorithm: A Probabilistic Approach
Full Text (PDF, 439KB), PP.66-75
Views: 0 Downloads: 0
Author(s)
Dipendra Gurung
1,*
Udit Kr. Chakraborty
1
Pratikshya Sharma
1
Index Terms
String matching, Probabilistic analysis, Markov chain, State diagram
Abstract
Due to the huge surge of digital information and the task of mining valuable information from huge amount of data, text processing tasks like string search has gained importance. Earlier techniques for text processing relied on following some predetermined sequence of steps or some hard coded rules. However, these techniques might soon prove to be inefficient as the amount of data generated by modern computer systems in increasing more and more. One solution to this problem lies in the development of intelligent algorithms that incorporate a certain degree of intelligence and unlike traditional algorithm are able to cope up with changing scenarios. This paper presents a string searching algorithm that incorporates a certain degree of intelligence to search for a string in a text. In the search of a string, the algorithm relies on a chance process and a certain probability at each step. An analysis of the algorithm based on the approach suggested by A. A. Markov is also presented in the paper. The expected number of average comparisons required for searching a string in a text is computed. Based on the varieties of applications that are coming up in the area of text processing and the related fields, this new algorithm aims to find its use.
Cite This Paper
Dipendra Gurung, Udit Kr. Chakraborty, Pratikshya Sharma, "An analysis of the Intelligent Predictive String Search Algorithm: A Probabilistic Approach", International Journal of Information Technology and Computer Science(IJITCS), Vol.9, No.2, pp.66-75, 2017. DOI:10.5815/ijitcs.2017.02.08
Reference
[1]Boyer, R. S.; Moore, J. S. A fast string searching algorithm. Commun. ACM 20, pp. 762-772, 1977.
[2]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.
[3]R. Nigel horspool, Practical fast searching in strings in: Software-Practice and Experience, vol. 10, pp. 501-506, 1980.
[4]Timo Raita, Tuning The Boyer-Moore-Horspool String Searching Algorithm in: Software-Practice And Experience, Vol. 22(10), pp. 879-884, October 1992.
[5]Gleb Gribakin, Probability and Distribution Theory, Chapter 4 Markov Chains, 110SOR201, 2002.
[6]Nimisha Singla, 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]Vivien Marx, Biology: The big challenges of big data, Nature 498, doi:10.1038/498255a, pp. 255–260, June 2013.
[9]Dipendra Gurung, Udit Kr. Chakraborty, Pratikshya Sharma, Intelligent Predictive String Search algorithm: Proceedings of International Conference on Communication, Computing and Virtualization (ICCCV) 2016, Elsevier Procedia Computer Science, Volume 79, 2016, Pages 161–169.
[10]Olaronke G. Iroju, Janet O. Olaleke, "A Systematic Review of Natural Language Processing in Healthcare", I.J. Information Technology and Computer Science, 2015, 08, pp. 44-50.
[11]Anany Levitin: Introduction to The Design and Analysis of Algorithms, 2nd edition, ISBN: 9780321358288, published by Pearson Education, Inc., 2007.
[12]Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, third edition, MIT press.
[13]Suranga Hettiariachchi, Wesley Kerr: Boyer-Moore String Matching algorithm, Technical paper downloaded from http://cs.eou.edu/CSMM/surangah/research/boyer/boy.pdf
[14]https://www.cs.cornell.edu/~ginsparg/physics/info295/mh.pdf
[15]Probabilistic algorithms, Spring 2001 course, http://users.abo.fi/atorn/ProbAlg/Abstract.html
[16]http://www.cs.utexas.edu/~moore/best-ideas/string-searching/index.html
[17]http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/ indexen.htm
[18]http://www.boost.org/doc/libs/1_54_0/libs/algorithm/doc/html/the_boost_algorithm_library/ Searching/BoyerMooreHorspool.html