查看: 112|回复: 0

小时到分钟 - 一步步优化巨量关键词的匹配

[复制链接]

该用户从未签到

发表于 2019-11-4 06:28:42 | 显示全部楼层 |阅读模式
题目由来

前些天工作中遇到一个题目:
有 60万 条短消息记载日志,每条约 50 字,5万 关键词,长度 2-8 字,绝大部分为中文。要求将这 60万 条记载中包含的关键词全部提取出来并统计各关键词的命中次数。
本文完整介绍了我的实现方式,看我如何将需要运行十小时的任务优化到十分钟以内。虽然实现语言是 PHP,但本文介绍的更多的头脑,应该能给各人一些帮助。
原始 - grep

计划

一开始接到任务的时候,我的小心思立即转了起来,日志 + 关键词 + 统计,我没有想到自己写代码实现,而是首先想到了 linux 下常用的日志统计下令 grep。
grep下令的用法不再多提,利用 grep 'keyword' | wc -l 可以很方便地进行统计关键词命中的信息条数,而php的 exec() 函数允许我们直接调用 linux 的 shell 下令,虽然这样实行伤害下令时会有安全隐患。
代码

上伪代码:
  1. foreach ($word_list as $keyword) {    $count = intval(exec("grep '{$keyword}' file.log | wc -l"));    record($keyword, $count);}
复制代码
在一台老机器上跑的,话说老机器效率真的差,跑了6小时。估计最新机器2-3小时吧,后面的优化都利用的新机器,而且需求又有变动,正文才刚刚开始。
原始,原始在想法和方法
进化 - 正则

计划

交了差之后,第二天产品又提出了新的想法,说以后想把某数据源接入进来,消息以数据流的形式传递,而不再是文件了。而且还要求了消息统计的实时性,一下把我想把数据写到文件再统计的想法也推翻了,为了方案的可扩展性,如今的统计对象不再是一个整体,而是要考虑拿n个单条的消息来匹配了。
这时,略懵的我只好祭出了最传统的工具- 正则。正则的实现也不难,各个语言也都封装好了正则匹配函数,重点是模式(pattern)的构建。
当然这里的模式构建也不难,/keyword1|keword2|.../,用|将关键词连接起来即可。
正则小坑

这里介绍两个利用中遇到的小坑:

  • 正则模式长度太长导致匹配失败:
    PHP 的正则有回溯限制,以防止消耗掉全部的进程可用堆栈, 终极导致 php 崩溃。太长的模式会导致 PHP 检测到回溯过多,停止匹配,经测试默认设置时最大模式长度为 32000 字节 左右。
    php.ini 内 pcre.backtrack_limit 参数为最大回溯次数限制,默认值为 1000000,修改或php.ini 或在脚本开始时利用ini_set(‘pcre.backtrack_limit’, n); 将其设置为一个较大的数可以进步单次匹配最大模式长度。当然也可以将关键词分批统计(我用了这个=_=)。
  • 模式中含有特别字符导致大量warning:
    匹配过程中发现 PHP 报出大量 warning:unknown modifier 乱码,细致检查发现关键词中有/字符,可以利用preg_quote()函数过滤一遍关键词即可。
代码

上伪代码:
  1. $end = 0;$step = 1500;$pattern = array();// 先将pattern 拆成多个小块while ($end < count($word_list)) {    $tmp_arr = array_slice($word_list, $end, $step);    $end += $step;    $item = implode('|', $tmp_arr);    $pattern[] = preg_quote($item);}$content = file_get_contents($log_file);$lines = explode("\n", $content);foreach ($lines as $line) {    // 利用各小块pattern分别匹配    for ($i = 0; $i < count($pattern); $i++) {        preg_match_all("/{$pattern[$i]}/", $line, $match);    }    $match = array_unique(array_filter($match));    dealResult($match);}
复制代码
为了完成任务,硬着头皮进程跑了一夜。当第二天我发现跑了近十个小时的时候内心是崩溃的。。。太慢了,完全达不到利用要求,这时,我已经开始考虑改换方法了。
当产品又改换了关键词策略,替换了一些关键词,要求重新运行一遍,并表示还会继续优化关键词时,我完全否定了现有方案。绝对不能用关键词去匹配信息,这样一条一条用全部关键词去匹配,效率着实是不可忍受。
进化,需求和实现的进化
觉醒 - 拆词

计划

我终于开始意识到要拿信息去关键词里对比。如果我用关键词为键建立一个 hash 表,用信息里的词去 hash 表里查找,如果查到就认为匹配命中,这样不是能达到 O(1) 的效率了么?
可是一条短消息,我如何把它拆分为刚好的词去匹配呢,分词?分词也是需要时间的,而且我的关键词都是些无语义的词,构建词库、利用分词工具又是很大的题目,终极我想到 拆词。
为什么叫拆词呢,我考虑以蛮力将一句话拆分为全部可能的词。如我是好人就可以拆成 我是、是好、好人、我是好、是好人、我是好人等词,我的关键词长度为 2-8,所以可拆词个数会随着句子长度迅速增长。不过,可以用标点符号、空格、语气词(如的、是等)作为分隔将句子拆成小短语再进行拆词,会大大减少拆出的词量。
其实分词并没有完整实现就被后一个方法替换了,只是一个极具实现可能的构想,写这篇文章时用伪代码实现了一下,供各人参考,即使不消在匹配关键词,用在其他地方也是有可能的。
代码

[code]$str_list = getStrList($msg);foreach ($str_list as $str) {    $keywords = getKeywords($str);    foreach ($keywords as $keyword) {        // 直接通过PHP数组的哈希实现来进行快速查找        if (isset($word_list[$keyword])) {            record($keyword);        }    }}/** * 从消息中拆出短句子 */function getStrList($msg) {    $str_list = array();    $seperators = array(',', '。', '的', ...);    $words = preg_split('/(?

相关技术服务需求,请联系管理员和客服QQ:2753533861或QQ:619920289
您需要登录后才可以回帖 登录 | 用户注册

本版积分规则

帖子推荐:
客服咨询

QQ:2753533861

服务时间 9:00-22:00

快速回复 返回顶部 返回列表