utf8中文字符串的多模式匹配算法的优化

效果

本节仅展示优化效果，对一些业务逻辑和背景未做解释，读者可直接跳至下一节。

上个月接触到了我组的一个关于在海量文本中匹配字符串业务。读源代码时发现一些问题，并针对这些问题做了优化工作，效果非常明显。

测试的硬件环境是只用一颗主频2.4G的Intel至强处理器核心。OS是tlinux2(腾讯自研的Linux发行版)。该业务目前载入11万3千条规则。优化前后的效果如下：

• 表中的“旧算法简版”指去掉了一个繁琐的预计算步骤

• 用11万3千条规则作为待检测文本使得新旧算法都会密集地走到“命中逻辑”，旨在比较“命中逻辑”的性能。
• 用四大名著作为待检测文本，使得新旧算法几乎不会走到“命中逻辑”，旨在比较算法处理正常文本时的性能。而每次处理文本的长度亦可能影响到性能表现。如表所示，处理短文本（10个汉字）时，新算法的优势有所降低，可解释为旧算法为启动每一次处理消耗较大的资源，而如果处理的文本较长时，这个资源消耗分摊到每个待处理字符就相对不那么明显了。

在一台24核的M2机器上(腾讯的机型分类)，理论估计新算法一天可以处理36,495,360M文本，36个T~

业务简述

该业务的核心问题简单地近似概括为：

有几十万甚至更多的模式(短字符串)集合P={P1, P2, ..., Pn}，输入一个utf8编码的字符串string，输出有哪些模式Px在string中出现。

实际问题比上面的描述稍微复杂一点点。业务需要通过找到的模式判断是否命中预定的规则。一个模式或多个模式都可以组成‘规则’。比如，单独的一个Px组成一条规则，多个不同的模式则会组合成一个 与 关系的规则（目前业务只支持与关系，支持更复杂的匹配规则是将来需要增强的地方）。比如，有下面几条规则：

1. 铁王座
2. 雪诺 & 提利昂
3. 雪诺 & 艾莉亚 & 2
4. 雪诺 & 龙母 & 床
5. 雪诺 & 夜王 & 异鬼军团 & 守夜人

下文的讨论将继续引用这个规则列表。

当输入的string中包括“铁王座”时，则命中规则1；当包括“雪诺”同时也有“提利昂”时，则命中规则2；如果需要命中规则3，string则必须同时包括三个短字符串“雪诺”，“艾莉亚”和一个单ascii字符“2"。

原算法的主要不足

原算法写于2010年左右，大致有以下几个问题。

1. 第一问题很容易注意到。原算法用共享内存存储字符串时相当“阔绰”。比如，存储“铁王座”，“雪诺”，“2”，统统需要256字节，而实际上它们的长度分别是9字节，6节字，1字节。
2. 原算法扫描一遍输入字符串string后，如果命中了至少一个模式，将进入一个非常“朴素”的穷举阶段：把所有的规则遍历一遍，对于每条规则中的每个模式，检查是否命中。设规则条数为n，规则的平均长度是m，这是一个O(n*m)的时间复杂度。当规则数有几十万之多是，这个阶段非常耗时。
3. 再说匹配多模式阶段的算法。原算法可以概括为“Trie Tree”和“Boyer-Moore 模式匹配算法”。Trie Tree是非常常见的组织字符串的数据结构。而Boyer-Moore算法在1977年由Robert S Boyer和Strother Moore发表1。简单地讲，Boyer-Moore算法预先计算两张“跳字符”的表，籍此提高匹配速度，它本身解决的问题是单模式的匹配，但面对多模式的问题时需要做一些简单的调整，而且，随着模式数的增长，当模式数目大大超过待检查字符串的长度时，所有的“跳字符”算法，包括Boyer-Moore算法将表现不佳2。事实上，原算法费尽心力（十分钟量级）预计算的跳字符表中的跳字符步长是1个byte。1个byte的步长让跳字符表，除了故弄玄虚的作用外，已变得毫无意义。为何计算得到1个byte的步长？因为这近20万个模式中有单个的ascii字符，单个ascii字符的长度只有一个byte。如果跳字符步长超过1byte，就有可能错过单个ascii字符模式。

新算法的改进

解决问题1

