正则表达式语言

2024-05-31

正则表达式语言（精选4篇）

正则表达式语言第1篇

在数据库中查找文本数据是应用程序中很常见的情形。有几种基于全文本的产品可用于IBM DB2 Universal Database TM,包括DB2 Text Information Extender和DB2 Net Search Extender。但是,DB2 Extenders;不包括执行正则表达式匹配的功能,该功能用来查找和替换字符串中的模式。本文描述了如何实现一个用户定义函数(UDF),该函数将普遍可用的正则表达式匹配库与DB2集成在一起。我们通过示例使用了pcre库(Perl兼容的正则表达式),但也可以用任何其它库替换它。

本文中所提供的描述适用于V7和V8版本的DB2通用数据库的Linux版、UNIX版和Windows版。

2 背景知识

本节描述了正则表达式是什么以及它们为什么有用。

正则表达式是什么?

正则表达式用于查找和替换字符串中的模式。正则表达式是用某种语法定义的,正则表达式引擎采用这种语法并将它与字符串进行比较。引擎返回字符串是否与语法匹配的指示;也即,该字符串是否包含能够从该语法派生的子串。此外,引擎还能够返回匹配的子串。术语“模式(pattern)”用来表示语法。

最基本的模式仅由单个字母组成。当与该模式进行比较时,包含这个字母的字符串就是一个“匹配”。例如,如果模式是“a”,则字符串“abcd”就是一个匹配,而字符串“xyz”则不是。正则表达式的强大功能来自于预定义的运算符(也称为元字符),它们可以用很小的空间来表示模式。根据“方言”和受支持的功能,可以使用不同的元字符。通常,其中的一些可用字符如下:

|—二中择一

[]—分组

*—多次出现(也匹配零次出现)

+—多次出现(至少一次)

?—随意的出现次数

—反斜杠

不同的系统实现了常用正则表达式的各种扩展。编程语言Perl中使用的正则表达式支持进一步的缩写。本文中所用的库实现了这些扩展。下面摘录了其中部分可以在Perl正则表达式语言中使用的缩写:

s—任意空白字符

w—任意字母数字字符

d—任意数字字符

另一个更高级的示例是模式“[A-Z]*=([0-9]|0x00);”。与这个模式相匹配的字符串包含这样的子串:它由几个大写字母、后面跟上一个空格、一个等号、另一个空格,然后是一个数字或字符串“0x00”组成。该子串的最后一个字符必须是分号。使用Perl,这个模式可以表示为“w*=(d|0x00);”。“NM=0x00;”和“X=7;”是两个可以与该模式匹配的字符串。但字符串“Z=123;”不能匹配,因为123是由三个数字所组成的。

DB2中的字符串匹配:除了Extender以外,DB2还允许几种用于文本比较的函数和运算符。但那些函数和运算符要么在用于模式匹配的功能方面有限制,要么就是会给可能使用它们的查询带来复杂性。

这里简要地摘录几个可用的功能:

=或<>谓词:逐字符地比较两个字符串是否相等。

LIKE谓词:使用通配符的基本模式匹配。

LOCATE函数:在字符串中查找子串。

尽管也可以用SQL运算符表示模式“[A-Z]*=([0-9]|0x00);”,但那样会很麻烦。例如,下列SELECT语句的WHERE子句中所使用的谓词会匹配字符串“str”中等号之后的部分,如清单1所示:

清单1使用LIKE匹配模式

这增加了可以匹配“[A-Z]*”子模式的谓词的复杂度,这可以使用对整个字符串进行迭代并进行逐字符比较的函数来完成,但您会发现使用内置功能既冗长又复杂。

3 示例方案

让我们定义下列清单(清单2)并插入几行:

清单2创建我们的样本表

这个清单及其数据被用于下面的所有示例。

4 实现模式匹配函数

您可以使用DB2的可扩展机制,在SQL语句内使用UDF,以便显著地改善这种情形。通过定义名为regex1的UDF(它采用模式和字符串作为输入参数),清单1中的WHERE子句现在可以写得象清单3中所示的那样:

清单3使用regex UDF来简化模式匹配

在本示例中,使用带有Perl扩展的正则表达式来匹配完整的模式,而不仅仅是清单1中给出的LIKE谓词所对应的部分模式。正如您所看到的,使用函数来为该模式编写谓词比用LIKE谓词表示同样的语义要容易得多。

5 结束语

