由于没有真正实现，也不知道效率如何。估算每个短句长度约为 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 树匹配的过程。

其中要点：

构造trie树 匹配

然后我们以 这位科学家很了不起！为例来发起匹配。

代码

完整代码我已经放到了GitHub上：Trie-GitHub-zhenbianshu，这里放上核心。

首先是数据结构树结点的设计，当然它也是重中之重：

$node = array( 'depth' => $depth, // 深度，用以判断已命中的字数 'next' => array( $val => $node, // 这里借用php数组的哈希底层实现，加速子结点的查找 ... ), );

然后是树构建时子结点的插入：

// 这里要往节点内插入子节点，所以将它以引用方式传入 private function insert(&$node, $words) { if (empty($words)) { return; } $word = array_shift($words); // 如果子结点已存在，向子结点内继续插入 if (isset($node['next'][$word])) { $this->insert($node['next'][$word], $words); } else { // 子结点不存在时，构造子结点插入结果 $tmp_node = array( 'depth' => $node['depth'] + 1, 'next' => array(), ); $node['next'][$word] = $tmp_node; $this->insert($node['next'][$word], $words); } }

最后是查询时的操作：

// 这里也可以使用一个全局变量来存储已匹配到的字符，以替换$matched private function query($node, $words, &$matched) { $word = array_shift($words); if (isset($node['next'][$word])) { // 如果存在对应子结点，将它放到结果集里 array_push($matched, $word); // 深度到达最短关键词时，即可判断是否到词尾了 if ($node['next'] > 1 && isset($node['next'][$word]['next']['`'])) { return true; } return $this->query($node['next'][$word], $words, $matched); } else { $matched = array(); return false; } }

结果

结果当然是喜人的，如此匹配，处理一千条数据只需要3秒左右。找了 Java 的同事试了下，Java 处理一千条数据只需要1秒。

这里来分析一下为什么这种方法这么快：

正则匹配：要用所有的关键词去信息里匹配匹配次数是 key_len * msg_len，当然正则会进行优化，但基础这样，再优化效率可想而知。

而 trie 树效率最差的时候是 msg_len * 9(最长关键词长度 + 1个特殊字符)次 hash 查找，即最长关键词类似 AAA，信息内容为 AAA...时，而这种情况的概率可想而知。

至此方法的优化到此结束，从每秒钟匹配 10 个，到 300 个，30 倍的性能提升还是巨大的。

终级，却不一定是终极

他径 - 多进程 设计

匹配方法的优化结束了，开头说的优化到十分钟以内的目标还没有实现，这时候就要考虑一些其他方法了。

我们一提到高效，必然想到的是 并发，那么接下来的优化就要从并发说起。PHP 是单线程的（虽然也有不好用的多线程扩展），这没啥好的解决办法，并发方向只好从多进程进行了。

那么一个日志文件，用多个进程怎么读呢？这里当然也提供几个方案：

进程内添加日志行数计数器，各个进程支持传入参数 n，进程只处理第 行数 % n = n 的日志，这种 hack 的反向分布式我已经用得很熟练了，哈哈。

这种方法需要进程传参数，还需要每个进程都分配读取整个日志的的内存，而且也不够优雅。

使用 linux 的 split -l n file.log output_pre 命令，将文件分割为每份为 n 行的文件，然后用多个进程去读取多个文件。

此方法的缺点就是不灵活，想换一下进程数时需要重新切分文件。

使用 Redis 的 list 队列临时存储日志，开启多个进程消费队列。

此方法需要另外向 Redis 内写入数据，多了一个步骤，但它扩展灵活，而且代码简单优雅。

最终使用了第三种方式来进行。

结果

这种方式虽然也会有瓶颈，最后应该会落在 Redis 的网络 IO 上。我也没有闲心开 n 个进程去挑战公司 Redis 的性能，运行 10 个进程三四分钟就完成了统计。即使再加上 Redis 写入的耗时，10分钟以内也妥妥的。

一开始产品对匹配速度已经有了小时级的定位了，当我 10 分钟就拿出了新的日志匹配结果，看到产品惊讶的表情，心里也是略爽的，哈哈~

他径，也能帮你走得更远

总结