Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1490222
  • 博文数量: 465
  • 博客积分: 8915
  • 博客等级: 中将
  • 技术积分: 6365
  • 用 户 组: 普通用户
  • 注册时间: 2010-07-30 15:05
文章分类

全部博文(465)

文章存档

2017年(33)

2016年(2)

2015年(4)

2014年(29)

2013年(71)

2012年(148)

2011年(178)

分类: IT业界

2011-08-17 17:52:26

什么是关键字链接?

博客服务Hatena Diary)支持关键字链接,这是个很特别的功能。

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

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

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

关键字链接的例子

Hatena Diary是博客

Hatena Diary博客

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

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

 

 

   

    eturn 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://blog.chinaunix.net/space.php?uid=13164110&do=blog&id=2211482

阅读(469) | 评论(0) | 转发(0) |
0

上一篇:何谓算法

下一篇:算法和数据结构

给主人留下些什么吧!~~