文章关键字替换的问题

Question

现在有一个 字典

key 是关键字名称

value 是 关键字的链接地址

 

发一篇文章 如何高效的替换 关键字为对应的文章

并且只替换一次呢？

并且已经是处于链接中的字 不参与替换

 

这种需求很多新闻网站都用得到 不知道各位有没有好的办法！

Answer 1

按照常规匹配，把长度为M的字典中的key都枚举出来，然后从长度为N的文章中搜索关键词，找到则替换。搜索的时间复杂度是O(M*N)。替换的时间复杂度取决于字典的查找速度和匹配到关键词的个数，假设字典的时间复杂度是最理想状况O(1)，要替换的关键字个数为K，那么替换的时间复杂度就是O(K)，如果通过数组存储整篇文章还需要调整位置，则为O(K*N)。这样最好情况下的复杂度就是O(M*N + K*N)。再按照楼主200个关键字，一篇平常的5000字文章需要搜索1百万次。假设有10处替换项，保守估计需要5万次的操作。这样算来，如果文章较长再加字典中关键词多，那就指数级增长。对于文章本身，可以中文分词后再匹配，会降低复杂度。对于字典，可以尝试使用其它数据结构，例如trie树等。

Answer 2

正则是个不错的选择,不知道你的字典里面到底有多少个key与value如果太多,并且文章非常长的话,那还是会存在效率问题的.

Answer 3

可以考虑在客户端用javascript实现吧,  很多highlight的library实现了关键字高亮,  使用其中的逻辑, 根据字典替换高亮成为链接。字典则可以从server端使用json传过去。