本文中简略地介绍了正则表达式以及DB2中可用的字符串比较和匹配功能。另外,描述了为什么正则表达式的强大功能是如此有用。UDF可以用来以两种形式在DB2中提供正则表达式。在第一种形式中,通过将字符串与给定模式进行比较来完成基本匹配。第二种形式是实现表函数,它从正则表达式抽取已捕获的子串,并将这些子串返回给DB2,以便用在SQL语句的进一步处理中。同时还给出了一些关于如何改进性能的提示。

参考文献

[1]位于http://www.ibm.com/cgi-bin/db2www/data/db2/udb/winos2unix/support/v8pubs.d2w/en_main的DB2Application Development Guide.

[2]位于http://www.ibm.com/cgi-bin/db2www/data/db2/udb/winos2unix/support/v8pubs.d2w/en_main的DB2SQL Reference.

[3]位于http://www.pcre.org的PCRE.

Java 正则表达式总结第2篇

正则表达式大全

匹配中文字符的正则表达式： [u4e00-u9fa5]

评注：匹配中文还真是个头疼的事，有了这个表达式就好办了

匹配双字节字符(包括汉字在内)：[^x00-xff]

评注：可以用来计算字符串的长度（一个双字节字符长度计2，ASCII字符计1）

匹配空白行的正则表达式：ns*r 评注：可以用来删除空白行

匹配HTML标记的正则表达式：<(S*?)[^>]*>.*?|<.*? />

评注：网上流传的版本太糟糕，上面这个也仅仅能匹配部分，对于复杂的嵌套标记依旧无能为力

匹配首尾空白字符的正则表达式：^s*|s*$

评注：可以用来删除行首行尾的空白字符(包括空格、制表符、换页符等等)，非常有用的表达式

匹配Email地址的正则表达式：w+([-+.]w+)*@w+([-.]w+)*.w+([-.]w+)* 评注：表单验证时很实用

匹配网址URL的正则表达式：[a-zA-z]+://[^s]*

评注：网上流传的版本功能很有限，上面这个基本可以满足需求

匹配帐号是否合法(字母开头，允许5-16字节，允许字母数字下划线)：^[a-zA-Z][a-zA-Z0-9_]{4,15}$ 评注：表单验证时很实用

匹配国内电话号码：d{3}-d{8}|d{4}-d{7}

评注：匹配形式如0511-4405222或021-87888822

匹配腾讯QQ号：[1-9][0-9]{4,} 评注：腾讯QQ号从10000开始

匹配中国邮政编码：[1-9]d{5}(?!d)评注：中国邮政编码为6位数字

匹配身份证：d{15}|d{18}

评注：中国的身份证为15位或18位

匹配ip地址：d+.d+.d+.d+ 评注：提取ip地址时有用

匹配特定数字：正则表达式大全

^[1-9]d*$

//匹配正整数

^-[1-9]d*$

//匹配负整数

^-?[1-9]d*$

//匹配整数

^[1-9]d*|0$

//匹配非负整数（正整数 + 0）

^-[1-9]d*|0$

//匹配非正整数（负整数 + 0）

^[1-9]d*.d*|0.d*[1-9]d*$

//匹配正浮点数

^-([1-9]d*.d*|0.d*[1-9]d*)$

//匹配负浮点数

^-?([1-9]d*.d*|0.d*[1-9]d*|0?.0+|0)$

//匹配浮点数

^[1-9]d*.d*|0.d*[1-9]d*|0?.0+|0$

//匹配非负浮点数（正浮点数 + 0）^(-([1-9]d*.d*|0.d*[1-9]d*))|0?.0+|0$

//匹配非正浮点数（负浮点数 + 0）

评注：处理大量数据时有用，具体应用时注意修正

匹配特定字符串：

^[A-Za-z]+$

//匹配由26个英文字母组成的字符串

^[A-Z]+$

//匹配由26个英文字母的大写组成的字符串

^[a-z]+$

//匹配由26个英文字母的小写组成的字符串

^[A-Za-z0-9]+$

//匹配由数字和26个英文字母组成的字符串

^w+$

//匹配由数字、26个英文字母或者下划线组成的字符串

在使用RegularExpressionValidator验证控件时的验证功能及其验证表达式介绍如下:

只能输入数字：“^*0-9+*$”

只能输入n位的数字：“^d,n-$”

只能输入至少n位数字：“^d,n,-$”

只能输入m-n位的数字：“^d,m,n-$”

只能输入零和非零开头的数字：“^(0|*1-9][0-9+*)$”

