原文链接:http://blog.csdn.net/dongle2001/article/details/1472235
1.编辑距离(Levenshtein Distance)
编辑距离就是用来计算从原串(s)转换到目标串(t)所需要的最少的插入,删除和替换
的数目,在NLP中应用比较广泛,如一些评测方法中就用到了(wer,mWer等),同时也常用来计算你对原文本所作的改动数。编辑距离的算法是首先由俄国科学家Levenshtein提出的,故又叫Levenshtein Distance。
Levenshtein Distance算法可以看作动态规划。它的思路就是从两个字符串的左边开始比较,记录已经比较过的子串相似度(实际上叫做距离),......
阅读全文