基于二元组的简单正则表达式的快速检索算法

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于二元组的简单正则表达式的快速检索算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要：

在大型数据集群网络中，业务逻辑节点和数据库节点分布在不同的地理位置，导致在该网络中创建或检索用户数据将经历较大的网络延迟。如何快速找到用户数据的地理位置节点（服务器识别号）将是减少网络延迟的关键。介绍一种动态索引算法，基于简单正则表达，建立用户数据和服务器组之间的映射关系，并引入动态多叉树，实现动态更改映射关系。引入一元组数据节点和二元组数据节点的概念，应用于多叉树，通过分析一元组多叉树和二元组多叉树的时间效率和空间效率，证明二元组多叉树随着树深的增长，检索时间复杂度保持更好的线性特性。通过一些性能测试的实验数据的比较，得出二元组方案的综合性能更优的结论。最后，简要地介绍该算法的应用领域。

关键词：

二元组；正则表达式；多叉树；快速检索；IMS；IMPI；IMPU

中图分类号：TN915.12 文献标识码：A 文章编号：1005-3824（2014）01-0071-05

0 引 言

随着3G网络商用化的成熟和LTE演进，移动数据网的用户数量必然随着各种丰富的移动应用而快速增长。移动数据网最大特点就是用户注册时能够实现用户标识分离[1]，即用户身份和用户终端标识的分离，IMS/SIP网中IMPI[2]/IMPU[3]能够很好支持用户标识分离。大型IMS/SIP商用网络的用户数据管理是基于数据集群网络，同一个用户的信息可能分布在不同的地理位置服务器，同时用户数据的主服务器和备份服务器也是分布在不同地理位置。这就决定了用户数据创建和检索的复杂性。通过数据库集群网络，如MySQL，解决这个困难的做法是，引入索引服务器，通过静态配置用户数据和服务器组的映射关系来克服。 但是这种方法由于具有静态性，用户不能动态更改映射关系，并且这种映射关系存在一对一的局限性，使问题的解决效率不高。

本文介绍了一种动态索引算法，该算法可以根据用户的需求，动态更新映射规则，并且实现一个用户数据对多个服务器（即一个服务器组）的复杂映射关系。算法的核心是：基于简单正则表达，实现用户数据和服务器组的复杂映射关系，并引入常驻内存的动态多叉树[4]实现用户动态更改映射关系。 因此，在IMS网络中用于创建或检索用户数据时，该算法能快速定位所在分布式数据集群网络中的地理位置节点。在此基础上，为了降低迭代次数，本文引入一元组数据节点和二元组数据节点的概念，分别应用于该多叉树。通过分析一元组数据节点和二元组数据节点，以及一元组多叉树和二元组多叉树的时间效率和空间效率，从理论上证明二元组多叉树虽然空间开销稍大一些，但是，基于二元组的多叉树随着树深增长，检索时间复杂度保持更好的线性特性。通过一些性能测试实验数据的比较证明了本文的理论分析，同时得出二元组方案综合性能更优的结论。最后，简要地介绍该算法可能的应用领域。

1 简单正则表达式的定义

简单正则表达式支持的格式为“…%x00w%x00…%x00w%x00…%x00w%x00…”，每个“.”是一个符合RFC2486[2]（IMPI 格式） 和 RFC3261[3]（SIP IMPU格式）规定的有效字符，%x00w%x00中的w是匹配规则通配符串，且%x00w%x00的个数和位置没有限定，为了简化算法和提高检索性能，我们规定如果出现多个%x00w%x00通配符，2个通配符中间至少需要一个“.”。

我们之所以选择%x00封装通配符，是因为根据RFC2486（IMPI） 和 RFC3261（SIP IMPU），“%x00”是未被IMPU和IMPI使用的；同时，使用%x00封装通配符可以避免和其他字符，如“[”，”]”，”{“，”}”，等发生冲突；另外，封装字符串%x00对大小写不敏感，也就是说 “%X00” 和“%x00” 是等价的。

“%x00w%x00” 通用语法确定为

“%x00*[A|D][m，n]%x00”

针对该通用语法的一些特例：

1）“%x00*%x00”表示任意大于等于0的字符串。

2）“%x00*m，n%x00”表示任意大于等于m而小于等于n的字符串， 例如 “%x00*2，6%x00” 表示任意大于等于2而小于等于6的字符串。如果n或m不出现，则表示没有上限或下限，例如， “%x00*，5%x00” 表示任意小于等于5的字符串；“%x00*2，%x00” 表示任意大于等于2的字符串。