只能输入有两位小数的正实数：“^*0-9]+(.[0-9+,2-)?$”

只能输入有1-3位小数的正实数：“^*0-9]+(.[0-9+ ,1,3-)?$”

只能输入非零的正整数：“^+?*1-9][0-9+*$”

只能输入非零的负整数：“^-[1-9] [0-9+*$”

只能输入长度为3的字符：“^.,3-$”

只能输入由26个英文字母组成的字符串：“^*A-Za-z++$”

只能输入由26个大写英文字母组成的字符串：“^*A-Z++$”

只能输入由26个小写英文字母组成的字符串：“^*a-z++$”

只能输入由数字和26个英文字母组成的字符串：“^*A-Za-z0-9++$”

只能输入由数字、26个英文字母或者下划线组成的字符串：“^w+$”

验证用户密码:“^*a-zA-Z+w,5,17-$”正确格式为：以字母开头，长度在6-18之间，只能包含字符、数字和下划线。

验证是否含有^%&”,;=?$”等字符：“*^%& “,;=?$x22++”

只能输入汉字：“^*u4e00-u9fa5+，0,-$”

验证Email地址：“^w+ *-+.]w+)*@w+([-.]w+)*.w+([-.+w+)*$”

验证InternetURL：“^http://(*w-]+.)+[w-]+(/[w-./?%&=+*)?$”

验证电话号码：“^((d,3,4-)|d,3,4--)?d,7,8-$”

正确格式为：“XXXX-XXXXXXX”，“XXXX-XXXXXXXX”，“XXX-XXXXXXX”，正则表达式大全

“XXX-XXXXXXXX”，“XXXXXXX”，“XXXXXXXX”。

验证身份证号（15位或18位数字）：“^d,15-|d,-18$”

验证一年的12个月：“^(0?*1-9]|1[0-2+)$”正确格式为：“01”-“09”和“1”“12”

验证一个月的31天：“^((0?*1-9])|((1|2)[0-9+)|30|31)$”

正确格式为：“01”“09”和“1”“31”。

匹配中文字符的正则表达式： [u4e00-u9fa5]

匹配双字节字符(包括汉字在内)：[^x00-xff]

匹配空行的正则表达式：n[s| ]*r

匹配HTML标记的正则表达式：/<(.*)>.*|<(.*)/>/

匹配首尾空格的正则表达式：(^s*)|(s*$)

匹配Email地址的正则表达式：w+([-+.]w+)*@w+([-.]w+)*.w+([-.]w+)*

正则表达式优化算法研究第3篇

1 反馈边问题

DFA算法和XFA算法中都存在反馈边过多的问题,极大的影响了算法对存储空间的需求,下面本文将给出自动机中转移边的分类方法以及其中反馈边问题的定义和描述。

1.1 反馈边的定义

图1所表示的是正则表达式{abcad}采用AC(Aho-Corasick)算法构造出的DFA,图中包括6个状态,15条转移边。根据转换目标的不同可以将这15条边分为4类:匹配失败边,重启边,反馈边,基本边。

失败边:图1中所有浅色边表示的转换称为失败边,失败边是指从某一个状态S转移到起始状态S0所经过的的转移边,表示当前输入的字符不在正则表达式{abcad}所描述的字符集范围内,匹配失败,重新开始对下一个字符进行匹配。

重启边:图1中所有虚线边表示的转换称为重启边,重启边是指从当前状态S转移到状态S1所经过的转移边,表示当前输入的字符为正则表达式{abcad}中的第一个字符,状态机跳到状态S1继续进行匹配。

反馈边:图1中加粗的边表示的转换称为反馈边,反馈边是指从当前状态S转换到状态S2的转移边,表示当前输入的字符与前一个输入的字符刚好匹配正则表达式{abcad}中的前两个字符,状态跳转到状态S2继续进行匹配。

基本边:图1中从状态S0一直连接到接收状态S5的一系列成功匹配的转移边称为基本边,它是所有成功匹配的输入必须要经过的边。

观察正则表达式{abcad}可以发现,该正则表达式中出现了2次字符a,而且其中一次出现在整个正则表达式的起始位置。在这种情况下,根据AC算法构造出的DFA就会产生一条反馈边,这条反馈边负责完成匹配输入为abcab*的功能。当输入字符a时,状态机跳转到状态S1,接着输入bca,状态机跳转到状态S4,当继续输入字符b的时候不能跳转到匹配失败时的状态S0,因为字符b的前一个输入字符为a,ab满足了反馈边的要求,所以应该指向第3个状态,状态S2。这样构造出的DFA才能够匹配类似与abcabcad这样的字符输入,符合正则表达式{abcad}描述的正确语义。

1.2 XFA中的反馈边

正则表达式{.*ab.*cd}与{.*df.*gh}合并后的XFA如图2所示,按照XFA构造算法的要求,首先第一步将两个正则表达式中带有.*结构的部分拆分,于是{.*ab.*cd}与{.*df.*gh}被拆分成{.*ab}、{.*cd}、{.*df}、{.*gh}四个表达式,然后转化成对应的DFA之后,状态S2添加一条指令信息:Bit1=true来表示{.*ab}被部分匹配的情况,与此同时状态S4添加一条指令信息:if(Bit1==true)Accept(regex1)来判断是否完成正则表达式{.*ab.*cd}的匹配。同样,在状态S6以及结束状态S8都添加了类似的指令信息,以达到消除DFA里面中间状态,避免出现状态爆炸的目的。

从图2中我们可以看到,存在一条从状态S4到状态S6的反馈边L4-6,产生这条反馈边的原因和多个DFA融合所产生的反馈边相同,都是因为在两个正则表达式中,存在某个公共字符位于其中的某一个表达式的首部。当出现公共字符的情况时,XFA中也必然会出现雷同的现象,在某些状态之间新增了一些反馈边。图3描述的是正则表达式{.*abcd.*cefg}与{.*dcge.*gkda}合并以后的XFA,从图中可以很明显的看到正则表达式之间的公共字符所引起的反馈边数量随着正则表达式长度的增加而明显增多,图3中所描述的XFA拥有状态数17个,基本边16条,1级反馈边7条,约占了所有边总数的1/3,根据图3中反馈边所占比例的分布情况可以预计随着正则表达式条数的增多和正则表达式长度的增长,反馈边的条数所占比例将会大大超过基本边的所占的比例。

2 CXFA算法

2.1 算法动机

动机一:反馈边问题不仅仅在DFA融合中存在,而且在高度压缩的XFA中也存在,甚至比DFA更加严重;

动机二:所有的反馈边所指向的状态都存在一条接收相同字符的边存在;

动机三:一级反馈边所占比例最大,消除一级反馈边可以极大的压缩存储空间;

动机四:一级反馈边的公共字符在第一级处理,消除一级反馈边相对于消除多级反馈边来讲实现代价最低。

2.2 形式化定义

传统的XFA进行匹配的基本模式如图4所示,Rule selector根据当前状态寄存器的值到转移边存储器中,通过查找的方法得到当前输入字符对应的下一状态,反馈回去,更新状态寄存器的值。与此同时,另外一边当前状态的值输入给变量存储器,通过查询和更新变量寄存器,完成XFA中指令信息的更新和查询功能。然后根据查询的结果输出XFA在当前输入字符下的匹配情况。

传统的XFA结构中并没有考虑到自动机状态之间的转移边的处理问题,基于算法动机二“反馈边所指向的状态都存在另外一条接收相同字符的基本边存在”的思想,我们可以试图通过利用这条接收相同字符的基本边来代替反馈边,从而达到消除一级反馈边,压缩自动机存储空间的目的。

这里我们提出一种CACHE-XFA自动机(简称CXFA)来达到消除失败边、重启边和1级反馈边,压缩存储空间的目的。在XFA自动机的基础上,增加一个独立的CACHE状态寄存器,由当前状态寄存器和CACHE状态寄存器共同配合完成XFA自动机状态切换,CXFA的详细结构如图5所示。

传统的XFA下一个状态的生成只与当前状态和输入字符相关,CXFA中下一状态的生成不仅与当前状态和当前输入字符相关,同时CACHE状态也对下一状态的生成产生影响。CXFA利用一个CACHE寄存器存储备用状态,输入字符在当前状态没有下一个状态的情况下,启用CACHE寄存器中存储的备用状态来接收当前字符,达到压缩自动机中冗余转移边的目的。CXFA的形式化定义如下:

定义基于状态的CXFA是一个九元组(Q,Σ,D,C,δ,θ,U,(q0,d0),F),其中:

(1)Q是一个有穷的状态集合。

(2)Σ是一个有穷的输入符号集合,一般称为字母表Σ。

(3)D是一个有穷的变量值的集合。

(4)C是一个CACHE状态集合,C是Q的一个子集。

(5)迁移函数δ是一个以Q中一个状态、C中的一个状态和Σ中一个输入字母为变量并返回Q中状态的函数。

(6)CACHE生成函数θ是一个以起始状态q0和Σ中一个输入字母为变量并返回C中状态的函数。

(7)变量更新函数U是一个对每个状态以Q中一个状态和D中一个变量值为变量并返回D中变量的函数。

(8)(q0,d0,c0)是初始配置,初始配置包含初始状态q0,变量的初始值d0,cache的初始值c0。

(9)接受配置F是Q和D的子集,集合的每个元素包含接受状态和变量的值。

2.3 CXFA中的Cache策略

在预处理阶段,删除从正则表达式集合生成出的CXFA中的失败边、重启边和1级反馈边,转移边集合中只包括基本边和n级反馈边。在字符匹配的阶段,CXFA通过状态转移函数和Cache状态生成函数来完成自动机的状态切换。

CXFA采用了3个输入状态的查表机制,在只存有基本边和n级反馈边的转移边存储器内查找Cache_State、Cur_State、S0所对应的INPUT字符的下一个状态,得到3个不同优先级的next状态S0_next、Cur_next、Cache_next。其中Cur_next优先级最高,Cache_next其次,S0_next优先级最低,通过一个优先级仲裁器输出最终的下一个状态返回给Cur_State寄存器完成一轮自动机状态切换。每一轮的转换过后将S0_next的输出返回给Cache_State寄存器,完成Cache更新操作。

如图7所示的CXFA是图3中的XFA经过删除失败边、重启边、1级反馈边以后得到的自动机。

对于正则表达式{.*abcd.*cefg}与{.*dcge.*gkda}对应的CXFA,输入字符流{abcgkdcgegkda}的状态转换过程如表1所示。表中第一列代表当前的输入字符,第二列代表当前状态,第三列代表CACHE状态,第4,5,6列分别代表生成Next_state的三个仲裁项Cache_state、Cur_next和Cache_next,最后两列代表CXFA中的两个变量的值。首先初始化Cur_state为S0,Cache_state为NULL,在收到第一个字符a的时候经过查找运算得到Cur_next为S1,Cache_next为NULL,S0_next为S1。Next_state取优先级最高的Cur_next,更新第二行的Cur_state为S1,同时更新Cache_state为第一行的S0_next:S1。依此类推,当状态上出现变量更新操作时,更新右边两栏对应的变量值。第13行,Cur_state为S15,Cache_next为S9时,当前输入的字符为a,根据查表运算得到Cur_next为S16,Cache_next为NULL,S0_next为S1,更新下一行。当前Cur_state为S16,Next_state为NULL,同时检查变量Bit2,看到Bit2等于1,输出匹配成功标志accept,完成CXFA匹配。从这里可以看出CXFA算法和XFA算法在功能上是等价的。

表1 CXFA匹配算法执行流程示意表

通过分析字符流{abcgkdcgegkda}的CXFA处理过程可以看出,在删除了失败边、重启边以及1级反馈边的基础上,CXFA在增添了1个Cache状态寄存器和一个优先级仲裁机制之后。通过对S0_next、Cur_next、Cache_next进行仲裁产生了正确的下一状态,能够顺利的完成状态更新,指令执行,变量赋值等XFA基本操作,成功的完成正则表达式匹配的任务,达到了压缩状态转移表,进一步缩小XFA存储空间的目的。

3 算法性能测试

本节将对CXFA算法在SNORT规则集上面的性能进行全面的测试,并对CXFA算法在SNORT规则的适用性进行评估。

本节的适用性测试选取了SNORT规则集中最具有代表性的六种应用层协议规则集作为基准测试集,它们分别是FTP.rules、SMTP.rules、POP3.rules、IMAP.rules、Vo IP.rules和Web-IIS.rules。

SMTP.rules、POP3.rules、IMAP.rules、Vo IP.rules和Web-IIS.rules规则集中CXFA算法相对于D2FA算法和XFA算法的存储规模比如图8所示。从图中线条的走势可以看出CXFA算法具有非常高的压缩率,同时CXFA算法相对于两种算法的压缩比与规则集的大小成正比。SMTP.rules规则集的总长度为2746,CXFA算法无论是相对于D2FA还是XFA都拥有超过30倍的压缩比;相反在规则集规模较小的POP3和IIS中,CXFA算法相对于D2FA的压缩比仅为16.7倍和2.7倍。在POP3和IIS规则集中,D2FA算法的存储压缩效果优于XFA算法。出现这样的情况的原因是由于,在规则集规模减小的情况下,转移边数目对存储的需求大于状态爆炸所引起的存储需求,此时XFA算法压缩效果比较一般。CXFA算法的提出避免了以上情况的发生,在规则集规模较小的情况下,CXFA仍然能够保证非常高的压缩性能。

CXFA算法在XFA算法致力于消除中间状态的基础上,消除了原本自动机中的失败边、重启边、1级反馈边,极大的压缩了边存储空间。在SNORT规则适用性的测试结果表明CXFA算法的存储性能平均是D2FA算法存储性能的40倍,是XFA算法的18倍。

4 总结