做宠物网站需要实现什么功能/成人教育培训机构排名

Ⅰ 前言

如果对动态规划的基础内容还有不了解的同学，可以跳转去看我下面的文章👇

【数据结构与算法】-＞算法-＞动态规划（上）-＞初识动态规划-＞怎么精准地帮助女朋友薅羊毛

【数据结构与算法】-＞算法-＞动态规划（中）-＞详解动态规划理论

在我前面的一篇文章 Trie 树 中我提到了搜索引擎的一个功能，关键词提示。除此之外，一般搜索引擎为了优化用户的体验，还有个拼写纠错的功能。

当你在搜索框中，不小心输入错单词时，搜索引擎就会非常智能地检测出你的拼写错误，并且用对应的正确单词来进行搜索。那么，这个功能是如何实现的呢？

Ⅱ 字符串相似度的量化

要实现拼写纠错功能，首先要能识别两个字符串，但是计算机只认识数字，两个字符串之间的相似度要如何量化呢？有一个非常著名的量化方法，那就是 编辑距离（Edit Distance）。

顾名思义，编辑距离指 的就是，将一个字符串转化成另一个字符串，需要的最少编辑操作次数（比如增加一个字符，删除一个字符，替换一个字符）。编辑距离越大，说明两个字符串的相似程度越小；相反，编辑距离越小，说明两个字符串的相似程度越大。对于两个完全相同的字符串来说，编辑距离就是 0。

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

而且，莱文斯坦距离和最长公共子串，是从两个相反的角度来分析字符串的相似程度。莱文斯坦距离的大小，表示两个字符串差异的大小；最长公共子串的大小，表示两个字符串相似程度的大小。

关于这两个计算方法，我举个例子来说明。下图中两个字符串，mitcum 和 mtacnu 的莱文斯坦距离是 3，最长公共子串长度是 4。

了解了编辑距离的概念之后，我们来看，如何快速计算两个字符串之间的编辑距离。

Ⅲ 莱文斯坦距离的计算

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

在上一篇文章中的总结里，我们说贪心、回溯、动态规划可以解决的问题，都可以抽象成这样一个模型。要解决这个问题，我们可以先用最简单的回溯算法试试。

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

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

我们用Java实现就是下面这样👇

package com.tyz.third.core;/*** 莱文斯坦距离的计算* @author Tong*/
public class LevenshteinDistance {private char[] strOne = "mitcmu".toCharArray();private char[] strTwo = "mtacnu".toCharArray();private int lengthOne = strOne.length;private int lengthTwo = strTwo.length;private int minDist = Integer.MAX_VALUE; //存储结果/*** 回溯法计算莱文斯坦距离* @param i 第一个字符串的遍历索引* @param j 第二个字符串的遍历索引* @param edist 编辑次数*/public void lvstBT(int i, int j, int edist) {//一个字符串已经遍历完了，另一个字符串剩下的字符数就是需要编辑的次数if (i == lengthOne || j == lengthTwo) {if (i < lengthOne) {edist += (lengthOne - i); }if (j < lengthTwo) {edist += (lengthTwo - j);}if (edist < minDist) {minDist = edist;}return;}if (strOne[i] == strTwo[j]) { //两个字符匹配lvstBT(i+1, j+1, edist);} else { //两个字符不匹配lvstBT(i + 1, j, edist + 1); //删除a[i]或者b[j]前添加一个字符lvstBT(i, j + 1, edist + 1); //删除b[j]或者a[i]前添加一个字符lvstBT(i + 1, j + 1, edist + 1); //将a[i]和b[j]替换为相同字符}}
}

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

在递归树中，每个节点代表一个状态，状态包含三个变量 (i, j, edist) ，其中，edist 表示处理到 a[i] 和 b[j] 时，已经执行的编辑次数。

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

到这里我们就发现了，这就是典型的动态规划的例子啊。不过，这个问题的状态转移方式，要比我在动态规划前两篇文章里说的还要复杂。我们求二维矩阵的最短路径，到达状态 (i, j) 只能通过 (i-1, j) 或 (i, j-1) 两个状态转移过来，但是今天这个问题，状态可能从 (i-1, j)， (i, j-1) 或 (i-1, j-1) 三个状态中的任意一个迁移过来。

基于上面的分析，我们可以把状态转移的过程，用公式写出来。

了解了状态与状态之间的递推关系，我们画出一个二维的状态图，按行依次填充状态表中的每个值。

我们现在既有状态转移方程，又理清了完整的填表过程，代码的实现就非常简单了。