3）当 “A” 或 “D”字母出现在星号之后，该通配符串用于匹配纯字母串或纯数字串。

2 动态多叉树的构建

表1中，我们给出了一个服务器组标识符和模式字符串之间映射的例子，模式字符串是在第一小节中定义的。本小节中，如何根据模式字符串构建动态多叉树，将给出2种不同的方案。

方案1。

每棵多叉树由3种节点组成。

根节点：即根模式节点，该节点只存储树的入口地址；

中间节点：即中间模式节点，除了存储指向子节点地址信息外，还存储最多不超过一个通配符加一个常字符分割符，或一个常字符分割串，但不能为空，我们把这种节点所存储的数据称为一元组数据；如果2个通配符之间有多个字符，从第二个字符开始，整个字符串作为常字符分割串存储在其子节点中；

叶子节点：即叶模式节点，除了存储1个一元组数据，还存储最终要检索的服务器组标识符。

如图1所示，我们把该多叉树称为一元组多叉树。

该方案的最大局限性是每个通配符后面都必须跟一个常字符分割符，因此它很难处理下例的模式字符串：

“%x00*1，5%x00bcd%x00*A1，3%x00”。

方案2。

每棵多叉树由3种节点组成。

根节点：即根模式节点，该节点只存储树的入口地址；

中间节点：即中间模式节点，除了存储指向子节点的地址信息外，还存储一个由通配符和一个常字符分割串组成的二元组，它定义如下

在该二元组里，具有先通配符串，后常字符分割串的先后顺序关系，并且通配符串和常字符分割串两者中，可以允许其中之一为空串，但不能2者都空。例如，一个模式字符串：2%x00*D2，2%，在1颗多叉树中，必须有如下1个匹配路径来匹配它：根节点（（。

叶子节点：即叶模式节点，除了存储1个二元组数据，还存储最终要检索的服务器组标识符。

如图2所示，我们把该多叉树称为二元组多叉树。表1列举了3个模式字符串及其对应的服务器组标识符。图1描述了由方案1构建的一元组多叉树，图2描述了由方案2构建的二元组多叉树。如果要检索“” 这个字符串对应的服务器组，在图1和图2中，灰色节点表示匹配该字符串的一个树路径，并最终找到服务器组标识符0x7，该标识符的意思是，在一个服务器集群中，服务器1，2，3存储了该字符串的相关信息。

3.3 数据节点的时间效率分析

方案1：如果输入的字符串要匹配模式字符串， 我们必须先判定模式字符串中是否存在通配符串；由于通配符串是被2个“%x00”包裹，这将产生一次find（）开销用来查找“%x00”。 C++标准定义该算法的复杂度为O（n*m），其中n是输入串的长度，m是检索串的长度。

方案2：在数据节点中存储了1个二元组数据对。由于通配符串和常字符分割串已经按顺序存储，我们就不需要花额外的开销来抽取。所以，在常字符分割串很长的情况下，方案2相比方案1减少很多时间开销。

3.4 多叉树的时间效率分析

对于给定一个输入串，多叉树必须提供一个匹配路径，否则，查询结果为空。这里，我们将最大长度的匹配路径定义为树深，记为H。对于一棵具有M个模式节点的多叉树，我们可以用公式（11）表示它们的关系为

方案1中，从公式（11），我们可以得到树深H和该多叉树所包含的通配符串个数（W）之间的近似关系为

H≈2W （12）

从公式 （12），我们可以得到检索时间的复杂度

TS∝O（2W） （13）

方案2中，从公式（11），我们可以得到树深H和该多叉树所包含通配符串个数（W）之间的近似关系为

H≈W （14）

从公式 （5），我们可以得到检索时间的复杂度如下，

TS∝O（W） （15）

从公式 （13） 和 （15），我们可以看到，当W增加时，二元组多叉树的性能要好于一元组多叉树的性能。 从上面对一元组多叉树和二元组多叉树的数据节点和整棵树时间效率和空间效率的理论分析，我们不难看出，虽然方案1的存储开销要稍小一点，但是它的时间开销要比方案2大不少。

CPU：32 bits， Dual-Core AMD Opteron（tm） 处理器 2212 1GHz。

内存：8 GB。

操作系统：Linux Redhat 5.3。

图11，12和13中的一元组多叉树是根据第2节方案1构建的，二元组多叉树是根据第2节方案2构建的。

4.2 实验案例

1）案例1。

