前言
本節(jié)課程思維導(dǎo)圖：
利用 Trie 樹，可以實現(xiàn)搜索引擎的關(guān)鍵詞提示功能，這樣可以節(jié)省用戶輸入搜索關(guān)鍵詞的時間。實際上，搜索引擎在用戶體驗方面的優(yōu)化還有很多，比如你可能經(jīng)常會用的拼寫糾錯功能。
當(dāng)你在搜索框中，一不小心輸錯單詞時，搜索引擎會非常智能地檢測出你的拼寫錯誤，并且用對應(yīng)的正確單詞來進行搜索。作為一名軟件開發(fā)工程師，你是否想過，這個功能是怎么實現(xiàn)的呢？
如何量化兩個字符串的相似度？
要解答開篇的問題，我們就要先來看，如何量化兩個字符串之間的相似程度呢？有一個非常著名的量化方法，那就是編輯距離（Edit Distance）。
顧名思義，編輯距離指的就是，將一個字符串轉(zhuǎn)化成另一個字符串，需要的最少編輯操作次數(shù)（比如增加一個字符、刪除一個字符、替換一個字符）。編輯距離越大，說明兩個字符串的相似程度越??；相反，編輯距離就越小，說明兩個字符串的相似程度越大。對于兩個完全相同的字符串來說，編輯距離就是 0。
根據(jù)所包含的編輯操作種類的不同，編輯距離有多種不同的計算方式，比較著名的有萊文斯坦距離（Levenshtein distance）和最長公共子串長度（Longest common substring length）。其中，萊文斯坦距離允許增加、刪除、替換字符這三個編輯操作，最長公共子串長度只允許增加、刪除字符這兩個編輯操作。
而且，萊文斯坦距離和最長公共子串長度，從兩個截然相反的角度，分析字符串的相似程度。萊文斯坦距離的大小，表示兩個字符串差異的大小；而最長公共子串的大小，表示兩個字符串相似程度的大小。
關(guān)于這兩個計算方法，我舉個例子給你說明一下。這里面，兩個字符串 mitcmu 和 mtacnu 的萊文斯坦距離是 3，最長公共子串長度是 4。
如何編程計算萊文斯坦距離？
了解了編輯距離的概念之后，我們來看，如何快速計算兩個字符串之間的編輯距離？我現(xiàn)在就給你展示一下，解決這個問題，我的完整的思考過程。
這個問題是求把一個字符串變成另一個字符串，需要的最少編輯次數(shù)。整個求解過程，涉及多個決策階段，我們需要依次考察一個字符串中的每個字符，跟另一個字符串中的字符是否匹配，匹配的話如何處理，不匹配的話又如何處理。所以，這個問題符合多階段決策最優(yōu)解模型。
我們前面講了，貪心、回溯、動態(tài)規(guī)劃可以解決的問題，都可以抽象成這樣一個模型。要解決這個問題，我們可以先看一看，用最簡單的回溯算法，該如何來解決。
回溯是一個遞歸處理的過程。
如果 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]。
代碼如下：
private char[] a = "mitcmu".toCharArray();
private char[] b = "mtacnu".toCharArray();
private int n = 6;
private int m = 6;
private int minDist = Integer.MAX_VALUE; // 存儲結(jié)果
// 調(diào)用方式 lwstBT(0, 0, 0);
public 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]替換為相同字符
}
}
根據(jù)回溯算法的代碼實現(xiàn)，我們可以畫出遞歸樹，看是否存在重復(fù)子問題。如果存在重復(fù)子問題，那我們就可以考慮能否用動態(tài)規(guī)劃來解決；如果不存在重復(fù)子問題，那回溯就是最好的解決方法。
在遞歸樹中，每個節(jié)點代表一個狀態(tài)，狀態(tài)包含三個變量 (i, j, edist)，其中，edist 表示處理到 a[i]和 b[j]時，已經(jīng)執(zhí)行的編輯操作的次數(shù)。
在遞歸樹中，(i, j) 兩個變量重復(fù)的節(jié)點很多，比如 (3, 2) 和 (2, 3)。對于 (i, j) 相同的節(jié)點，我們只需要保留 edist 最小的，繼續(xù)遞歸處理就可以了，剩下的節(jié)點都可以舍棄。所以，狀態(tài)就從 (i, j, edist) 變成了 (i, j, min_edist)，其中 min_edist 表示處理到 a[i]和 b[j]，已經(jīng)執(zhí)行的最少編輯次數(shù)。
這個問題的狀態(tài)轉(zhuǎn)移方式，要比之前兩節(jié)課中講到的例子都要復(fù)雜很多。今天這個問題，狀態(tài) (i, j) 可能從 (i-1, j)，(i, j-1)，(i-1, j-1) 三個狀態(tài)中的任意一個轉(zhuǎn)移過來。
基于剛剛的分析，我們可以嘗試著將把狀態(tài)轉(zhuǎn)移的過程，用公式寫出來。
如果：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)
如果：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))
其中，min表示求三數(shù)中的最小值。
了解了狀態(tài)與狀態(tài)之間的遞推關(guān)系，我們畫出一個二維的狀態(tài)表，按行依次來填充狀態(tài)表中的每個值。
具體代碼如下：
public int lwstDP(char[] a, int n, char[] b, int m) {
int[][] minDist = new int[n][m];
for (int j = 0; j < m; ++j) { // 初始化第0行:a[0..0]與b[0..j]的編輯距離
if (a[0] == b[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 = 0; i < n; ++i) { // 初始化第0列:a[0..i]與b[0..0]的編輯距離
if (a[i] == b[0]) minDist[i][0] = i;
else if (i != 0) minDist[i][0] = minDist[i-1][0]+1;
else minDist[i][0] = 1;
}
for (int i = 1; i < n; ++i) { // 按行填表
for (int j = 1; j < m; ++j) {
if (a[i] == b[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[n-1][m-1];
}
private int min(int x, int y, int z) {
int minv = Integer.MAX_VALUE;
if (x < minv) minv = x;
if (y < minv) minv = y;
if (z < minv) minv = z;
return minv;
}
關(guān)于復(fù)雜算法問題的解決思路，我還有一些經(jīng)驗、小技巧，可以分享給你。
當(dāng)我們拿到一個問題的時候，我們可以先不思考，計算機會如何實現(xiàn)這個問題，而是單純考慮“人腦”會如何去解決這個問題。人腦比較傾向于思考具象化的、摸得著看得見的東西，不適合思考過于抽象的問題。所以，我們需要把抽象問題具象化。那如何具象化呢？我們可以實例化幾個測試數(shù)據(jù)，通過人腦去分析具體實例的解，然后總結(jié)規(guī)律，再嘗試套用學(xué)過的算法，看是否能夠解決。
除此之外，我還有一個非常有效、但也算不上技巧的東西，我也反復(fù)強調(diào)過，那就是多練。
如何編程計算最長公共子串長度？
最長公共子串作為編輯距離中的一種，只允許增加、刪除字符兩種編輯操作。從名字上，你可能覺得它看起來跟編輯距離沒什么關(guān)系。實際上，從本質(zhì)上來說，它表征的也是兩個字符串之間的相似程度。
針對這個問題，我直接定義狀態(tài)，然后寫狀態(tài)轉(zhuǎn)移方程。
每個狀態(tài)還是包括三個變量 (i, j, max_lcs)，max_lcs 表示 a[0…i]和 b[0…j]的最長公共子串長度。那 (i, j) 這個狀態(tài)都是由哪些狀態(tài)轉(zhuǎn)移過來的呢？
我們先來看回溯的處理思路。我們從 a[0]和 b[0]開始，依次考察兩個字符串中的字符是否匹配。
如果 a[i]與 b[j]互相匹配，我們將最大公共子串長度加一，并且繼續(xù)考察 a[i+1]和 b[j+1]。
如果 a[i]與 b[j]不匹配，最長公共子串長度不變，這個時候，有兩個不同的決策路線：
- 刪除 a[i]，或者在 b[j]前面加上一個字符 a[i]，然后繼續(xù)考察 a[i+1]和 b[j]；
- 刪除 b[j]，或者在 a[i]前面加上一個字符 b[j]，然后繼續(xù)考察 a[i]和 b[j+1]。
反過來也就是說，如果我們要求 a[0…i]和 b[0…j]的最長公共長度 max_lcs(i, j)，我們只有可能通過下面三個狀態(tài)轉(zhuǎn)移過來：
(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]的最長公共子串長度。
如果：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-1, j), max_lcs(i, j-1))；
其中max表示求三數(shù)中的最大值。
代碼如下：
public int lcs(char[] a, int n, char[] b, int m) {
int[][] maxlcs = new int[n][m];
for (int j = 0; j < m; ++j) {//初始化第0行：a[0..0]與b[0..j]的maxlcs
if (a[0] == b[j]) maxlcs[0][j] = 1;
else if (j != 0) maxlcs[0][j] = maxlcs[0][j-1];
else maxlcs[0][j] = 0;
}
for (int i = 0; i < n; ++i) {//初始化第0列：a[0..i]與b[0..0]的maxlcs
if (a[i] == b[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 < n; ++i) { // 填表
for (int j = 1; j < m; ++j) {
if (a[i] == b[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[n-1][m-1];
}
private int max(int x, int y, int z) {
int maxv = Integer.MIN_VALUE;
if (x > maxv) maxv = x;
if (y > maxv) maxv = y;
if (z > maxv) maxv = z;
return maxv;
}
解答開篇
今天的內(nèi)容到此就講完了，我們來看下開篇的問題。
當(dāng)用戶在搜索框內(nèi)，輸入一個拼寫錯誤的單詞時，我們就拿這個單詞跟詞庫中的單詞一一進行比較，計算編輯距離，將編輯距離最小的單詞，作為糾正之后的單詞，提示給用戶。這就是拼寫糾錯最基本的原理。
針對糾錯效果不好的問題，我們有很多種優(yōu)化思路，我這里介紹幾種。
我們并不僅僅取出編輯距離最小的那個單詞，而是取出編輯距離最小的 TOP 10，然后根據(jù)其他參數(shù)，決策選擇哪個單詞作為拼寫糾錯單詞。比如使用搜索熱門程度來決定哪個單詞作為拼寫糾錯單詞。
我們還可以用多種編輯距離計算方法，比如今天講到的兩種，然后分別編輯距離最小的 TOP 10，然后求交集，用交集的結(jié)果，再繼續(xù)優(yōu)化處理。
我們還可以通過統(tǒng)計用戶的搜索日志，得到最常被拼錯的單詞列表，以及對應(yīng)的拼寫正確的單詞。搜索引擎在拼寫糾錯的時候，首先在這個最常被拼錯單詞列表中查找。如果一旦找到，直接返回對應(yīng)的正確的單詞。這樣糾錯的效果非常好。
我們還有更加高級一點的做法，引入個性化因素。針對每個用戶，維護這個用戶特有的搜索喜好，也就是常用的搜索關(guān)鍵詞。當(dāng)用戶輸入錯誤的單詞的時候，我們首先在這個用戶常用的搜索關(guān)鍵詞中，計算編輯距離，查找編輯距離最小的單詞。
針對糾錯性能方面，我們也有相應(yīng)的優(yōu)化方式。我講兩種分治的優(yōu)化思路。文章來源：http://www.zghlxwxcb.cn/news/detail-770414.html
如果糾錯功能的 TPS 不高，我們可以部署多臺機器，每臺機器運行一個獨立的糾錯功能。當(dāng)有一個糾錯請求的時候，我們通過負載均衡，分配到其中一臺機器，來計算編輯距離，得到糾錯單詞。
如果糾錯系統(tǒng)的響應(yīng)時間太長，也就是，每個糾錯請求處理時間過長，我們可以將糾錯的詞庫，分割到很多臺機器。當(dāng)有一個糾錯請求的時候，我們就將這個拼寫錯誤的單詞，同時發(fā)送到這多臺機器，讓多臺機器并行處理，分別得到編輯距離最小的單詞，然后再比對合并，最終決定出一個最優(yōu)的糾錯單詞。文章來源地址http://www.zghlxwxcb.cn/news/detail-770414.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)與算法之美學(xué)習(xí)筆記：42 | 動態(tài)規(guī)劃實戰(zhàn)：如何實現(xiàn)搜索引擎中的拼寫糾錯功能？的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
