正则表达式搜索

by AprocySanae

好久不见。

众所周知，或者说单纯以我的经验而言，在sql的查询条件中，使用正则通常是不被鼓励的。究其原因，查询条件中使用正则，会导致查询不会走索引，结果就是sql异常缓慢。

在线上环境中，慢查询的出现，会导致雪崩级的事故。

通常的解决思路是增加额外的冗余字段，通过对该字段建索引的方式来加速。不过，带来的问题是不得不维护极有可能是一堆的冗余字段。

postgresql中的GIN提供了一种实现，可以建一个特殊的索引，从而加速正则表达式的搜索速度，本着对该技术实现原理的好奇，诞生这这篇文章。

本文虽然标注为正则表达式搜索，不过大抵是某些泛泛而谈，如果能为您提供一些干货，那就再好不过了。

GIN的全称是Generalized Inverted Index，事实上，pg另外还提供了Gist，全称是Generalized Search Tree。不过，我只使用到了GIN，也只看过与之相关的资料，所以聊聊前者就好。

GIN其本质就是倒插索引，当然，这样随意抛出来这个结论是很无聊的，况且，这样也并不能解释为什么使用了倒插索引就能够加速正则表达式的搜索，所以我们慢慢来。

考虑到希望让本文尽可能地浅显易懂，所以最开始，先说说倒插索引。

首先给出来一个结论: 倒插索引的用处主要是为了缩小范围，而不是用来精确匹配的。

考虑如下字符串：

(1) sometimes, he goes to forest.
(2) I like books too.
(3) too young
(4) too simple
(5) sometimes naive

当然，真正使用的时候，这些字符串都是文本，很长很长，出于习惯，我们称这里的每一个字符串，都是一篇文档。一篇文档可能是一句话，可能是一段话，也可能干脆是本天龙八部，看个人的喜好和定义就好。

于是很容易的，其倒插索引如下：

sometimes: 1,5
he: 1
goes: 1
to: 2,3,4
forest: 1
....

我们对每个词，都让它索引上其出现文档的ID，这样，在某些情况下已经能提高不少速度了。比如，如果是这样的正则：where text ~ 'sometimes.+，我们就知道，去文档1，5中各走一次匹配就好，这样比单纯逐个匹配，来得快上不少。

但是，正则式在写的时候，泰半不见得这么规矩地用单词作为边界去查，更多的情况是^aa{m,n}这样的一坨。于是引入第二个概念: Q-grams。

照搬一些定义：

(1) Q-gram是一个长度为q的子字符串

(2) 它可以作为源字符串的签名

通常我们使用3-grams，于是以此为例，还是用上面的例句，现在有（以下用_代替空格）：

_he: 1
_go: 1
_to: 1,2
_fo: 1
_bo: 2
I_l: 2
som: 1,5
ome: 1,5
ive: 5
....

能大致看懂意思就好。

这时候，如果需要匹配some.*ive，那么，实际上就是去找som AND ome AND ive这个的交集。当然了，就是文档5。

不过如果要匹配的是some.*ve这样的呢？

我考虑了一下，大概有这么几种可能的方法:

  1. 直接舍弃不满3个字符的

  2. 对所有的Q维护一个后缀树，讨论枚举ve结尾的Q

仁者见仁吧，如果是英文文档的话，额外建立一颗后缀树的成本其实很低。如果i18n，其实后缀树也还好，不过为了方便直接舍弃也没太大问题就是了。

这里有两种优化手段:

第一个手段是用范围代替id。

比如，假如som反复出现，出现了很多很多。具体来说，出现在了这些文档: [1,2,3,4,6,7,8,9,11,13,17,18]。 那么，一个优化手段是，把上面这个整数列表，改写为[(1,4),(6,9),(11,11), (13,13), (17,18)]，也就是，储存范围而不是值。这个优化，对大多数情况其实都是有效的，引述的最后一篇论文专门研究了这个问题，得出的结论数据虽然说不上惊人，也很是可喜。

如果是这种方法的话，AND操作等效于对两个列表做交集，OR相当于并集。算法很简单。说起来，之前在v2ex上看到有对类似问题的提问，不过他的那个模型是时间片。不过我很好奇那个问题为什么讨论到最后都是各种库的调用，分明是个很简单的可以自己造轮子解决的问题。

上面的这个优化结果虽然能起到一定的作用，不过下面这个更加有用一些:

Q-grams会产生很多无用的unit。譬如说，the这个单词，我们认为，是不能起到过滤掉某些文档的作用的。但是，如果这个unit(或者叫grams)是zxx的话，就是很有区分度的。大概，如果你有一个大的数据库，储存了大量爬取下来的博客，然后可能仅仅只有几篇（例如本文），出现过zxx这个unit。考虑如果能有一种方法，能区分出一个unit是useful的，还是useless的，然后以useful的unit建立Q-grams的话，一方面不仅能节省大量的空间，另一方面也能提高查找的速度。算得上是很有优势的优化思路。

一个简单的方法是，设定一个阈值，求解每一个unit的概率，如果高于这个阈值，就是useless的，反之useful。

不过，Fast Regular Expression Indexing Engine这篇paper研究了这个问题，他多了一个叫做Prefix free的概念。也就是，最后得到的这个grams中，没有任意一个unit是另一个的前缀。后面可以看到，这个优化被google的代码搜索借鉴并发展了。

上面泛泛而谈了两种可能的优化，接下来继续讨论正则的搜索。

注意，我说的是搜索不是匹配。归根结底，倒插索引只是用来缩小范围而已，可能很容易的知道，这个正则表达式在哪个文档中出现，并不能知道，正则式中匹配的内容。

如果还希望知道匹配出来的结果的话，那么还是只能在搜出来的文档中，整个再进行正则的匹配。

怎么使用我们的grams呢？

举个栗子：

/[ab]cde/ -> (acd OR bcd) AND cde

理论上说，所有的正则式都可以通过这样的方法来确定。如果尤其要求速度的话，大概不算特别快。

Fast Regular Expression Indexing Engine，提出了一种优化的方式。

这篇论文给出了一个叫做重写regular expression的方法，这里只能大概说说，更详细的我觉得最好去读读这篇paper，算是很出名的，大概。

可惜我这里不太好上图……

假设现在，我们有一个这样的正则式：(Bill|William).*Clinton。

这个等效于(Bill|William)(a|b|c)*Clinton，.这里简写为(a|b|c)了，因为不影响。

为了方便在没有图的情况下看，我用S式来表达parser tree。

上面那个正则式的解析树是:

(AND (AND (OR Bill William) (* (OR (OR a b) c))) Clinton)

把这个正则式拆成parser tree，容易注意到，*后面跟了一颗子树。事实上，既然是*，也就是说，*后面的内容，可能出现，也可能不出现。于是这部分很明显，我们用不上grams了，因为它有可能不出现。所以，这部分对搜索grams没有贡献，我们用NULL来代替。

(AND (AND (OR Bill William) NULL) Clinton)

NULL表示，我们利用不上grams，不能减小我们的搜索集。

于是引入了这个NULL的前提下，再来讨论接下来的问题。

首先讨论OR操作。如果现在有一颗子树不为NULL，另一颗为NULL，那么也就是说，这个OR符号下面的条件，有可能能减小结果集有可能不能减小结果集，所以，我们认为它不能减小结果集，改写为NULL。同样，如果是AND操作，那么，一定能查出不为NULL部分的结果集，所以，改写为不为NULL的子树。

这部分很绕，推荐看看paper画画图。

总而言之，上面的那个正则，经过重写后，会被改写为:

(AND (OR Bill William) Clinton)

于是仔细看了看，咦，你这个也就被化简成为了(Bill|William)Clinton而已嘛，有什么大不了的？

于是我们继续。

记得么，Q-grams的单位是unit或者说gram，并不是单词。

恩，假设，现在是4-grams，然后Bill这个单词在useless里面，Bill被改写成为NULL， William被拆成Will,liam都在useful里面,Clinton被拆成Clin和nton，也都在useful里面。当然这只是假设。于是现在的parser tree：

(AND (OR NULL (AND Will liam) (AND Clin nton)))

最终被改写为:

(AND Clin nton)

最后这个，就是其最有区分度的grams。

优化了不少是吧。

当然啦，这个只是一种重写正则的手法，注重的是区分度，然而一个很明显的弊端就是，丧失了信息。譬如，William和Bill莫名其妙不在了……

做工程的这帮家伙比较粗暴（因为有很多机器），然后也不希望丢失东西，反而希望能精确缩小范围（因为有很多机器）。

Russ Cox设计了google的code search，这篇文章解释了当时他们做的方法。

恩，其实这篇文章的话，到trigrams之前都和上文提到的思路是一致的，不过在讨论如何得出trigrams的时候，使用了不一样的方法。

其重写regular expression的核心是5个集合（当然也不尽然，譬如emptyable这个怎么想都只是一个boolean）。

分别是：emptyable, exact, prefix, suffix, match。

emptyable指明该正则式是否可能为空，比如a*就可能为空，a+就不可能。