分别构建一棵由10， 25， 50， 100，250，500，1 000个模式字符串组成的多叉树，每个模式字符串组由一个常字符分割串（至少有2个字符组成）+通配符串+常字符分割串组成；再构建一个输入字符串集，集合大小等于模式字符串组的个数，对于每个输入字符串，该多叉树上总能找到一条路径来匹配它；然后随机产生输入字符串来搜索该多叉树，重复1 000次后取平均值作为字符串的检索时间。方案1检索时间对应于图5示例为一元组多叉树的曲线，方案2检索时间对应于图5示例为二元组多叉树的曲线。由此可以看出这2种方案在树深不大的情况下，字符串的检索时间差别不大。

分别构建一棵由50个模式字符串组成多叉树，其他实验数据与实验方法和案例2相同。方案1检索时间对应于图7示例为一元组多叉树的曲线，方案2检索时间对应于图7示例为二元组多叉树的曲线。实验案例3进一步强化了实验案例2的结论：由此可以看出随着树深增加，对于字符串的检索时间，方案2比方案1的优势越来越明显。当通配符串的个数达到9的时候，二元组多叉树的开销要比一元组多叉树的开销省将近48%。

5 结 论

从第3节性能分析和第4节性能测试数据可以看出，随着通配符串个数的增加，二元组多叉树的检索时间保持了比较好的线性特性，一元组多叉树的检索时间则出现了比较大的非线性特性。由此，我们可以得出这样一个结论，二元组多叉树的综合性能要优于一元组多叉树。

6 算法应用领域的思考

在电信领域，随着IMS网络应用的普及，移动互联网用户数的不断增加，分布式用户数据构架已经得到广泛的应用。在这种大背景下，该算法应用于标识用户身份的IMPI/IMPU，创建用户数据时，根据管理人员创建的模式字符串和服务器组映射规则，将其创建到不同后台数据库服务器；同时根据这些模式字符串，查询用户数据的时候，可以迅速定位到该用户位于哪些服务器组。同样，该算法也可以应用于AUC[2] 数据，如 authchar，和 SLF[1，5-7] 数据，如SLFIMPI， SLFIMPU 和SLFMSISDN的创建和查询。

参考文献：

[1]3GPP.TS 23.228-2010 [EB/OL].[2013-09-05]..

[4] CIACCIA P， PATELLA M， ZEZULA P. M-tree： An Efficient Access Method for Similarity Search in Metric Spaces[EB/OL].[2013-09-02]. http：///conf/1997/P426.PDF.

[5] ETSI. ES 282 001-2005 [EB/OL]. [2013-09-08].http：///deliver/etsi_es/282000_282099/282001/01.01.01_60/es_282001v010101p.pdf.

[6] 3GPP. TS 23.002-2011 [EB/OL]. [2013-09-15]. http：//www.quintillion.co.jp/3GPP/Specs/23002-930.pdf

[7] 3GPP.TS22.228-2000[EB/OL]. [2013-09-29]. http：///ftp/tsg_sa/TSG_SA/TSGS_09/Docs/PDF/SP-000370.pdf.

作者简介：

潘志铂（1977-），男，福建永春人，工学硕士，工程师，主要研究方向为大型分布式网络的数据处理。

Fast searching algorithm based on 2-tuple data pair for mini

regular expression

PAN Zhibo

（Alcatel-Lucent Qingdao R&D， Qingdao shandong 266101， P.R.China）

Abstract：

In the large-size data cluster network， service logic nodes and database nodes located in different geographical sites， which cause the creating or querying subscriber data， will experience a big network delay. So how to quickly find the server ID list for the subscriber data will be a key factor to reduce the network delay. In order to resolve this issue， a “dynamic indexing” algorithm is proposed in this paper. The core algorithm is based on two technologies： 1） a mini regular expression which can realize the complicated mappings between subscriber data and server list， and 2） the dynamical M-tree on which user can change the mapping rules dynamically. This paper introduces the concepts of 1-tuple data and 2-tuple data pair for this M-tree respectively. After analyzing key factors for this algorithm， including its time efficiency and space efficiency， this paper makes a conclusion that compared with the 1-tuple M-tree， the searching time complication is keeping better linear for the 2-tuple M-tree when the tree depth is continuously growing. Some performance testing data for them is also provided to consolidate this conclusion. At the end of this paper， some considerations are provided for the applications of this algorithm.

Key words：

2-Tuples，mini regular expression，m-tree，fast search，IMS，IMPI，IMPU