面向大数据库正则表达式查询的有效算法

张晓煜，林 晓，王志杰

(1.郑州航空工业管理学院 计算机科学与应用系，河南 郑州 450015；2.上海交通大学 计算机科学与工程系，上海 200240)



面向大数据库正则表达式查询的有效算法

张晓煜1，林 晓2，王志杰2

(1.郑州航空工业管理学院 计算机科学与应用系，河南 郑州 450015；2.上海交通大学 计算机科学与工程系，上海 200240)

针对大数据库中正则表达式查询，提出了一种基于索引的有效算法。首先，构造索引。该索引结构在前缀树基础上加以改进，为每个节点创建二维数组存放该节点所辖子树各层的首次关键节点，并对每个节点附加关键节点指针以指向同层的下一关键节点。然后，通过所提出的索引结构进行查询。最后，分析了所提出算法的时间和空间复杂度，并进行了实验。实验结果证明：随着数据集的增加，其查询时间和输入/输出(I/O)时间增长速度较缓慢，说明其可扩展性较好，适合于大数据库中正则表达式查询。并且，随着查询字串的增加，查询时间与I/O时间均呈递减趋势，证明了该算法的效率和有效性。

正则表达式；查询处理；大数据库；索引

0 引言

模式匹配在计算机科学领域有着广泛应用，如文本编辑、符号操纵、数据检索、网络入侵检测等[1-2]。‘正则表达式’在模式匹配中有着举足轻重的作用，用来描述一系列符合某个句法规则的字符串。过去数十年，正则表达式相关研究吸引了许多学者关注[3-5]。正则表达式匹配的一种经典方法是创建一个确定性的有限自动机(DFA)，通过它来验证输入信息是否匹配目标信息[3]。由于DFA中状态数目可能呈指数级，该方法可扩展性较差。另一种是基于Patricia树的方法[6]，该方法通过创建有效的索引结构来克服传统方法的缺陷，适合于整个索引条目能够载入到主存储器的情形，不太适用于处理大数据。

面向大数据库的正则表达式相关课题在国内外受到广泛关注。文献[7]讨论了如何高效地索引正则表达式。文献[8]讨论了参数化模式查询。文献[9]讨论了时间序列数据库中的子串匹配。文献[10]讲解了面向数据流的正则表达式查询等。这些工作与本文关注的问题有相似之处，但在语义上与本文不同。本文提出一种有效的索引结构MP-tree，基于该索引结构进一步提出了查询处理算法，并对算法的复杂度进行了详细分析。随后，通过大量实验证实了提出方法的效率和有效性。

1 符号及问题定义

定义1(正则表达式查询) 给定数据库D和查询字串Q，正则表达式查询是指找出记录的字段S与查询字串Q的正则表达式匹配的所有记录。即对任意记录r∈D，如果r.S为匹配字串Q的正则表达式，则r将作为结果返回；否则，r不是查询结果。

2 基于索引的方法

为了有效支持面向大数据库的正则表达式查询，提出一种基于索引的方法。其主要思想是通过构造索引来有效管理记录。为了适应所解决问题，提出的索引结构在传统前缀树基础上进行适当修改(注：传统的前缀树不能用于正则表达式查询，因为正则表达式查询不是传统意义上简单的字符串匹配)。为了区分起见，将其称之为修改的前缀树(MP-tree)。本节将详细介绍这种索引结构，并介绍具体算法来描述如何采用该索引完成所讨论的查询。

2.1 修改的前缀树

为便于讨论，本节采用一个具体例子来解释改进前缀树的原理及细节。如某数据库存放了一系列记录(见表1)，每条记录由两个字段构成：标示字段ID及一个字符串属性字段S。改进索引结构的概貌如图1所示。

图1 改进的前缀树(MP-tree)

MP-tree中每条从根节点到叶子节点的路径对应于数据库中记录S字段的值(即一个字符串)。节点所处层数对应于树的深度，其中，根节点为第0层，其他节点层数依次类推。为每节点赋予一个位置信息，该信息有助于访问和存储节点。其位置信息由两个元素构成：节点所处的层数和节点在该层数所插入的次序。例如在第2层，节点被插入的次序为：第1条记录的‘y’，第2条记录的‘z’，第3条记录的‘x’，依次类推。为简短起见，令Node(x，y)表示节点的位置信息，其中，x表示层数，y表示节点在该层数的位置顺序。例如，Node(3,6)表示节点位于第3层，次序为6。

