歡迎光臨
每天分享高質量文章

使用 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 上面了:

也可以點擊這裡查看。

使用起來是有點效果的,比如:

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

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


原文出處:於江水的博客(@於江水)

赞(0)

分享創造快樂