2009年10月Journal on Communications October 2009 第30卷第10A期通信学报V ol.30No.10A
正则表达式的DFA压缩算法
杨毅夫1,2,3，刘燕兵1,2,3，刘萍1,3，郭牧怡1,2,3，郭莉1,3
(1. 中国科学院计算技术研究所，北京 100190；2. 中国科学院研究生院，北京 100039;
3. 信息内容安全技术国家工程实验室，北京 100190)
摘要：基于确定有限自动机（DFA）的正则表达式匹配技术通常用于网络流量实时处理、病毒检测等系统中。
随着正则表达式的数量不断增加，DFA的存储空间急剧膨胀。为此，提出了一种有效的DFA压缩算法——簇分割算法，首先总结了DFA的一个结构特征；然后依据此特征把DFA分割为3个部分分别存入3个矩阵中，由此构造出2个特征明显的矩阵和1个典型的稀疏矩阵；最后分别对3个矩阵进行压缩。实验表明，簇分割算法在各组数据中均达到了很好的压缩效果，空间压缩率比较稳定。
关键词：字符串匹配；自动机压缩；正则表达式；入侵检测
中图分类号：TP302 文献标识码：A 文章编号：1000-436X(2009)10A-0036-07
Effective algorithm of compressing regular expressions’ DFA
YANG Yi-fu1,2,3, LIU Yan-bing1,2,3, LIU Ping1,3, GUO Mu-yi1,2,3,GUO Li1,3
(1. Institute of Computing Technology Chinese Academy of Sciences, Beijing 100190, China;
2. Graduate University of Chinese Academy of Sciences, Beijing 100039, China；
3. National Engineering Laboratory for Information Security Technologies, Beijing 100190, China)
Abstract: Regular expression matching technology based on DFA is often used in network real-time processing and virus detection systems. With the number of regular expressions growing, the storage of DFA expands rapidly. An effective al-gorithm of compressing regular expressions’ DFA was presented, which was called cluster-split algorithm. Firstly, a structural characteristic of DFA was summarized. Secondly, the DFA was divided into three parts based the characteristic.
Finally, the three parts was compressed respectively. Experiments show that cluster-split algorithm achieves good effects in all test data, and its space compression rate is relatively stable.
Key words: string matching; automaton compression; regular expressions; intrusion detection
1引言
近年来，正则表达式匹配技术成为计算机安全领域研究的热点问题。正则表达式广泛应用于入侵检测/入侵防御、病毒检测、协议识别等系统中，如Snort[1]、Bro[2]、L7-filter[3]等。随着网络带宽和流量的膨胀以及需要处理的正则表达式规模的不断增加，传统的正则表达式匹配技术正面临严峻的挑战。
传统的正则表达式匹配技术主要是基于非确定有限自动机（NFA）实现的，其匹配速度较慢，并且每次匹配都需要逐条扫描每条表达式。随着表达式规模不断扩大，基于NFA的匹配技术性能急剧下降，已经不能满足应用的需求，因此人们使用匹配速度更快的基于DFA的匹配技术来代替传统的
收稿日期：2009-08-08
基金项目：国家重点基础研究发展计划（“973”计划）基金资助项目（2007CB311100）Foundation Item: The National Basic Research Program of China (973 Program)(2007CB311100)
第10A期杨毅夫等：正则表达式的DFA压缩算法·37·
匹配技术。然而DFA同时带来了另一个问题：DFA 的状态数量有可能指数增加从而导致存储空间急剧增加。例如正则表达式.*AB.{1024}CD对应的DFA的状态规模高达O(21024)。目前对正则表达式的研究主要集中在如何压缩DFA的存储空间，以达到用较少存储空间获取较快匹配速度的目的。
针对DFA占用存储空间过大的问题，本文提出了一种DFA的压缩算法——“簇”分割压缩算法。文章给出了“簇”的定义，并且根据“簇”把DFA 分割成几个部分，然后分别对这些部分进行压缩。本文第2节介绍DFA压缩的相关工作，第3节详细描述簇分割压缩算法，第4节通过详细的实验分析算法的有效性，第5节是结束语。
2 相关工作
正则表达式匹配问题是计算机领域的经典问题，文献[4~6]在正则表达式匹配理论和算法的研究方面卓有成效；随着正则表达式在应用系统中的广泛使用，人们更加关注匹配技术在系统中的实际效果。在实际的系统中，如何降低DFA的状态规模、减少DFA的存储空间仍是研究的焦点。
Fang Y u在文献[7]中用规则分类和规则改写的方法来化简正则表达式。文中依据正则表达式转化成确定有限自动机的状态数规模，把正则表达式分为5类，并提出了2条改写规则以DFA的状态规模。但是经过上述规则改写后的表达式并不与原来的表达式完全等价，只适合于非重叠匹配（non-overlapping match）的情况，因此限制了它的使用范围。
Kumar在文献[8]中提出了D2FA方法来压缩DFA的存储空间。通过引入默认转移边（default transition）来减少转移边的数目，从而降低自动机的存储空间。引入默认转移边能极大地减少了确定DFA的转移边，该文的实验表明，该方法平均能够减少95%的转移边。但是该方法的缺陷是，每处理一个字符可能需要在D2FA中进行多次状态跳转，导致实际的匹配性能不高。
Ficara在文献[9]中提出了δFA方法来压缩DFA 的状态表。该方法提取子状态和父状态的相同元素来消除状态转换表的冗余。在状态访问序列中，如果当前状态t要访问的元素next[t, c]与其前一个状态s的对于元素next[s, c]相同，那么可以直接从前一个状态中读取相应的值。该方法能够取得非常好的压缩效果，但是每次状态转换需要对时间进行更新，因此总的扫描时间是O(n*|Σ|)，这是非常费时的。
Smith在文献[10]中提出了XFA方法来解决正则表达式合并过程中出现的状态爆炸问题。该方法对有限自动机进行扩展，在每个自动机状态上附加计数标记来记录正则表达式中字符的重复次数。该方法能够比较好地解决DFA的状态爆炸问题，但是有如下2个缺陷：①对每个状态需要更新和检查相关的计数器，影响了匹配速度；②该方法只能对单个字符进行计数，在正则表达式中往往出现一个字符串的多次重复，如(abc){1, 4}，XFA无法解决这种计数问题。
陈曙晖等在文献[11]中提出了集合交割的预编码方法（SI-precode）来状态转移表的存储空间。该方法对于包含大量字符组的正则表达式压缩效果非常明显，但是无法解决一般正则表达式状态表的压缩问题。
张伟等在文献[12]中设计并实现了一种多正则表达式匹配的硬件架构MRM。该架构将正则表达式分解为普通字符串和限定重复的简单正则表达式，并针对NIDS系统的规则进行了优化，获得了2.8Gbit/s的扫描速度。但是该方案也只能支持一类特殊的正则表达式规则（分解为普通字符串和限定重复的简单正则表达式），因而限制了其应用范围。
从上面的工作可以看出，现有的正则表达式匹配方法具有如下不足之处：①在已有的对空间进行压缩的方法中，往往只关注压缩比，对匹配性能的分析都是理论层面上的，实际运行效果不佳；②现有的优化方法都是针对一类特殊的正则表达式进行的，无法解决一般正则表达式的匹配问题，其原因在于没有更好地挖掘多正则表达式之间由于正则语义带来的冗余关系和分布特征。因此需要对多正则表达式做进一步的研究。
3 簇分割压缩算法
本节首先引入簇的定义，然后介绍DFA的一个重要特征及压缩思想，接着详细描述整个算法，最后分析算法的状态转移时间复杂度及存储空间复杂度。整个过程以表达式.*A.{2}CD为例，其对应的DFA和存储矩阵如图1所示。
3.1簇的定义
在trie结构中，一个状态的后继状态集合称为一个簇。初始状态是单独的一个簇。簇在本质上就是对trie结构的一个划分，因此trie结构中的每个
·38· 通 信 学 报 第30卷
状态都属于唯一的一个簇。
在DFA 中，按层次进行遍历（宽度优先遍历）可以得到唯一确定的trie 结构，在trie 结构上可以得到唯一确定的簇划分，因此在DFA 中也可以得到唯一确定的簇划分。图1中右图是DFA 按照层次遍历得到的trie 结构，按照簇的定义，可以知道初始状态{0}是一个簇；0的下一个状态集合是{1}，因此{1}也是一个簇；同理，状态集合{2,3}、{4,5}、{6,7}、{8}、{9}都是一个簇。这些簇不仅是对trie 结构的一个划分，也是对DFA 的一个划分。 3.2 DFA 的特征及压缩算法的主要思想
经过大量的实验可以发现DFA 的一个重要特征：每个状态的转移边不是随机分布的，而是比较集中地指向其中的2个簇。表1列出了L7-Filter 中几条典型规则的转移边分布情况。把每个状态的转移边按簇进行分类，把指向同一簇最多的转移边放在第1个矩阵T 1中，把指向同一簇第二多的转移边放在第2个矩阵T 2中。表中第1列是所使用规则的名称，第2、3列是矩阵T 1、T 2中有效元素的比例，第4列是矩阵T 1、T 2有效元素的总比例。从表中可以看出，DFA 的绝大部分转移边都集中地指向其中的2个簇。
表1 后继状态的分布特征
规则 T 1比例 T 2比例 总比例
http 65.4% 34.07% 99.47%
ftp 62.38% 36.93% 99.31%
smtp 99% 0.95% 99.95%
dns 75.67% 20.26% 95.93%
ssl 99.71% 0.25% 99.96%
簇分割算法利用上述特征对DFA 进行压缩，其主要思想是：DFA 中每个状态的转移边都集中地指向其中的2个簇，因此把DFA 按簇分割为3个部分（包括矩阵T 1、T 2及剩余部分T 3），然后分别对每个部分进行压缩。图2是算法的处理流程：算法首先对DFA 按层次进行重排，使得每个簇中的状态编号是一个连续的序列；然后把DFA 按簇分割为矩阵T 1、T 2和T 3；最后分别对3个矩阵进行压缩，其中T 1、T 2的结构相同，因此可以使用相同的方法进行压缩；T 3是一个典型的稀疏矩阵，使用经典的稀疏矩阵压缩算法即可。
Procedure Compress (DFA, N )
1) rearrange DFA's state label in breadth first traversing order 2) (T 1, T 2, T 3) ? Split (DFA, N ); //分割DFA 为3个矩阵3) Compress1(T 1, N ) //对第1个矩阵进行压缩 4) Compress1(T 2, N ) //对第2个矩阵进行压缩 5) Compress2(T 3, N ) //对剩余的稀疏矩阵进行压缩
6)
End of procedure
图2 簇分割算法的主要思想
3.3 DFA 分割及矩阵压缩算法
上一节描述了DFA 簇分割算法的主要思想，本节将对算法进行详细介绍：首先介绍DFA 的分割算
法，然后介绍分割后矩阵的压缩算法。
3.3.1 DFA 分割算法
前面提到按层次遍历DFA ，可以得到DFA 唯
一的簇划分，其簇划分为{{0}，{1}，{2，3}，{4，
5}，{6，7}，{8}，{9}}。
利用DFA 的特征，即DFA 中每个状态的转移
边都集中地指向其中的2个簇，把DFA 分割成3
图1 表达式.*A.{2}CD 的簇分割压缩算法过程
第10A期杨毅夫等：正则表达式的DFA压缩算法·39·
个部分，分别用3个矩阵进行存储。具体过程如下：把指向同一簇最多的转移边放到矩阵T1中，把指向同一簇第二多的元素放到矩阵T2中，把剩余的元素放到矩阵T3中。DFA的分割过程如图3中左图所示，图中的4个矩阵分别代表DFA的存储矩阵T，分割后的第1个矩阵T1，第2个矩阵T2及第3个矩阵T3。对状态0，其转移边分别指向状态1、0、0，其中有两条转移边指向簇{0}，有1条转移边指向簇{1}，因此把指向簇{0}的2条转移边放到矩阵T1中，把指向簇{1}的一条转移边放到矩阵T2中，矩阵T3中状态0对应的行无有效元素；对状态1，其转移边分别指向状态2、3、3，3条边都指向簇{2，3}，因此把3条转移边都放到矩阵T1中，矩阵T2、T3中状态1对应的行无有效元素；同理，对其他状态的转移边做同样的处理即可得到矩阵T1、T2、T3。
3.3.2 矩阵的压缩
矩阵T1和T2有共同的特征，即矩阵中的每行元素都属于同一个簇；矩阵T3是一个典型的稀疏矩阵，使用经典的稀疏矩阵压缩算法即可，本文不再讨论。在描述矩阵T1和T2的压缩算法前，先引入一个概念。
可合并的行：在存储矩阵T中，行r和s如果对任意字符c都满足T[r,c]=?1或T[s,c]=?1或T[r,c]=T[s,c]，则称r和s是可合并的行。
如果矩阵中的行r和s是可合并的，则按如下方式进行合并：①对字符c，如果T[s,c]=?1,则T[s,c]=T[r,c]；如果T[s,c]=T[r,c]或者T[r,c]=?1，则T[s,c]的值不变；②增加索引数组equal，使得equal[r]=s，表示行r和行s是可合并的；③删除矩阵中的行r。
压缩矩阵T1、T2的核心思想是：通过把矩阵转化为偏移量矩阵，从而构造出大量的可合并行，然后进行合并以减少存储空间。在3.2节中提到，对DFA按层次重排后，每个簇中的状态编号是一个连续序列，假设连续序列为{a, a+1, a+2,…, a+n}，对序列提取一个base值，把序列转化为a + {0, 1, 2, …, n}。矩阵T1和T2的每行都是指向同一簇的转移边，因此通过对每行提取base可以把T1、T2转化为偏移量矩阵，而偏移量矩阵大大增加了可合并行的数量，其原因如下：假如矩阵中的2行r={a, a+1, a+2, …, a+n}和s={b, b+1, b+2, …, b+n}，并且其有效元素的位置都一一对应，根据可合并行的定义，行r和s是不可合并的。通过对2个序列提取base，r转化为a+r'（r'={0, 1, 2,…, n}），s2转化为b+s’(s’={0, 1, 2, …, n})，根据可合并行的定义，序列r'和s'是可合并的。因此，通过提取base可以把矩阵中不可合并的行转化为可合并的行。
图3中右图是矩阵T1的合并过程，其中第1个矩阵是T1，第2矩阵是T1对每个状态提取base 后的存储结构，第3个矩阵是可合并的行进行合并后的存储结构。
压缩算法代码如图4所示。算法首先提取出每个簇的base值；然后把矩阵转化为偏移量矩阵；最后合并可合并的行。
3.4状态转移时间复杂度及空间复杂度分析
图5是压缩算法的状态转移过程。算法首先判断转移边所在的矩阵，如果在矩阵T1中，则通过T1访问，需要4次访存；如果在矩阵T2中，则通
(a) DFA按簇分割过程(b) 矩阵T1合并过程
图3 DFA按簇分割过程及矩阵行合并过程
·40·
通 信 学 报 第30卷
Procedure Compress1(T 1; N ) 1 For i ? 0, N ?1 Do 2
base[i ] ? the min value of the ith cluster;
3 For c ? 0, C ?1 Do
4 If T 1[i ,c ] != ?1 Then 5
T 1[i ; c ]? T 1[i ; c ] ? base[i ]
6 End of if
7
End of for
8 End of for
9 EquRowElim (T 1, N ) //合并矩阵的可合并行 10
End of procedure
图4 矩阵T 1、T 2的压缩算法
Procedure NextState (int cur, unsigned char c ) 1
If T [cur][c] is in T 1 Then
2 Return T 1[equal1[cur]][c ] + base1[cur]
3 If T [cur][c ] is in T 2 Then
4 Return T 2[equal2[cur]][c ] + base2[cur]
5 Else
6 Return T 3[cur][c ]
7
End of Procedure
图5 压缩算法的状态转移过程
过T 2访问，需要5次访存；如果在矩阵T 3中，则
通过T 3访问，如果T 3采用“三数组”[13]存储，需要5次访存。可以通过增加位图来快速判断转移边所在的矩阵，但位图需要占用一定的存储空间。
算法的存储空间主要由3个部分组成：T 1经过压缩后得到的矩阵T 1'，T 1的base 数组，T 1的equal 数组，以及标识T1的位图bitmap ；T 2经过压缩后得到的矩阵T 2'，T 2的base 数组，T 2的equal 数组；T 3经过压缩的结构T 3'。3个部分的存储空间用公式表示如下： T 1=T 1'+base(T 1)+equal(T 1)+bitmap(T 1) (1)
T 2=T 2'+ base(T 2)+equal(T 2) (2)
T 3=T 3' (3)
本文使用空间压缩率来评价算法的压缩效果。
定义空间压缩率=压缩后的存储空间/压缩前的存储空间，因此空间压缩率越小，算法的压缩效果越好；空间压缩率越大，算法的压缩效果越差。
为了计算簇分割算法的空间压缩率，需要引入一些变量。n 表示DFA 的状态数量，即矩阵T 的大小；n 1和n 2分别表示矩阵T 1'和T 2'的大小。
需要注意的是，T 1'和T 2'是偏移量矩阵，其元素的大小≤|Σ|，如果字符集为ASCII ，则每个元素只用一个字节即可存储；base 是一个int 型数组，其大小为n ；equal 数组中每个元素用lb T '字节表示，其大小为n ；矩阵T 3使用经典的稀疏矩阵压缩方法，最终的存储空间与T 3中的有效元素有关，因
此只统计T 3中的有效元素的占用比例，用r 表示。用MR 表示算法空间压缩率，把上面的公式代入MR 可得到：
MR = (T 1+T 2+T 3)/T (4)
=124n n n ++12
22log log 25632
n n +×+3.9%+r (5)
式中只有n ，n 1，n 2和r 是变量，因此实验中
只需统计这些变量便可得出算法的空间压缩率。
4 实验及分析
实验主要包括2个部分，分别是算法的空间压缩率对比实验和匹配速度对比实验。 4.1 实验数据
实验数据如表2所示，包括104条L7-filter 规则，3组Snort 规则，1组BRO 规则以及按照文献[7]生成的几类规则（表2中规则type-1到type-6）。实验使用由Michela Becchi 提供的工具regex-tool
(https://www.doczj.com/doc/6d8634279.html,/)来生成DFA 。
regex-tool 能对规则自动分组，把一个规模巨大、无法存储的DFA 分成若干个规模适中的DFA ，104条L7-filter 规则被分成了8组（表2中规则L7-1到L7-8）。
表2
实验数据
规则集
规则数 DFA 状态数
规则描述
L7-1 26 3 172 L7-Flter L7-2 7 42 711 L7-Flter L7-3 6
30 135 L7-Flter
L7-4 13 22 608 L7-Flter
L7-5 13
8 344 L7-Flter L7-6 13 12 896 L7-Flter
L7-7 13 3 473 L7-Flter L7-8 13 28 476 L7-Flter Snort24 24 13 882 Snort Snort31 31 19 522 Snort Snort34 34 13 834 Snort BRO217 217 6 533 BRO type-1 50 248 ^ABCD type -2 10 78 337 ^AB.*CD type -3 50 8 338 ^AB.{0,j }CD type -4 10 5 290 ^A+[A-Z]{j }D type -5 50 7 828 ^AB.{j }CD type -6
50
14 496
A[A-Z]{j }D
第10A期杨毅夫等：正则表达式的DFA压缩算法·41·
4.2空间压缩率比较
在空间压缩率实验中，簇分割压缩算法与算法δFA[9]、Default_Row[13]（三数组方法的一个版本，通过提取每行最频繁的元素，把存储矩阵转化为稀疏矩阵，然后进行压缩）进行对比。
3个算法空间压缩率的结果对比如表3所示。压缩前的DFA压缩率设为1.0，表中n代表DFA的状态数量，n1代表矩阵T1的大小，n2代表矩阵T2的大小，r代表矩阵T3中有效元素的比例。
分析表3中n1和n2的实验结果，可以看出通过把矩阵T1和T2转化为偏移量矩阵构造出了大量的可合并行，最终压缩后的矩阵的行的数量不超过原矩阵的1%，在L7-3数据下n1甚至只有n的0.01%。分析表中r的实验结果，可以看出在提取出矩阵T1、T2后，剩余的矩阵T3是一个比较稀疏的矩阵，这从实验方面验证了本文对DFA特征的总结。
从表3中可以看出，簇分割算法的空间压缩率在规则L7-filter、BRO、type-1及type-6中优于其他算法。最重要的是，簇分割算法的空间压缩率比较稳定，在绝大部分数据下其压缩率保持在5%左右，最坏的情况下（规则L7-4）其空间压缩率也不超过10%。
δFA的空间压缩率在Snort规则下最优，但在其他数据下效果相对较差；Default_Row算法的空间压缩率在规则type-2，type-3，type-4，type-5下最优，实验结果表明针对这些类别的规则，提取每行中最频繁的元素可以把矩阵转化为稀疏矩阵。
4.3匹配速度比较
在匹配速度实验中，簇分割算法和原始的DFA
算法、δFA[9]算法进行比较。实验规则为表2中的type-2规则，待匹配数据为随机生成100MB文本。
从前面的分析可知，簇分割算法和δFA算法的
匹配速度与其包含的稀疏矩阵的压缩方法有关，在
本实验的测试中，实现了3种经典的稀疏矩阵压缩
方法：
1) 顺序存储：稀疏矩阵中的有效元素按顺序存储，使用二分查找访问有效元素。
2) 三数组方法[13]：使用base、next和check 3个数组来存储稀疏矩阵中的有效元素，可在O(1)
时间内访问有效元素。
3) Tetris-hashing[15]：Tetris-hashing是使用hash
方法存储稀疏矩阵的经典方法，通过hash计算可在
O(1)时间内访问有效元素。
采用不同的稀疏矩阵压缩方法，3种算法的匹
配速度如表4所示。δFA算法的Tetris-hash由于构
建时间太长，在表中没有给出其结果。原始DFA
的存储矩阵没有进行压缩，因此在3种方法下的匹
配速度相同。
从表3及表4可以看出，簇分割算法对各组数
据不但达到了很好的压缩效果，而且搜索速度没有
明显地降低。另一方面，虽然δFA在Snort规则下
有很好的压缩效果，但是搜索速度却远远小于其他
表3 算法的空间压缩率对比（n-DFA的大小；n1-矩阵T1的大小；n2-矩阵T2的大小；r-矩阵T3中有效元素的比例）压缩前的DFA 簇分割算法
规则集
n 压缩率n1 n2 r 压缩率
δFA压缩率 Default_Row压缩率L7-1 3 172 1.0 52 22 0.024 621 0.064 543 0.634 964 0.232 905 L7-2 42 711 1.0 31 53 0.010 378 0.050 345 0.918 592 0.243 461 L7-3 30 135 1.0 3 21 0.011 429 0.050 997 0.960 985 0.356 860 L7-4 22 608 1.0 7 44 0.054 823 0.094 585 0.097 177 0.381 078 L7-5 8 344 1.0 57 7 0.005 791 0.045 585 0.820 768 0.203 315 L7-6 12 896 1.0 103 40 0.007 236 0.047 315 0.827 021 0.055 044 L7-7 3 473 1.0 36 7 0.001 071 0.040 808 0.912 125 0.059 149 L7-8 28 476 1.0 207 86 0.008 930 0.049 187 0.804 303 0.231 309 Snort24 13 882 1.0 13 34 0.021 074 0.060 880 0.037 515 0.108 468 Snort31 19 522 1.0 7 34 0.020 840 0.060 571 0.053 581 0.061 309 Snort34 13 834 1.0 6 17 0.017 938 0.057 565 0.032 259 0.060 473 BRO217 6 533 1.0 1 14 0.020 456 0.059 840 0.061 814 0.224 820 type-1 249 1.0 1 2 0.000 016 0.039 163 0.111 281 0.186 697 type-2 78 337 1.0 512 2 0.000 102 0.040 011 0.099 659 0.030 254 type-3 8 338 1.0 43 5 0.002 395 0.042 113 0.948 123 0.018 575 type-4 5 290 1.0 236 4 0.012 469 0.052 368 0.990 808 0.046 357 type-5 7 828 1.0 1 22 0.002 451 0.041 598 0.947 048 0.019 762 type-6 14 496 1.0 9 22 0.002 300 0.041 715 0.973 929 0.173 284
·42· 通 信 学 报
第30卷
杨毅夫（1982-），男，湖南郴州人，中国科学院计算技术研究所硕士生，主要研究方向为字符串处理相关的算法、信息安全等。
算法，这是因为δFA 算法的状态转移时间复杂度高达O (Σ)，而其他算法则是O (1)的，因此δFA 不适合软件实现。
表4 算法的匹配速度（单位：MB/s ）对比
算法 顺序存储
三数组方法
Tetris-hashing
原始DFA 63.37 63.37 63.37
簇分割算法
53.33 52.88 52.47
δFA
0.16 0.35 —
5 结束语
随着网络带宽和流量的急剧增加以及应用需求
的不断增长，传统基于NFA 的正则表达式匹配技术已经不能满足实际应用的需求。目前人们研究的焦点集中在匹配速度更快基于DFA 的匹配技术，但DFA 巨大的存储空间导致其无法应用于实际系统中。本文提出了一种有效的DFA 压缩算法——簇分割DFA 压缩算法：文章首先总结了DFA 的1个结构特征；然后依据此特征把DFA 分割为3个部分分别存入3个矩阵中，由此构造出2个特征明显的矩阵和1个典型的稀疏矩阵；最后分别对3个矩阵进行压缩。实验表明，簇分割算法在各组数据中均达到了很好地压缩效果，空间压缩率比较稳定，保持在5%左右，并且匹配速度相对其他算法也有一定优势。 参考文献：
[1] Snort user manual, the snort project[EB/OL]. https://www.doczj.com/doc/6d8634279.html,/
assets/82/snort_manual.pdf.
[2] Introduction to bro[EB/OL]. https://www.doczj.com/doc/6d8634279.html,/wiki/index.php/ Bro. [3] L7-filter classifier README[EB/OL]. http: https://www.doczj.com/doc/6d8634279.html,/
README.
[4] THOMPSON K. Programming techniques: regular expression search
algorithm[J]. Communications of the ACM, 1968, 11(6):419-422. [5] MYERS E W. A four russians algorithm for regular expression pattern
matching[J]. Journal of the ACM, 1992. 39(2):430-448.
[6] NA V ARRO G. Compact DFA representation for fast regular expression
search[A]. Proceedings of the 5th Workshop on Algorithm Engineer-ing[C]. Lecture Notes in Computer Science, 2001. 1-12.
[7] YU F, CHEN Z, DIAO Y . Fast and memory-e±cient regular expression
matching for deep packet nspection[A]. Proceedings of the 2006 ACM/IEEE symposium on Architecture for Networking and Commu-nications Systems[C]. 2006. 93-102.
[8] KUMAR S, DHARMAPURIKAR S, YU F, et al . Turner algorithms to
accelerate multiple regular expressions matching for deep packet in-spection[J]. ACM SIGCOMM Computer Communication Review,
2006. 36(4):339-350.
[9] DOMENICO F, STEFANO G , GREGORIO P, et al . An improved DFA
for fast regular expression matching[J]. ACM SIGCOMM Computer Communication Review, 2008, 38(5): 29-40.
[10] SMITH R, ESTAN C, JHA S. XFA: faster signature matching with
extended automata[A]. IEEE Symposium on Security and Privacy[C].
Oakland, 2008. 187-201.
[11] 陈曙晖,苏金树,范慧萍等. 一种基于深度报文检测的FSM 状态表
压缩技术[J]. 计算机研究与发展, 2008,8:1299-1306.
CHEN S H, SU J S, FAN H P, et al . An FSM state table compressing
method based on deep packet inspection[J]. Journal of Computer Re-search and Development, 2008, 45(8): 1299-1306.
[12] ZHANG W, SONG T, WANG D S. A multiple regular expressions
matching architecture for network intrusion detection system[A]. Communications and Networking in China(ChinaCom2008)[C]. Third International Conference on, 2008.687-691.
[13] AHO A V, SETHI R, ULLMAN J D. Compilers : Principles, Tech-niques, and Tools. Addison-Wesley Publishing Co.[S]. ISBN 0-201- 10088-6, 1986. 144.
[14] AHO A V, CORASICK M J. Efficient string matching: an aid to
bibliographic search[J]. Communication of the ACM, 1975, 18(6): 333-340.
[15] GALLI N, SEYBOLD B, SIMON K. Tetris-hashing or optimal table
compression[J]. Discrete Applied Mathematics, 2001, 110(1):41-58.
作者简介：
刘燕兵（1981-），男，湖北麻城人，中国科学院博士生，中国科学院计算技术研究所助理研究员，主要研究方向为字符串处理相关的算法、信息安全等。
刘萍（1972-），女，山东济南人，中国科学院计算技术研究所助理研究员、中国计算机学会会员，主要研究方向为信息安全、数据流处理、字符串匹配算法。
郭牧怡（1984-），女，河北石家庄人，中国科学院计算技术研究所硕士生，主要研究方向为字符串处理相关的算法、信息安全等。
郭莉（1969-），女，湖南株洲人，中国科学院计算技术研究所正研级高级工程师、硕士生导师，主要研究方向为信息安全、数据流处理。
正则表达式 一、什么是这则表达式 正则表达式（regular expressions）是一种描述字符串集的方法，它是以字符串集中各字符串的共有特征为依据的。正则表达式可以用于搜索、编辑或者是操作文本和数据。它超出了java程序设计语言的标准语法，因此有必要去学习特定的语法来构建正则表达式。一般使用的java.util.regex API所支持的正则表达式语法。 二、测试用具 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Scanner; import java.util.regex.Matcher; import java.util.regex.Pattern; public class Regex{ public static void main(String[]args)throws Exception{ BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); if(br==null){ System.out.println("没有输入任何数据"); System.exit(1); } while(true){ System.out.print("输入表达式："); Pattern pattern=https://www.doczj.com/doc/6d8634279.html,pile(br.readLine()); System.out.print("输入字符串："); Matcher matcher=pattern.matcher(br.readLine()); boolean found=false; while(matcher.find()){ System.out.println("找到子字符串"+matcher.group()+" 开始于索引"+matcher.start()+"结束于索引"+matcher.end()+"\n") found=true; } if(!found){ System.out.println("没有找到子字符串\n"); } } } }
引言 正则表达式（regular expression）就是用一个“表达式”来描述一个特征，然后去验证另一个“字符串”是否符合这个特征。比如表达式“ab+” 描述的特征是“一个 'a' 和任意个'b' ”，那么 'ab', 'abb', 'abbbbbbbbbb' 都符合这个特征。 正则表达式可以用来：（1）验证字符串是否符合指定特征，比如验证是否是合法的邮件地址。（2）用来查找字符串，从一个长的文本中查找符合指定特征的字符串，比查找固定字符串更加灵活方便。（3）用来替换，比普通的替换更强大。 正则表达式学习起来其实是很简单的，不多的几个较为抽象的概念也很容易理解。之所以很多人感觉正则表达式比较复杂，一方面是因为大多数的文档没有做到由浅入深地讲解，概念上没有注意先后顺序，给读者的理解带来困难；另一方面，各种引擎自带的文档一般都要介绍它特有的功能，然而这部分特有的功能并不是我们首先要理解的。 文章中的每一个举例，都可以点击进入到测试页面进行测试。闲话少说，开始。 1. 正则表达式规则 1.1 普通字符 字母、数字、汉字、下划线、以及后边章节中没有特殊定义的标点符号，都是"普通字符"。表达式中的普通字符，在匹配一个字符串的时候，匹配与之相同的一个字符。 举例1：表达式 "c"，在匹配字符串 "abcde" 时，匹配结果是：成功；匹配到的内容是："c"；匹配到的位置是：开始于2，结束于3。（注：下标从0开始还是从1开始，因当前编程语言的不同而可能不同） 举例2：表达式 "bcd"，在匹配字符串 "abcde" 时，匹配结果是：成功；匹配到的内容是："bcd"；匹配到的位置是：开始于1，结束于4。 1.2 简单的转义字符 一些不便书写的字符，采用在前面加 "\" 的方法。这些字符其实我们都已经熟知了。
Sed基础用法篇 刚开始接触linux，其实还是老实用vim来编辑文件，不过同样的过程重复多次，你就要想办法简化你的过程。sed绝对是一个好的命令或者工具，你不需要用vim打开文件就可以直接编辑(推荐掌握以下用法)。 1、删除行首空格 sed 's/^[ ]*//g' filename sed 's/^ *//g' filename sed 's/^[[:space:]]*//g' filename 2、行后和行前添加新行 行后：sed 's/pattern/&\n/g' filename 行前：sed 's/pattern/\n&/g' filename &代表pattern 3、使用变量替换(使用双引号) sed ‐e "s/$var1/$var2/g" filename 4、在第一行前插入文本 sed ‐i '1 i\插入字符串' filename 5、在最后一行插入 sed ‐i '$ a\插入字符串' filename
6、在匹配行前插入 sed ‐i '/pattern/ i "插入字符串"' filename 7、在匹配行后插入 sed ‐i '/pattern/ a "插入字符串"' filename 8、删除文本中空行和空格组成的行以及#号注释的行 grep ‐v ^# filename | sed /^[[:space:]]*$/d | sed /^$/d 9、要将目录/modules下面所有文件中的zhangsan都修改成list，可用如下命令:(注意备份原文件) sed ‐i 's/zhangsan/list/g' `grep zhangsan ‐rl /modules` Linux命令FIND详解 由于find具有强大的功能，所以它的选项也很多，其中大部分选项都值得我们花时间来了解一下。即使系统中含有网络文件系统( NFS)，find命令在该文件系统中同样有效，只你具有相应的权限。在运行一个非常消耗资源的find命令时，很多人都倾向于把它放在后台执行，因为遍历一个大的文件系统可能会花费很长的时间(这里是指30G字节以上的文件系统)。 一、find 命令格式 1、find命令的一般形式为； find pathname ‐options [‐print ‐exec ‐ok ...]
正则表达式基础知识 一个正则表达式就是由普通字符（例如字符a 到z）以及特殊字符（称为元字符）组成的文字模式。该模式描述在查找文字主体时待匹配的一个或多个字符串。正则表达式作为一个模板，将某个字符模式与所搜索的字符串进行匹配。如：
下面看几个例子： "^The"：表示所有以"The"开始的字符串（"There"，"The cat"等）； "of despair$"：表示所以以"of despair"结尾的字符串； "^abc$"：表示开始和结尾都是"abc"的字符串——呵呵，只有"abc"自己了；"notice"：表示任何包含"notice"的字符串。 '*'，'+'和'?'这三个符号，表示一个或一序列字符重复出现的次数。它们分别表示“没有或更多”，“一次或更多”还有“没有或一次”。下面是几个例子： "ab*"：表示一个字符串有一个a后面跟着零个或若干个b。（"a", "ab", "abbb",……）；"ab+"：表示一个字符串有一个a后面跟着至少一个b或者更多； "ab?"：表示一个字符串有一个a后面跟着零个或者一个b； "a?b+$"：表示在字符串的末尾有零个或一个a跟着一个或几个b。 也可以使用范围，用大括号括起，用以表示重复次数的范围。 "ab{2}"：表示一个字符串有一个a跟着2个b（"abb"）； "ab{2,}"：表示一个字符串有一个a跟着至少2个b； "ab{3,5}"：表示一个字符串有一个a跟着3到5个b。
请注意，你必须指定范围的下限（如："{0,2}"而不是"{,2}"）。 还有，你可能注意到了，'*'，'+'和'?'相当于"{0,}"，"{1,}"和"{0,1}"。 还有一个'|'，表示“或”操作： "hi|hello"：表示一个字符串里有"hi"或者"hello"； "(b|cd)ef"：表示"bef"或"cdef"； "(a|b)*c"：表示一串"a""b"混合的字符串后面跟一个"c"； '.'可以替代任何字符： "a.[0-9]"：表示一个字符串有一个"a"后面跟着一个任意字符和一个数字； "^.{3}$"：表示有任意三个字符的字符串（长度为3个字符）； 方括号表示某些字符允许在一个字符串中的某一特定位置出现： "[ab]"：表示一个字符串有一个"a"或"b"（相当于"a|b"）； "[a-d]"：表示一个字符串包含小写的'a'到'd'中的一个（相当于"a|b|c|d"或者"[abcd]"）；"^[a-zA-Z]"：表示一个以字母开头的字符串； "[0-9]%"：表示一个百分号前有一位的数字； "[0-9]+"：表示一个以上的数字； ",[a-zA-Z0-9]$"：表示一个字符串以一个逗号后面跟着一个字母或数字结束。 你也可以在方括号里用'^'表示不希望出现的字符，'^'应在方括号里的第一位。（如："%[^a-zA-Z]%"表 示两个百分号中不应该出现字母）。 为了逐字表达，必须在"^.$()|*+?{\"这些字符前加上转移字符'\'。 请注意在方括号中，不需要转义字符。
QRegExp正则表达式 2010-03-20 17:00 "^\d+$" //非负整数（正整数 + 0） "^[0-9]*[1-9][0-9]*$" //正整数 "^((-\d+)|(0+))$" //非正整数（负整数 + 0） "^-[0-9]*[1-9][0-9]*$" //负整数 "^-?\d+$" //整数 "^\d+(\.\d+)?$" //非负浮点数（正浮点数 + 0） "^(([0-9]+\.[0-9]*[1-9][0-9]*)|([0-9]*[1-9][0-9]*\.[0-9]+)|([0-9]*[1-9][0-9]*))$" //正浮点数 "^((-\d+(\.\d+)?)|(0+(\.0+)?))$" //非正浮点数（负浮点数 + 0） "^(-(([0-9]+\.[0-9]*[1-9][0-9]*)|([0-9]*[1-9][0-9]*\.[0-9]+)|([0-9]*[ 1-9][0-9]*)))$" //负浮点数 "^(-?\d+)(\.\d+)?$" //浮点数 "^[A-Za-z]+$" //由26个英文字母组成的字符串 "^[A-Z]+$" //由26个英文字母的大写组成的字符串 "^[a-z]+$" //由26个英文字母的小写组成的字符串 "^[A-Za-z0-9]+$" //由数字和26个英文字母组成的字符串 "^\w+$" //由数字、26个英文字母或者下划线组成的字符串 "^[\w-]+(\.[\w-]+)*@[\w-]+(\.[\w-]+)+$" //email地址 "^[a-zA-z]+://(\w+(-\w+)*)(\.(\w+(-\w+)*))*(\?\S*)?$" //url "^(d{2}|d{4})-((0([1-9]{1}))|(1[1|2]))-(([0-2]([1-9]{1}))|(3[0|1]))$" // 年-月-日 "^((0([1-9]{1}))|(1[1|2]))/(([0-2]([1-9]{1}))|(3[0|1]))/(d{2}|d{4})$" // 月/日/年 "^([w-.]+)@(([[0-9]{1,3}.[0-9]{1,3}.[0-9]{1,3}.)|(([w-]+.)+))([a-zA-Z ]{2,4}|[0-9]{1,3})(]?)$" //Email "(d+-)?(d{4}-?d{7}|d{3}-?d{8}|^d{7,8})(-d+)?" //电话号码 "^(d{1,2}|1dd|2[0-4]d|25[0-5]).(d{1,2}|1dd|2[0-4]d|25[0-5]).(d{1,2}|1 dd|2[0-4]d|25[0-5]).(d{1,2}|1dd|2[0-4]d|25[0-5])$" //IP地址 ^([0-9A-F]{2})(-[0-9A-F]{2}){5}$ //MAC地址的正则表达式 ^[-+]?\d+(\.\d+)?$ //值类型正则表达式 QRegExp是Qt的正则表达式类. Qt中有两个不同类的正则表达式. 第一类为元字符.它表示一个或多个常量表达式. 令一类为转义字符,它代表一个特殊字符. 一.元字符 . 匹配任意单个字符.例如, 1.3 可能是1. 后面跟任意字符,再跟3 ^ 匹配字符串首. 例如, ^12可能是123,但不能是312
VC正则表达式的使用 2010年9月11日星期六邵盛松 正则表达式是一种对字符进行模糊匹配的一个公式。在数据有效性验证，查找，替换文本中都可以使用正则表达式。 本篇文章主要描述的是使用ATL中两个模板类CAtlRegExp和CAtlREMatchContext。 在使用CAtlRegExp类之前需要添加#include
多少年来，许多的编程语言和工具都包含对正则表达式的支持，.NET基础类库中包含有一个名字空间和一系列可以充分发挥规则表达式威力的类，而且它们也都与未来的Perl 5中的规则表达式兼容。 此外，regexp类还能够完成一些其他的功能，例如从右至左的结合模式和表达式的编辑等。 在这篇文章中，我将简要地介绍System.Text.RegularExpression中的类和方法、一些字符串匹配和替换的例子以及组结构的详细情况，最后，还会介绍一些你可能会用到的常见的表达式。 应该掌握的基础知识 规则表达式的知识可能是不少编程人员“常学常忘”的知识之一。在这篇文章中，我们将假定你已经掌握了规则表达式的用法，尤其是Perl 5中表达式的用法。.NET的regexp类是Perl 5中表达式的一个超集，因此，从理论上说它将作为一个很好的起点。我们还假设你具有了C#的语法和.NET架构的基本知识。 如果你没有规则表达式方面的知识，我建议你从Perl 5的语法着手开始学习。在规则表达式方面的权威书籍是由杰弗里?弗雷德尔编写的《掌握表达式》一书，对于希望深刻理解表达式的读者，我们强烈建议阅读这本书。 RegularExpression组合体 regexp规则类包含在System.Text.RegularExpressions.dll文件中，在对应用软件进行编译时你必须引用这个文件，例如： csc r:System.Text.RegularExpressions.dll foo.cs 命令将创建foo.exe文件，它就引用了System.Text.RegularExpressions文件。 名字空间简介 在名字空间中仅仅包含着6个类和一个定义，它们是： Capture: 包含一次匹配的结果； CaptureCollection: Capture的序列； Group: 一次组记录的结果，由Capture继承而来； Match: 一次表达式的匹配结果，由Group继承而来； MatchCollection: Match的一个序列； MatchEvaluator: 执行替换操作时使用的代理； Regex: 编译后的表达式的实例。 Regex类中还包含一些静态的方法： Escape: 对字符串中的regex中的转义符进行转义； IsMatch: 如果表达式在字符串中匹配，该方法返回一个布尔值； Match: 返回Match的实例； Matches: 返回一系列的Match的方法； Replace: 用替换字符串替换匹配的表达式； Split: 返回一系列由表达式决定的字符串； Unescape:不对字符串中的转义字符转义。
js正则表达式使用 一，概述 1，正则表达式，可以说是任何一种编程语言都提供的机制，它主要是提供了对字符串的处理能力。 2，正则表达式在页面处理中的使用场景： 1）表单验证。验证某些域符合某种规则，例如邮件输入框必须输入的是邮件、联系电话输入框输入的必须是数字等等 2）处理DOM模型。例如通过表达式定位DOM中的一个对象或一系列对象，一个例子就是定位id属性中含有某个特殊字符的div对象。 3）纯编程逻辑。直接用于编程的逻辑之中。 3，说明：本部分所举的正则表达式的代码片断，都是经过测试的，但有一点需要注意，对于换行的字符串的定义，我们在表述时使用的是类似如下的形式： var str=“It?s is a beautiful city”； 这种形式直接写在JS代码中是错误的，那如何获取具有换行的字符串呢？简单的办法：在textarea中输入文本并换行，然后将该值赋给JS变量即可。例如： var str=document.forms[0].mytextarea.value; 二，语法与使用 1，定义正则表达式 1）定义正则表达式有两种形式，一种是普通方式，一种是构造函数方式。 2）普通方式：var reg=/表达式/附加参数 表达式：一个字符串，代表了某种规则，其中可以使用某些特殊字符，来代表特殊的规则，后面会详细说明。 附加参数：用来扩展表达式的含义，目前主要有三个参数： g：代表可以进行全局匹配。 i：代表不区分大小写匹配。 m：代表可以进行多行匹配。 上面三个参数，可以任意组合，代表复合含义，当然也可以不加参数。 例子： var reg=/a*b/; var reg=/abc+f/g; 3）构造函数方式：var reg=new RegExp(“表达式”,”附加参数”); 其中“表达式”与“附加参数”的含义与上面那种定义方式中的含义相同。 例子： var reg=new RegExp(“a*b”); var reg=new RegExp(“abc+f”,”g”); 4）普通方式与构造函数方式的区别 普通方式中的表达式必须是一个常量字符串，而构造函数中的表达式可以是常量字符串，也可以是一个js变量，例如根据用户的输入来作为表达式参数等等： var reg=new RegExp(document.forms[0].exprfiled.value,”g”);
语法词法生成器 一、语法词法生成器Flex 语法扫描器生成器 flex (fast lexical analyser generator) 是Lex的另一个替代品。它经常和自由软件Bison语法分析器生成器一起使用。Flex 最初由Vern Paxson 于1987 年用C语言写成。语法分析生成器JavaCC JavaCC(Java Compiler Compiler) 是一个用JA V A开发的最受欢迎的语法分析生成器。这个分析生成器工具可以读取上下文无关且有着特殊意义的语法并把它转换成可以识别且匹 配该语法的JA VA程序。它还提供JJTree等工具来...语法分析器生成工具YACC 这是一个经典的生成语法分析器的工具，大学的《编译原理》课程里介绍过。词法分析工具ANTLR ANTLR(ANother Tool for Language Recognition)它是Java开发的词法分析工具，它可以接受词文法语言描述,并能产生识别这些语言的语句的程序。作为翻译程序的一部分,你可以使用简单的操作符和动作来参数化你的文法...解析器生成器
Bison GNU bison是一个自由软件，用于自动生成语法分析器程序，实际上可用于所有常见的操作系统。Bison把LALR形式的上下文无关文法描述转换为可做语法分析的C或C++程序。在新近版本中，Bison增加了对GLR语法分析算法的支...词法分析器生成工具Lex 这是一个经典的生成词法分析器的工具语法分析器生成工 具Berkeley Yacc Berkeley Yacc (byacc) 是一个高质量的yacc 变种，其目的是为了避免依赖某个特定的编译器。语法分析生成器JFlex JFlex是一个Java的词法/语法分析生成器。JavaScript解析器Jison JavaScript解析器，Coffee就是使用Jison解析的。Jison 将一个上下文无关语法作为输入，输出对应的JavaScript代码，类似Yacc。词法/语法分析框架chrysanthemum chrysanthemum （中文名“菊花”）是一个由C++写成的小巧
《易语言“正则表达式”教程》 本文改编自多个文档，因此如有雷同，不是巧合。 “正则表达式”的应用范围越来越广，有了这个强大的工具，我们可以做很多事情，如搜索一句话中某个特定的数据，屏蔽掉一些非法贴子的发言，网页中匹配特定数据，代码编辑框中字符的高亮等等，这都可以用正则表达式来完成。 本书分为四个部分。 第一部分介绍了易语言的正则表达式支持库，在这里，大家可以了解第一个正则表达式的易语言程序写法，以及一个通用的小工具的制作。 第二部分介绍了正则表达式的基本语法，大家可以用上述的小工具进行试验。 第三部分介绍了用易语言写的正则表达式工具的使用方法。这些工具是由易语言用户提供的，有的工具还带有易语言源码。他们是：monkeycz、零点飞越、寻梦。 第四部分介绍了正则表达式的高级技巧。 目录 《易语言“正则表达式”教程》 (1) 目录 (1) 第一章易语言正则表达式入门 (3) 一．与DOS下的通配符类似 (3) 二．初步了解正则表达式的规定 (3) 三．一个速查列表 (4) 四．正则表达式支持库的命令 (5) 4.1第1个正则表达式程序 (5) 4.2第2个正则表达式例程 (7) 4.3第3个例程 (8) 4.4一个小型的正则工具 (9) 第二章揭开正则表达式的神秘面纱 (11) 引言 (12) 一.正则表达式规则 (12) 1.1普通字符 (12) 1.2简单的转义字符 (13) 1.3能够与“多种字符”匹配的表达式 (14) 1.4自定义能够匹配“多种字符”的表达式 (16) 1.5修饰匹配次数的特殊符号 (17) 1.6其他一些代表抽象意义的特殊符号 (20) 二.正则表达式中的一些高级规则 (21) 2.1匹配次数中的贪婪与非贪婪 (21)
1、正则表达式-完结篇---工具类开发--- ? 1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3 1 4 1 '/.+/', 'email'=> '/^\w+([-+.]\w+)*@\w+([-.]\w+)*\.\w+([-.]\w+)*$/', 'url'=> '/^http(s?):\/\/(?:[A-za-z0-9-]+\.)+[A-za-z]{2,4}(?:[\/ \?#][\/=\?%\-&~`@[\]\':+!\.#\w]*)?$/', 'currency'=> '/^\d+(\.\d+)?$/', 'number'=> '/^\d+$/', 'zip'=> '/^\d{6}$/', 'integer'=> '/^[-\+]?\d+$/', 'double'=> '/^[-\+]?\d+(\.\d+)?$/',
5 1 6 1 7 1 8 1 9 2 0 2 1 2 2 2 3 2 4 2 5 2 6 2'english'=> '/^[A-Za-z]+$/', 'qq'=> '/^\d{5,11}$/', 'mobile'=> '/^1(3|4|5|7|8)\d{9}$/', ); //定义其他属性 private$returnMatchResult=false; //返回类型判断 private$fixMode=null; //修正模式 private$matches=array(); //存放匹配结果 private$isMatch=false; //构造函数，实例化后传入默认的两个参数 public function __construct($returnMatchResult=false,$fixMode=null){ $this->returnMatchResult=$returnMatchResult; $this->fixMode=$fixMode; } //判断返回结果类型，为匹配结果matches还是匹配成功与否isMatch，并调用返回方法 private function regex($pattern,$subject){ if(array_key_exists(strtolower($pattern), $this->validate)) $pattern=$this->validate[$pattern].$this->fixMode; //判断后再连接上修正模式作为匹配的正则表达式 $this->returnMatchResult ?
正则表达式是常见常忘，所以还是记下来比较保险，于是就有了这篇笔记。 希望对大家会有所帮助。J 1．什么是正则表达式 简单的说，正则表达式是一种可以用于文字模式匹配和替换的强有力的工具。是由一系列普通字符和特殊字符组成的能明确描述文本字符串的文字匹配模式。 正则表达式并非一门专用语言，但也可以看作是一种语言，它可以让用户通过使用一系列普通字符和特殊字符构建能明确描述文本字符串的匹配模式。除了简单描述这些模式之外，正则表达式解释引擎通常可用于遍历匹配，并使用模式作为分隔符来将字符串解析为子字符串，或以智能方式替换文本或重新设置文本格式。正则表达式为解决与文本处理有关的许多常见任务提供了有效而简捷的方式。 正则表达式具有两种标准： ·基本的正则表达式(BRE – Basic Regular Expressions) ·扩展的正则表达式(ERE – Extended Regular Expressions)。 ERE包括BRE功能和另外其它的概念。 正则表达式目前有两种解释引擎： ·基于字符驱动(text-directed engine) ·基于正则表达式驱动(regex-directed engine) Jeffery Friedl把它们称作DFA和NFA解释引擎。 约定： 为了描述起来方便，在本文中做一些约定： 1. 本文所举例的所有表达时都是基于NFA解释引擎的。 2. 正则表达式，也就是匹配模式，会简写为Regex。 3. Regex的匹配目标，也就是目标字符串，会简写为String。 4. 匹配结果用会用黄色底色标识。 5. 用1\+1=2 括起来的表示这是一个regex。 6. 举例会用以下格式： Regex Target String Description test This is a test 会匹配test，testcase等 2．正则表达式的起源正则表达式的?祖先?可以一直上溯至对人类神经系统如何工作的早期研究。Warren McCulloch 和 Walter Pitts 这两位神经生理学家研究出一种数学方式来描述这些神经网络。 1956 年, 一位叫 Stephen Kleene 的美国数学家在 McCulloch 和 Pitts 早期工作的基础上，发表了一篇标题为?神经网事件的表示法?的论文，引入了正则表达式的概念。正则表达式就是用来描述他称为?正则集的代数?的表达式，因此采用?正则表达式?这个术语。
2re模块的基本函数 在上面的说明中，我们已经对re模块的基本函数‘findall’很熟悉了。当然如果光有findall 的话，很多功能是不能实现的。下面开始介绍一下re模块其它的常用基本函数。灵活搭配使用这些函数，才能充分发挥Python正则式的强大功能。 首先还是说下老熟人findall函数吧 findall(rule,target[,flag]) 在目标字符串中查找符合规则的字符串。 第一个参数是规则，第二个参数是目标字符串，后面还可以跟一个规则选项（选项功能将在compile函数的说明中详细说明）。 返回结果结果是一个列表，中间存放的是符合规则的字符串。如果没有符合规则的字符串被找到，就返回一个空列表。 2.1使用compile加速 compile(rule[,flag]) 将正则规则编译成一个Pattern对象，以供接下来使用。 第一个参数是规则式，第二个参数是规则选项。 返回一个Pattern对象 直接使用findall(rule,target)的方式来匹配字符串，一次两次没什么，如果是多次使用的话，由于正则引擎每次都要把规则解释一遍，而规则的解释又是相当费时间的，所以这样的效率就很低了。如果要多次使用同一规则来进行匹配的话，可以使用https://www.doczj.com/doc/6d8634279.html,pile函数来将规则预编译，使用编译过返回的Regular Expression Object或叫做Pattern对象来进行查找。 >>>s='111,222,aaa,bbb,ccc333,444ddd' >>>rule=r’\b\d+\b’ >>>compiled_rule=https://www.doczj.com/doc/6d8634279.html,pile(rule) >>>compiled_rule.findall(s) ['111','222'] 可见使用compile过的规则使用和未编译的使用很相似。compile函数还可以指定一些规则标志，来指定一些特殊选项。多个选项之间用’|’（位或）连接起来。 I IGNORECASE忽略大小写区别。 L LOCAL字符集本地化。这个功能是为了支持多语言版本的字符集使用环境的，比如在转义符\w，在英文环境下，它代表[a-zA-Z0-9]，即所以英文字符和数字。如果在一个法语环境下使用，缺省设置下，不能匹配"é"或"?"。加上这L选项和就可以匹配了。不过这个对于中文环境似乎没有什么用，它仍然不能匹配中文字符。 M MULTILINE多行匹配。在这个模式下’^’(代表字符串开头)和’$’(代表字符串结尾)将能够匹配多行的情况，成为行首和行尾标记。比如 >>>s=’123456\n789012\n345678’ >>>rc=https://www.doczj.com/doc/6d8634279.html,pile(r’^\d+’)#匹配一个位于开头的数字，没有使用M选项 >>>rc.findall(s) ['123']#结果只能找到位于第一个行首的’123’ >>>rcm=https://www.doczj.com/doc/6d8634279.html,pile(r’^\d+’,re.M)#使用M选项 >>>rcm.findall(s) ['123','789','345']#找到了三个行首的数字
前端资源收集 前端资-源收集 收集的资-源 44个 Javascript 变态题解析 javascript 变态题解析 正则表达式收集 正则表达式收集 十大经典排序算法总结（JavaScript描述）排序算法的总结 前端工具库汇总 前端工具库总结 怎么学JavaScript？ 学习javascript 的学习指导 不定期更新 JavaScript技巧 javascript 编码技巧总结 H5项目常见问题汇总及解决方案 高质量的常见问题汇总 廖雪峰的 git 教-程 Git忽略规则.gitignore梳理 git 配置提交规则 全局环境，执行环境
setTimeout promises 很酷，但很多人并没有理解就在用了 promises 使用错误汇总 promises webpack 2 中文文档 输入url后的加载过程 详细解答从输入URL 到页面显示的过程 数组Array.prototype方法 介绍了数组的一些新的方法 移动端真机调试 Web 客户端存储 ESLint中文指南 webpack 2 集成ESLint react-webpack2-skeleton webpack 2 react 成功案例，包括热加载 cookie 小结 CSS定制多行省略 Ajax 知识体系大梳理 js+nodejs完成文件上传 用 webpack 实现持久化缓存 搜罗一切webpack的好文章好工具 深入理解 CSS：字体度量、line-height 和 vertical-align
原生JS中DOM节点相关API合集 正则表达式前端使用手册 聊一聊H5应用缓存-Manifest fetch进阶指南 mozilla 开发者网络 深入理解javascript原型和闭包系列JavaScript深入系列 深度长文 JavaScript数组所有API全解密你真的懂 JavaScript 的正则吗？webpack2 终极优化 文件上传那些事儿 写给前端工程师的DNS基础知识 初识weex（前端视角） - 环境搭建 前端命名规范 正则表达式 总有你要的编程书单（GitHub ）JavaScript深入系列 javascript 的一些功能点 如何在小程序中调用本地接口 移动端浏览器调试方法汇总 HTML5移动开发中的input输入框类型 互联网协议入门
Java正则表达式详解 仙人掌工作室 如果你曾经用过Perl或任何其他内建正则表达式支持的语言，你一定知道用正则表达式处理文本和匹配模式是多么简单。如果你不熟悉这个术语，那么“正则表达式”（Regular Expression）就是一个字符构成的串，它定义了一个用来搜索匹配字符串的模式。 许多语言，包括Perl、PHP、Python、JavaScript和JScript，都支持用正则表达式处理文本，一些文本编辑器用正则表达式实现高级“搜索-替换”功能。那么Java又怎样呢？本文写作时，一个包含了用正则表达式进行文本处理的Java规范需求（Specification Request）已经得到认可，你可以期待在JDK的下一版本中看到它。 然而，如果现在就需要使用正则表达式，又该怎么办呢？你可以从https://www.doczj.com/doc/6d8634279.html,下载源代码开放的Jakarta-ORO库。本文接下来的内容先简要地介绍正则表达式的入门知识，然后以Jakarta-ORO API为例介绍如何使用正则表达式。 一、正则表达式基础知识 我们先从简单的开始。假设你要搜索一个包含字符“cat”的字符串，搜索用的正则表达式就是“cat”。如果搜索对大小写不敏感，单词“catalog”、“Catherine”、“sophisticated”都可以匹配。也就是说： 1.1句点符号 假设你在玩英文拼字游戏，想要找出三个字母的单词，而且这些单词必须以“t”字母开头，以“n”字母结束。另外，假设有一本英文字典，你可以用正则表达式搜索它的全部内容。要构造出这个正则表达式，你可以使用一个通配符——句点符号“.”。这样，完整的表达式就是“t.n”，它匹配“tan”、“ten”、“tin”和“ton”，还匹配“t#n”、“tpn”甚至“t n”，还有其他许多无意义的组合。这是因为句点符号匹配所有字符，包括空格、Tab字符甚至换行符： 1.2方括号符号 为了解决句点符号匹配范围过于广泛这一问题，你可以在方括号（“[]”）里面指定看来有意义的字符。此时，只有方括号里面指定的字符才参与匹配。也就是说，正则表达式“t[aeio]n”只匹配“tan”、“Ten”、“tin”和“ton”。但“Toon”不匹配，因为在方括号之内你只能匹配单个字符 1.3“或”符号
正则表达式
目录
1. 引言 2. 基本语法 3. sed 4. awk 5. 练习:在 C 语言中使用正则表达式
1. 引言
以前我们用 grep 在一个文件中找出包含某些字符串的行,比如在头文件中找出一个宏定义. 其实 grep 还可以找出符合某个模式(Pattern)的一类字符串.例如找出所有符合 xxxxx@xxxx.xxx 模式的字符串(也就是 email 地址),要求 x 字符可以是字母,数字,下划 线,小数点或减号,email 地址的每一部分可以有一个或多个 x 字符,例如 abc.d@https://www.doczj.com/doc/6d8634279.html,, 1_2@987-6.54,当然符合这个模式的不全是合法的 email 地址,但至少可以做一次初步筛选, 筛掉 a.b,c@d 等肯定不是 email 地址的字符串.再比如,找出所有符合 yyy.yyy.yyy.yyy 模 式的字符串(也就是 IP 地址),要求 y 是 0-9 的数字,IP 地址的每一部分可以有 1-3 个 y 字 符. 如果要用 grep 查找一个模式,如何表示这个模式,这一类字符串,而不是一个特定的字符串 呢?从这两个简单的例子可以看出,要表示一个模式至少应该包含以下信息: 字符类(Character Class):如上例的 x 和 y,它们在模式中表示一个字符,但是取 值范围是一类字符中的任意一个. 数量限定符(Quantifier): 邮件地址的每一部分可以有一个或多个 x 字符,IP 地址 的每一部分可以有 1-3 个 y 字符 各种字符类以及普通字符之间的位置关系:例如邮件地址分三部分,用普通字符@和. 隔开,IP 地址分四部分,用.隔开,每一部分都可以用字符类和数量限定符描述.为 了表示位置关系,还有位置限定符(Anchor)的概念,将在下面介绍.
规定一些特殊语法表示字符类,数量限定符和位置关系,然后用这些特殊语法和普通字符一 起表示一个模式,这就是正则表达式(Regular Expression).例如 email 地址的正则表达式 可以写成[a-zA-Z0-9_.-]+@[a-zA-Z0-9_.-]+\.[a-zA-Z0-9_.-]+,IP 地址的正则表达式可以 写成[0-9]{1,3}\.[0-9]{1,3}\.[0-9]{1,3}\.[0-9]{1,3}.下一节介绍正则表达式的语法, 我们先看看正则表达式在 grep 中怎么用.例如有这样一个文本文件 testfile:
192.168.1.1
第 1 页 共 10 页
Java中的正则表达式 众所周知，在程序开发中，难免会遇到需要匹配、查找、替换、判断字符串的情况发生，而这些情况有时又比较复杂，如果用纯编码方式解决，往往会浪费程序员的时间及精力。因此，学习及使用正则表达式，便成了解决这一矛盾的主要手段。 大家都知道，正则表达式是一种可以用于模式匹配和替换的规范，一个正则表达式就是由普通的字符（例如字符a到z）以及特殊字符（元字符）组成的文字模式，它用以描述在查找文字主体时待匹配的一个或多个字符串。正则表达式作为一个模板，将某个字符模式与所搜索的字符串进行匹配。 自从jdk1.4推出java.util.regex包，就为我们提供了很好的JAVA正则表达式应用平台。 因为正则表达式是一个很庞杂的体系，所以我仅例举些入门的概念，更多的请参阅相关书籍及自行摸索。 \\ 反斜杠 \t 间隔 ('\u0009') \n 换行 ('\u000A') \r 回车 ('\u000D') \d 数字等价于[0-9] \D 非数字等价于[^0-9] \s 空白符号 [\t\n\x0B\f\r] \S 非空白符号 [^\t\n\x0B\f\r] \w 单独字符 [a-zA-Z_0-9] \W 非单独字符 [^a-zA-Z_0-9] \f 换页符 \e Escape \b 一个单词的边界 \B 一个非单词的边界 \G 前一个匹配的结束 ^为限制开头 ^java 条件限制为以Java为开头字符 $为限制结尾 java$ 条件限制为以java为结尾字符 .为限制一个任意字符 java.. 条件限制为java后除换行外任意两个字符 加入特定限制条件「[]」 [a-z] 条件限制在小写a to z范围中一个字符 [A-Z] 条件限制在大写A to Z范围中一个字符 [a-zA-Z] 条件限制在小写a to z或大写A to Z范围中一个字符 [0-9] 条件限制在小写0 to 9范围中一个字符
C#正则表达式之Regex类用法详解 正则表达式的本质是使用一系列特殊字符模式，来表示某一类字符串，正则表达式无疑是处理文本最有力的工具，而.NET提供的Regex类实现了验证正则表达式的方法。 Regex类表示不可变（只读）的正则表达式。它还包含各种静态方法，允许在不显式创建其他类的实例的情况下使用其他正则表达式类。 正则表达式基础概述 什么是正则表达式 在编写字符串的处理程序时，经常会有查找符合某些复杂规则的字符串的需要。正则表达式就是用于描述这些规则的工具。换句话说，正则表达式就是记录文本规则的代码。 通常，我们在使用WINDOWS查找文件时，会使用通配符（*和?）。如果你想查找某个目录下的所有Word文档时，你就可以使用*.doc进行查找，在这里，*就被解释为任意字符串。和通配符类似，正则表达式也是用来进行文本匹配的工具，只不过比起通配符，它能更精确地描述你的需求——当然，代价就是更复杂。 一、C#正则表达式符号模式
说明： 由于在正则表达式中“\”、“?”、“*”、“^”、“$”、“+”、“（”、“）”、“|”、“{”、“[”等字符已经具有一定特殊意义，如果需要用它们的原始意义，则应该对它进行转义，例如希望在字符串中至少有一个“\”，那么正则表达式应该这么写：\\+。
二、在C#中，要使用正则表达式类，请在源文件开头处添加以下语句： 复制代码代码如下: using Syst https://www.doczj.com/doc/6d8634279.html, ressions; 三、RegEx类常用的方法 1、静态Match方法 使用静态Match方法，可以得到源中第一个匹配模式的连续子串。 静态的Match方法有2个重载，分别是 Regex.Match(string input,string pattern); Regex.Match(string input,string pattern,RegexOptions options); 第一种重载的参数表示：输入、模式 第二种重载的参数表示：输入、模式、RegexOptions枚举的“按位或”组合。 RegexOptions枚举的有效值是： Complied表示编译此模式 CultureInvariant表示不考虑文化背景 ECMAScript表示符合ECMAScript，这个值只能和IgnoreCase、Multiline、Complied连用ExplicitCapture表示只保存显式命名的组 IgnoreCase表示不区分输入的大小写 Ign https://www.doczj.com/doc/6d8634279.html, pace表示去掉模式中的非转义空白，并启用由#标记的注释Multiline表示多行模式，改变元字符^和$的含义，它们可以匹配行的开头和结尾 None表示无设置，此枚举项没有意义 RightToLeft表示从右向左扫描、匹配，这时，静态的Match方法返回从右向左的第一个匹配Singleline表示单行模式，改变元字符.的意义，它可以匹配换行符