在论坛和聊天室这样的场景里，为了保证用户体验，我们经常需要屏蔽很多不良词语。对于单个关键词查找，自然是indexOf、正则那样的方式效率比较高。但对于关键词较多的情况下，多次重复调用indexOf、正则的话去匹配全文的话，性能消耗非常大。由于目标字符串通常来说体积都比较大，所以必须要保证一次遍历就得到结果。根据这样的需求，很容易就想到对全文每个字符依次匹配的方式。比如对于这段文字：“Mike Jordan had said "Just do IT", so Mark has been a coder.”，假如我们的关键词是“Mike”“Mark”，那么可以遍历整句话，当找到“M”就接着看能不能匹配到“i”或者“a”，能一直匹配到最后则成功找到一个关键词，否则继续遍历。那么关键词的结构就应该是这样的：
var keywords = { M: { i: { k: { e: {end: true} } }, a: { r: { k: {end: true} } } } }
由上文可以看出这个数据就是一个树结构，而根据关键词组来创建树结构还是比较耗时的，而关键词却又是我们早已给定的，所以可以在匹配前预先创建这样的数据结构。代码如下：
function buildTree(keywords) { var tblCur = {}, key, str_key, Length, j, i; var tblRoot = tblCur; for(j = keywords.length - 1; j >= 0; j -= 1) { str_key = keywords[j]; Length = str_key.length; for(i = 0; i < Length; i += 1) { key = str_key.charAt(i); if(tblCur.hasOwnProperty(key)) { tblCur = tblCur[key]; } else { tblCur = tblCur[key] = {}; } } tblCur.end = true; //最后一个关键字 tblCur = tblRoot; } return tblRoot; }
这段代码中用了一个连等语句：tblCur = tblCur[key] = {}，这里要注意的是语句的执行顺序，由于[]的运算级比=高，所以首先是在 tblCur对象中先创建一个key属性。结合tblRoot = tblCur = {} 看，执行顺序就是：
var tblRoot = tblCur = {}; tblRoot = tblCur; tblCur['key'] = undefined; // now tblRoot = {key: undefined} tblCur['key'] = {}; tblCur = tblCur['key'];
通过上面的代码就构建了好了所需的查询数据，下面看看查询接口的写法。
对于目标字符串的每一字，我们都从这个keywords顶部开始匹配。首先是 keywords[a] ，若存在，则看 keyword[a][b]，若最后 keyword[a][b]…[x]=true 则说明匹配成功，若 keyword[a][b]…[x]=undefined，则从下一个位置重新开始匹配 keywords[a] 。
function search(content) { var tblCur, p_star = 0, n = content.length, p_end, match, //是否找到匹配 match_key, match_str, arrMatch = [], //存储结果 arrLength = 0; //arrMatch的长度索引 while(p_star < n) { tblCur = tblRoot; //回溯至根部 p_end = p_star; match_str = ""; match = false; do { match_key = content.charAt(p_end); if(!(tblCur = tblCur[match_key])) { //本次匹配结束 p_star += 1; break; } else { match_str += match_key; } p_end += 1; if(tblCur.end) //是否匹配到尾部 { match = true; } } while (true); if(match) { //最大匹配 arrMatch[arrLength] = { key: match_str, begin: p_star - 1, end: p_end }; arrLength += 1; p_star = p_end; } } return arrMatch; }
以上就是整个关键词匹配系统的核心。这里很好的用到了js的语言特性，效率非常高。我用一篇50万字的《搜神记》来做测试，从中查找给定的300个成语，匹配的效果是1秒左右。重要的是，由于目标文本是一次遍历的，所以目标文本的长短对查询时间的影响几乎不计。对查询时间影响较大的是关键词的数量，目标文本的每个字都遍历一遍关键词，所以对查询有一定影响。
简单分析
看到上文估计你也纳闷，对每个字都遍历一遍所有关键词，就算有些关键词有部分相同，但是完全遍历也是挺耗时的呀。但js中对象的属性是使用哈希表来进行构建的，这种结构的数据跟单纯的数组遍历是有很大不同的，效率要比基于顺序的数组遍历高得多。可能有些同学对数据结构不太熟悉，这里我简单说一下哈希表的相关内容。
首先看看数据的存储。
数据在内存的存储由两部分组成，一部分是值，另一部分是地址。把内存想象成一本新华字典，那字的解释就是值，而目录就是地址。字典里面是按拼音排序的，比如相同发音的“ni”就排在同一块，也就是说数组整齐排列在一块内存区域里面，这样的结构就是数组，你可以指定“ni” 1号，10号来访问。结构图如下：
数组的优势是遍历简单，通过下标就能直接访问相应的数据了。但是它要增删某一项就非常困难。比如你要把第6项删掉，那第5项之后的数据都要向前移一个位置。如果你要删除第一位，整个数组都要移动，消耗非常大。
