當我們使用 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];}

?

?

實際應用

那么我們現在就來實現一個簡單的搜索功能。

?

原文地址：http://www.yujiangshui.com/javascript-levenshtein-distance/

?

轉載于:https://www.cnblogs.com/LoveOrHate/p/4487987.html

總結

以上是生活随笔為你收集整理的使用 JavaScript 实现简单候选项推荐功能（模糊搜索）【收藏】【转】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。