问题由来
前些天工作中遇到一个问题：
有 60万 条短消息记录日志，每条约 50 字，5万 关键词，长度 2-8 字，绝大部分为中文。要求将这 60万 条记录中包含的关键词全部提取出来并统计各关键词的命中次数。
本文完整介绍了我的实现方式，看我如何将需要运行十小时的任务优化到十分钟以内。虽然实现语言是 PHP，但本文介绍的更多的思想，应该能给大家一些帮助。
原始 - grep 设计一开始接到任务的时候，我的小心思立刻转了起来，日志 + 关键词 + 统计，我没有想到自己写代码实现，而是首先想到了 linux 下常用的日志统计命令 grep。
grep命令的用法不再多提，使用 grep 'keyword' | wc -l 可以很方便地进行统计关键词命中的信息条数，而php的 exec() 函数允许我们直接调用 linux 的 shell 命令，虽然这样执行危险命令时会有安全隐患。
代码上伪代码：
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()函数过滤一遍关键词即可。
上伪代码：
$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，所以可拆词个数会随着句子长度迅速增加。不过，可以用标点符号、空格、语气词（如的、是等）作为分隔将句子拆成小短语再进行拆词，会大大减少拆出的词量。
其实分词并没有完整实现就被后一个方法替代了，只是一个极具实现可能的构想，写这篇文章时用伪代码实现了一下，供大家参考，即使不用在匹配关键词，用在其他地方也是有可能的。
代码$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('/(?<!^)(?!$)/u', $msg); $str = array(); foreach ($words as $word) { if (in_array($word, $seperators)) { $str_list[] = $str; $str = array(); } else { $str[] = $word; } } return array_filter($str_list); } /** * 从短句中取出各个词 */ function getKeywords($str) { if (count($str) < 2) { return array(); } $keywords = array(); for ($i = 0; $i < count($str); $i++) { for ($j = 2; $j < 9; $j++) { $keywords[] = array_slice($str, $i, $j); // todo 限制一下不要超过数组最大长度 } } return $keywords; }
结果我们知道一个 utf-8 的中文字符要占用三个字节，为了拆分出包含中英文的每一个字符，使用简单的 split() 函数是做不到的。
这里使用了 preg_split('/(?<!^)(?!$)/u', $msg) 是通过正则匹配到两个字符之间的''来将两个字符拆散，而两个括号里的 (?<!^)(?!$) 是分别用来限定捕获组不是第一个，也不是最后一个（不使用这两个捕获组限定符也是可以的，直接使用//作为模式会导致拆分结果在前后各多出一个空字符串项）。 捕获组的概念和用法可见我之前的博客 PHP正则中的捕获组与非捕获组
相关文章
精彩导读
热门资讯
关注我们