/*** 动态规划求莱文斯坦距离* 莱文斯坦距离的计算* 如果: a[i] != b[j], 那么: min_edist(i, j) 就等于 * 					min(min_edist(i-1, j)+1, min_edist(i-1, j-1)+1)* 如果: a[i] == b[j], 那么: min_edist(i, j) 就等于 * 					min(min_edist(i-1, j)+1, min_edist(i-1, j-1)+1, min_edist(i-1, j-1))* 其中, min表示求三个数中的最小值*/public int lvstDB(char[] strOne, int lengthOne, char[] strTwo, int lengthTwo) {int[][] minDist = new int[lengthOne][lengthTwo];//初始化第0列:a[0...i]到b[0...0]的编辑距离for (int i = 0; i < lengthOne; i++) {if (strOne[i] == strTwo[0]) {minDist[i][0] = i; //在第一个字符匹配之前, 前面的全是不匹配的, 所以编辑距离等于i} else if (i != 0) { //只要不是第一行的, 下一行的编辑距离就等于上一行的加1minDist[i][0] = minDist[i-1][0] + 1; } else {minDist[i][0] = 1; //a(0， 0)出现不匹配，编辑距离为1}}//初始化第0行:a[0...0]到b[0...j]的编辑距离for (int j = 0; j < lengthTwo; j++) {if (strOne[0] == strTwo[j]) {minDist[0][j] = j; } else if (j != 0) { minDist[0][j] = minDist[0][j-1] + 1; } else {minDist[0][j] = 1; } }for (int i = 1; i < lengthOne; i++) {for (int j = 1; j < lengthTwo; j++) {if (strOne[i] == strTwo[j]) {minDist[i][j] = min(minDist[i-1][j]+1,minDist[i][j-1]+1, minDist[i-1][j-1]);} else {minDist[i][j] = min(minDist[i-1][j]+1,minDist[i][j-1]+1, minDist[i-1][j-1]+1);}}}return minDist[lengthOne-1][lengthTwo-1];}/*** 求x,y,z中的最小值* @param x* @param y* @param z* @return*/private int min(int x, int y, int z) {int minValue = Integer.MAX_VALUE;if (x < minValue) {minValue = x;}if (y < minValue) {minValue = y;}if (z < minValue) {minValue = z;}return minValue;}

Ⅳ 最长公共子串长度的计算

这个问题的解决思路和莱文斯坦距离的解决思路非常相似，也可以用动态规划解决。我们前面已经详细描述了莱文斯坦距离的动态规划解决思路，所以针对最长公共子串的计算，我直接定义状态，然后写状态转移方程。

每个状态还是包括三个变量 (i, j, max_lcs)，max_lcs 表示 a[0…i] 和 b[0…j] 的最长公共子串长度。那 (i, j) 这个状态都是由哪些状态转移过来的呢？

我们先来看回溯的处理思路。我们从 a[0] 和 b[0] 开始，依次考察两个字符串中的字符是否匹配。注意我们前面说的，最长公共子串长度只允许增加、删除字符这两个编辑操作。

• 如果 a[i] 与 b[j] 互相匹配，我们将最大公共子串长度加 1，并且继续考察 a[i+1] 和 b[j+1]。
• 如果 a[i] 与 b[j] 不匹配，最长公共子串长度不变，这时候，有两个不同的决策路线。
  • 删除 a[i]，或者在 b[j] 前面加上一个字符 a[i]，然后继续考察 a[i+1] 和 b[j];
  • 删除 b[j]，或者在 a[i] 前面加上一个字符 b[j]，然后继续考察 a[i] 和 b[j+1]。

反过来也就是说，如果我们要求 a[0…i] 和 b[0…j] 的公共长度 max_lcs(i, j)，我们只有可能通过下面这个三个状态转移过来：

• (i-1, j-1, max_lcs)，其中 max_lcs 表示 a[0…i-1] 和 b[0…j-1] 的最长公共子串长度；
• (i-1, j, max_lcs)，其中 max_lcs 表示 a[0…i-1] 和 b[0…j] 的最长公共子串长度；
• (i, j-1, max_lcs)，其中 max_lcs 表示 a[0…i] 和 b[0…j-1] 的最长公共子串长度；

如果我们把这个转移过程，用状态转移方程写出来，就是下面的样子：

有了状态转移方程，我们将可以实现代码了。大家可以对照着讲解做一个参考。

package com.tyz.third.core;/*** 动态规划计算最长公共子串长度* 如果: a[i] == b[j], 那么: max_lcs(i, j)就等于:* 							max(max_lcs(i-1, j-1)+1, max_lcs(i-1, j), max_lcs(i, j-1));* 如果: a[i] != b[j], 那么: max_lcs(i, j)就等于:* 							max(max_lcs(i-1, j-1), max_lcs(i, j-1));* 其中max表示求三个数中的最大值* @author Tong*/
public class LongestCommonSubstring {public int lcs(char[] strOne, int lengthOne, char[] strTwo, int lengthTwo) {int[][] maxlcs = new int[lengthOne][lengthTwo];//初始化第0行: a[0...0]与b[0...j]的maxlcsfor (int j = 0; j < lengthTwo; j++) {if (strOne[0] == strTwo[j]) {maxlcs[0][j] = 1;} else if (j != 0) {maxlcs[0][j] = maxlcs[0][j-1];} else {maxlcs[0][j] = 0;}}//初始化第0列: a[0...i]与b[0...0]的maxlcsfor (int i = 0; i < lengthOne; i++) {if (strOne[i] == strTwo[0]) {maxlcs[i][0] = 1;} else if (i != 0) {maxlcs[i][0] = maxlcs[i-1][0];} else {maxlcs[i][0] = 0;}}for (int i = 1; i < lengthOne; i++) {for (int j = 1; j < lengthTwo; j++) {if (strOne[i] == strTwo[j]) {maxlcs[i][j] = max(maxlcs[i-1][j], maxlcs[i][j-1], maxlcs[i-1][j-1]+1);} else {maxlcs[i][j] = max(maxlcs[i-1][j], maxlcs[i][j-1], maxlcs[i-1][j-1]);}}}return maxlcs[lengthOne-1][lengthTwo-1];}private int max(int x, int y, int z) {int maxValue = Integer.MIN_VALUE;if (x > maxValue) {maxValue = x;}if (y > maxValue) {maxValue = y;}if (z > maxValue) {maxValue = z;}return maxValue;}
}

Ⅴ 如何实现搜索引擎的拼写纠错

当用户在搜索框内，输入一个拼写错误的单词时，我们就拿这个单词跟词库里的单词一 一进行比较，计算编辑距离，将编辑距离最小的单词，作为纠正之后的单词，提示给用户。

这就是拼写纠错最基本的原理。不过，真正用于商用的搜索引擎，拼写纠错功能显然不会就这么简单。一方面，单纯利用编辑距离来纠错，效果并不一定好；另一方面，词库中的数据量可能非常大，搜索引擎每天要支持海量的搜索，所以对纠错的性能要求很高。

针对纠错效果不好的问题，我们有很多种优化思路，我这里介绍几种。

• 我们并不仅仅取出编辑距离最小的那个单词，而是取出编辑距离最小的 TOP 10，然后根据其他参数，决策选择哪个单词作为拼写纠错单词。比如使用搜索热门程度来决定哪个单词作为拼写纠错单词。
• 我们还可以用多种编辑距离计算方法，比如这篇文章里讲的两种，然后分别编辑距离最小的 TOP 10，然后求交集，用交集的结果，再继续优化处理。
• 我们还可以通过统计用户的搜索日志，得到最常被拼错的单词列表，以及对应的拼写正确的单词。搜索引擎在拼写纠错的时候，首先在这个最常被拼错单词列表中查找，如果一旦找到，直接返回对应的正确的单词。这样纠错的效果非常好。
• 我们还有更加高级一点的做法，引入个性化因素，针对每个用户，维护这个用户特有的搜索偏好，也就是常用的搜索词。当用户输入错误的单词的时候，我们首先在这个用户常用的搜索关键词中，计算编辑距离，查找编辑距离最小的单词。

针对纠错性能方面，我们也有相应的优化方式，我在这里讲两种分治的优化思路。

• 如果纠错功能的 TPS 不高，我们可以部署多台机器，每台机器运行一个独立的纠错功能。当有一个纠错请求的时候，我们通过负载均衡，分配到其中一台机器，来计算编辑距离，得到纠错单词。
• 如果纠错系统的响应时间太长，也就是，每个纠错请求处理时间太长，我们可以将纠错的词库，分配到很多台机器。当有一个纠错请求的时候，我们就将这个拼写错误的单词，同时发送到多台机器，让多台机器并行处理，分别得到编辑距离最小的单词，然后再对比合并，最终决定出一个最优的纠错单词。

真正的搜索引擎的拼写纠错优化，肯定不会这么简单，但是万变不离其宗，我们搞清楚了核心原理，就能更好地去理解它。