提到关键字搜索首先联想到的无非就是使用一些indexOfreplace之类的字符函数最多加上一些正则表达式而已实现起来虽然很简单但是这 背后的效率问题可曾仔细考虑过？例如论坛中的关键字过滤一般情况下需过滤的关键字数量及检测的文本长度都不大所以这一瞬间的过程没有太多值得关注的地 方但若关键字数量不在是屈指可数而是有成千上万 并且待检测的文本也是一长篇大论结果可不再是那么乐观了大家都知道每多一个关键字就要增加一次全文的检索最终花费的时间将远远超出可接受的范围 内
既然考虑的是那种极端的关键字搜索通常的逐个遍历搜索显然是行不通的如今用的是JavaScript若不使用Hash表实在是太对不起这门语言了有着对表特天独厚的支持不妨就拿出少量的空间来换取大量的时间吧
先看个例子比如有如下的关键字: foofoobarbar既然要用空间换时间因此搜索之前先将他们预处理前面提到了JS灵活又高效的表显而易见使用树的结构是最 有优势的即使不明白也没关系最终实现结构正如如下的代码熟悉JSON同样很亲切
复制代码 代码如下:
var Root =
{
f:
{
o:
{
o:
{
: true
: true
}
}
}
b:
{
a:
{
r:
{
: true
: true
}
}
}
};
这一层层的结构正如一棵树每个字符便是树的一个分枝到了最后一个字符便是树叶不再有新的节点
此时你应该明白了只要对文章的每个字沿着这棵树往下搜就是了能到达树叶的就说明当前字符就是关键字的一个中途寻找不到对应枝干的当然就不是关键字
例如foo顺着Root结构向下访问最终到达Root[f][o][o][]即完成了一次匹配之后跳过foo的长度继续往后检索
因此整篇文章只需一次检索即可找出每个关键字的位置
由于JS的hash表性能非常高所以所谓的寻找枝干也就非常的快了因为JS的灵活性实现此效果的代码同样很简短
事实上可以发现关键字的数量与搜索的时间并没太多的关系那仅仅影响了树的宽度而已只有文章的长度才是决定搜索的时间
来一次极限测试
关键字 成语全集(条)
内容诛仙全集txt (字)
用时ms
(Chrome / i的CPU)
万字的文章匹配万个关键字还不到秒的时间可见充分利用JavaScript的灵活性仍能发挥很大的潜力