exact是是否能改写集合表示的精确形式。比如 exact(e1|e2)当然能够精确地改写成为exact(e1) U exact(e2)，但是exact(a*)就不可能被改写，这种情况，改写为ANY。

prefix是前缀，prefix(a+)前缀就是a了，不过如果是prefix(a*)，前缀只能是''，因为空集是可能的。

suffix和前缀类似，match则更类似于前面提到的OR，AND连接的形式。match(e1|e2) -> match(e1) OR match(e2)，不过match(c)->ANY以及match(a*)->ANY，这个请注意一下。因为match单字符当然没有任何区分度，对缩小文档数没有贡献，同样，a*也没有贡献，因为可能是空集。

链接的文章里面详述了各种正则经过五种规则计算出来的结果，推荐看一下，不过实际上，真正用到的并不是那么多……主要还是利用前缀，后缀以及本身的关系。

这里的ANY您可以等效看作前面提到的NULL，就结果而言，都是表示对缩小文档树没有贡献的意义。

真正计算的话，根据上面那篇文章，规则是这样(假设用于计算的函数名字叫trigrams):

  1. 如果trigrams(e1)中，e1字符数小于3，改写为ANY

  2. result = trigrams(prefix) AND trigrams(suffix) AND trigrams(exact)

这是save规则，另外还有discard规则，给出了4条，但是我只能想清楚2条……

  1. 如果prefix(e)同时包含s和t，并且s是t的前缀，舍弃掉t。

其实这个很容易理解啦，比如/abcabc+/，直接使用abc就可以了，不需要拆成abc AND bcd AND cab

  1. 如果suffix(e)同时包含s和t，并且s是t的后缀，舍弃掉t。

一样的。

热个身吧，看看示例。

示例一:

/abc+de/

prefix: abc
suffix: cde
exact: NULL

-> abc AND cde

示例二:

/(abc*)+de/

prefix: ANY
suffix: de
exact: NULL

-> nothing

这个需要说一下，由于prefix可能是abc，也可能是''，这种情况，按照前面所述，prefix为ANY。suffix倒是有了，但是小于三个字符，所以也是ANY，exact根本计算不出来，所以置NULL。也就是说，这个正则式在使用这种方法的情况下，没有选择度。

示例三:

/ab(cd)*ef/

prefix: ab
suffix: ef
exact: NULL

-> nothing

其他的请大家自己画画就好。

上面介绍了两种方法，一种重写正则式的方式，能够筛选出来最有选择性的最简Q-grams，另一种具有一定的冗余，能保证大多数情况下，筛出一个较小的文档范围。

pg中gin的实现并非是上文中提到的两种，虽然很明显接受了其中的某些影响。

pg的实现方式不太好使用文字描述，推荐的是看作者写的slide，wiki。

不过思路看着很简单。

第一步，展开原始的DFA，正则表达式的DFA，每个结点是一个状态，当然只有一个字符。但是，引入了Q-grams之后，一个字符意义不大。所以，展开这个DFA，把它变成一个有向图，每一个结点都代表一个grams。

第二步，简化这个图，把没有筛选意义的路径截掉

第三步，按照图展示出来的结果，简化为能用AND以及OR表达的grams。

于是说了和没说一样……

我看了看这个的原理，其实就感觉上，这个实现思路也很scholar，漂亮。而且似乎作者也和上文提及的方式做了对比，就生成的grams来看，和google方法的结果较为类似，并且也规避了示例二或者示例三中，由于源正则表达式的某些限制，导致无法筛选的问题。不过相应的，看起来这个方法，在转化原始regular expression为有向图的过程中，复杂度会略微高一些，不过选择度应该最好的。考虑到正则式通常不长，所以pg的实现应该是目前较好的方案。不过当然，场景是很重要的。

以上是本次的全部内容，比较长，辛苦看到这里的读者，谢谢。

引用资料:

[1] Alexander Korotkov, Index support for regular expression search, https://wiki.postgresql.org/images/6/6c/Index_support_for_regular_expression_search.pdf

[2] Russ Cox, Regular Expression Matching with a Trigram Index or How Google Code Search Worked, https://swtch.com/~rsc/regexp/regexp4.html

[3] Junghoo Cho and Sridhar Rajagopalan, A Fast Regular Expression Indexing Engine, http://oak.cs.ucla.edu/~cho/papers/cho-regex.pdf

[4] Wu hao, Li guoliang and Zhou lizhu, Ginix: Generalized inverted index for keyword search, http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=6449411

rex 笔记 DFA Q-grams invert