Improved Edit Distance Algorithm Based on Local Variability
Wang Wei-hon · Jisuanji gongcheng · 2015
For the low computational efficiency in solving the similarity of two strings by traditional algorithm,an improved edit distance algorithm is proposed.It firstly obtains the longest common prefix and the longest common suffix of the two strings,and then gets the edit distance between the remainder of the two strings by traditional algorithm.Proof by contradiction is used to prove that this edit distance equals to the solution by traditional algorithm.On this basis,the improved algorithm is researched about the advantages and be applied to the Web tamper detection.Experimental results show that compared with the traditional algorithm,the improved edit distance algorithm has better computational efficiency in obtaining the similarity between the pages in the same URL.