问题1是耗内存太多。这个很容易解决，不作重点阐述。新算法广泛使用C 的标准数据结构，而不是手工在共享内存上实现朴素，笨拙，易越界的数据结构。旧方式容易产生的微妙bug，用新的开发思路，很多bug在编译期就能被检查到。效果则是不仅从消耗4G内存降到200M，而且在实现各小需求时获得明显的开发效率和代码质量的提升。

解决问题2

问题2是在命中模式后确定命中哪些规则的效率问题。旧算法不管三七二十一把所有规则全遍历一遍。新算法大的思路是使用信息检索广泛使用的“倒排索引”。并辅以更多的优化。新算法将建立的数据结构简述如下：

• 建立“模式-->规则”的倒排索引。并预先计算一个表征“当前模式命中后，它对应的规则有多大可能性被命中”的值，更专业地讲，引入了信息论中的“熵”。“熵”将决定当命中很多个模式时，先查找哪个模式对应的规则有更高的效率。下文会继续讨论“熵”的作用。
• 对每个模式对应的规则进行分级，只有一个模式的规则入全局哈希表，只有两个模式的规则也入全局哈希表，有三个和三个以上模式的规则放在一起作为对应该模式的多模式规则集合。这么做的理由是，只有一个模式和只有两个模式的规则最容易用哈希表快速处理，而确定是否命中多模式规则需要大得多的开销。

以上文的五条规则为例详细阐述新算法的思路：

1. 为每个模式编号： 1:铁王座 2:雪诺 3:提利昂 4:艾莉亚 5:2 6:龙母 7:床 8:夜王 9:异鬼军团 10:守夜人
2. 建立索引(从规则映射到模式)：
   • Rule1 -> set(Pattern1)
   • Rule2 -> set(Pattern2, Pattern3)
   • Rule3 -> set(Pattern2, Pattern4, Pattern5)
   • Rule4 -> set(Pattern2, Pattern6, Pattern7)
   • Rule5 -> set(Pattern2, Pattern8, Pattern9, Pattern10)
3. 建倒排索引(从模式映射到规则)
   • Pattern1 -> 只有单模式，入单模式全局哈希表 Pattern1 -> Rule1
   • Pattern2 -> 入双模式全局哈希表 (Pattern2, Pattern3) -> Rule2; 自有多模式集合set(Rule3, Rule4, Rule5; 熵 := 3)下文讨论如何计算熵
   • Pattern3 -> 入双模式全局哈希表 (Pattern2, Pattern3) -> Rule2; 没有自有多模式集合。
   • ...略...
   • Pattern6 -> 自有多模式集合set(Rule4; 熵Entropy := 1下文解释 )
   • Pattern10 -> 自有多模式集合set(Rule5; Entropy := 1 )

下面再详细地讨论为什么引入熵，及如何计算熵：

