An Efficient Algorithm for Approximate String Matching
Journal Title: International Journal for Research in Applied Science and Engineering Technology (IJRASET) - Year 2015, Vol 3, Issue 7
Abstract
The approximate string matching is the technique of finding strings that match a pattern approximately (rather than exactly). Most often when we need to match a pattern exact matching is not possible, due to insufficient data, broken data, or other such reasons. So we try to find a close match instead of an exact match. And for this we need to find the distance between two strings. We have different approaches for the same such as edit distance in the form of Hamming distance, Levenshstien distance, Dameru-Levenshstein distance, Jaro-Winkler distance and Longest Common Subsequence (LCS). In our classical approach which is studied academically, we form a dynamic programming matrix to find our solution. In mathematics, computer science, and economics, dynamic programming is a method for solving complex problems by breaking them down into simpler sub problems. It is applicable to problems exhibiting the properties of overlapping sub problems which are only slightly smaller and optimal substructure. When applicable, the method takes far less time than naive methods.
Authors and Affiliations
Neha, Rachna Dhaka
Keywords
Related Articles
- EP ID EP21041
- DOI -
- Views 251
- Downloads 4
Low Cost Reliable 3D Printer Design Using CPU Board XMC4500
3D printing is a process of making a three-dimensional solid object of virtually any shape from a digital model. A 3D printer is just like a normal color printer. The main difference is that it prints with plastic and 3...
Optical and Structural Properties of Zinc Oxide Nanowires Fabricated by Hydrothermal Method
Nanocrystalline film of Zinc Oxide (ZnO) nanowires were prepared on glass substrate at a low temperature using a low cost, simple hydrothermal method. We used different concentration of ZnO nanowires precursor solution...
Advanced Microwave Active & Passive Remote Sensing Application and Its Utilization
Microwave sensing circumscribes both active and passive forms of remote sensing. Long wavelengths, match up to the visible and infrared. Its radiation can penetrate through haze, cloud cover and dust. Longer wavelengths...
Optimization in Turning of Ti-6AL-4V Using Anova and Regression Analysis
Surface roughness is an important factor to evaluate cutting performance. The primary factors such as speed, feed, depth of cut, type of material, tool geometry etc. have high impact on surface roughness. So it is a mea...
FPGA Implementation of 64-bit fast multiplier using barrel shifter
In this paper we have described the implementation of a 64-bit Vedic multiplier which is enhanced in terms of propagation delay when it is compared with conventional multiplier like modified booth multiplier, Wallace tr...