微信号:FrontDev

介绍:分享 Web 前端相关的技术文章、工具资源、精选课程、热点资讯

使用 JavaScript 实现简单候选项推荐功能(模糊搜索)

2015-01-23 20:25 前端大全
点击上方蓝字↑↑↑,轻松关注哦~

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


也可以点击这里查看。


使用起来是有点效果的,比如:





但是也有很大的偏差,比如要搜索的关键词和相似结果编辑距离太大,超过了同等长度的不同字符,这时候就会出现错误的推荐:



如果数据足够多,各种情况都具备,那么推荐准确的可能性更大些。如果要改善这个功能,可能需要结合中文分词对关键词进行匹配综合等等,超出本文范畴这里不再赘述。



原文出处:于江水的博客(@于江水)


/////////////////


1. 『前端大全』分享 Web 前端相关的技术文章、工具资源、精选课程、热点资讯,欢迎关注。微信号:FrontDev

2. 点击“阅读原文”,查看更多前端文章。


 
前端大全 更多文章 5个典型的JavaScript面试题(上) Limu:JavaScript的那些书 Web开发:我希望得到的编程学习路线图 JavaScript基础工具清单 常用排序算法之JavaScript实现
猜您喜欢 博赛网络9月新班即将开课 【前辈指导】知名产品总监谈:产品经理成长三阶段 Ant+JMeter+WebDriverAgent 游记 程序员如何迎接2016 给微信产品经理的十个建议