问题由来前些天工作中遇到一个问题有 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 报出大量 warningunknown 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正则中的捕获组与非捕获组由于没有真正实现也不知道效率如何。估算每个短句长度约为 10 字左右时每条短消息约50字左右会拆出 200 个词。虽然它会拆出很多无意义的词但我相信效率绝不会低由于其 hash 的高效率甚至我觉得会可能比终极方法效率要高。最终没有使用此方案是因为它对句子要求较高拆词时的分隔符也不好确定最重要的是它不够优雅。。。这个方法我不太想去实现统计标识和语气词等活显得略为笨重而且感觉拆出很多无意义的词感觉效率浪费得厉害。觉醒意识和思路的觉醒终级 - Trie树trie树于是我又来找谷哥帮忙了搜索大量数据匹配有人提出了 使用 trie 树的方式没想到刚学习的 trie 树的就派上了用场。我上上篇文章刚介绍了 trie 树在空间索引 - 四叉树 里字典树这一小节大家可以查看一下。当然也为懒人复制了一遍我当时的解释(看过的可以跳过这一小节了)。字典树又称前缀树或 trie 树是一种有序树用于保存关联数组其中的键通常是字符串。与二叉查找树不同键不是直接保存在节点中而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀也就是这个节点对应的字符串而根节点对应空字符串。我们可以类比字典的特性我们在字典里通过拼音查找晃(huang)这个字的时候我们会发现它的附近都是读音为huang的可能是声调有区别再往前翻我们会看到读音前缀为huan的字再往前是读音前缀为hua的字... 取它们的读音前缀分别为h qu hua huan huang。我们在查找时根据abc...xyz的顺序找到h前缀的部分再根据ha he hu找到hu前缀的部分...最后找到huang我们会发现越往后其读音前缀越长查找也越精确这种类似于字典的树结构就是字典树也是前缀树。设计那么 trie 树怎么实现关键字的匹配呢? 这里以一幅图来讲解 trie 树匹配的过程。