使用 JavaScript 实现简单候选项推荐功能（模糊搜索）【收藏】【转】

时间：2024-08-14 19:04:14

当我们使用 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/

相关文章