The String Pattern Matching Algorithm Based On Edit Distance

Edit Edit distance is an important aspect of the pattern matching, pattern matching is a kind of similarity metrics. It has an important basic role in pattern matching, has an irreplaceable significance. Because of the existing schema matching matching speed and is not very good, the accuracy of the edit distance is not very high. Therefore, edit distance gradually become hot research topic in the pattern matching problem. This article in view of the existing poor definition edit distance and speed of pattern matching problem, detailed understanding of the definition of edit distance and all sorts of pattern matching algorithm and the calculation method of the similarity of different pattern matching, and definition of edit distance and edit distance algorithm is studied and analyzed.First First of all, the pattern matching is already in the edit distance definition and the advantages and disadvantages of edit distance algorithm has carried on the detailed analysis, aiming at the accuracy of the edit distance in pattern match and poor efficiency of edit distance algorithm, this paper proposes a new edit distance definition, and on the basis of the new definition of edit distance is proposed based on string edit distance fast scanning algorithm, makes the calculated value of edit distance has better accuracy.Second,this paper comprehensive, detailed analysis of the several kinds of edit distance calculation algorithm, aiming at the problem of poor efficiency of the existing schema matching speed, on the basis of the new definition of edit distance, pattern matching algorithm based on edit distance is proposed. In large-scale data set using the pattern matching algorithm, can effectively reduce the execution time repeatedly, in order to gain the higher time efficiency.Finally, through theoretical proof and mathematical methods for the experiment on the model data set, by comparing with the edit distance algorithm, we validate the pattern matching algorithm based on edit distance matching speed and efficiency.