基于动态规划思想的编辑距离计算

编辑距离: 给定两文本或句子,计算需要多少步操作能够从一个句子转换为另外一个句子,允许操作有增加、删除和替换。距离越小,说明二者越相似,距离与大,说明二者差距越大。 利用动态规划计算编辑距离,其模型如下: 对于两个字符串a和b,计算两个字符串的相似度,即计算两个字符串的编辑距离,相当于计算它们字串的编辑距离,再加上从子串到全串所需的最少编辑次数即可,不断地进行递推。 递推公式如下: hp[i][j]指的是a的前i个字符和b中前j个字符之间的距离,字符串计算从index = 1开始(实际预算需要在字符串前补0),最终编辑距离为i=|a|,j=|b|时的hp[i][j]。 当min⁡(i,j)=