度量正则表达式状态复杂度的方法及装置

摘要

本发明涉及一种度量正则表达式状态复杂度的方法及装置。度量正则表达式状态复杂度的方法包括：步骤一，判断给定非确定型有限自动机M中任意两状态p、q间的卷曲关系，该卷曲关系为如下五种关系之一：互斥关系、等价关系、包含于关系、包含关系、独立关系，M=(Q,Σ,δ,q

说明书

技术领域

本发明涉及信息技术领域，尤其涉及一种度量正则表达式状态复杂度的 方法及装置。

背景技术

深度包检测系统中正则表达式的复杂化和大规模化使得经典的NFA （Non-deterministic Finite Automaton，非确定型有限自动机）和DFA （Deterministic Finite Automaton，确定型有限自动机）匹配方法都无法 实现线速匹配的要求。目前，相关研究人员已提出大量的算法、架构和数据 结构来匹配效率低下和内存开销巨大的问题。但这些工作普遍存在如下几个 问题：1）只能应用在小规模（数十条或数百条）的正则表达式匹配，当规 模较大时仍不能很好地解决甚至不能解决所面临的问题；2）只面向某些特 殊类型的正则表达式，对较复杂的正则表达式匹配不能正确地解决甚至不能 解决，不具有通用性；3）通过在多个可选结果中大量测试和比较来找到较 好的结果解决问题，预处理时间太长，无法应对正则表达式的频繁更新。出 现这些问题的根本原因是缺少有效手段对正则表达式的状态复杂度进行度 量。

状态复杂度的研究可以追朔到上世纪的六七十年代，它是基于DFA对 正则语言的描述复杂度的度量。一个正则语言通常会被多个（可能无穷多个） DFA识别，正则语言的状态复杂度定义为识别该语言的最小DFA的状态数 目，最小DFA意味着其状态数目在所有识别该语言的DFA中是最少的。正 则语言的状态复杂度研究的问题是对状态复杂度给定的正则语言，如何给出 经过某些操作得到的正则语言的状态复杂度在最坏情况下的界限。

但在正则表达式匹配中，需要研究的是正则表达式的状态复杂度。虽然 正则表达式和正则语言的描述能力是等价的并可相互转换，但上述研究的成 果并不能直接用来实现对正则表达式的定量分析和可靠比较的目的。这是因 为上述研究主要着眼于给出在最坏情况下状态复杂度的上界，但真实深度包 检测系统中的大部分正则表达式并不满足得到最坏情况所要求的条件，并且 仅依靠特殊情况下的上界是无法对正则表达式进行可靠比较的。

发明内容

本发明所要解决的技术问题是提供一种度量正则表达式状态复杂度的 方法及装置，能够快速地得到一个合理的估计值，提高度量效率。

为解决上述技术问题，本发明提出了一种度量正则表达式状态复杂度的 方法，包括：

步骤一，判断给定非确定型有限自动机M中任意两状态p、q间的卷曲 关系，所述卷曲关系为如下五种关系之一，M=(Q,Σ,δ,q₀,F)，其中，Q是一 个有穷集，Q的每个元素称为一个状态,Σ是一个有穷字母表，Σ的每一个 元素称为一个输入字符,δ是状态转移函数,q₀∈Q,q₀是唯一的一个开始状 态,F是终止状态集：

（1）互斥关系：表示为p||q，当且仅当p的语言和q的语言的交集为空 时成立,p的语言是指以状态p定义的字符串集合，q的语言是指以状态q定 义的字符串集合；

（2）等价关系：表示为p≡q，当且仅当p的语言和q的语言完全相同 并且交集非空时成立；

（3）包含于关系：表示为当且仅当p的语言是q的语言的一个 非空真子集时成立；

（4）包含关系：表示为当且仅当p的语言是q的语言的一个非 空真超集时成立；

（5）独立关系：表示为当且仅当p的语言和q的语言的交集非空， 并且任何一个状态的语言都不是另一个状态的语言的子集时成立；

步骤二，根据步骤一的判断结果估计正则表达式的状态复杂度，该状态 复杂度即对M确定化得到的确定型有限自动机M′的状态数目|Q′|， M′=(Q′,Σ,δ′,q₀′,F′)。

进一步地，上述度量正则表达式状态复杂度的方法还可具有以下特点， 步骤二包括：

若M中任意两状态p、q都相互不独立，则|Q′|≤|Q|，其中，|Q|为M的 状态数目。

进一步地，上述度量正则表达式状态复杂度的方法还可具有以下特点， 步骤二包括：

若M中任何两个状态都不等价，并且M中任何一个状态p∈Q的语言满 足则令|Q′|=|Q|+|E|，其中，|Q|为M的状态数 目、|E|为M的状态间相互独立的数目。

进一步地，上述度量正则表达式状态复杂度的方法还可具有以下特点， 步骤一包括：

记Xα为通过字符α转移到状态p的所有状态的集合，Yα为通过字符α 转移到状态q的所有状态的集合，将Xα（Yα）作为一个新状态pα（qα）计 算的值，表示状态p和状态q间的卷曲关系，有如下四种情形：

情形1，如果Xα和Yα都仅有一个值，那么等于这两个状态的 卷曲关系值；

情形2，如果Xα只有一个状态而Yα包含多个状态，假设Xα={x}，Yα=S  U{y,z},的值可以通过下表获得，

  0 1 2 3 4 5 6 7 0 0 1 x x x x x x

1 1 1 x x x x x x 2 x x 2 3 4 5 6 7 3 x x 3 3 5 5 7 7 4 x x 4 5 4 5 4 5 5 x x 5 5 5 5 5 5 6 x x 6 7 4 5 6/4 7/5 7 x x 7 7 5 5 7/5 7/5

其中，上表中每行为的取值，每列为的取值，0、1、2、3表 示互斥关系，4表示等价关系，5表示包含于关系，6表示包含关系，7表示 独立关系，将{y,z}作为一个新状态t，那么Yα=S U{t}，通过每次查表就 可将Yα的状态数目减少一，依次进行直到情形1；

情形3，如果Xα包含多个状态而Yα只有一个状态，假设Xα=S U{y,z}， Yα={x},的值通过下表获得，

  0 1 2 3 4 5 6 7 0 0 x 2 x x x x x 1 x 1 x 3 4 5 6 7 2 2 x 2 x x x x x 3 x 3 x 3 6 7 6 7 4 x 4 x 6 4 4 6 6 5 x 5 x 7 4 5/4 6 7/6 6 x 6 x 6 6 6 6 6 7 x 7 x 7 6 7/6 6 7/6

其中，上表中每行为的取值，每列为的取值，将{y,z}想象为 一个新状态t，那么Xα=S U{t}，通过每次查表就可将Xα的状态数目减少 一，依次进行直到情形1；

情形4，如果Xα和Yα都包含多个状态，先对Xα中的每个状态和Yα 执行情形2，这样Xα不变而Yα变为一个状态，然后执行情形3；令其中“|”是异或运算符。

为解决上述技术问题，本发明提出了一种度量正则表达式状态复杂度的 装置，包括：

判断模块，用于判断给定非确定型有限自动机M中任意两状态p、q间 的卷曲关系，所述卷曲关系为如下五种关系之一，M=(Q,Σ,δ,q₀,F)，其中， Q是一个有穷集，Q的每个元素称为一个状态,Σ是一个有穷字母表，Σ的 每一个元素称为一个输入字符,δ是状态转移函数,q₀∈Q,q₀是唯一的一个 开始状态,F是终止状态集：

（1）互斥关系：表示为p||q，当且仅当p的语言和q的语言的交集为空 时成立，p的语言是指以状态p定义的字符串集合，q的语言是指以状态q定 义的字符串集合；

（2）等价关系：表示为p≡q，当且仅当p的语言和q的语言完全相同 并且交集非空时成立；

（3）包含于关系：表示为当且仅当p的语言是q的语言的一个 非空真子集时成立；

（4）包含关系：表示为当且仅当p的语言是q的语言的一个非 空真超集时成立；

（5）独立关系：表示为当且仅当p的语言和q的语言的交集非空， 并且任何一个状态的语言都不是另一个状态的语言的子集时成立；

度量模块，用于根据判断模块的判断结果估计正则表达式的状态复杂度， 该状态复杂度即对M确定化得到的确定型有限自动机M′的状态数目|Q′|， M′=(Q′,Σ,δ′,q₀′,F′)。

进一步地，上述度量正则表达式状态复杂度的装置还可具有以下特点， 度量模块包括：

第一度量单元，用于在M中任意两状态p、q都相互不独立时，得到度 量结果|Q′|≤|Q|，其中，|Q|为M的状态数目。

进一步地，上述度量正则表达式状态复杂度的装置还可具有以下特点， 度量模块包括：

第二度量单元，用于在M中任何两个状态都不等价，并且M中任何一 个状态p∈Q的语言满足时，得到度量结果|Q′|= |Q|+|E|，其中，|Q|为M的状态数目、|E|为M的状态间相互独立的数目。

进一步地，上述度量正则表达式状态复杂度的装置还可具有以下特点， 判断模块包括：

第一计算单元，用于记Xα为通过字符α转移到状态p的所有状态的集 合，Yα为通过字符α转移到状态q的所有状态的集合，将Xα（Yα）作为一 个新状态pα（qα）计算的值，表示状态p和状态q间的卷曲关 系，有如下四种情形：

情形1，如果Xα和Yα都仅有一个值，那么等于这两个状态的 卷曲关系值；

情形2，如果Xα只有一个状态而Yα包含多个状态，假设Xα={x}，Yα=S U{y,z},的值通过下表获得，

  0 1 2 3 4 5 6 7 0 0 1 x x x x x x 1 1 1 x x x x x x 2 x x 2 3 4 5 6 7 3 x x 3 3 5 5 7 7 4 x x 4 5 4 5 4 5 5 x x 5 5 5 5 5 5 6 x x 6 7 4 5 6/4 7/5 7 x x 7 7 5 5 7/5 7/5

其中，上表中每行为的取值，每列为的取值，0、1、2、3表示 互斥关系，4表示等价关系，5表示包含于关系，6表示包含关系，7表示独 立关系，将{y,z}作为一个新状态t，那么Yα=S U{t}，通过每次查表就可将 Yα的状态数目减少一，依次进行直到情形1；

情形3，如果Xα包含多个状态而Yα只有一个状态，假设Xα=S U{y,z}， Yα={x},的值通过下表获得，

  0 1 2 3 4 5 6 7 0 0 x 2 x x x x x 1 x 1 x 3 4 5 6 7 2 2 x 2 x x x x x 3 x 3 x 3 6 7 6 7 4 x 4 x 6 4 4 6 6 5 x 5 x 7 4 5/4 6 7/6 6 x 6 x 6 6 6 6 6 7 x 7 x 7 6 7/6 6 7/6

其中，上表中每行为的取值，每列为的取值，将{y,z}想象为 一个新状态t，那么Xα=S U{t}，通过每次查表就可将Xα的状态数目减少 一，依次进行直到情形1；

情形4，如果Xα和Yα都包含多个状态，先对Xα中的每个状态和Yα 执行情形2，这样Xα不变而Yα变为一个状态，然后执行情形3；

第二计算单元，用于令其中“|”是异或运算符。

本发明的度量正则表达式状态复杂度的方法及装置，能够快速地得到一 个合理的估计值，提高度量效率。

附图说明

图1为本发明实施例中度量正则表达式状态复杂度的方法的流程图；

图2为本发明实施例中度量正则表达式状态复杂度的装置的结构框图；

图3为以L7-Filter系统中的107条正则表达式为实验规则对本发明度 量正则表达式状态复杂度的方法进行验证得到的验证结果示意图；

图4为本发明度量正则表达式状态复杂度的方法的度量偏差率示意图。

具体实施方式

以下结合附图对本发明的原理和特征进行描述，所举实例只用于解释本 发明，并非用于限定本发明的范围。

图1为本发明实施例中度量正则表达式状态复杂度的方法的流程图，如 图1所示，本实施例中，度量正则表达式状态复杂度的方法的流程包括：

步骤S101，判断给定非确定型有限自动机M中任意两状态p、q间的卷 曲关系，该卷曲关系为如下五种关系之一，M=(Q,Σ,δ,q₀,F)，其中，Q是一 个有穷集，Q的每个元素称为一个状态,Σ是一个有穷字母表，Σ的每一个元 素称为一个输入字符,δ是状态转移函数,q₀∈Q,q₀是唯一的一个开始状态, F是终止状态集：

（1）互斥关系：表示为p||q，当且仅当p的语言和q的语言的交集为空 时成立；其中，某一状态的语言是指以该状态定义的字符串集合。

（2）等价关系：表示为p≡q，当且仅当p的语言和q的语言完全相同并 且交集非空时成立；

（3）包含于关系：表示为当且仅当p的语言是q的语言的一个非 空真子集时成立；

（4）包含关系：表示为当且仅当p的语言是q的语言的一个非空 真超集时成立；

（5）独立关系：表示为当且仅当p的语言和q的语言的交集非空， 并且任何一个状态的语言都不是另一个状态的语言的子集时成立；

步骤S102，根据步骤S101的判断结果估计正则表达式的状态复杂度， 该状态复杂度即对M确定化得到的确定型有限自动机M′的状态数目|Q′|， M′=(Q′,Σ,δ′,q₀′,F′)。

具体地，步骤S101可以包括如下子步骤：

记Xα为通过字符α转移到状态p的所有状态的集合，Yα为通过字符α 转移到状态q的所有状态的集合，将Xα（Yα）想象为一个新状态pα（qα） 计算的值，表示状态p和状态q间的卷曲关系，有如下四种情形：

情形1，如果Xα和Yα都仅有一个值，那么等于这两个状态的 卷曲关系值；

情形2，如果Xα只有一个状态而Yα包含多个状态，假设Xα={x}，Yα=S U{y,z},根据集合论的知识，的值可以通过表1获得，

表1

  0 1 2 3 4 5 6 7 0 0 1 x x x x x x 1 1 1 x x x x x x 2 x x 2 3 4 5 6 7 3 x x 3 3 5 5 7 7 4 x x 4 5 4 5 4 5 5 x x 5 5 5 5 5 5 6 x x 6 7 4 5 6/4 7/5 7 x x 7 7 5 5 7/5 7/5

其中，表1中每行为的取值，每列为的取值，0、1、2、3表示 互斥关系，4表示等价关系，5表示包含于关系，6表示包含关系，7表示独 立关系，将{y,z}想象为一个新状态t，那么Yα=S U{t}，通过每次查表就可 将Yα的状态数目减少一，依次进行直到情形1；

情形3，如果Xα包含多个状态而Yα只有一个状态，假设Xα=S U{y,z}， Yα={x},根据集合论的知识，的值可以通过表2获得，

表2

  0 1 2 3 4 5 6 7 0 0 x 2 x x x x x 1 x 1 x 3 4 5 6 7 2 2 x 2 x x x x x

3 x 3 x 3 6 7 6 7 4 x 4 x 6 4 4 6 6 5 x 5 x 7 4 5/4 6 7/6 6 x 6 x 6 6 6 6 6 7 x 7 x 7 6 7/6 6 7/6

其中，表2中每行为的取值，每列为的取值，将{y,z}想象为 一个新状态t，那么Xα=S U{t}，通过每次查表就可将Xα的状态数目减少 一，依次进行直到情形1；

情形4，如果Xα和Yα都包含多个状态，先对Xα中的每个状态和Yα 执行情形2，这样Xα不变而Yα变为一个状态，然后执行情形3；

令其中“|”是异或运算符。

具体地，步骤S102可以包括如下子步骤：

若M中任意两状态p、q都相互不独立，则|Q′|≤|Q|。

步骤S102还可以包括如下子步骤：

若M中任何两个状态都不等价，并且M中任何一个状态p∈Q的语言满 足则令|Q′|=|Q|+|E|。

其中，|Q|为M的状态数目、|Q|为M′的状态数目，|E|为M的状态间相 互独立的数目，|Q′|即为正则表达式的状态复杂度。

下面对本发明的原理进行说明。

根据自动机和文法理论，正则表达式具有与FSM（Finite State  Machine,有限状态机）等价的描述能力，正则表达式匹配通常都是通过有 限状态机来实现的。有限状态机M是一个五元组，表达式为：M=(Q,Σ,δ,q₀,F)， 其中Q是一个有穷集，它的每个元素称为一个状态；Σ是一个有穷字母表， 它的每一个元素称为一个输入字符；δ是状态转移函数；q₀∈Q是唯一的一 个开始状态；是终止状态集，又称为接受状态集。非确定有限自动机 NFA和确定有限自动机DFA是两种经典的有限状态机，二者的区别在于NFA 的状态转移函数是非确定性的，即NFA中δ是Q×Σ→2^Q，也就是说，NFA中， 一个状态经过一个字符可以转移到多个状态；而DFA的状态转移函数是确定 性的，即DFA中δ是Q×Σ→Q，也就是说，DFA中，一个状态经过一个字符 只能转移到一个状态。有限状态机通过一个字符接一个字符的读入字符串 ω∈Σ⁺，其中，“ω”表示字符串，“∑”表示有穷字母表，“∑⁺”表示由 有穷字母表构成的字符串集合，并根据给定的状态转移函数一步步地进行状 态转移来完成对ω的匹配。匹配过程开始于有限状态机的开始状态，它沿着 当前所有活跃状态的标记为当前待处理字符的所有转移边进行转移，当转移 至某个终结状态时报告一次匹配，并返回匹配位置和被命中的正则表达式。 由于一个NFA状态对一个给定的字符可能有多条转移边（也可能没有），因 此在NFA的匹配过程中可能有多个状态同时活跃，通常称为活跃状态集。相 反，每个DFA状态对任意给定的字符有且仅有一条转移边，因而在DFA的匹 配过程的任意时刻只有一个状态活跃。

DFA可由NFA确定化得到的，确定化的核心思想就是用DFA的一个状态 来表示NFA的一个活跃状态集。那么DFA的状态数目（也即正则表达式的状 态复杂度）就是NFA的所有可能的活跃状态集的数目。而一个状态集（实为 NFA状态集的子集）是否能够活跃取决于其中状态间的关系，例如如果两状 态任意时候都是同时活跃的，若该状态集只有其中一个状态，那显然该状态 集不是一个可能的活跃状态集。

基于此，本发明基于NFA的状态间的关系来对DFA的状态数目（即正则 表达式的状态复杂度）进行度量。

对给定有限状态机M=(Q,Σ,δ,q₀,F)和其中任意两状态p,q∈Q，称状态q 能被字符串ω∈Σ⁺从状态p激活，如果在p和q之间存在着一条标记为ω的转 移路径，简记为那么每个状态q∈Q都可以用来定义一个字符串 集合称该字符串集合为状态q的语言。

对有限状态机M=(Q,Σ,δ,q₀,F)和其两状态p,q∈Q，根据状态的语言间的 集合关系定义状态之间的关系共有以下五种卷曲关系）

（1）互斥关系

表示为p||q，当且仅当p的语言和q的语言的交集为空时成立。

（2）等价关系

表示为p≡q，当且仅当p的语言和q的语言完全相同并且交集非空时成 立。

（3）包含于关系

表示为当且仅当p的语言是q的语言的一个非空真子集时成立。

（4）包含关系

表示为当且仅当p的语言是q的语言的一个非空真超集时成立。

（5）独立关系

表示为当且仅当p的语言和q的语言的交集非空，并且任何一个 状态的语言都不是另一个状态的语言的子集时成立。

从上面的定义可知，任意两状态之间的卷曲关系是且仅是互斥、等价、 包含、包含于和独立五种关系中的一种。实际上，两状态间的卷曲关系和它 们的同时活跃情况是相对应的。语言交集为空时两状态才互斥，也就是说不 存在任何字符串能从开始状态可以把它们都激活，即在匹配的任何时刻具有 互斥关系的两个状态是不可能同时活跃的。同理可以得到：具有等价关系的 两状态在任何时刻都是同时活跃的；p包含q说明状态q活跃时状态p必然活 跃，但存在p活跃而q不活跃的情形；p包含于q说明状态p活跃时状态q必 然活跃，但存在q活跃而p不活跃的情形；具有独立关系的两状态在活跃时 互不影响，即在匹配过程中存在着同时活跃的情形，也存在着一个状态活跃 而另一个不活跃的情形。

在下面的描述中，如果没有特别说明，默认自动机M=(Q,Σ,δ,q₀,F)是一 个NFA，自动机M′=(Q′,Σ,δ′,q₀′,F′)是对M确定化得到的DFA。根据卷曲关系 的定义，可以得到如下三个定理。

定理1 如果任意非确定型有限自动机M中的任意两个状态p,q∈Q都相 互不独立，那么|Q′|≤|Q|。

其中，|Q|为非确定型有限自动机M的状态数目（也即正则表达式的NFA 状态数目），|Q′|为确定型有限自动机M′的状态数目（也即正则表达式的DFA 状态数目），M′由M确定化得到。

从定理1可知，不具有独立关系的NFA不会导致DFA的状态数目增加， 那么独立关系是导致NFA到DFA的确定化过程中发生状态膨胀的原因。

定理2 对给定的NFA M=(Q,Σ,δ,q₀,F)，如果它的独立图G=(V,E)有c_i个 顶点数目为i的簇(1≤i≤ω(G)),那么子集构造生成的DFA M′的状态数目 不少于c_i之和，即

其中，|E|为NFA状态间相互独立的数目。

对NFA M，其独立图为一个无向图G=(V,E)，其中顶点集V表示M的 状态集Q，如果状态p和q相互独立，在无向图的两顶点（状态）p和q间添 加一条边。ω(G)为无向图G的最大簇的顶点数目。显然定理2是定理1在允 许NFA的状态间存在独立关系的更一般形式。

给定一个正则表达式集合，通过计算来获得其DFA的状态 复杂度是非常低效率的，这是因为在NFA的独立图中找到所有的簇是NP困 难的。而且在大多数情况下|Q′|的值远小于

定理3 对给定的NFA M=(Q,Σ,δ,q₀,F)，如果它的任何两个状态都不等 价，并且其任何一个状态p∈Q的语言那么子 集构造生成的DFA M′的状态数目不小于NFA M的状态数目，即|Q′|≥|Q|。

由于可以利用|Q|+|E|的值作为对|Q′|的度量， 即利用正则表达式的NFA的状态数目与该NFA中状态间相互独立的数目之和 作为对正则表达式的状态复杂度（正则表达式的DFA的状态数目）的度量。 这就是本发明给出的基于卷曲关系的状态复杂度度量方法。虽然该方法给出 的状态复杂度不是一个准确值，但能快速地得到一个合理的估计值。因为通 常一个具有更多状态数目和更多相互独立的状态对的NFA会被确定化为一个 具有更多状态数目的DFA。

下面说明如何确定状态间的卷曲关系。

对给定的NFA，通过分析该自动机的所有可能活跃状态集可以得到任意 两状态间的卷曲关系。然而，该种方法的时间开销是极大的，因为它首先需 将该NFA转换为DFA来获得所有活跃状态集，本文中简称该方法为“转换- 确定法”。

Yang和Prasanna采用如下方式确定状态x和状态y间的卷曲关系：通过 比较两状态的语言中具有相同后缀的字符串间的关系来确定状态间的关系， 算法不断增加后缀的长度并在该长度的所有可能后缀上进行比较，直到发现 一个能从开始状态同时激活x和y的后缀。实际上该方法的时间开销是非常 巨大的，因为为得到任意两状态间的卷曲关系，状态的语言中具有某个后缀 的字符串集合需要重复地创建。因而Yang和Prasanna仅在12条他们精心 挑选的正则表达式上进行实验。在实验过程中，发现该方法的效率比“转换 -确定法”还低。此外，两状态的语言可能都是无穷大的且交集为空，在这 种情况下该方法会不停地进行比较永不停止，因为不存在相同后缀使得从开 始状态同时激活这两个状态。

本发明给出了一种能够快速确定给定NFA中任意两状态间卷曲关系的方 法。根据卷曲关系的定义，可知状态x和状态y间的卷曲关系，表示为可以通过和三个条件的真假决定，如图 A所示。

状态x的语言可以表示成L(x)=∪_α∈ΣL_∪(X_α)α，其中X_α是该NFA中能通过 字符α转移到状态x的所有状态的集合，其中L_∪(X_α)是X_α中所有状态的语言 的并集。类似地，L(y)=∪_α∈ΣL_∪(Y_α)α。

定理4（1）如果那么（2）如果 那么（3）如果那么

根据定理4可知，判定和三个条件 的真假相应地就转化为了判定和 三个条件的真假。可以将X_α（Y_α）想象为一个新状态x_α，其 语言是X_α（y_α）中各状态的语言的并集。那么根据定理4，可推得其中|是异或运算符。

下面说明如何计算的值。若X_α和Y_α都只包含一个状态， 显然的值就是这两个状态的卷曲关系值。需要注意的是X_α和Y_α中都可 能包括多个状态。假设X_α={p}、Y_α={q,s}，以此为例说明求如果和的值已知，可以根据集合论的知识求得的值。对和的不 同取值组合，可能的值如表1所示。例如，如果并且可 以推得因为L(p)与L(q)和L(s)都没有交集，相应地关于x_α和y_α的 三个判定条件分别为假、真、真。然而，在某些和的取值下，可能存在多个可能值。例如，当和时意味着L(q)和L(s)是L(p)的 两个非空真子集。此时如果恰好L(p)=L(q)∪L(s)，那么（说明x_a和y_a等价，表1中的加粗倾斜字体所示的值），否则（说明x_a包含y_a， 表1中的加粗不倾斜字体所示的值）。在对真实系统的正则表达式构造的NFA 中，存在L(p)=L(q)∪L(s)的可能性非常小。因而在计算的值时，可以仅 以加粗不倾斜字体所示的值作为唯一的可能值来简化计算过程。类似地，当 或时，有7和5两种可 能的取值。表1中‘x’表明相应的和的取值不可能同时成立。例 如，说明L(p)是空集，而的值大于1说明L(p)是非空的，因而两 者不可能同时成立，相应的也不存在任何取值。

类似地，可以基于和的值为构造查询矩阵如表2所示。

若X_α和Y_α都包含多个状态，按照如下的方式重复地执行上面的计算： 每次可以认为从X_α（Y_α）中移除两个状态，并加入一个语言等价于所删除 两状态语言的并集的状态至X_α（Y_α）中，然后计算新加状态与其他状态之 间的关系。由于需求得NFA中所有状态之间的卷曲关系，因而在计算过程中 可以从开始状态起按照转移字符的大小顺序宽度优先进行计算状态间的卷 曲关系。也就是说：对给定状态x和字符α,β∈Σ，当或者 且α>β时，若x与状态q的卷曲关系未知，则计算x 与状态p间的卷曲关系要早于计算x与状态q间的卷曲关系。这样的话，在 计算x_α和y_α的卷曲关系时，就能知道几乎所有那些在计算时需要用到的一个 状态对在X_α中另一个状态在Y_α中的状态对的卷曲关系。如果计算时需要用 的状态间的卷曲关系仍然未知，处理策略是跳过对这些未知关系的处理。对 上面例子中的X_α={p}和Y_α={q,s}，若的关系未知则认为

由于上述方法是通过计算来得到任意两NFA状态间的卷曲关系，在后文 中简称该方法为“计算-确定法”。由于在计算过程中“计算-确定法”在两 处进行了投机性的处理（忽略表1和表2中小概率的加粗倾斜字体所示的值 的存在和忽略对未知卷曲关系的处理），因而该方法得到的状态间的卷曲关 系可能是错误的，但该方法的优势在于其运算效率特别快。

用四个在实验中常用的正则表达式集合snort24、snort31、snort34和 bro217来评价“计算-确定法”的效果，如表3所示。状态间的卷曲关系的 准确值是通过“转换-确定法”获的，其中绝大部分的运行时间是消耗在了 NFA到DFA的确定化过程中。对一个具有n个状态的NFA，转换确定法和计算 -确定法需计算的状态间的卷曲关系数为n(n-1)/2。然而，本发明中的计算- 确定法的运行时间随着n呈二项式增长，而转换-确定法的运行时间理论上在 最坏情况下随着n呈指数增长。从表3可以看出，计算-确定法能将计算卷曲 关系的速度平均提升45.1倍，而代价是仅将不到0.1%的状态间的卷曲关系 计算错误。这表明计算-确定法能快速并较可靠地完成状态间的卷曲关系的 计算。

与表3所示的四个实验集合相比较，转换-确定法在bro217规则集上消 耗的时间最短，而计算-确定法消耗的时间却是最多的。主要原因是bro217 集合中几乎所有的正则表达式都是大小写不敏感的字符串，因而导致构造的 合并DFA不会发生状态膨胀，虽然规则数目最多但却具有最少的DFA状态数。 相应地，计算-确定法在该集合上的加速比较小。由此可以推测，对含有复 杂正则表达式的集合，其更容易发生状态膨胀，从而计算-确定法能在这样 的集合上取得更大的加速比。

表3 计算-确定法的效果评价

以L7-Filter系统中的107条正则表达式为实验规则对本发明度量正则 表达式状态复杂度的方法进行验证，每条正则表达式的NFA状态数目|Q|、 DFA的状态数目|Q′|（准确状态复杂度）和NFA的状态数目与NFA状态间相 互独立的数目之和|Q|+|E|（估计状态复杂度）如图3所示（为了使图中三 条曲线更容易区分，具有最大状态数目的一条正则表达式的结果未在图3中 显示。所对应的值分别为|Q|=129、|Q|+|E|=1135、|Q′|=3278）。从图3中可 以看出，每条正则表达式的DFA状态数目都要大于其NFA的状态数目，这也 从实验上验证了即使条件不成立，定理3的结论在大部分情况下也是正确的。

本发明度量正则表达式状态复杂度的方法的度量偏差率如图4所示，其 中度量偏差率定义为度量的估计值与状态复杂度的真实值之差与真实值的 比值。从图4中可以很显然地看出，该方法的度量偏差率是很小的，对 L7-Filter的规则集来说其偏差范围在-1到1之间，绝大部分情况下该值是 接近于0的。通常情况下度量偏差率都是小于0的，这说明该方法给出的状 态复杂度的估计值通常是偏小的。但也有少部分特殊的正则表达式得到的偏 差率是大于0的，例如L7-Filter系统中用于识别socks5协议的正则表达 式

“\x05[\x01-\x08]*\x05[\x01-\x08]?.*\x05[\x01-\x03][\x01\x03].*\x 05[\x01-\x08]?[\x01\x03]”。经过分析发现，出现这种情况的原因是在NFA 中若干互相独立的状态其语言的交集是相同的，类似于 L(p)∩L(q)∩L(s)=L(p)∩L(q)=L(p)∩L(s)=L(q)∩L(s)的情形，因而|Q|+|E|中包 含了某些不可能存在的活跃状态集。

可见，本发明的度量正则表达式状态复杂度的方法，能够快速地得到一 个合理的估计值，提高度量效率。

本发明的度量正则表达式状态复杂度的方法，可以应用于信息内容安全、 信息过滤、信息检索等领域。

本发明还提出了一种度量正则表达式状态复杂度的装置，用以执行上述 的度量正则表达式状态复杂度的方法。

图2为本发明实施例中度量正则表达式状态复杂度的装置的结构框图。 如图2所示，本实施例中，度量正则表达式状态复杂度的装置包括判断模块 210和度量模块220。其中，判断模块210用于判断给定非确定型有限自动 机M中任意两状态p、q间的卷曲关系，该卷曲关系为如下五种关系之一， M=(Q,Σ,δ,q₀,F)，其中，Q是一个有穷集，Q的每个元素称为一个状态,Σ是 一个有穷字母表，Σ的每一个元素称为一个输入字符,δ是状态转移函数, q₀∈Q,q₀是唯一的一个开始状态,F是终止状态集：（1）互斥关系： 表示为p||q，当且仅当p的语言和q的语言的交集为空时成立；（2）等价关 系：表示为p≡q，当且仅当p的语言和q的语言完全相同并且交集非空时成 立；（3）包含于关系：表示为当且仅当p的语言是q的语言的一个非 空真子集时成立；（4）包含关系：表示为当且仅当p的语言是q的语 言的一个非空真超集时成立；（5）独立关系：表示为当且仅当p的语 言和q的语言的交集非空，并且任何一个状态的语言都不是另一个状态的语 言的子集时成立。度量模块220用于根据判断模块210的判断结果估计正则 表达式的状态复杂度，该状态复杂度即即对M确定化得到的确定型有限自动 机M′的状态数目|Q′|，M′=(Q′,Σ,δ′,q₀′,F′)。

在本发明实施例中，度量模块220可以包括第一度量单元。第一度量单 元用于在M中任意两状态p、q都相互不独立时，得到度量结果|Q′|≤|Q|，其 中，|Q|为M的状态数目。

在本发明实施例中，度量模块220可以包括第二度量单元。第二度量单 元用于在M中任何两个状态都不等价，并且M中任何一个状态p∈Q的语言 满足时，得到度量结果|Q′|=|Q|+|E|，其中，|Q| 为M的状态数目、|E|为M的状态间相互独立的数目。

在本发明实施例中，判断模块210可以包括第一计算单元和第二计算单 元。第一计算单元用于记Xα为通过字符α转移到状态p的所有状态的集合， Yα为通过字符α转移到状态q的所有状态的集合，将Xα（Yα）作为一个新 状态pα（qα）计算的值，表示状态p和状态q间的卷曲关系， 有如下四种情形：

情形1，如果Xα和Yα都仅有一个值，那么等于这两个状态的 卷曲关系值；

情形2，如果Xα只有一个状态而Yα包含多个状态，假设Xα={x}，Yα=S U{y,z},的值通过前述的表1获得，

其中，表1中每行为的取值，每列为的取值，0、1、2、3表 示互斥关系，4表示等价关系，5表示包含于关系，6表示包含关系，7表示 独立关系，将{y,z}作为一个新状态t，那么Yα=S U{t}，通过每次查表就可 将Yα的状态数目减少一，依次进行直到情形1；

情形3，如果Xα包含多个状态而Yα只有一个状态，假设Xα=S U{y,z}， Yα={x},的值通过前述的表2获得，

其中，表2中每行为的取值，每列为的取值，将{y,z}想象为 一个新状态t，那么Xα=S U{t}，通过每次查表就可将Xα的状态数目减少 一，依次进行直到情形1；

情形4，如果Xα和Yα都包含多个状态，先对Xα中的每个状态和Yα 执行情形2，这样Xα不变而Yα变为一个状态，然后执行情形3；

第二计算单元，用于令其中“|”是异或运算符。

本发明的度量正则表达式状态复杂度的装置，能够快速地得到一个合理 的估计值，提高度量效率。

以上所述仅为本发明的较佳实施例，并不用以限制本发明，凡在本发明 的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发 明的保护范围之内。