区总工会加强网站意识形态建设,什么网站可以做音乐相册,金坛城乡建设管理网站,学校机构网站建设内容当我们使用 Google 等搜索功能时#xff0c;会出现与搜索内容有关的候选项。使用 JavaScript 搜索字符串#xff0c;通常会使用 indexOf 或者 search 函数#xff0c;但是非常僵硬#xff0c;只能搜索匹配特定词语。比如使用关键词 今天是星期几 想要检索 今天是星期五 这个… 当我们使用 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
