天水网站建设,工程管理专业后悔死了,wordpress cms微信插件,三明注册公司文章出处#xff1a;极客时间《数据结构和算法之美》-作者#xff1a;王争。该系列文章是本人的学习笔记。
莱文斯坦距离
在搜索引擎中会有搜索词纠错的功能。这个功能背后的原理是编辑距离。
编辑距离
编辑距离是量化两个词之间的相似度。 编辑距离是指将一个字符串变为…文章出处极客时间《数据结构和算法之美》-作者王争。该系列文章是本人的学习笔记。
莱文斯坦距离
在搜索引擎中会有搜索词纠错的功能。这个功能背后的原理是编辑距离。
编辑距离
编辑距离是量化两个词之间的相似度。 编辑距离是指将一个字符串变为另外一个字符串需要的最少编辑操作次数。编辑操作包含新增一个字符、修改一个字符、删除一个字符。编辑次数越少编辑距离越小两个字符串相似度越大。如果两个字符串完全相同编辑距离为0。
根据所包含的编辑操作种类的不同编辑距离有多种不同的计算方式比较著名的有莱文斯坦距离Levenshtein distance和最长公共子串长度Longest common substring length。其中莱文斯坦距离允许增加、删除、替换字符这三个编辑操作最长公共子串长度只允许增加、删除字符这两个编辑操作。
莱文斯坦距离
用莱文斯坦距离替换两个字符串的过程。
回溯解法
莱文斯坦距离将一个字符串替换为另外一个字符串计算最少的编辑次数。需要考虑字符串中每一位上的字符。如果字符相同怎么处理字符不同怎么处理。这是一个多阶段决策最优解模型。
贪心、回溯、动态规划都可以解决这类问题。我们先用回溯法解决看是不是有重复子问题。如果没有回溯就是最优解如果有重复子问题那就需要用动态规划优化。
回溯是一个递归处理问题的过程。假设我们要把a字符串替换为b字符串。如果a[i]和b[j]匹配则i,j。如果不匹配可以采取的措施有 1 删除a[i]然后递归考察a[i1]和b[j] 2 在a[i]前面插入字符b[j]然后递归考察a[i]和b[j1] 3 将a[i]替换为b[j]然后递归考察a[i1]和b[j1]。
翻译成代码 public class LevenshteinDistance {private char[] a mitcmu.toCharArray();private char[] b mtacnu.toCharArray();private int n a.length;private int m b.length;private int minEdist Integer.MAX_VALUE;private void lwstBT(int i,int j,int edist){if(in || jm){if(jm) {edist m-j;}if(in){edist n-i;}minEdist Math.min(edist,minEdist);return;}if(a[i]b[j]){lwstBT(i1,j1,edist);}else{lwstBT(i1,j,edist1);//删除a[i]lwstBT(i,j1,edist1);//在a[i]前面插入b[j]lwstBT(i1,j1,edist1);//修改a[i]b[j]}}public void lwstBT(){lwstBT(0,0,0);}public static void main(String[] args){LevenshteinDistance l new LevenshteinDistance();l.lwstBT();System.out.println(l.minEdist);}
}我们依据回溯代码来看下递归树。 递归树的每一个节点表示一种状态用(i,j,edist)表示i表示指针在a字符串的位置j表示指针在b字符串的位置(i,j)都表示将要处理的字符位置edist表示到达(i,j)时已经执行的编辑次数。递归树中的一条边对应一种处理方式。
从树中能够看出(i,j)相同的节点很多。例如(2,2)、2,3。同一个状态的节点只要保留一个编辑距离最小的就可以。因为我们的目标就是找编辑距离最小的。这样也可以避免递归树节点指数级增长。
我们接着看下状态转移方式。状态(i,j)可能从(i-1,j-1)、(i-1,j)、(i,j-1)这三个状态的任一状态转变过来。 状态表法
接下来我们按照这种方式计算状态转移表。我们画出一个二维状态表表中的行、列表示字符串在a、b中的位置表中的数值表示从00到这个位置需要执行的最短编辑次数。需要说明的是这个编辑次数是包含本次操作的。与递归树的状态中数值的含义略微不同。 这里说一下填表的过程。 (0,0):m-m 不需要编辑。 (0,1)m-mt 需要 一次编辑。 … 这张表比较难填写我没明白怎么填写的。如果从00开始算后面还能算明白想往回递推就搞不懂了。 比较简单的理解就是想决定(2,2)的值从(1,1). (1,2). (2,1)三个值中选择一个最小值再加1。就对了。加1是因为a!t。图下面有补充2021-1-1 这里补充一下之前不能理解的地方。例如想要到达dp[2][2]这个状态就是说想要字符串mit变为mta。 我们已经知道dp[1][1]1也就是说从mi最少有1次操作可以变为mt。这个时候我们在mi变成的mt后面添加一个t在mt字符串后面添加一个a我们将t替换为a(mtc-mta)就可以实现将字符串mit变为mta。也就是说dp[1][1]1。这里需要说明的是如果同时追加的都是a字符的话那就不用编辑操作。mta-mta不需要操作那这时候的编辑次数就是dp[i-1][j-1]。 我们已经知道dp[1][2]2也就是说从mi变为mta需要2次操作。这时候在mi后面追加字符t那么只需要把字符t删除(mtat-mta)就能实现从mit变为mta。也就是说dp[1][2]1。 我们已经知道dp[2][1]1也就是说从mit变为mt需要1次操作。那么只需要在后面添加一个a字符(mt-mta)就能实现从mit变为mta。也就是说dp[2][1]1。
状态转移方程
根据状态转移方式很容易得到状态转移方程。 如果a[i]b[j] min_edist(i.j) min(min_edist(i-1,j)1,min_edist(i,j-1)1,min_edist(i-1,j-1));如果a[i]!b[j] min_edist(i.j) min( min_edist(i-1,j)1,min_edist(i,j-1)1,min_edist(i-1,j-1)1 );DP代码 public int lwstDP(char[] a, int n, char[] b, int m) {int[][] minDist new int[n][m];for(int i0;in;i){for(int j0;jm;j){if(i0 j0){minDist[0][0] a[0]b[0]?0:1;}else{minDist[i][j] Integer.MAX_VALUE;if(i0 j0){minDist[i][j] Math.min(minDist[i][j],minDist[i-1][j-1](a[i]b[j]?0:1));}if(i0 j0){minDist[i][j] Math.min(minDist[i][j],minDist[i][j-1]1);}if(i0 j0){minDist[i][j] Math.min(minDist[i][j],minDist[i-1][j]1);}}}}return minDist[n-1][m-1];}
