算法:动态规划实现搜索引擎中的拼写纠错功能

2022/2/1 11:28:55

本文主要是介绍算法:动态规划实现搜索引擎中的拼写纠错功能,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

如何量化两个字符串的相似度

量化两个字符串的相似度有一个非常著名的量化方法,那就是编辑距离。

所谓编辑距离就是指,将一个字符串转换成另一个字符串,需要的最少编辑操作次数(比如增加一个字符、删除一个字符、替换一个字符)。编辑距离越大,说明两个字符串的相似程度越小;编辑距离越小,说明两个字符串的相似程度越大。对于两个完全相同的字符串来说,编辑距离就是0.

根据所包含的编辑,编辑距离有多种不同的计算方式,比较著名的有莱文斯坦距离最长公共子串长度。其中,莱温斯坦距离允许增加、删除、替换字符这三个编辑操作,最长公共子串长度只允许增加、删除字符这两个编辑操作。

而且,莱温斯坦距离和最长公共子串长度,从两个截然相反的角度,分析字符串的相似程度。莱温斯坦距离的大小,表示两个字符串差异的大小;最长公共子串的大小,表示两个字符串相似程度的大小。

比如,两个字符串 mitcmu 和mtacnu 的莱文斯坦距离是 3,最长公共子串长度是 4。
在这里插入图片描述

如何编程计算莱文斯坦距离?

这个问题是求一个字符串变成另一个字符串,需要的是最少编辑次数。整个求解过程,涉及多个决策阶段,我们需要依次考察一个字符串中的每个字符,跟另一个字符串中的字符是否匹配,匹配的话如何处理,不匹配的话又如何处理。所以,这个问题符合多阶段决策最优解模型

要解决这个问题,我们先来用最简单的回溯算法来解决。

回溯是一个递归处理的过程,如果 a [ i ] a[i] a[i]和 a [ j ] a[j] a[j]匹配,我们递归考察 a [ i + 1 ] a[i+1] a[i+1]和 b [ j + 1 ] b[j+1] b[j+1]。如果 a [ i ] a[i] a[i]和 b [ j ] b[j] b[j]不匹配,那我们有多种处理方式可选:

  • 可以删除 a [ i ] a[i] a[i],然后递归考察 a [ i + 1 ] a[i+1] a[i+1]和 b [ j ] b[j] b[j]
  • 可以删除 b [ i ] b[i] b[i],然后递归考察 a [ i ] a[i] a[i]和 b [ j + 1 ] b[j+1] b[j+1]
  • 可以在 a [ i ] a[i] a[i]前面添加一个跟 b [ j ] b[j] b[j]相同的字符,然后递归考察 a [ i ] a[i] a[i]和 b [ j + 1 ] b[j+1] b[j+1]
  • 可以在 b [ j ] b[j] b[j]前面添加一个跟 a [ i ] a[i] a[i]相同的字符,然后递归考察 a [ i + 1 ] a[i+1] a[i+1] 和 b [ j ] b[j] b[j]
  • 可以将 a [ i ] a[i] a[i] 替换成 b [ j ] b[j] b[j],或者将 b [ j ] b[j] b[j]替换成 a[i],然后递归考察 a [ i + 1 ] a[i+1] a[i+1] 和 b [ j + 1 ] b[j+1] b[j+1]

上面过程代码实现如下:

	private char[] a = "mitcmu".toCharArray();
    private char[] b = "mtacnu".toCharArray();
    private int n = 6;
    private int m = 6;
    private int minDist = Integer.MAX_VALUE; //存储结果
    // 调用 lwstDT(0, 0, 0);
    public void lwstBT(int i, int j, int edist){
        if(i == n || j == m){
            if(i < n){
                edist += (n - i);
            }
            if(j < m){
                edist += (m - j);
            }
            if(edist < minDist){
                minDist = edist;
            }
            return;
        }

        // 两个字符匹配
        if(a[i] == b[j]){
            lwstBT(i +1, j + 1, edist);
        }else{ //两个字符不匹配
            lwstBT(i + 1, j, edist + 1); // 删除 a[i] 或者 b[j] 前添加一个字符
            lwstBT(i, j + 1, edist + 1); // 删除 b[j] 或者 a[i] 前添加一个字符
            lwstBT(i + 1, j + 1, edist + 1); // 将 a[i] 和 b[j] 替换为相同字符
        }
    }

根据回溯算法的代码实现,我们可以画出递归树,看是否存在重复子问题。如果存在重复子问题,那我们就可以考虑是否能用动态规划来解决;如果不存在重复子问题,那回溯就是最好的解决方法。

在这里插入图片描述
在递归树中,每个节点代表一个状态,状态包含三个变量 ( i , j , e d i s t ) (i,j,edist) (i,j,edist),其中,edist表示处理到 a [ i ] a[i] a[i]和 b [ j ] b[j] b[j]时,已经执行的编辑操作的次数。

在递归树中, ( i , j ) (i,j) (i,j)两个变量重复的节点很多,比如 ( 3 , 2 ) (3,2) (3,2)和 ( 2 , 3 ) (2,3) (2,3)。对于 ( i , j ) (i,j) (i,j)相同的节点,我们只需要考虑保留edist最小的,继续递归处理就可以了,剩下的节点都可以舍弃。所以,状态就从 ( i , j , e d i s t ) (i,j,edist) (i,j,edist)变成了 ( i , j , m i n d i s t ) (i,j,mindist) (i,j,mindist),其中mindist表示处理到 a [ i ] a[i] a[i]和 b [ j ] b[j] b[j],已经执行的最少编辑次数。

这里的动态递归跟矩阵最短路径很相似,在矩阵最短路径中,到达状态(i,j)只能通过(i-1,j)或者(i,j-1)两个状态转移过来,而字符编辑距离状态(i,j)可能从(i-1,j),(i,j-1),(i-1,j-1)三个状态中的任意一个转移过来。

在这里插入图片描述



这篇关于算法:动态规划实现搜索引擎中的拼写纠错功能的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程