为快速知晓节点本身及所辖子节点对应记录的ID，为每个非叶子节点创建一个链表，用于保存其本身及孩子节点的ID信息，用Ilist表示。例如对于Node(1,1)，其Ilist将保存4个ID信息，分别为：null，3,8,1，其中，null表示从根节点到该节点所组成的字符串本身在数据库中不存在。假如正则表达式在Node(1,1)已经满足匹配，那么就可简单地返回第3条、第8条和第1条记录，因为Node(1,1)的子节点有共同的前缀。

除以上基本信息外，每个节点将附带一个二维数组。介绍这两个二维数组的具体构成前，先进行如下定义。

定义2(关键节点) 给定一个节点Nd及一个字符c，若该字符c在给定节点Nd的某个子树中首次出现，且出现字符c的节点没有祖先节点(除去节点Nd)也出现字符c，则称出现字符c的那个节点为字符c关于节点Nd在该子树的关键节点。

注意：给定一个节点和一个字符，其关键节点可能有多个，因为给定节点可能对应多个子树。例如，字符‘x’关于根节点的关键节点为：Node(2,3)，Node(3,6)，Node(1,2)，Node(2,6)。

定义3(首次/末次关键节点) 给定一个节点Nd以及一个字符c，假定节点n2，n3，…，nk为字符c关于节点n1在树的第l层出现的所有关键节点，则首次/末次出现的那个关键节点为字符c关于节点n1在第l层的首次/末次关键节点。特别当第l层只有一个关键节点时，该节点既是字符c关于节点n1在第l层的首次关键节点，也是末次关键节点。

例如，字符‘x’关于根节点在第2层的首次关键节点为Node(2,3)，末次关键节点为Node(2,6)。注意：字符‘x’关于根节点在第3层的首次和末次关键节点均为节点Node(3,6)，因为在该层中，字符‘x’关于根节点只有一个关键节点。

现在介绍附加在每个节点上的二维数组的具体构成。明确二维数组用于存放每个字符在该节点所辖子树各层的首次关键节点。例如，表2和表3分别为根节点和Node(1,4)各自所附加的二维数组。以表3的第1行为例，它表示字符‘w’关于根节点在第l、2、3、4层的首次关键节点分别为Node(1,1)，Node(2,4)，Node(3,5)和null，其中null即为空，返回结果为Φ。

因为某些字符在某些层上可能存在多个关键节点，为了便于访问所有关键节点，对每个节点附加一个关键节点指针，该指针用于指向同一层的下一个关键节点，用pnext表示该指针。对于末次关键节点，让其pnext指针指向null。自此，就可基于节点所附加的二维数组和关键节点指针pnext对有相同符号的所有(关键)节点有效地遍历。例如，如果初始位置在根节点，并想访问字符‘y’在第3层的所有节点，可先通过根节点的首次关键节点数组得知‘y’在第3层的首次关键节点为Node(3,1)。然后，通过Node(3,1)的指针pnext得知其下一个关键节点为Node(3,2)；类似地，通过Node(3.2)的指针pnext得知下一个关键节点为Node(3,4)。最后，因为Node(3,4)的pnext指针为null，遍历到此步终止。到目前为止，已经讨论了MP-tree的主要构件。在下一小节，介绍如何利用MP-tree支持正则表达式查询。值得注意的是，当对数据库进行记录的增加或删除时，需要相应地更新MP-tree，其更新操作与前缀树类似，但需要额外开销更新MP-tree中新增的组件。

表2 根节点首次关键节点

表3 Node(1,4)首次关键节点

2.2 正则表达式查询处理

