ITPub博客

首页 > Linux操作系统 > Linux操作系统 > 什么是关键字链接?

什么是关键字链接?

原创 Linux操作系统 作者:broadviewbj 时间:2011-08-17 17:51:49 0 删除 编辑

什么是关键字链接?

什么是关键字链接?

博客服务Hatena Diaryhttp://d.hatena.ne.jp/)支持关键字链接,这是个很特别的功能。

该功能在前面的图5.3p.112)的关键字链接截图中已介绍过。如图5.3所示,写博客时部分关键字会自动加上链接,链接目标就是该关键字的解释页面。Wiki的实现也能给Wiki关键字自动加链接,这个功能与它很相似。

被链接的关键字就是用户在Hatena Keywordhttp://k. hatena.ne.jp/)上添加的关键字。本书执笔时(20098月),Hatena Keyword已有27万条以上关键字,用户每天创建的新关键字大约有100个。

关键字链接功能就是将输入的文章与27万条关键字字典进行匹配,将必要的地方替换成链接。链接替换操作实际上只是将特定关键字替换成HTML链接标签而已,所以问题就是如何对文章中的关键字进行文本替换。

关键字链接的例子

Hatena Diary是博客

Hatena Diary博客

最初的实现

Hatena Diary刚刚上线时,该功能并没有花太多功夫,简单地采用了正则表达式,将字典中的所有单词用OR连接做成正则表达式。

(foo|bar|baz| ...)

就是这种正则表达式。假设将文本放在$text变量中,那么把替换选项和替换字符串看作表达式的eval选项进行组合,变成以下形式就可以了:

use URI::Escape;

 

$text =~ s/(foo|bar|baz)/&replace_keyword($1)/ge;

 

sub replace_keyword {

    my $w = shift;

    return sprintf '%s', uri_escape($w), $w;

}

出问题了!—关键字字典越来越大

由于关键字是用户创建的,刚上线时单词数并不多,从数据库中取出后直接创建正则表达式以实现关键字链接,这种奢侈的处理也完全没有问题。但是,随着关键字的数量不断增加,问题就来了。处理正则表达式要花费很长时间。最耗时的地方有两处:

u编译正则表达式的处理;

v用正则表达式进行模式匹配的处理。

对于u,可以预先创建正则表达式并保持在内存或磁盘上,即通过缓存的方法能够绕过去了。

对于问题v,把完成了关键字链接的正文文本进行缓存等处理后,开始时能绕过该问题,但要将新添的关键字反映到关键字链接中,必须花费一定时间重新建立缓存,或者从博客服务的特性上看,多一半文章的访问量并不大,导致缓存很难生效,所以该问题并没有完全解决。

用模式匹配实现关键字链接的问题

随着服务的运营,关键字的单词数超过了10万条,而且Hatena Diary增加的整体访问量使得关键字链接的处理次数也增加了许多,系统终于承受不住了。

关键字链接计算耗费大量时间的原因在于正则表达式的算法。详细情况可以参考正则表达式的书籍,简单来说,正则表达式的模式匹配是基于自动机实现的。而且,Perl的正则表达式实现采用的是NFANondeterministic Finite Automata,非确定型有穷自动机)。不仅Perl,实用的语言大多采用了NFA引擎。

像(foo|bar|baz)这种模式匹配,NFA会使用一种简单的方法,从输入的开头尝试匹配,失败的话就尝试下一个单词,如果又失败了,就再次尝试下一个单词。因此,foo不匹配就尝试bar,如果还不匹配,就尝试baz……如此循环下去。因此,计算量与关键字的个数成比例。

服务刚开始时,关键字个数很少,相应的计算量也很少,所以没有发生什么问题。

 

本文节选自《大规模WEB服务开发技术》一书

图书详细信息:http://space.itpub.net/?uid-13164110-action-viewspace-itemid-705176

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/13164110/viewspace-705181/,如需转载,请注明出处,否则将追究法律责任。

上一篇: 何谓算法
下一篇: 算法和数据结构
请登录后发表评论 登录
全部评论

注册时间:2008-02-22

  • 博文量
    1030
  • 访问量
    1617986