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 268
- Downloads 4
Experimental Investigation to Study the Effect of the Mineral Oil and Carbide Insert Shapes on Machining of Aisi 4140
There are so many machining parameters, which affects the surface finish of product. One important machining parameter is the shape of the cutting tool and another one is the cutting condition (dry or wet). In this stud...
Effect of Poly Vinyl Acetate and Poly Vinyl Alcohol as Cement Admixture on Strength of Concrete
This paper reviews the observations of addition of poly vinyl alcohol and poly vinyl acetate the poly fibers together to cement bond matrix. Polymer fiber serves as superplastitisizer which results in low rate of water...
A novel anti-islanding technique in a Distributed generation systems
This paper proposes a photovoltaic generation system interfaced with a dc distribution system. DC interface allows for the improvement of system efficiency by fully utilizing dc-based renewable sources and storage devic...
Bus Monitoring System Based on RFID Technology with GSM Communication
The innovation in technology today has made our Lifestyle much easier and fun. This research work proposes and implements a solution for enhancing public transportation management services based on RFID and GSM. The sys...
A Review of FTIR and Thermal Resistance test of Cement Mortar made with Metakaolin and Flyash Partially Replaced in cement cured in sea water
In this present study the strength and quality and thermal effect of the cement mortar having partially replaced metakaolin and flyash in cement by compressive strength and thermal resistance and Fourier Transform Infra...