令recordList表示存放结果集的链表。ch表示存放字符的变量，Q[i]表示查询字串中第i个字符，root表示MP-tree的根节点。表4描述了正则表达式查询处理的伪代码。其大致步骤是先判断查询字串是否为空，或者查询字串的第1个字符是否在根节点的首次关键节点数组中的第i层到第(m-i+1)层存在(m是指数据库中记录字段S的最大长度)。如果查询字串为空或者查询字串的第1个字符不能在根节点的首次关键节点数组中第i层到第(m-i+1)层找到，那么直接返回结果为Φ。否则，根据根节点的首次关键节点数组以及节点的pnext指针，找到第1个字符关于根节点的所有第i层到第(m-i+1)层关键节点。对于上述找到的每个关键节点，调用子函数FindRecordInSubtree( )，然后将子函数找到的结果逐一合并，最后返回结果集合recordList。

表4 正则表达式查询处理

算法1中子函数FindRecordInSubtree( ) 是一个递归函数，该函数在当前节点所辖子树中进一步查找将满足匹配的具体记录。算法2描述了该函数的伪代码，如表5所示。其大致步骤为先判断到当前节点为止，是否已经匹配；如果是，则将该节点Ilist中的所有记录ID返回；注意，Ilist是用于存放节点本身及孩子节点ID的链表。如不能确定已经匹配，继续查找该节点的首次关键节点数组，如在该数组中找不到相应字符的首次关键节点，则表明该节点后不需继续查找，直接返回Φ。否则，根据当前节点的首次关键节点数组以及节点的pnext指针，找到相应字符关于当前节点的所有关键节点。然后，对于上述找到的关键节点，继续调用该递归函数，合并结果并返回。

表5 查询子树中相符记录

例如，假定查询字串为‘zx’，首先根据根节点的关键节点数组找到关于字符‘z’的在第1层到第4层的首次关键节点，这里，Node(1,4)、Node(2,2)和Node(3,3)分别为第1、2、3层的首次关键节点。然后，根据节点的指针pnext找到在该层的所有关于字符‘z’的关键节点。这里，Node(1,4)的pnext为空，所以第1层只有一个关于字符‘z’的关键节点；第3层也只有一个关于字符‘z’的关键节点。然而，Node(2,2)的指针pnext为Node(2,8)，Node(2,8)的指针pnext为空，所以在第2层有两个关键节点。接下来，针对每个关于字符‘z’的关键节点，在该节点的关键节点数组中的第2层到第3层找关于字符‘x’的首次关键节点，根据关于字符‘x’的首次关键节点的pnext指针找到所有关于字符‘x’的关键节点。这里，Node(1,4)的关于字符‘x’的首次关键节点为Node(2,6)，且Node(2,6)的pnext为空，所以Node(1,4)的关于字符‘x’的关键节点只有一个，即Node(2,6)。类似地，对于Node(2,2)、Node(2,8)和Node(3,3)也可以找到其关于字符‘x’的关键节点，其中，关于字符‘x’的关键节点Node(2,2)的为空，Node(2,8)的为Node(3,6)，Node(3,3)的为空。所以，到目前为止，只剩下Node(2,6)和Node(3,6)这两个关键节点所处路径为候选结果。此时，查询字串‘zx’的两个字符都已检查，因此，直接返回这两个节点Ilist中的元组ID，最终返回结果为{6,8}。

2.3 复杂度分析

3 实验结果

为验证提出方法的有效性和效率，与文献[4]中方法进行了比较。为适应所讨论问题，文献[4]的算法需进行简单的修改。具体地，首先，需要将查询字串转换为‘.*’形式的正则表达式；然后，调用其正则表达式匹配算法对每条记录进行匹配验证；最后，返回所有匹配记录的ID信息。简短起见，称这种方法为参照方法，用CM表示。称本文提出方法为基于MP-tree方法，用MPM表示。

随机生成一些列的字符串作为测试数据集。字符串的每个字母都从字符集合C中选取。设C={a,b,c,…,y,z}，设每条生成字符串的长度为10。为测试数据集大小的影响，生成了几组数据集大小不同的集合，其数量分别为：1e+3，1e+4，1e+5，1e+6，1e+7，5e+7，1e+8(其中,1e+7为缺省设置)。此外，为测试查询字串长度影响，使用长度分别为3、4、5、6、7、8、9的字串作为查询字串(其中，5为缺省设置)。这些字串均随机生成，且每组生成10个。每次测试运行10遍，然后计算平均输入/输出(I/O)时间和平均查询时间(CUP时间和I/O时间之和)。

