2 yca2220206 yca2220206 于 2014.06.12 11:13 提问

集思广益,有个几百万关键字的文本匹配的算法,大家进来看看

关键字 都是放在一个数组中的,譬如$keyword_arr=["key1","key2","example",......],大约有几百万甚至上千万的关键字,这些关键字已经按照优先级从前到后排列了,越靠前的关键字优先匹配,匹配的最多次数是$max次;目前采用for循环$keyword_arr数组,然后将关键字组装成'/\b(?:'.$value.')\b/i';正则来匹配文本内容$text;如果已经匹配了$max次了,就停止匹配。

这个算法肯定是最低效的,大家有好的建议可以提出来,主要问题是关键字优先级有点麻烦

php: 目前采用正则匹配:

        foreach ($keyword_arr as $key=>$value) {
            $pattern = '/\\b(?:'.$value.')\\b/i';
            preg_match($pattern, $text, $match, PREG_OFFSET_CAPTURE);
            if ($match && trim($match[0][0]) != '' && !in_array(strtolower($match[0][0]), $match_keyword_arr)) {
                $match_keyword_arr[] = strtolower($match[0][0]);
                $count ++;
                if ($count >= $max) {
                    break;
                }
        }

1个回答

kevin_Luan
kevin_Luan   2014.06.15 18:35

类似这种处理不建议正则,大量使用正则会消耗很高的CPU。
优化方法:
建议使用状态机的方式实现。其实你的需求简单理解为通过一批关键字匹配关键字然后处理后续的业务等。

我之前处理相似的业务
1. 写了一个StringToken处理类
http://blog.csdn.net/kevin_luan/article/details/26875341
2. 敏感词过滤
http://download.csdn.net/detail/kevin_luan/7322435

我使用JAVA写的,不过PHP同样可以实现相似的业务,希望对你有所启发。

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
文本中关键字匹配算法
给定一定数量的关键字,对任一篇文本,寻找文本中包含哪些关键字并加亮这些关键字 这个文本处理需要一个算法, 普通的文本处理直接去遍历所有的关键字,但是这种算法太复杂,时间复杂度太高。 之前的文章中有说过,实际用到的算法,为了加快执行速度,都是在时间和空间上做的兑换。这里同样可以,通过增加存储空间来减少程序执行时间。 可以选择开一个数组,数组的长度是char类型的最大长度加一。
文本中关键字匹配算法的实现
文本中关键字匹配算法的实现
几种文字匹配算法
最近 Android 做了一个全文关键字高亮的功能,直接用了 Java 现成的 API 解决了,在查阅资料的过程中得知还有几种匹配算法:BF、RK、KMP、BM、Sunday,有空就做了一些了解。这里记录一下防止忘记,阮一峰大神关于这些算法的博客写的很好。BF暴力检索,这种方法最容易想到,也是最容易实现的,从首字母开始挨个的将关键字和做比对。用下面的图片就能只管的说明(图片来自阮一峰大神的博客)
文本比较算法剖析(1)-如何确定最大匹配率
最近看到有人在找关于文本比较的算法,刚好最近休假,研究了一下,终于找到一个简单有效的算法,和大家分享一下。 算法本身很简单,但是要说清楚思路和原理就比较复杂了,打算分两次发表(明天就要上班拉!),分别对应文本比较算法中的两个主要问题: 1。如何确定最大匹配率;  2。如何确定最优的匹配路径; 算法本身是基于图论的,太麻烦了,所以不打算介绍整个思路,只将最后的结果详细解说给大家。有问题可以发
从文件中查找关键字算法
// (1)源文件为一个txt文档,内容为符号串; // (2)给定一个关键字文件,内容为自定义的关键字(注:关键字有若干个,用空格隔开); // (3)依据关键字文件中的关键字在源文件中进行检索判断,得到关键字 #include"stdio.h" #include"string.h" #include"malloc.h" #define BUFLEN 2048
DFA 算法实现关键词匹配
起因: 从网页中爬去的页面,需要判断是否跟预设的关键词匹配(是否包含预设的关键词),并返回所有匹配到的关键词 。 目前pypi 上两个实现ahocorasick https://pypi.python.org/pypi/ahocorasick/0.9 esmre https://pypi.python.org/pypi/esmre/0.3.1但是其实包都是基于DFA 实现的 这里提供源码如
关键字匹配之BF算法-python实现
关键字匹配之BF算法
中文文本关键字分割算法
这几天为Gimi Talk研究中文的分词,主要问题是要消除歧义的关键字,如何分割的问题。 参看了几篇文章,例句:长春市长春药店 1.查找所有有效词(起始位置和词长): 长春(0,2),长春市(0,3),市长(2,2),长春(3,2),春药(4,2),药店(5,2) 2.找出所有有效词可能的组合:      a.长春/市长/春药/店     登录词:3个     碎
KMP文本匹配算法
KMP算法作者:ljs2011-06-20(转载请注明出处,谢谢!)KMP(Knuth–Morris–Pratt)算法的发明时间几乎跟BM(Boyer-Moore)算法在同一时期,即上世纪70年代末(巧合的是随着互联网的发展对文本处理提出了更高的要求,从而最近几年字符处理又成了热门话题),二者在最坏情况下的时间复杂度都是O(n)。它与BM算法的主要区别是:1)在每次匹配中都是从左到右匹配,BM算法
文本关键词提取算法总结
1.TF-IDF 昨天给大家演示简单的文本聚类,但要给每个聚类再提取一两个关键词用于表示该聚类。我们还是用TFIDF算法来做,因为这是比较简单的提取特征算法,不过这里的TF是指某词在本聚类内所有文章的词频,而不是本文章内出现的次数,IDF还是在所有文章里出现的倒文档频率。 原理:1、先给本聚类内的所有文档进行分词,然后用一个字典保存每个词出现的次数 2、遍历每个词,得到每个词在所有文档里