使用 JavaScript 實現簡單候選項推薦功能（模糊搜索）

當我們使用 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 上面了：

也可以點擊這里查看。

使用起來是有點效果的，比如：

和

但是也有很大的偏差，比如要搜索的關鍵詞和相似結果編輯距離太大，超過了同等長度的不同字符，這時候就會出現錯誤的推薦：

如果數據足夠多，各種情況都具備，那么推薦準確的可能性更大些。如果要改善這個功能，可能需要結合中文分詞對關鍵詞進行匹配綜合等等，超出本文范疇這里不再贅述。

來自：http://yujiangshui.com/javascript-levenshtein-distance/