实验运行环境如下：2.6GHzCPU，2G内存，4K页面大小，Windows7操作系统。所有代码均采用C++编程语言，开发工具为MicrosoftVisualStudio2010。接下来报告主要的实验结果。

表6为数据集大小从1e+3增加到1e+8时的平均查询时间。由表6可知：当数据集增大时，CM的查询时间急剧增加，然而MPM的查询时间增长速度相对较缓慢，说明其可扩展性较好。特别当数据集大小达到一定规模时，查询时间比基线方法的查询小几个数量级，说明了提出方法的有效性。

表7为数据集大小对I/O时间的影响。正如所预料的，CM的I/O时间随数据集大小增加迅速增加，然而对MPM的I/O时间影响较小(只是轻微增加)。这组结果表明：MPM更适合于大数据库中正则表达式查询。

表6 查询时间与数据集大小

表7 I/O时间与数据集大小

表8为查询字串长度从3增大到9的查询时间。从表8中可知：查询字串的长度几乎对CM的查询时间没有影响，然而当查询字串增长时，提出方法的查询时间呈递减趋势，这主要因为查询字串越长，查询范围将会越受限，从而大多数节点可以提前被修剪。同时，MPM的查询时间比CM的查询时间小几个数量级，进一步说明了提出方法的有效性。

表9为查询字串长度对I/O的影响。从表9中容易看到：CM的I/O时间几乎与查询字串长度无关，然而对于MPM，其I/O时间与查询字串长度成反比。即查询字串长度越大，I/O时间越小，其主要原因如先前所述，即较长的查询字串有助于限定(或减小)MP-tree搜索范围。

表8 查询时间与查询字串长度

表9 I/O时间与查询字串长度

4 结束语

本文提出了一种处理大数据库中正则表达式查询的算法，并通过理论分析和大量实验证明了其有效性。该算法构造了一种新的索引结构，并在此基础上对正则表达式进行查询处理。查询时，随着数据集的增加，I/O时间和查询时间的增加均较为缓慢，证明其适用于大数据库中正则表达式查询。并且随着查询字串的增加，其I/O时间和查询时间反而呈递减趋势，其查询效率较高。在未来工作中，将尝试扩展该方法使其适用于大数据库中其他类型的查询处理。

[1] 樊爱京,杨照峰.用于网络入侵检测的模式匹配新方法[J].计算机应用,2011,31(11):2961-2964.

[2] 孙钦东,黄新波,王倩.面向中英文混合环境的多模式匹配算法[J].软件学报,2008,19(3):674-686.

[3] 黄昆,张大方,谢高岗,等.一种面向深度数据包检测的紧凑型正则表达式匹配算法[J].中国科学:信息科学,2010,40(2):356-370.

[4] 张树壮,罗浩,方滨兴,等.一种面向网络安全检测的高性能正则表达式匹配算法[J].计算机学报,2010,33(10):1976-1986.

[5] 王培凤,李莉.一种改进的多模式匹配算法在Snort中的应用[J].计算机科学,2012,39(2):72-75.

[6] Ricardo A B Y,Gaston H G.Fast Text Searching for Regular Expressions or Automaton Searching on Tries[J].Journal of ACM,1996,43(6):915-936.

[7] Junghoo C,Rajagopalan S.A Fast Regular Expression Indexing Engine[C]//ICDE.2002:419-430.

[8] Cédric du M,Philippe R,Michel S.Efficient Evaluation of Parameterized Pattern Queries[C]//CIKM.2005:728-735.

[9]Wook-Shin H,Jinsoo L,Yang-Sae M,et al.A New Approach for Processing Ranked Subsequence Matching Based on Ranked Union[C]//SIGMOD.2011:457-468.

[10] Anirban M,Rajeev R,Sriram V.Scalable Regular Expression Matching on Data Streams[C]//SIGMOD.2008:161-172.

国家自然科学基金项目(U1304616);河南省科技攻关基金项目(122102210480)

张晓煜(1973-),女,河南洛阳人,副教授,硕士,主要研究方向为数据处理、模式识别.

2014-11-24

1672-6871(2015)04-0056-06

TP3

A