Volume-6 , Issue-2 , Dec 2018, ISSN 2321-905X Go Back

• Open Access   Article

  An Levenshtein Transpose Distance Algorithm for approximating String Matching

  Meena Malviya, Rajendra Gupta

  Research Paper | Journal-Paper (WAJM)

  Vol.6 , Issue.2 , pp.1-4, Dec-2018

  Abstract

  Full-Text HTML

  References

  Citation

  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
  

  Citation
  Meena Malviya, Rajendra Gupta, "An Levenshtein Transpose Distance Algorithm for approximating String Matching," World Academics Journal of Management, Vol.6, Issue.2, pp.1-4, 2018