An Levenshtein Transpose Distance Algorithm for approximating String Matching

Meena Malviya¹ , Rajendra Gupta²

Section:Research Paper, Product Type: Journal-Paper
Vol.6 , Issue.2 , pp.1-4, Dec-2018

Online published on Mar 31, 2018

Copyright © Meena Malviya, Rajendra Gupta . This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
 

View this paper at   Google Scholar | DPI Digital Library

XML View     PDF Download

How to Cite this Paper

Abstract :
The string-matching is a very essential issue in the wider area of text processing. String-matching algorithms are basic components used in implementations of practical existing software under most operating systems. Furthermore, they emphasize programming methods that serve as paradigms in other fields of computer science. There are different solutions have been proposed that allow solving the string matching issues. The main characteristic of string matching algorithm is the fact that it attempts to establish the correspondence of the substring with the pattern in the reverse direction. This paper focuses on an approach by implementing Levenshtein distance algorithm using transposition of characters. After the testing of data, it is found that the implemented algorithm gives significant results while string matching.

Key-Words / Index Term :
Levenshtein Distance Algorithm, Approximating String Matching, Stop words

References :
[1] C. Charas, T. Lecroq and J. D. Pehoushek. 2005. A very fast string matching algorithm for small alphabets and long patterns, Lecture notes in Computer Science, Volume 1448, pp. 55-64, 2018
[2] J. J. McConnell, “Analysis of Algorithms”, Canisius College, pp 125-128, 2018
[3] M. Crochemore and D. Perrin, 1991, Two Way String Matching, Journal of the Association for Computing Machinery, Vol. 38, No 3, pp.65I-675, 2018
[4] T. Raita, 1992, Tuning the Boyer–Moore–Horspool String, Searching Algorithm, Software Practice and Experience, Vol 22(10),pp 879–884, 2018
[5] R. Baeza-Yates and G. H. Gonnet, 1992, A New Approach To Text Searching, Communication of the ACM,Vol.35, No.10, 2018
[6] James Lee Holloway, “Algorithms for string matching with applications in Molecular Biology”, Oregon State University Corvallis, OR, USA, 2018
[7] Luqman Gbadamosi, “Voice Recognition System Using Template Matching”, International Journal of Research in Computer Science, Volume 3 Issue 5, pp. 13-17, 2017
[8] Saurabh Tiwari and Deepak Motwani, “Feasible Study on Pattern Matching Algorithms based on Intrusion Detection Systems”, International Journal of Computer Applications 96(20):13-17, 2017
[9] Kavita Ahuja, Preeti Tuli, "Object Recognition by Template Matching Using Correlations and Phase Angle Method", International Journal of Advanced Research in Computer and Communication Engineering, Vol. 2, Issue 3, 2017
[10] Prabhudeva S, "Plagiarism Detection by using Karp-Rabin and String Matching Algorithm Together", IJCSNS International Journal of Computer Science Engineering and Network Security, VOL.8 No.10, 2017
[11] Koloud Al-Khamaiseh, “A Survey of String Matching Algorithms”, International Journal of Engineering Research and Applications, Vol. 4, Issue 7, Version 2, pp.144-156, 2017
[12] Knuth, D. E., Morris, J. H. Jr., and Pratt, V. R., “Fast pattern matching in strings,” SIAM Journal of Computer, Vol. 6, No. 2, pp. 323-350, 2017.
[13] Boyer, R. S., and Moore, J. S., "A fast string searching algorithm” Communication in ACM, Vol. 20, No. 10, pp. 762-772, 2016
[14] Rivest, R. L., “On the worst case behavior of string-searching algorithms”, SIAM Journal of Computer, Vol. 6, No. 4, pp. 669-674, 2016
[15] Galil, Z., “An improving the worst-case running time of the Boyer-Moore string matching algorithms” Communication ACM, Vol. 22, No. 9, pp. 505-508, 2016
[16] Rytter, W., “A correct preprocessing algorithm for Boyer-Moore string-searching” SIAM Journal of Computer, Vol. 9, No. 3, pp. 509-512, 2016
[17] Guibas, L. J. and Odlyzko, A. R., “A new proof of the linearity of the Boyer-Moore string searching algorithm” SIAM, Journal of Computer, Vol. 9, No. 4, pp. 672-682, 2016
[18] Horspool, R. N., "fast searching in strings” Software Practice Experience, Vol. 10, pp. 501-506, 2016
[19] Smit, G. “Comparison of three string matching Algorithms” Software Practice Experience, Vol. 12, pp. 57-66, 2015
[20] Ushijima, K., Kurosaka, T., and Yoshida, K., “SNOBOL with Japanese text processing facility” Proc. ICTP 83, pp. 235-240, 2015