假如已知命中了模式“龙母”，那么将有2种可能。要么命中Rule3，要么不命中任何规则。如果已知命中了模式“雪诺”，那么将有5种可能。命中Rule2，命中Rule3，命中Rule4, 命中Rule5，和不命中任何规则。那么，如果已经发现同时有命中多个模式，其中包括“龙母”，和“雪诺”。通过查找倒排索引，能拿到潜在可能命中的所有规则。但问题是，究竟先找“龙母”的倒排，还是先找“雪诺”的倒排呢？在这个简单的例子中，我们容易凭自觉知道，得先查“龙母”的倒排效率更高，而查“雪诺”的倒排可能会尝试不可能命中的规则。在实际业务中，有部分模式对应的规则有几千个之多，但只可能命中其中一两个，这个效率是不高的。但这个问题可以用信息论解决：发生事件“已找到模式龙母”较之发生事件“已找到模式雪诺”，事件“命中规则”在前者的条件下的确定性更高，即“熵”更小。从“熵”小的开始处理。但如何计算“熵”呢？更一般地，记找到模式Px这个事件为y，记输入string命中规则这个事件为z，记命中模式Px对应的规则这个事件为x。则计算发生命中模式Px的情况下将命中规则的条件熵的公式为：undefined H(X|Y,Z) = -∑P(x,y,z)|logP(x|y,z) x∈{y对应的规则集合｝ 事实上，这是个简化的模型。更严谨地，如果已知命中多个模式y1,y2,y3...yn时，则条件概率应该是P(x|y1,y2,...yn,z)。不继续展开，回到上面的公式。如果有足够多的输入文本就可以求出H(X|Y)，或者在运行时积累数据，慢慢迭代也可逼近准确的熵值。但如果不在乎损失效率，还能再继续简化。用模式Px对应的多模式规则集合的大小来替代H(X|Y)，用它作为非常不严谨的“熵”值。集合中的规则个数越少，则优先选用这个集合中的规则作检查。仅管求得严谨地熵将获得更高的效率，但用这个极简化的版本也能取得不错的效果。不过，上述算法只适用于“一但匹配到一个规则就迅速跳出”的情况，如果要找出所有匹配规则就没必要这么做了。但下文的实例推演中还将介绍另一个优化的方法。

举实例简述匹配方法：

1. 输入字符串 “xxxx铁王座xxxxx”undefined匹配到模式“铁王座”时，检查“单模式规则查询表”，发现该模式在表中，迅速命中Rule1。如果业务只需要发现一个匹配规则，此时就可以快速结束其它逻辑。
2. 输入字符串 “xxx提利昂xxxx雪诺xxxx”undefined匹配到“提利昂”时，检查“单模式规则查询表”，没有匹配。 匹配到“雪诺”时，检查“单模式规则查询表”，没有匹配。 把“雪诺”和“提利昂”合在一起生成一个唯一key，查“双模式规则建查询哈希表”，命中。
3. 输入字符串 “xxxx雪诺xxxx夜王xxxx龙母xxxx异鬼军团xxxxx守夜人”undefined会连续匹配到5个模式，每匹配到一个模式，按照前述1，2的方法检查单模式哈希表和双模式哈希表。一般地，命中第n次模式时，将会带来一次单模式哈希表的检查和 n-1 次双模式哈希表的检查。直到字符串扫描结束。进入处理多模式字符串的阶段。在这个阶段，已经拿到了字符串中出现的5个模式，通过查找“倒排索引表”，可以找到所有可能的多模式规则。按照预先计算好的“熵”的大小排序，取熵最小（即确定性最高）的模式对应的多模式规则开始尝试。此例中，模式“龙母”，“守夜人”，“异鬼军团”，“夜王”的熵都是1，而“雪诺”的熵是4，表示查“雪诺”对的规则将有最大的不确定性。于是，从熵小的模式开始，查“龙母”的倒排找到Rule3，发现不匹配；再查“守夜人”的倒排找到Rule5，此时发现Rule5命中。这里，就体现出来了简化“熵”的缺点，在实际应用中，如果算得严谨的熵值，会较大概率地先选择“守夜人”模式对应的多模式规则，一击即中！
4. 输入字符串 “xxxx雪诺xxxx夜王xxxx龙母xxxx异鬼军团xxxxx” 此例与例3类似，但结果将是不匹配任何规则。前部分步骤与例3一样，当所有“熵”是1的模式对应的多模式规则被检查发现不匹配后，再找到“雪诺”对应的所有多模式规则：Rule3,Rule4,Rule5。此时，需要检查这三个规则吗？不需要！因为不可能匹配到。这个断言可以一般性的概括为：

已找到 n 个彼此不相同的模式，并且已经查找过 m 个模式对应的规则皆不匹配，还剩余 n -m 个模式对应的多模式规则需要被检查。这时取第 m 1个模式对应的所有多模式规则。对于其中每个规则，取得它的size，即这条规则由多少个模式组成。如果 size > (n - m)，那么，可以立即肯定这个Rule无法匹配。不用浪费时间。想想为什么？我感觉很难描述，提示是个反证法！ 上述规律适用于“查找过m个模式对应的规则皆不匹配”的情况，如果处理前m个模式的对应规则时有q个模式的对应规则存在命中，则判断式改为 size > (n - m q)

改进问题3

问题3是匹配算法的效率问题，是否还有可改进的空间呢？

新算法大概从四个方面提升匹配算法的效率：

1. 前文有提到在20万之多大量模式的前提下，旧算法计算的“跳字符”步长实际是1。而我们的业务处理的字符多是utf8编码的中文，一个中文字有3个bytes，当处理中文时，显然步长可以放心地提到3bytes。一般地，utf8编码的首字节记载了当前“字”的长度3，这个长度即可以作为“跳字符”的步长。在中文字占绝对多数的情况下，平均步长应该非常接近3，而旧算法只有1。粗略地，乐观地估计，这个改进将使得新的算法将获得接近3倍的性能提升。
2. 业务处理的文本多是utf8编码的中文文本，而旧算法用的是通用的编码无关的算法，未对utf8中文作优化。很容易想到，如果以一个utf8字符为单位建Trie Tree比以Byte为单位建Trie Tree将获得更紧凑的内存布局，和更高效的cpu利用。既能提高速度又能节省内存。
3. 至此，新算法将在Trie Tree的结点存一个utf8字符，大多数情况下是一个3bytes的中文字。但现代服务器的cpu是64位的，一个中文字也才占了3字节，还有5个字节没有利用上啊！这时，有点NLP经验的开发者应该马上想到Bigram了。使用Bigram“二元模型”能继续提高性能。扫描utf8字符串时，每次取一个Bigram，虽然跳节符跳字符步长仍然是一个utf8字符，但因为每次取出两个utf8字组成Bigram增加了上下文信息，匹配效率将大大增加，大量地减少了因为单个utf8字匹配到模式第一个utf8字而造成的无谓地“爬树”时间。为利用好Bigram，新算法的Trie Tree的第1层（树根记为第0层）将存一个Bigram，而其他层仍然存单个utf8字。新旧算法的Trie Tree将分别如下文的Figure 1，Figure 2所示。但引入上述Bigram的逻辑将引入一个新问题，即无法用新的Trie Tree命中单个utf8字的模式。比如Rule2中的ascii字符，数字“2”和Rule4中的中文字“床”。好在这样的单个字模式在规则中量很少，可以把找单个字模式的逻辑推迟到命中了需要单个字模式的规则时。举例说明即当发现命中了Rule4中的模式“龙母”，潜在可能命中Rule4，此时再扫描一遍原文本看有没有“床”这个模式。因为这个特殊情况在所有规则中所占比重非常低，所以执行到这个逻辑也会很少，因此这个额外的推迟逻辑不会拖累新算法的整体效率。在绝大多数情况下，引入Bigram将提高效率，可忽略引入的额外逻辑造成的负担。还有极端的只有一个utf8字的模式单独组成一个规则，这种极端情况目前没有出现，未来出现的可能性也很低，暂时不予考虑。即使出现了也能在不可避免地，至少一次遍历字符串时轻易解决。
4. 第四点倒不是算法层面的改进，而是把旧算法中不必要的堆分配以及各种不必要的其他开销全部删掉，留下干干净净纯干活的代码。

综合上述改进，如下示意图是新旧匹配算法的Trie Tree。

新算法的Trie Tree

Figure 1 新算法的Trie Tree

旧算法TrieTree

Figure 2 旧算法的Trie Tree

对照新旧算法的Trie Tree，看图，更容易理解为何新算法又快又省内存。

新算法的Trie Tree第一层使用Bigram，一些不会命中的普通文本几乎在树的第一层就被发现了，而旧算法每个结点只存了一个Byte的数据，但utf8中文字的第一个Byte有四个bit位是固定的，在有近二十万个模式的情况下，旧算法几乎对每个中文字都会“爬树”到至少第二层。

再举个例子，输入字符串“雪花啤酒”，因为有模式“雪诺”，当处理第一个汉字“雪”时。新算法会取Bigram"雪花"，在树的第一层即发现不可能匹配，但旧算法爬到树的第三层时会命中“雪”，至少要爬到树的第四层才能得出不匹配的结论。

未来改进

新的形势对该业务提出更高的要求，未来需要处理更复杂的匹配规则，比如酌情实现“正则式”的子集。

参考资料

1: Robert S. Boyer, Standford Research Institute & J Strother Moore, Xerox Palo Alto Research Center. A fast String Searching Algorithm. Communications of the ACM. 1977.

2: Ricardo Baeza-Yates & Berthier Ribeiro-Neto. Modern Information Retrieval, 2nd. P385, 3rd paragraph. 2011.

3: utf8维基百科词条 https://en.wikipedia.org/wiki/UTF-8