正则表达式（共9篇）
正则表达式 篇1
1 引言
正则表达式起源于早期对人类神经系统工作原理的研究。1956年,数学家Stephen Kleen在对神经网络早期研究的论文《神经网事件的表示法》里,用称之为正则集合的数学符号来描述模型,引入了正则表达式的概念。之后,Unix之父Ken Thompson把这一成果应用于计算搜索算法的一些早期研究,并将此符号系统引入编辑器QED,然后是Unix上的编辑器ED,并最终引入GREP。从此,正则表达式被广泛地应用到各种Unix或类似于Unix的工具中,例如Perl。Perl的正则表达式源自于Henry Spencer编写的regex,之后已演化成了pcre(Perl兼容正则表达式Perl Compatible Regular Expressions),pcre是一个由Philip Hazel开发的,为很多现代工具所使用的库。正则表达式的第一个实用应用程序即为Unix中的QED编辑器。
近几十年,正则表达式逐渐从模糊而深奥的数学概念,发展成为在计算机各类工具和软件包应用中的主要功能,在各种计算机语言和各类应用领域得到了很大的应用和发展。不仅众多Unix工具支持正则表达式,在WIndows的阵营下,正则表达式的思想和应用在大部分Windows开发者工具包中也得到支持和嵌入应用。如今,Windows系列产品对正则表达式的支持发展到无与伦比的程度,几乎所有Microsoft开发者和所有.NET语言都可以使用正则表达式。主流操作系统、主流的开发语言(PHP、C#、Java、C++、VB、Javascript、Rubby等)、各种应用软件,都支持正则表达式。
2 概念
正则表达式是一种语言,它可以明确描述文本字符串中的模式,它由一些普通字符和一些元字符组成。普通字符包括大小写的字母和数字,元字符是一些具有特殊含义的字符。一个正则表达式就是用某种模式去匹配一类字符串的公式。要使用正则表达式解决实际问题,不仅需要能够读懂别人写的表达式,还需要学习构造合适的表达式。
3 构造正则表达式
3.1 元字符
要想真正地用好、构造好正则表达式,需要正确地理解元字符,如表1所示。
3.5 替换
正则表达式里的替换指的是有几种规则,如果满足其中任意一种规则都应该看做匹配,用“|”把不同的规则分隔开。使用替换时顺序非常重要,匹配替换时,从左向右测试每个分枝条件,如果满足了某个分枝的条件,就不去继续测试其他条件了。
实例:d{5}-d{4}|d{5}匹配5位数字或用“-”间隔的9位数字。
d{5}|d{5}-d{4}匹配5位数字和9位数字的前5位。
3.6 反向引用
用小括号来指定子表达式后,匹配这个子表达式的文本即此分组捕获的内容。反向引用用于重复搜索前面某个分组匹配的文本。每个分组会自动拥有一个组号,组号的规则是:从左向右,以分组的左括号为标志,第一个出现的分组组号为1,第二个为2,以此类推。反向引用除了自动给组号,还可以指定表达式的组号(组名)。语法是:(?
实例:匹配重复的单词
3.7 零宽断言
像b、^、$等用于指定一个位置,该位置应该满足一定的条件(断言),它们也被称为零宽断言。它又分两种情况:(?=exp)零宽度正预测先行断言,它断言自身出现位置的后面能匹配表达式exp;(?<=exp)零宽度正回顾后发断言,它断言自身出现位置的前面能匹配表达式exp。
实例:bw+(?=ingb)匹配ing结尾的单词的前面部分,不含ing。
3.8 负向零宽断言
它也分两种情况:(?!exp)零宽度负预测先行断言,它断言此位置的后面不能匹配表达式exp;(?
实例:d{5}(?!d)匹配5位数字,并且这5位数字后面不能是数字。
3.9 贪婪与懒惰
贪婪指在匹配时匹配尽可能多的字符。懒惰指匹配尽可能少的字符,后面需要加“?”。
实例:a.*?b匹配“aabab”时只匹配到“aab”就结束。
4 正则表达式的应用
纵观正则表达式的发展过程,可以看到它已经从最开始的对字符的处理发展到现在的方方面面的应用领域。我们可以用它来描述字符串中的模式、用来遍历匹配、用来将字符串按照某种模式解析为需要的子字符串、以智能方式替换文本或重新设置文本格式等等。在此基础上还可以用正则表达式来解决一些实际问题,可以用它来验证数据的有效性、合法性,例如验证用户密码、提取EML地址、分析Internet URL、验证电话号码、验证身份证、进行文字种类识别、在网站制作中限制表单输入等等,用正则表达式来解决与文本相关的问题有效、简洁并且高效。
在研制的《多文种自动识别系统》的项目中,多次使用正则表达式解决了实际问题,现举例如下:
实例1:通过构造正则表达式构造各文种字典,来进行模式匹配,判定文种类型。
匹配中文的正则表达式:
匹配英文的正则表达式:
实例2:抽取网页内容后过滤html格式字符,也可以用正则表达式来匹配过滤。
过滤超文本链接的内容:
5 结语
对于没有使用过正则表达式的人而言,正则表达式可能是晦涩难懂的。当试着去了解它时,会觉得正则表达式无非是一些遵循一定语法要求的字符组成的公式,入门似乎很简单。但是当把正则表达式的应用从低层次的对字符串的各种处理、验证数据有效性上升到利用它来掌握、控制数据并使之服务解决一些实际问题的高层次的时候,就会发现想要随心所欲地构造出适合的准确的表达式,并不是一件容易的事情,这需要深刻地理解,并更加深入地学习它而且要求有相当的经验的积累。想要把正则表达式的作用和灵活性发挥到极致,就要和它做最亲密的接触,这也正是它的魅力所在。
参考文献
[1][美]Jeffrey E.F.Friedl Mastering Regular Expressions,3rdEdition,电子工业出版社.
正则表达式 篇2
正则表达式是一种可以用于模式匹配和替换的强有力的工具
正则表达式使用详解
简介
简单的说，正则表达式是一种可以用于模式匹配和替换的强有力的工具，其作用如下：
测试字符串的某个模式。例如，可以对一个输入字符串进行测试，看在该字符串是否存在一个电话号码模式或一个信用卡号码模式。这称为数据有效性验证。
替换文本。可以在文档中使用一个正则表达式来标识特定文字，然后可以全部将其删除，或者替换为别的文字。
根据模式匹配从字符串中提取一个子字符串。可以用来在文本或输入字段中查找特定文字。
基本语法
在对正则表达式的功能和作用有了初步的了解之后，我们就来具体看一下正则表达式的语法格式。
正则表达式的形式一般如下：
/love/其中位于“/”定界符之间的部分就是将要在目标对象中进行匹配的模式。用户只要把希望查找匹配对象的模式内容放入“/”定界符之间即可。为了能够使用户更加灵活的定制模式内容，正则表达式提供了专门的“元字符”。所谓元字符就是指那些在正则表达式中具有特殊意义的专用字符，可以用来规定其前导字符(即位于元字符前面的字符)在目标对象中的出现模式。
较为常用的元字符包括： “+”， “*”，以及 “?”。
“+”元字符规定其前导字符必须在目标对象中连续出现一次或多次。
“*”元字符规定其前导字符必须在目标对象中出现零次或连续多次。
“?”元字符规定其前导对象必须在目标对象中连续出现零次或一次。
下面，就让我们来看一下正则表达式元字符的具体应用。
/fo+/因为上述正则表达式中包含“+”元字符，表示可以与目标对象中的 “fool”, “fo”, 或者 “football”等在字母f后面连续出现一个或多个字母o的字符串相匹配。
/eg*/因为上述正则表达式中包含“*”元字符，表示可以与目标对象中的 “easy”, “ego”, 或者 “egg”等在字母e后面连续出现零个或多个字母g的字符串相匹配。
/Wil?/因为上述正则表达式中包含“?”元字符，表示可以与目标对象中的 “Win”, 或者“Wilson”,等在字母i后面连续出现零个或一个字母l的字符串相匹配。
有时候不知道要匹配多少字符。为了能适应这种不确定性，正则表达式支持限定符的概念。这些限定符可以指定正则表达式的一个给定组件必须要出现多少次才能满足匹配。
{n} n 是一个非负整数。匹配确定的 n 次。例如，‘o{2}‘ 不能匹配 “Bob” 中的 ‘o‘，但是能匹配 “food” 中的两个 o。
{n,} n 是一个非负整数。至少匹配 n 次。例如，‘o{2,}‘ 不能匹配 “Bob” 中的 ‘o‘，但能匹配 “foooood” 中的所有 o。‘o{1,}‘ 等价于 ‘o+‘。‘o{0,}‘ 则等价于 ‘o*‘。
{n,m} m 和 n 均为非负整数，其中n <= m。最少匹配 n 次且最多匹配 m 次。例如，“o{1,3}” 将匹配 “fooooood” 中的前三个 o。‘o{0,1}‘ 等价于 ‘o?‘。请注意在逗号和两个数之间不能有空格。
除了元字符之外，用户还可以精确指定模式在匹配对象中出现的频率。例如，/jim {2,6}/ 上述正则表达式规定字符m可以在匹配对象中连续出现2-6次，因此，上述正则表达式可以同jimmy或jimmmmmy等字符串相匹配。
在对如何使用正则表达式有了初步了解之后，我们来看一下其它几个重要的元字符的使用方式。
s：用于匹配单个空格符，包括tab键和换行符;
S：用于匹配除单个空格符之外的所有字符;
d：用于匹配从0到9的数字;
w：用于匹配字母，数字或下划线字符;
W：用于匹配所有与w不匹配的字符;
. ：用于匹配除换行符之外的所有字符。
(说明：我们可以把s和S以及w和W看作互为逆运算)
下面，我们就通过实例看一下如何在正则表达式中使用上述元字符。
/s+/ 上述正则表达式可以用于匹配目标对象中的一个或多个空格字符。
/d000/ 如果我们手中有一份复杂的财务报表，那么我们可以通过上述正则表达式轻而易举的查找到所有总额达千元的款项。
除了我们以上所介绍的元字符之外，正则表达式中还具有另外一种较为独特的专用字符，即定位符。定位符用于规定匹配模式在目标对象中的出现位置。 较为常用的定位符包括： “^”, “$”, “” 以及 “B”。
“^”定位符规定匹配模式必须出现在目标字符串的开头
“$”定位符规定匹配模式必须出现在目标对象的结尾
“”定位符规定匹配模式必须出现在目标字符串的开头或结尾的两个边界之一
“B”定位符则规定匹配对象必须位于目标字符串的开头和结尾两个边界之内，
即匹配对象既不能作为目标字符串的开头，也不能作为目标字符串的结尾，
同样，我们也可以把“^”和“$”以及“”和“B”看作是互为逆运算的两组定位符。举例来说： /^hell/ 因为上述正则表达式中包含“^”定位符，所以可以与目标对象中以 “hell”, “hello”或“hellhound”开头的字符串相匹配。 /ar$/ 因为上述正则表达式中包含“$”定位符，所以可以与目标对象中以 “car”, “bar”或 “ar” 结尾的字符串相匹配。 /bom/ 因为上述正则表达式模式以“”定位符开头，所以可以与目标对象中以 “bomb”, 或 “bom”开头的字符串相匹配。/man/ 因为上述正则表达式模式以“”定位符结尾，所以可以与目标对象中以 “human”, “woman”或 “man”结尾的字符串相匹配。
为了能够方便用户更加灵活的设定匹配模式，正则表达式允许使用者在匹配模式中指定某一个范围而不局限于具体的字符。例如：
/[A-Z]/上述正则表达式将会与从A到Z范围内任何一个大写字母相匹配。
/[a-z]/上述正则表达式将会与从a到z范围内任何一个小写字母相匹配。
/[0-9]/ 上述正则表达式将会与从0到9范围内任何一个数字相匹配。
/([a-z][A-Z][0-9])+/ 上述正则表达式将会与任何由字母和数字组成的字符串，如 “aB0” 等相匹配。
这里需要提醒用户注意的一点就是可以在正则表达式中使用 “” 把字符串组合在一起。“()”符号包含的内容必须同时出现在目标对象中。因此，上述正则表达式将无法与诸如 “abc”等的字符串匹配，因为“abc”中的最后一个字符为字母而非数字。
如果我们希望在正则表达式中实现类似编程逻辑中的“或”运算，在多个不同的模式中任选一个进行匹配的话，可以使用管道符 “|”。例如：/to|too|2/ 上述正则表达式将会与目标对象中的 “to”, “too”, 或 “2” 相匹配。
正则表达式中还有一个较为常用的运算符，即否定符 “[^]”。与我们前文所介绍的定位符 “^” 不同，否定符 “[^]”规定目标对象中不能存在模式中所规定的字符串。例如：/[^A-C]/ 上述字符串将会与目标对象中除A，B，和C之外的任何字符相匹配。一般来说，当“^”出现在 “[]”内时就被视做否定运算符;而当“^”位于“[]”之外，或没有“[]”时，则应当被视做定位符。
最后，当用户需要在正则表达式的模式中加入元字符，并查找其匹配对象时，可以使用转义符“”。例如：/Th*/ 上述正则表达式将会与目标对象中的“Th*”而非“The”等相匹配。
在构造正则表达式之后，就可以象数学表达式一样来求值，也就是说，可以从左至右并按照一个优先级顺序来求值。优先级如下：
1. 转义符
2.(), (?:), (?=), [] 圆括号和方括号
3.*, +, ?, {n}, {n,}, {n,m} 限定符
4.^, $, anymetacharacter 位置和顺序
5.|“或”操作
使用实例
在JavaScript. 1.2中带有一个功能强大的RegExp()对象，可以用来进行正则表达式的匹配操作。其中的test()方法可以检验目标对象中是否包含匹配模式，并相应的返回true或false。
我们可以使用JavaScript编写以下脚本，验证用户输入的邮件地址的有效性。
正则表达式对象
本对象包含正则表达式模式以及表明如何应用模式的标志。
语法 1 re = /pattern/[flags]
语法 2 re = new RegExp(“pattern”,[“flags”])
参数
re
必选项。将要赋值为正则表达式模式的变量名。
Pattern
必选项。要使用的正则表达式模式。如果使用语法 1，用 “/” 字符分隔模式。如果用语法 2，用引号将模式引起来。
Flags
可选项。如果使用语法 2 要用引号将 flag 引起来。标志可以组合使用，可用的有：
g (全文查找出现的所有 pattern)
i (忽略大小写)
m (多行查找)
示例
下面的示例创建一个包含正则表达式模式及相关标志的对象(re)，向您演示正则表达式对象的用法。在本例中，作为结果的正则表达式对象又用于 match 方法中：
代码如下:
function MatchDemo()
{
var r, re; // 声明变量。
var s = “The rain in Spain falls mainly in the plain”;
re = new RegExp(“ain”,“g”); // 创建正则表达式对象。
r = s.match(re); // 在字符串 s 中查找匹配。
return(r);
}
Python正则表达式研究 篇3
1.1 基本概念
正则表达式 (Regular Expression), 又称正规表示法、常规表示法, 在代码中常简写为regex、regexp或RE。正则表达式是对字符串操作的一种逻辑公式, 就是用事先定义好的一些特定字符及 这些特定 字符的组 合 , 组成一个 “规则字符 串”,这个“规则字符串”用来表达对字符串的一种过滤逻辑。
给定一个正则表达式和另一个字符串, 可以达到如下的目的:
(1) 给定的字符串是否符合正则表达式的过滤逻辑 ( 称作“匹配”)。
(2) 可以通过正则表达式 , 从字符串中获取我们想要的特定部分。
1.2 正则表达式的特点
(1) 灵活性、逻辑性和功能性非常强。
(2) 可以迅速地用极简单的方式表示复杂的字符串。
(3) 对于刚接触的人来说 , 比较晦涩难懂。
(4) 常用来匹配或提取一些特征字符串。
1.3 正则表达式定义
正则表达式由一些普通字符 (literal characters) 和一些元字符 (meta characters) 组成。普通字符包 括大小写 的字母、数字和可打印的符号, 而元字符则具有特殊的含义。
1.4 正则表达式的结构
Anchors Character-Sets Modifiers
Python处理正则表达式的模块是re模块。
1.4.1 锚定符
如表1所示。
1.4.2 字符集由普通字符和元字符组成
如表2所示。
1.4.3 修饰符
由普通字符和元字符组成, 非贪婪匹配, *?+?, 如表3所示。
2 Python 正则表达式
主要介绍Python中常用的正则表达式处理函数。Python处理正则表达式的模块是re, 要使用正则表达式, 需要先import re模块。
Python中处理正 则匹配最 常见的函 数是match和search函数。
2.1 match 函数
re.match尝试从字符串的开始匹配一个模式。
函数语法:
re.match (pattern, string, flags=0)
函数参数说明如表4所示。
匹配成功则match函数返回一个匹配的正则对象, 否则返回None。
2.2 search 函数
re.search尝试从字符串中匹配一个模式。函数语法:
函数语法:
re.search (pattern, string, flags=0)
函数参数含义和match类似。
2.3 案例
输出:
2.4 re.match 与 re.search 的区别
re.match从字符串开始起匹配指定正则表达式, 如果字符串开始不符合正则表达式, 则匹配失败, 函数返回None; 而re.search从字符串开始匹配正则表达式, 直至找到一个尽可能的匹配。
2.5 正则表达式分组
可以使用group (num) 或groups() 匹配对象函数来获取匹配表达式, 如表5所示。
以上实例执行结果如下:
3 正则表达式实例
如表6所示。
4 结语
研究了正则表达式的基本概念和在Ptyhon中的常用函数,随后结合实际例子演示了Python的正则表达式使用, 从研究可以看到正则表达式在文本匹配和文本抽取方面有着强大的功能, 在实际工作中如匹配用户邮箱或手机号, 抽取网页内容等领域有着广泛的应用。
摘要：研究了正则表达式的基本概念、定义及其元字符,讲解Python中正则表达式的常用函数和使用实例,并做了简单对比,分析了正则分组的概念并利用分组进行实际的正则匹配结果抽取。
asp 电话号码正则表达式 篇4
<%
' 判断电话号码是否正确
Function IsValidTel(para)
Dim Str
Dim l, i
If IsNull(para) Then
IsValidTel = false
Exit Function
End If
Str = CStr(para)
If Len(Trim(Str))<7 Then
IsValidTel = false
Exit Function
End If
l = Len(Str)
For i = 1 To l
If Not (Mid(Str, i, 1)>= ”0“ And Mid(Str, i, 1)<= ”9“ Or Mid(Str, i, 1) = ”-“) Then
IsValidTel = false
Exit Function
End If
Next
IsValidTel = true
End Function
正则表达式 篇5
正则表达式是由一系列特殊字符和普通字符组成的字符集合，其中每个特殊字符都被称为元字符，这些元字符并不表示它们字面上的含义，而会被解释为一些特定的含义。正则表达式的大致匹配过程是：依次拿出正则表达式和文本中的字符比较，如果每一个字符都能匹配，则匹配成功；一旦有匹配不成功的字符则匹配失败。
许多程序设计语言都支持利用正则表达式进行字符串操作。Python自1.5版本起增加了re模块，它提供Perl风格的正则表达式模式。re模块使Python语言拥有全部的正则表达式功能。
2 正则表达式基本概念
2.1 正则表达式
正则表达式由一些普通字符(literal characters)和一些元字符（meta characters）组成。普通字符包括大小写的字母、数字和可打印的符号，而元字符则是具有特殊含义的字符，具备比普通字符更强的表达能力。
2.2 通配符
在linux/unix下面有通配符的概念，通常用来模糊匹配文件名，主要的通配符有*和？
2.3 正则表达式的结构
正则表达式结构为：锚定符字符集修饰符
锚定符如下：
字符集由普通字符和元字符组成，元字符是一些有特殊含义的字符，如下：
修饰符是一些量词，用来表示在前面的字符或字符集出现的次数，如下：
2.4 正则表达式和通配符区别
正则表达式表示满足某一个模式的字符串集合，包含通配符的字符串也表示一定规则的集合，差别主要在于元字符*和?表示的含义有较大差别。
在正则表达式中，*和？都是量词，用来修饰之前的字符出现的次数，而在通配符中，*和？不仅是量词，也表示任意字符，具体的例子是：
通配符中的*和正则表达式中的.*等价，正则匹配时也需要带上re.S标记，表示匹配任何字符（包括换行）。
3 正则表达式应用场景
正则表达式的常用场合有如下3种：
测试字符串的某个模式。例如，可以对一个输入字符串进行测试，看在该字符串是否存在一个电话号码模式或一个信用卡号码模式。这称为数据有效性验证。
文本替换。可以在文档中使用一个正则表达式来标识特定文字，然后可以全部将其删除，或者替换为别的文字。
根据模式匹配从字符串中提取一个子字符串。可以用来在文本或输入字段中查找特定文字。
4 正则表达式高级特性
正则表达式有无命名组和命名分组2种情况。
无名分组是由一对小括号括起来的子正则表达式。如下面例子中的(d+):
匹配结果：
groups返回所有的分组组成的list，也可以用group(num)来获得匹配的分组内容，num表示匹配的分组序号，从1开始，第一个为第一个（）分组
命名分组由?P<…>表示，(?P'代表这是一个Python的语法扩展'<…>'里面是你给这个组起的名字，如可以给一个全部由字母和数字组成的组叫做'name'，它的形式就是'(?P<name>w+)'。
起了名字之后，我们就可以在后面的正则式中通过名字调用这个组，它的形式是
(?P=name)'调用已匹配的命名组，注意的是，再次调用的这个组是已被匹配的组，也就是说它里面的内容是和前面命名组里的内容是一样的。
例子1：匹配超链中的文本
匹配结果：google
说明：<a.*?>表示匹配标签<a>标签，a标签可以有任意合法属性，然后(.*)表示匹配超链的文本。
例子2：命名分组例子
说明：(<?P<text>.*)表示一个命名分组，分组名是text，在正则匹配成功后可以通过
m.group(‘text’),text为分组的名称。
后向引用有无名引用和有名引用2种情况。
如需要匹配连续的3个go或ha字符串
有4种断言，我们通过例子来看这几种断言的应用。
如希望找出C语言的注释中的内容，它们是包含在''之间，不过并不希望匹配的结果把''也包括进来，那么可以这样用：
如希望匹配不以数字开头且不以txt结尾的文件名：
5 结语
正则表达式语法简单，功能强大，在日常的文本匹配、替换、解析中有很大的作用，而且各种语言对正则表达式都有很好的支持，掌握正则表达式的基本语法和用法，能大大提高了处理字符串和文本的效率，随着技术的发展，正则表达式的应用领域和功能也会越来越强大。
摘要：介绍了正则表达式的基本概念和语法,并重点讲解了Python中正则表达式的一些高级特性分组,数据抽取,后向引用等。
基于正则表达式的协议识别方案 篇6
在进行协议分析之前, 需要对应用层协议进行识别。传统的协议识别技术是端口识别, 这种识别具有较高的效率, 但是现在大量的应用层协议为了避免识别, 逃避防火墙的检查, 使用随机端口进行通信。如这几年出现的P2P协议, 其采用动态端口。还有一种是使用特征字符串进行协议识别的技术, 统计协议以实际交互过程中出现频率高的字符串作为匹配串, 检查全报文以匹配多个串, 往往适用于少量协议, 效率较低, 且其正确性有待提高。
1 动态应用层协议识别架构
动态应用层协议识别的基本思想是:每个应用层服务都有相应的可标识的特征字符串集合 (也可称作模式集合) , 可以将应用层的内容和事先定义好的应用层协议特征字符串集合进行匹配, 如果匹配成功就说明这个数据包属于某种协议。这里采用模块化思想将整个识别过程作为一个整体模块, 称为协议识别模块 (Protocol Identification Module:PIM) , 它由两部分组成:模式匹配单元和由正则表达式表示的特征码字符串集合, 如图1所示。
2 基于正则表达式的应用层协议识别算法
2.1 正则表达式的匹配
正则表达式 (regular expression) 描述了一种字符串匹配的模式, 可以用来检查一个串是否含有某个子串、将匹配的子串做替换或者从某个串中取出符合某个条件的子串等。
NFA因为不确定, 所以限制比DFA要少, 构造起来也比较方便一点, 但匹配速度较慢, 而DFA依次匹配并记录匹配过程中每个字符的位置, 因此每个字符最多被匹配一次, 其匹配速度比NFA要高许多。虽然要把正则表达式先转化为NFA, 再把NFA转换为DFA, 其转换时间相对要长, 但是只需在匹配报文前对正则表达式编译一次, 因此匹配报文的总体时间要比NFA的匹配引擎快很多。
针对NFA匹配速度较慢的情况, 本文采用了经典的Thompson算法构造不同的NFA;接着运用经典的子集构造算法, 将NFA转化成DFA;进而提出一种最优DFA状态数的算法, 该算法保证在任意有限的系统资源下时间复杂度最小;最后通过比较三种匹配方式, 并且和One-Pass扫描算法相结合, 选择一种最佳匹配方式。整个过程分为5步, 如图2所示。
2.2 正则表达式构造NFA
非确定有限状态自动机NFA (Deterministic Finite Automaton) 是由下述5个元素构成的数学模型: (S, Σ, δ, S0, F) 。其中:S是有限的, 非空的状态集;Σ是输入字母表;δ是转移函数。Σ (s, a) =S’意味着:当现行状态为s、输入字符为a时, 将换到下一个状态S’, 我们称S’为s的后继状态;S0∈S是初始状态;FS是终结状态集。
从正则表达式构造等同的NFA, 经典的算法是Thompson构造法。该构造法的基本思想是利用ε-转换将正则表达式的机器片段“粘在一起”, 以构造与整个表达式相对应的机器。因此该结构是归纳的, 而且它依照正则表达式定义的结构。
2.3 NFA转换为DFA
将NFA转换为DFA采用最小子集构造算法, 假定M= (S, Σ, δ, S0, F) , 最小子集构造算法主要步骤为: (1) 定义状态集合I的ε-闭包 (ε-clousure (I) ) 为状态集合I中的任何状态S经过任意多条ε弧而能到达的状态集合; (2) 状态集合I的a弧转换 (move (I, a) ) :定义为状态集合J, 其中J是所有那些可以从I的某一状态经过一条a弧而到达的状态的全体; (3) 定义Ia=ε-clousure (J) :其中I为某个状态集合, J为状态集合I的a弧转换move (I, a) , 也就是说, 从某一个状态集合中的任何一个状态S, 经过一条a弧, 再经过任意多条ε弧所能到达的状态的全体为Ia; (4) 由初始结点出发, 找出其闭包构成的集合ε-clousure ({S0}) 作为初始集合, 作为矩阵的第1行第1列, 依次求出集合Ia, 作为第1行第2列, 有穷输入集Σ中的每一个输入字符的Ix依次对应一列。如果这些集合未出现过, 则把这些集合作为下一个初始集合, 即下一行的第1列, 依次找出Ia, 作为第2列, 依次类推得出一个状态转换矩阵。对矩阵中的所有状态子集重新命名后, 即得出DFA的状态转换矩阵。
2.4 最优DFA状态数算法
2.4.1 存在的问题
对于给定的正则表达式集合, 将集合中的所有正则表达式构造一个DFA, 可以达到最快的匹配速度。然而一般而言, 多个模式对应一个DFA的状态数要远远大于一个模式对应一个DFA状态数的总和。由于对任一个正则表达式, 都能够用一个状态有限的DFA来表示, DFA占据的内存量的大小, 取决于状态的数量和每个状态的转换的数量的乘积 (为了表述方便, 下面内存的大小按照状态数来衡量) 。因此上述表述也可以理解为:多个模式对应一个DFA所需内存要远远大于一个模式对应一个DFA所需内存的总和。
2.4.2 算法描述
设在有限的系统资源下, m个模式集合为{P1P2…Pm}, 每个模式对应DFA的状态数用Dpi表示;m个模式组合成一个DFA, 对应的状态数用Dm表示;根据DFA状态数增长, 在有限的系统资源下, 为了达到最小时间复杂度的目的, 将m个模式构造成k个DFA, 用{R1R2…Rk}表示, 每个DFA对应的状态数表示为DRi, 中间状态数表示为Dtmp Ri, 内存大小用ME表示。
本算法分为3个部分, 具体算法如下:
(1) 构造图。输入集合{P1P2…Pm}中的每个模式Pi, 通过词法分析器Flex可以得到给定模式生成DFA的状态数Dpi, 将模式集合{P1P2…Pm}两两做为一组, 即对任意的PiPj构造DFA, 计算其状态数Dpij。将Dpi, Dpij保存在数组S[m][n]中, 其中Dpi存放在S[i][i]中, Dpij保存在S[i][i]中 (S[j][i]与S[i][j]的值相同) 。根据若两个模式构造的DFA状态数大于其分别构造DFA状态数之和, 那么两个模式, 即图中的两点之间存在一条边。即计算S[i][j]是否大于S[i][i]与S[j][j]之和, 若成立, 那么图Graph[i][j]=1, 同时Graph[j][i]=1;若不成立, Graph[i][j]=0, Graph[j][i]=0.其中m个模式对应图中的m个定点。
(2) 构造{R1R2…Rk}。步骤一:开始构造集合{R1R2…Rk}。根据图Graph, 查找图中度数最小的点t, 加入Ri, tmp Ri (为计算方便, 保存中间状态的集合) 中, 作为模式集合Ri中的一员, 并在图中去掉t, 同时将可用内存变更为ME=ME-Dpt;步骤二:在图中剩余的点里查找和当前Ri中的点连接最少的点j加入tmp Ri, 比较即需要比较将模式j加入到模式集合Ri中是否会引起内存的迅速增加, 若成立那么Ri构造结束, 进行步骤三;若不成立, 那么将点j, 加入到Ri, tmp Ri中。然后判断图中是否还有点存在, 若有返回步骤二;若无, 将可用内存变更为ME=ME-DRi+Dpt, 并在图中去掉点j。转到步骤三;步骤三:计算图中剩余点的度数和, 若度数和>1即图中存在边, 那么返回步骤二, 对Ri+1进行构造;若度数之和等于0, 即剩余的点为孤立点, 或图中已无剩余点, 那么进行第三部分的计算。
(3) 对构造的模式集合{R1R2…Rk}进行最后的处理。判断图中是否已无点剩余, 若是, {R1R2…Rk}构造结束;若否, 对图中剩余的点进行新的构造。首先判断剩余的点即剩余的模式构造成一个DFA是否超过当前内存的限制, 若否, 那么将剩余的模式构造成一个DFA, 完成{R1R2…Rk}的计算;若是, 将剩余点 (即模式) 中的一个单独构造一个DFA, Rs, s
2.5 匹配方式和One-Pass扫描
当报文到达后, 采用何种方式送入匹配引擎对匹配速度和精确度都有较大的影响, 下面对常用的3种匹配方式进行比较。
(1) 单报文匹配。一个数据流的每个报文到达时都提取其应用层数据送入匹配引擎进行匹配, 直到匹配成功, 则后续报文不再送去匹配。这种匹配方式匹配速度快, 而且正确性高。
(2) 多报文叠加匹配。第一个报文到来时, 提取其应用层数据进行匹配, 如果未匹配上, 则当第二个报文到来时, 把第一个和第二个报文的数据结合起来再一起匹配, 依次进行下去, 每个报文都和前面所有报文的内容结合起来一起取匹配。这种匹配方式正确性很高, 但是匹配速度很慢。
(3) 报文一次性匹配。存储一个数据流已到达的报文, 直到其报文到达一定数目, 再一起送去匹配, 如匹配, 则后续报文无需再送去匹配, 否则表示这个数据流无法识别。这种匹配方式有利于跨报文的匹配, 而且避免了多报文叠加匹配方式对同一数据流报文的多次匹配, 节省了匹配时间, 一次性完成匹配, 提高了速度。但缓存报文个数的选取直影响匹配效果, 选取有一定难度。
本文采用的是DFA匹配引擎, 在DFA下有两种匹配扫描算法:Repeated Scan算法和One-Pass Scan算法。Repeated Scan算法主要用于语言解析过程中, 处理报文内容时速度很慢, One-Pass Scan算法只扫描一次, 随着输入从开始到结束, DFA可以在输入的任何位置识别模式, 而无需重复扫描, 对未识别的数据流, 从当前位置而不是初始状态继续匹配。对单报文匹配方式, 如果需要跨报文识别的协议, 采用One-Pass Scan算法可以增加其正确性;对于多报文叠加匹配方式, 则可以提高其匹配速度。因此, 本文选择的是One-Pass Scan算法, 判断每一个数据流前p Num个报文, 通过一次扫描就能确定报文所属的协议。具体算法描述如下:
3 结束语
传统的L7-filter应用层协议识别方法采用的是非确定有限状态自动机NFA匹配引擎。本文将NFA匹配改为DFA匹配, 大大改善了匹配效率。并且针对模式数量和模式中的匹配符对DFA状态数的影响, 提出一种构造最优DFA状态数的算法, 实验表明此算法具有最小的时间复杂度和空间复杂度。将单报文匹配方式One-Pass扫描算法相结合, 能够得到更好的匹配性能和匹配精确度。从上面的分析可知, 此方案可以很好地应用在入侵检测系统中, 通过随后的应用层协议分析, 能够进行内容级的深度检测。
参考文献
[1]周华先, 王伟平.基于Linux下L7-filter模块的P2P流量控制[J].湖南科技学院学报, 2008 (4) .
[2]Holger Dreger, Anja Feldmann, Michael Mai, Vern Paxson, Robin Sommer.Dynamic Application-Layer Protocol Analysis for Network Intrusion Detection[J].15th USENIX Security Symposium, 2006 (15) .
[3]Alfred V.Aho, Ravi Sethi, Jeffrey D.Ullman, Compilers:principles, techniques, and tools[M].Addison-Wesley, 1986.
[4]正则表达式参考文档[R].http://www.regexlab.com/zh/regref.htm.
[5]邓超成.正规文法、NFA、DFA、状态转换图、正规式之间的等价变换关系及变换方法[J].四川师范大学学报 (自然科学版) , 1997 (2) .
[6]Jean-Paul Tremblay, Paul G.Sorenson, The theory and practice of compiler writing[M].McGraw-Hill, 1985.
正则表达式 篇7
在深度报文检测技术上,经典的字符串匹配算法有单模式匹配的KMP和BM算法,改进的多模式匹配的AC算法、CM算法、WANG方法和Wu-Manber算法,然而这些算法都采用字符串匹配为基础。随着网络的不断发展,应用软件特征字符识别的复杂度越来越大,采用字符串匹配已难以匹配识别,因此这些算法的局限性也凸显出来。基于正则表达式的多模式匹配具备了优越的表达匹配能力和灵活性,相比传统的字符串匹配更加精确高效。
基于正则表达式的多模式匹配是把正则表达式转变为自动机,自动机分为两种:非确定有限自动机(NFA)和确定有限自动机(DFA)。NFA的优点是占用内存和系统资源少,但是需要对每个字符进行遍历,处理状态集里的所有状态,很耗费时间。如good(day|night|evening):若要搜goodday,NFA需要把goodday、goodnight、goodevening全部遍历一次才能完成搜索。相比之下,DFA搜索一个字符只需要访问一个状态,但是若把所有的正则表达式都转变为DFA将会占用非常大的系统内存资源,目前的硬件条件还无法满足这一点。
结合NFA和DFA各自的优缺点,本文提出了一种猜测-分组-检验的匹配算法。使用DFA在猜测的基础上添加分组,能够更有效减少系统内存占用率;然后再结合NFA检测确保算法具备高匹配度。
1 正则表达式相关算法
深度报文包检测技术是基于系统规则库对在网络中捕获的数据包中的每一个字节进行扫描和识别,标准的字符串匹配算法有:Aho-Corasiek[1]、Coment Z-Walter[2]和Wu-Manber[3]算法。如今随着网络协议复杂度日益增加,传统的字符串匹配算法难以精确地识别出复杂多变的协议类型[4]。
SOMMER R和PAXSON V[5]认为,用正则表达式描述网络中数据协议行为比用字符串表达更为高效、灵活。KUMAR S[6]等通过将DFA的某些状态用单条缺省边来代替,提出一种称为延迟输入DFA,实验结果表明,相比于传统的DFA存储空间可减少95%以上。但是引入缺省边导致处理一个字符需要多次访问内存,参考文献[7]对参考文献[6]进行改进,提出一种目录寻址的D2FA-CD2FA,用包含部分状态信息的目录标签来代替状态的ID,而这些信息一般是保存在状态表的条目中,使得一次转移只消耗一个字符。
YU F等人提出了将正则表达式进行分组的思想[8]。其方法是:计算正则表达式两两之间是否引起状态增长,在进行分组时,选择一条与其他表达式具有最小相关度的正则表达式开始,然后按照相同的原则向这个组里不断添加,直到这个组形成的DFA内存超过预先设定的阈值,再开始创建另一个新组。重复这个过程,直到所有的表达式都被分配出去为止。
参考文献[9]提出了一种混合自动机的方法,其基本思想是:将整个规则集编译成一个NFA结构之后,并不对它进行完全的确定化,而是在确定化之前判断状态之间跳转的原因。进行部分确定化的结果就是形成了一个混合的自动机结构,它的前面一部分是DFA的状态,而在每个边界状态之后都带有一个NFA,这个NFA以边界状态作为初始状态。
张树壮等人提出了一种基于猜测-验证的匹配方法[10]:首先使用DFA对正则表达式中的部分子特征进行搜索,完成特征存在性的猜测。当猜测到有可能匹配某个特征后,再使用NFA进行验证。这种方法既充分利用了DFA的高效性,减少了对相对较慢的验证过程,又借助NFA避免了内存消耗过于巨大。
本文在深入研究和分析以上算法的基础上,针对DPI规则库这样十分庞大的规则系统,借鉴一些经典正则表达式匹配算法,提出一种猜测-分组-检验算法。该算法把分组作为核心步骤,利用正则表达式之间的相关性组合后进行分组,能够十分有效地降低系统内存资源的使用率。结合NFA验证,该算法能够对输入进行有效的匹配和识别。
2 算法描述
正则表达式匹配算法分为三个步骤:猜测、分组和检验。总体来说,在安全监控中所使用的规则一般都可以分为若干个特征子块Sub-feature,如图1所示,每个子特征之间通过正则表达式运算符连接在一起。获取到这些特征子块之后,可以简单地把它们合并转换为一个DFA。然而这样一个DPI的规则库,将会占用十分庞大的系统内存资源。所以在获得特征子块后,需要采用相似性度分析对这些子块进行分组,把相似程度高的子块聚合在一起,并通过子集构造法转换为一个DFA,再通过正则运算符把各个组的DFA连接在一起。分组后的DFA占用系统内存资源小,可以有效减少空间使用率,进而提高资源的有效利用率。若某个输入与猜测选择出的特征子块匹配,则把输入进行NFA验证,验证方法是基于DPI库中的每条规则转变为NFA得到的。
2.1 猜测
在面向网络数据流匹配的基础上,安全监控中使用的规则可以明显地分为若干个部分(Sub-feature)。首先从系统规则库保留的某条规则中还原出Sub-feature,然后以Sub-feature的出现为依据猜测输入是否与某些规则匹配。在本文中,根据规则库每条规则中某段字符串出现的概率来选取Sub-feature进行输入猜测。
2.2 分组
若正则表达式两两之间具有相似性(这里的相似性定义为:当正则表达式单独转换为DFA所需要的状态数大于正则表达式联合在一起转换为DFA所需要的状态数,那么称正则表达式具备相似性),则它们联合在一起转变为DFA所需要的状态数小于其单独转换所需要的状态数总和,这将大大减少占用的系统内存资源。若两个正则表达式具有相似性,例如abde、abdz两个正则表达式,将它们单独转换为DFA,如图2、图3所示,联合起来转换为DFA,如图4所示。结果表明,联合转换需要7个状态,而单独转换共需要10个状态,联合转换比单独转换减少了3个状态。
相似性计算中采用字符串相似性计算法,如式(1)所示:
其中S1和S2分别为代表两个需做比较的正则表达式,ED(S1,S2)是指S1和S2之间编辑距离,max(|S1|,|S2|)是选择两个正则表达式中字符多的一个。若两个正则表达式完全一样,则计算结果为1;若两个正则表达式完全不同,则计算结果为0。式(1)的字符串相似度算法复杂度小、精确度大,采用其进行相似度计算能够有效减少内存消耗并且确保极高的匹配率。
采用上述的相似性计算法将每个Sub-feature进行相似度分析并分组。首先,在所有未分组的Sub-feature中选取一个与其他Sub-feature具有相似性的Sub-feature加入一个新组并记为group0;其次,在所有未处理的Sub-feature中,选取一个与group0中所有Sub-feature具有相似性的Sub-feature加入group0中;然后,重复以上步骤,把相似度低的或者未处理的正则表达式另行分组为group1、group2、group3等。
Sub-feature分组后,对每个组group0、group1、group2及group3等分别进行DFA转换,分组转换后的DFA要比没有分组直接转换DFA所需要的状态数少,有效地降低了系统资源使用率。
2.3 检验
经过上述的猜测和分组过程可以将大部分不满足条件的输入过滤掉,只剩少数数据可以与某条规则中的网络数据流所有特征子块相匹配从而需要进行完整验证过程。因此可以使用速度相对较慢、但内存需求较低的NFA来完成。NFA是通过从特征子块中提取的各条完整规则,经过Thompson构造法转换得到的。该检验方法通过占用系统内存资源不大的NFA来实现,保证了匹配结果的精确性。
为方便描述现定义:S表示规则中所有的正则表达式集合,r为集合中的正则表达式,rk为Sub-feature,Gd表示基于相似度算法分组数:
该算法首先从正则表达式中搜索出Sub-feature作为猜测条件,根据相似性算法函数ES计算所有Subfeature的相似度,并选出相似度大于70%的Sub-feature,储存在分组函数groupi(i=0,1,2,…,d-1)中,共有d个分组。在输入前,通过函数make_DFA、make_NFA生成预处理的DFA和NFA。当有输入时,算法进行匹配,若输入能够满足猜测并与DFA匹配成功,则对输入的完整规则进行NFA匹配。
3 实验结果与分析
正则表达式匹配算法性能是否优越的一个评价标准是系统内存占用率。本实验将猜测-检验算法进行对比和分析。实验采用的正则表达式来自Linux Lay er-7filter(L7)以及snort规则集中常用的Web-misc规则类;并用编译工具在VC上生成NFA和DFA。
实验配置:主机CPU频率2.69 GHz;1.99 GB内存;Window XP操作系统,网络配置器是Realtek RTL81698110 Family Gigabit Ethernet NIC。
实验步骤:(1)在L7和snort规则集中提取出Subfeature;(2)采用式(1)中字符串相似性算法把相似性大于70%的Sub-feature分为一组,实验中对L7和Web-misc类的Sub-feature进行分组;(3)将每组中的正则表达式分别通过编译工具生成DFA,并最终合并为一个DFA;(4)对比猜测-检验算法。
实验结果与分析:表1、表2分别给出了L7和snor中的Web-misc规则采用本文算法与猜测-检验算法所占内存需求对比。由实验结果可以看出,基于L7规则库,猜测-分组-检验算法所占用的内存比猜测-验证算法减少了35%;而基于snort中Web-misc规则库,猜测-分组-检验算法所占用的内存比猜测-验证算法减少了5%,且猜测-分组-检验算法的DFA状态数大幅度小于猜测-验证算法。由此可知,本文所提正则表达式算法能更有效地减少系统内存资源的使用。
本文在深入学习、研究正则表达式和探讨了优化NFA与DFA的基础上,借鉴一些经典的正则表达式匹配算法提出了一种新的面向网络数据流正则表达式匹配算法:猜测-分组-检验算法。这种算法首先使用分组算法对正则表达式中的Sub-feature进行相似性分组,然后完成对输出的特征子块猜测,最后将通过猜测的输出进行完整的NFA检验。算法通过对比猜测-验证算法进行实验分析,验证了该算法具备系统内存资源占用率低和匹配能力强的优点。
参考文献
[1]AHO A V,CORASIEK M J.Effieient string matehing:an aid to bibliographic searerch[J].Communications of the ACM,1975,18(6):333-340.
[2]WALTER B C.A string matching algorithm fast on the average[J].Processing of ICALP,1979,71(7):118-132.
[3]WU S,MANBER U.A fast algorithm for multi-pattern searching[C].Department of Computer Science,1994.
[4]Qi Deyu,Qian Zhengping,Zheng Weipin.Fast dynamic pattern matching for deep packet inspection[C].Proceedings of2008IEEE International Conference on Networking,Sens-ing and Contriol,ICNSC,2008.
[5]SOMMER R,PAXSON V.Elthaneing byte-level network intrusion deteetion signatures with context[C].ACM conf,on Computer and Communication Security,2003.
[6]KUMAR S,DHARMAPURIKAR S,YU F.Algorithms to accel-erate multiple regular expressions matching for deep packet inspection[J].Computer Communication Review,2006,36(4):339-350.
[7]KUMAR S,TUMER J,WILLIAMS J.Advanced algorithmsfor fast and scalable deep packet inspection[C].ACM,2006.
[8]YU F,CHEN Z F,DIAO Y L,et al.Fast and memory-efficient regular expression matching for deep packet inspe-ction[C].In:Proc.of the IEEE/ACM Symp.on Architec-tures for Networking and Communications Systems.San Jose,2006.
[9]BECCHI M,CROWLEY P.A hybrid finite automaton for practical deep packet inspection[C].In:Processing of the ACM CoNEXT2007,2007.
正则表达式 篇8
因特网已经成为人们获取知识的不可或缺的手段,而因特网信息的表现形式大多为半结构化的文本,降低了信息的利用率,经过十几年的发展,形成了以搜索引擎为代表的信息检索技术,初步解决了信息检索问题。人们信息抽取技术就是将获取的信息根据预先定义的模板,从文本抽取特定的信息,形成结构化的数据,帮助对信息内容进行分析和整理,因此信息抽取技术成为网络信息处理中的新的研究热点。
正则表达式是对一类字符串共性描述的规则,提供了一种从字符集合中搜寻特定字符串的机制。本文以抽取电子文档的主要信息为例,介绍了正则表达式及其在信息抽取中的应用。
2 正则表达式
正则表达式由美国数学家Stephen Kleene于1956年提出,主要用于描述正则集代数。随后人们发现可以将此表达式应用于实用Ken Thompson的计算搜索算法的一些早期研究。正则表达式的第一个实用应用程序就是Unix中的qed编辑器。
正则表达式的形式为/匹配模式/,其中位于”/”定界符之间的部分就是将要在目标对象中进行匹配的模式。用户只要把希望查找匹配对象的模式内容放入”/”定界符之间即可。为了能够更加灵活的定制模式内容,正则表达式提供了专门的“元字符”。
所谓元字符就是指那些在正则表达式中具有特殊意义的专用字符,可以用来规定其前导字符(即位于元字符前面的字符)在目标对象中的出现模式。
较为常用的元字符包括:”+”;”*”,以及”?”。其它主要元字符的使用方式如下:s用于匹配单个空格符,包括tab键和换行符;S用于匹配除单个空格符之外的所有字符;d用于匹配从0到9的数字;w用于匹配字母,数字或下划线字符;W用于匹配所有于w不匹配的字符。
在正则表达式中,可以用方括号括起若干个字符来表示一个元字符。除元字符外,正则表达式支持限定符的概念。这些限定符可以指定正则表达式的一个给定组间必须要出现多少词才能满足匹配,因而可以适应不知道要匹配多少字符时的不确定情况。限定符的使用说明如下:
1){n}n是一个非负整数。匹配确定的n次。例如,”o{2}”不能匹配”Bob”中的”o”,但是能匹配”food”中的两个o。
2){n,}n是一个非负整数。至少匹配n次。例如,”o{2}”不能匹配”Bob”中的”o”,但是能匹配”fooooooood”中的所有o。”0{1,}”等价于”o+”,”o{0,}”则等价于”o*”。
3){n,m}m和n均是非负整数,其中n<=m。最少匹配n次且最多匹配m次。例如,
”o{1,3}”将匹配“fooooooood”中的前三个o。“o{0,1}”等价于“o?”
正则表达式的优点是简洁,结构化,它提供了一种从字符集合着那个搜寻特定字符串的机制[2]。它可以让用户通过使用一系列的特殊字符构建匹配模式,然后把匹配模式与数据文件、程序输入等目标对象进行比较,根据目标对象中是否包含匹配模式,执行相应的程序[3]。正则表达式有以下几个主要功能,用于测试字符串的某个模式是否有效。如测试一个字符串是否符合E-mail的模式。替换文本功能,用于在文档中使用匹配模式来标识特定文字,然后将其删除或进行替换。提取子串功能,用于根据模式匹配,从字符串中提取一个子字符串。
3 信息抽取
随着计算机的普及以及互联网(WWW)的迅猛发展,大量的信息以电子文档的形式出现在人们面前。为了应对信息爆炸带来的严重挑战,迫切需要一些自动化的工具帮助人们在海量信息源中迅速找到真正需要的信息。信息抽取(Information Extraction)研究正是在这种背景下产生的。
信息抽取系统的主要功能是从文本中抽取出特定的事实信息(factual information)。比如,从新闻报道中抽取出恐怖事件的详细情况:时间、地点、作案者、受害人、袭击目标、使用的武器等;从经济新闻中抽取出公司发布新产品的情况:公司名、产品名、发布时间、产品性能等;从病人的医疗记录中抽取出症状、诊断记录、检验结果、处方等等。通常,被抽取出来的信息以结构化的形式描述,可以直接存入数据库中,供用户查询以及进一步分析利用。
信息抽取处理的文本可分为三类:非结构化文本、半结构化文本和结构化文档。信息抽取最初目的是从非结构化的普通文本中抽取有限的主要信息。非结构化文本的信息抽取系统通常采用自然语言处理的方法,其抽取规则主要是通过建立在词和词类间句法关系的基础上,需要结合机器学习等人工智能方面的技术对大量的文本进行训练和学习。结构化文本是根据某种约定格式生成的文本。从这样的文本中抽取特定的信息只需按照约定的格式指定规则即可。半结构化文本是一种介于非结构化和结构化文本之间的文本形式,如WEB网页。另,如文本格式的法律条约,专利文献等,看似为非结构化的,但其内容结构都遵循有一定的模式结构,因此也可以看作半结构化的。
4 正则表达式在信息抽取中的应用
对于信息抽取的任务,通常需要抽取的信息只是某一领域中数量有限的事件或关系。本文分别以web网页和文本文档为数据源,介绍了利用正则表达式,对其进行信息抽取。
4.1 正则表达式在web新闻网页中的信息抽取
信息网页是具有很强开发价值的一类网页,它具有时效性强,信息量大、结构稳定、更新快、需求广泛、实用价值高等特点。其中各大门户网站或新闻网站用来提供用户检索新闻之用的新闻页面最具代表性。这类新闻网页包含符合检索条件的若干条新闻记录,可以用来指引用户查阅新闻全文。这类新闻网页其实就是各大网站给自己站内的所有新闻网页编的“索引”,能起到很好的说明和指示作用。
4.2 正则表达式在文本文档中的信息抽取
电子文档除上述web网页格式外,还有一些信息是以文本格式存储的。为充分利用现有资源,提高效率,将非结构化的文本格式转化成半结构化的格式是必要的。下面本文介绍了如何将法律条文这种非结构化的文件,利用正则表达式进行信息抽取,转化成半结构化的形式。
对于法律条约,虽然是以非结构化的格式存储的,但其内容本身是有结构的。如每个条约包括序言和正文两个组成部分;正文包含若干个章或编;每章包括若干个节;每节包括若干个条;每条包含若干个款等。根据以上特点,我们可以使用正则表达式匹配条约正文中的特征文字,抽取相应的信息,生成具有序言、章、节、条、款等层次结构信息和其它属性信息的法律条约。如抽取法律条约中的每一行内容,其相应的正则表达式为:”^([wW]*?)$”其中,^表示一行的开始;()表示括号内的内容分组;[]表示里面的多个内容中取一个;w表示字母(a~z,A~Z)以外的字符;*表示后面接0个或多个字符;?表示后面接0个或一个字符;*?的结合表示后面可以接其它字符(不包含换行符);$表示行结束符。获取章的标题和内容,并对每一章进行节的解析;若不存在,直接进行节的解析,则相关的正则表达式为:“^s*(第s*[^条节部分]{1,3}s*[章编])([wW]*?)$”。其中s表示空白字符(空格、tab等);[^]除括号内的符号外的其它符号(如[^条节]表示条、节的其它符号);{1,3}表示前面的符号至少一个,至多三个。
5 结论
正则表达式是对一类字符串共性描述的规则,提供了一种从字符集合中搜寻特定字符串的机制。本文介绍了正则表达式的理论,并利用其快速匹配文本的特点,抽取Web文档和法律条文两种格式电子文档中的主要信息,进行信息抽取。通过以上实例,可以看出,对于半结构化文本和结构化文档,正则表达式能够很好的进行信息抽取。而对于非结构化的文档,还有待进一步研究。
摘要：正则表达式是对一类字符串共性描述的规则,提供了一种从字符集合中搜寻特定字符串的机制。信息抽取的主要功能是从文本中抽取出特定的事实信息(factual information)。该文利用正则表示式快速匹配文本的特点,以抽取电子文档的主要信息为例,介绍了正则表达式理论以及在信息抽取中的应用。
关键词：正则表达式,信息抽取
参考文献
[1]Liger F,Queen C M,Wilton P.C#字符串和正则表达式参考手册[M].刘乐亭,译.北京:清华大学出版社,2003.
[2]The Single Unix Specification,Version2[OL].Http://www.opengroup.org/onlinepubs/.
[3]吕晓波.正则表达式使用详解[OL].http://dev.csdn.net/article/8/8254.shtm.
[4]Harry R.Lweis,Christos H Papadimitriou.计算理论基础[M].张立昂,刘田,译.北京:清华大学出版社,2000.
正则表达式 篇9
关键词：网络报名,网上报名系统,JS正则表达式
1 概述
目前各高校自主招生如火如荼, 对自主招生院校招生管理者而言, 既要为考生报名提供即时、便捷的服务, 提高报名工作效率, 又要准确获取考生信息, 这是一个亟待考虑和解决的问题。创建网络在线报名系统, 提供网上报 名服务 ,可以方便考生报名, 减轻院校招生工作人员的负荷, 提高招生管理的质量, 是一种很好的解决方案。而网络在线报名系统中采用基于JS正则表达式校验技术, 不仅简单易行, 而且可以减少数据冗余, 提高考生报名信息准确率。
2 正则表达式
2.1 定 义
正则表达 式 (Reg Exp) 是种特殊 字符串 , 由普通字 符(原义字符 ) 和特殊字符 (元字符 ) 组成 , 能按照特定语法规则被解释成多种字符串, 并以此对目标字符串进行匹配。在Web应用中 , 正则表达式可以让用户通过使用一系列特殊字符构建匹配模式, 然后把匹配模式与Web页面表单输入等目标对象进行比较, 根据比较对象中是否包含匹配模式, 以执行相应处理操作。由于正则表达式字符处理能力强大、灵活高效、适应性强, 因此广泛用于字符串校验和替换等。
2.2 构 造法则
利用正则表达式校验, 首先构造正则表达式, 其过程就是用多种元字符将小的表达式相互连接在一起创建更大的表达式。常用元字符和操作符可见相关文献, 利用它们能写出具有各种校验功能的正则表达式。
实际应用中, 正则表达式必须放在一对分隔符之间, 这样编程语言才可以识别并执行, 不同语言对应分隔 符不同 ,JScript是用一对正斜杠" /" 来定界 , 并使用match和test方法进行验证, 格式如下: /元字符表达式/。
2.3 构 造实例
以Jscript为脚本语言, 构造满足如下要求正式:(1) 匹配考生号 (或身份证号 )
考生号为全国统一的14位0~9数字构成, 其含义如下:
1) 第1、2位为年度代码 : 如2015年填写“15”。
2) 第3、4位为省市代码 : 安徽省代码为“34”。
3) 第5、6、7、8位为县、市 、区代码。
4) 第9位为考试类别代码 : 普通高考代码为“1”, 中职代码"9"。
5) 第10位为科类代码 :
1文史类—1
2外语类—2
3艺术类 (文) —3
4理工类—5
5艺术类 (理) —7
6体育类 (理) —8
6) 第11、12、13、14位为考生顺序号。
对应正式格式: /^1534 [0-9] [0-9] [0-9] [0-9] [19][123578] d {4} $/, 其中
/: 正式定界符号 ;
^: 匹配输入字符串的开始位置 ;
[0-9]: 用于匹配从0到9的任意一个数字 ;
d {4}: 用于匹配从0到9的任意四个数字 ;
$:匹配输入字符串的结束位置。
3 应用实例
3.1 考生号验证代码
3.2 匹 配 Email 地 址验证
4 结语