知識星球
當我們使用 Google 等搜尋功能時，會出現與搜尋內容有關的候選項。使用 JavaScript 搜尋字串，通常會使用 indexOf 或者 search 函式，但是非常僵硬，只能搜尋匹配特定詞語。比如使用關鍵詞 今天是星期幾 想要檢索 今天是星期五 這個內容，就無法實現，雖然它們只有很小的差別。
本文就來介紹一個有趣的演演算法 編輯距離（Levenshtein Distance），然後用它來實現一個簡單的候選項推薦（模糊搜尋）功能。
編輯距離（Levenshtein Distance）
簡單的說，編輯距離就是把一個字串修改變成另一個字串的修改次數。如果修改的次數越小，我們可以簡單的認為這兩個字串之間的關係越緊密。比如 今天是星期幾 對於 今天是星期五 和 明天是星期五比較，跟 今天是星期五 更加緊密一些，因為前者的編輯距離是 1，後者的編輯距離是 2。
更詳細的百度百科已經說的很清楚了，這裡不再贅述，主要給出 JavaScript 的實現方法：
按照自然語言表達的演演算法，我們先需要根據兩個字串的長度建立一個二維表：
function levenshtein(a, b) {
var al = a.length + 1;
var bl = b.length + 1;
var result = [];
var temp = 0;
// 建立一個二維陣列
for (var i = 0; i < al; result[i] = [i++]) {}
for (var i = 0; i < bl; result[0][i] = i++) {}
}
之後就需要遍歷這個二位陣列，按照如下的規則取得三個值的最小值：
如果最上方的字元等於最左方的字元，則為左上方的數字。否則為左上方的數字 + 1。
左方數字 + 1
上方數字 + 1
需要判斷兩個值是否相等來決定左上方數字是否 + 1，所以引入 temp 變數。我們可以寫出如下遍歷程式碼：
for (i = 1; i < al; i++) {
for (var j = 1; j < bl; j++) {
// 判斷最上方和最左方數字是否相等
temp = a[i – 1] == b[j – 1] ? 0 : 1;
// result[i – 1][j] + 1 左方數字
// result[i][j – 1] + 1 上方數字
// result[i – 1][j – 1] + temp 左上方數字
result[i][j] = Math.min(result[i – 1][j] + 1, result[i][j – 1] + 1, result[i – 1][j – 1] + temp);
}
}
最後將二維陣列最後一個值傳回，該值就是編輯距離：
return result[i-1][j-1];
這個函式就完成了：
function levenshtein(a, b) {
var al = a.length + 1;
var bl = b.length + 1;
var result = [];
var temp = 0;
// 建立一個二維陣列
for (var i = 0; i < al; result[i] = [i++]) {}
for (var i = 0; i < bl; result[0][i] = i++) {}
for (i = 1; i < al; i++) {
for (var j = 1; j < bl; j++) {
// 判斷最上方和最左方數字是否相等
temp = a[i – 1] == b[j – 1] ? 0 : 1;
// result[i – 1][j] + 1 左方數字
// result[i][j – 1] + 1 上方數字
// result[i – 1][j – 1] + temp 左上方數字
result[i][j] = Math.min(result[i – 1][j] + 1, result[i][j – 1] + 1, result[i – 1][j – 1] + temp);
}
}
return result[i-1][j-1];
}
實際應用
那麼我們現在就來實現一個簡單的搜尋功能。
大體思路就是將資料與要搜尋的字串計算編輯距離，然後進行排序，將編輯距離小的放在上面顯示。具體 Demo 做在 jsfiddle 上面了：
也可以點選這裡檢視。
使用起來是有點效果的，比如：
和
但是也有很大的偏差，比如要搜尋的關鍵詞和相似結果編輯距離太大，超過了同等長度的不同字元，這時候就會出現錯誤的推薦：
如果資料足夠多，各種情況都具備，那麼推薦準確的可能性更大些。如果要改善這個功能，可能需要結閤中文分詞對關鍵詞進行匹配綜合等等，超出本文範疇這裡不再贅述。
原文出處：於江水的部落格（@於江水）