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 253
- Downloads 4
Acute Mylogenous Leukemia Detection Using Blood Microscopic Images
Leukemia is a specific kind of cancer, where the blood cells i.e., RBC’s, leukocytes or WBC’s; lymphatic system or bone marrow gets affected. Blood tests aids in diagnosing blood cancer, where affected blood cells are e...
Optimized Interaction of PODC and SSSC To Improve the Transient Stability Performance In Power System
The enlargement of the contemporary power system has lead to an increasing difficulty in the study of power systems, also presents new challenges to power system stability and in meticulous to the aspects of transient s...
Orthogonal Frequency Division Multiplexing (OFDM)
Orthogonal frequency-division multiplexing (OFDM) is a method of encoding digital data on multiple carrier frequencies. OFDM has developed into a popular scheme for wideband digital communication, whether wireless or ov...
Transafe Vehicle: Safety in Public Transport
As urban areas are becoming more noticeable and developed, safety management becomes more challenging. Through our project, we let people meet today’s high demands for improved and safe transportation systems. Whether w...
Automation of VFD Based Sugarcane Crusher with PLC and SCADA Control
Three phase induction motors are widely used motor in sugar industry because of its simple maintenance. In recent years, Variable Frequency Drive is used to change the rotating direction and speed of three phase inducti...