基于TCAM的确定性有穷状态自动机DFA的匹配方法和装置

摘要

本发明涉及一种基于TCAM(ternary content addressable memory，三态内容寻址存储器)的DFA的匹配方法和装置。该方法主要包括：将DFA的每个状态用若干TCAM条目表示，每个TCAM条目由源状态域、输入字符域和目的状态域三个域组成，基于生成所述DFA的非确定性有穷状态自动机NFA中的链式结构，以及所述NFA和所述DFA之间的内在链式结构特征，识别出所述DFA中的链式结构；根据所述DFA中的链式结构对所述DFA的状态进行重新编号和编码，在TCAM中对所述DFA的状态转移边进行重新编码；以具体的所述源状态域和输入字符域的拼接作为搜索关键词，按照所述搜索关键字在所述DFA的所有TCAM条目中进行搜索，将搜索得到的目的状态域作为输出结果。本发明实施例通过在TCAM中通过对DFA的状态转移边进行编码和压缩，使得DFA中的副本链式结构在TCAM中能够被合并，以达到减少存储空间的目的。

说明书

技术领域

本发明涉及计算机应用技术领域，尤其涉及一种基于TCAM(ternary content addressable  memory，三态内容寻址存储器)的DFA的匹配方法和装置。

背景技术

正则表达式技术是计算机网络系统的一项核心基础技术，被广泛应用于入侵检测和防护、 签名匹配、蠕虫检测、包内容过滤、流量分析、协议识别等领域。正则表达式具有灵活、强 大的描述字符串模式的能力，正则表达式的匹配通过有限自动机实现，该有限自动机包括NFA (non-deterministic finite automaton，非确定性有限自动机)和DFA(deterministic  finite automaton，确定性有限自动机)。即可将正则表达式编译为一个NFA，然后可以将此 NFA转化为一个与之等价的DFA，通过NFA或者DFA的状态转换检查输入字符串中是否存在给定 的正则表达式模式。NFA和DFA在存储空间和匹配速度两个方面拥有各自的优点和缺点。

有限自动机存储的是一个状态转换表，给定一个当前活跃状态和一个输入字符，通过在 状态转换表中查询，可得到下一时刻活跃的状态。自动机的存储空间取决于这个状态转换表 的大小，由于字符表的大小通常是确定的(如ASCII表)，所以自动机的存储空间主要取决于 状态的个数。

NFA所需存储空间小，其状态数与正则表达式的规则集大小(即规则集中字符数)成线性 增长关系。但NFA的匹配速度很慢。由于NFA的不确定性，对于每个字符，NFA中的状态都 有可能同时转移到多个目的状态，导致一次状态转换需要多次内存访问。对于这些同时激活 的目的状态，在处理下一个输入字符时，它们又会同时激活更多的目的状态。因此，NFA的匹 配速度是不可预测的，实际应用中，通常需要几十次内存访问才能完成一次NFA状态转换， 远不能满足网络线速(line rate)。

DFA具有确定性的匹配速度，由于对于每个输入字符，每个DFA状态有且仅有唯一的目的 状态，因此每次DFA状态转换仅需一次内存访问。但DFA的状态数可能与正则表达式的规则 集大小成指数增长关系，导致正则表达式规则通常无法用DFA存储。目前的基于DFA的方法都 无法突破一个存储体积的瓶颈，即所存储的DFA转移边的数目总是大于DFA状态数，因此也就 无法存储状态数成指数膨胀的DFA。

目前，由于上述有限状态自动机的体量非常大，导致上述基于DFA的正则表达式匹配方法 亟待改进。

【发明内容】

本发明的实施例提供了一种基于TCAM的DFA的匹配方法和装置，以实现解决同时兼顾存 储空间和匹配速度的难题。

为实现上述的发明目的，本发明采用下述的技术方案：

一种基于TCAM的确定性有穷状态自动机DFA的匹配方法，包括：

将确定性有穷状态自动机DFA的每个状态用若干三态内容寻址存储器TCAM条目表示，每个 TCAM条目由源状态域、输入字符域和目的状态域三个域组成，基于生成所述DFA的非确定性有 穷状态自动机NFA中的链式结构，以及所述NFA和所述DFA之间的内在链式结构特征，识别出所 述DFA中的链式结构；

根据所述DFA中的链式结构对所述DFA的状态进行重新编号和编码，在TCAM中对所述DFA 的状态转移边进行重新编码；

以具体的所述源状态域和输入字符域的拼接作为搜索关键词，按照所述搜索关键字在所 述DFA的所有TCAM条目中进行搜索，将搜索得到的目的状态域作为输出结果。

一种基于TCAM的确定性有穷状态自动机DFA的匹配装置，包括：

DFA链式结构识别模块，用于将DFA的每个状态用若干三态内容寻址存储器TCAM条目表示， 每个TCAM条目由源状态域、输入字符域和目的状态域三个域组成，基于生成所述DFA的非确定 性有穷状态自动机NFA中的链式结构，以及所述NFA和所述DFA之间的内在链式结构特征，识别 出所述DFA中的链式结构；

重编码处理模块，根据所述DFA中的链式结构对所述DFA的状态进行重新编号和编码，在 TCAM中对所述DFA的状态转移边进行重新编码；

搜索匹配模块，用于以具体的所述源状态域和输入字符域的拼接作为搜索关键词，按照 所述搜索关键字在所述DFA的所有TCAM条目中进行搜索，将搜索得到的目的状态域作为输出结 果。

本发明实施例通过对DFA状态ID重新编号以反映DFA中链式结构副本的特征；最终基于重 新编号的状态ID，在TCAM中通过对DFA的状态转移边进行编码和压缩，使得DFA中的副本链式 结构在TCAM中能够被合并，以达到减少存储空间的目。

【附图说明】

图1为本发明实施例一提供的一种基于TCAM(ternary content addressable memory， 三态内容寻址存储器)的DFA的匹配方法的具体处理流程图；

图2为本发明实施例二所提供的用于匹配正则表达式ab[^h]*cd的和ef[^h]*c[hH]的 NFA；

图3为本发明实施例二所提供的用于匹配正则表达式ab[^h]*cd的和ef[^h]*c[hH]的 DFA，状态号以整数编码；

图4为本发明实施例二所提供的图2中的各个DFA状态所对应的“副本ID”、椭ID” 和NFA子集；

图5为本发明实施例五所提供的用于匹配正则表达式ab[^h]*cd的和ef[^h]*c[hH]的 DFA，状态号以(副本ID，私有ID)编码；

图6为本发明实施例六所提供的根据私有ID划分的状态分组以及不同状态分组的状态之 间的“模板”关系示意图；

图7为本发明实施例七所提供的图5中的状态00的TCAM条目；

图8为本发明实施例八所提供的副本ID的编码方案；

图9为本发明实施例八所提供的私有ID的编码方案；

图10为本发明实施例九所提供的为对图5的整个DFA进行编码后的TCAM；

图11为本发明实施例十所提供的对图10中的TCAM重新排序后的TCAM；

图12为本发明实施例十所提供的对图11的TCAM经过状态间压缩和状态内压缩后最终的 结果；

图13为本发明实施例十所提供的将图12中的部分条目的“异或标志位”取“0”后再压 缩的结果；

图14为本发明实施例十一提供的一种基于TCAM的DFA的匹配装置的具体结构图。

【具体实施方式】

为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合附图，以对本发明实 施例进行清楚、完整地描述人员。

本发明实施例的目的在于突破当前DFA实现技术难以同时兼顾存储空间和匹配速度的难 题，尤其是在不牺牲匹配速度的前提下突破DFA状态数指数膨胀的问题，提供一种基于TCAM 实现DFA的方法。

实施例一

该实施例提供的一种基于TCAM的DFA的匹配方法的具体处理流程如图1所示，包括如下的 处理步骤：

步骤S101、将DFA的每个状态用若干TCAM条目表示，每个TCAM条目由源状态域、输入字符 域和目的状态域三个域组成，所述源状态域和目的状态域由副本ID域和私有ID域两个子域组 成。

DFA可采用TCAM实现。TCAM作为一种高速并行查找引擎，已广泛部署于各种高速网络设备 中，用于IP地址查找和基于包头的包分类等网络应用。TCAM存储单元可存储“0”、“1”、 “*”三种状态的比特值，其中，比特值“*”表示“不关心状态”，即既可以是“0”也可以 是“1”。TCAM芯片由一定数目的TCAM条目(entry)组成。每个时钟周期内，TCAM并行地将 所有条目与搜索关键词(search key)进行比较，在所有满足匹配条件的条目中，TCAM返回 第一个条目作为输出。TCAM的输出将作为新的搜索关键词的一部分，继续参与下一次匹配。 由于TCAM能存储“*”的模糊匹配能力，使得TCAM能有效存储和压缩DFA的存储空间；由于TCAM 的并行查找能力，使得TCAM每执行一次DFA状态转换，只需要一次TCAM时钟周期，从而保证了 不牺牲DFA的匹配速度。基于TCAM实现DFA，有望同时兼顾存储空间和匹配速度两大难题。

当上述输入字符采用ASCI I字符时，因为ASCI I字符有256个，所有每个状态对应256个TCAM 条目。在实际应用中，上述“出发状态”域和“输入字符”域可以是由“0”、“1”和“*” 组成的字符串，“到达状态”域可以是“0”和“1”组成的字符串。

上述DFA可能是由正则表达式规则编译得到，也可能是由字符串规则编译得到，甚至别的 任何方式得到。

本发明实施例将DFA的每个状态用若干TCAM条目表示，每个TCAM条目由源状态域”、“输 入字符域”和“目的状态域”三个域组成。表示同一状态的TCAM条目的“出发状态”相同。 “源状态域”、“输入字符域”存储在TCAM中，“目的状态域”存储在附属的SRAM中。

所述源状态域和目的状态域由副本ID域和私有ID域两个子域组成。

步骤S102、基于生成所述DFA的非确定性有穷状态自动机NFA中的链式结构，以及所述NFA 和所述DFA之间的内在链式结构特征，识别出所述DFA中的链式结构。

定义NFA的“ε边”，它是不消耗任何输入字符转移到新状态的边；

定义“ε-NFA”，它是存在着ε边的NFA；

根据所述DFA所表达的正则表达式构建一个“ε-NFA”和与之等价的DFA，识别NFA中的“链 式”结构，根据NFA中的链式结构和NFA和DFA之间的内在“链式”结构特征，识别NFA的链式 结构在DFA中的副本，该副本即为DFA中的链式结构。具体处理过程如下：

步骤1、根据所述DFA所表达的正则表达式构建一个ε-NFA和与之等价的DFA；

步骤2、识别所述ε-NFA中的链条；

找到所有的NFA链首状态，即无任何非ε入边的NFA状态；

依次从每个NFA链首状态出发开始扩展链条：如果当前NFA状态有一条非ε出边到达下一 个NFA状态，且下一个NFA状态没有ε边指向该链条上已经扩展的状态，则扩展链条至下一个 NFA状态，并将下一个NFA状态作为当前状态，继续按上述方法扩展链条；否则，停止扩展该 链条；

每个NFA链条都赋予一个唯一的链条ID；

步骤3、由ε-NFA构造一个标准的状态数最小化的DFA，并且记录每个DFA状态的NFA子集；

步骤4、若当前DFA状态的子集包含某个NFA链条的链首并且当DFA状态尚未标记过，则 将此DFA状态标记为当前NFA链条的ID，且将该NFA链条的链首作为当前NFA状态，开始扩展一 个新的DFA链条，将此DFA链条标记为当前NFA链条的ID，其步骤如下：

若当前NFA状态不存在一条非ε出边到达下一个NFA状态，则结束本次迭代；否则，对于 这条非ε出边上的字符集，检查以下条件是否同时满足：

当前DFA状态对其中超过或等于一半的的字符都存在一条出边到达同一个新的不在当前 DFA链表上的DFA状态，称这个新的DFA状态为“下一个DFA状态”；

下一个DFA状态的子集包含了下一个NFA状态；

下一个DFA状态不是自循环状态；

下一个DFA状态与当前DFA状态的相似度超过一定的阈值(128)；

若以上条件不能同时满足，则结束本次迭代；否则，扩展DFA链条至下一个DFA状态，将 下一个DFA状态作为当前DFA状态，将下一个NFA状态作为当前NFA状态；

若当前DFA状态尚未标记过，则将其标记为当前NFA链条的ID，同时将当前DFA链条标记为 当前NFA链条的ID，重复本次迭代的步骤；

步骤5、每个DFA链条上的状态都被标记为某个NFA链条的ID，称这些状态为“注册状态”； 不属于任何DFA链条的DFA状态则被称之为“未注册状态”。

步骤S103、基于上述NFA和DFA之间的内在链式结构特征，对DFA状态进行编号，同时建立 状态间的“模板”关系。

定义NFA的“组合边”，它是将所有从同一个NFA状态出发，到达同一个目的NFA状态，但 代表不同输入字符的出边组合而成的一条边，该组合边上的输入字符为一个字符集，为所有 组合前的边上的输入字符的集合，下述文字中提到到的NFA的边均指组合边；

定义“NFA链条”，它由若干NFA状态组成，除链尾状态外，链条上的每个状态均通过唯 一的非ε出边转移到链条上的下一个状态，链条上的所有状态从链首到链尾形成链式的有序 的结构；

定义“DFA状态的NFA子集”，根据NFA到DFA的转化关系，一个DFA状态本质上代表的是 原NFA所有状态的集合的一个子集，这个NFA子集称之为该“DFA状态的NFA子集”，或简称 为该“DFA状态的子集”；

定义“DFA链条”，它是一条NFA链条在DFA中的一份副本，即它的链首的子集包含NFA 链条的链首，沿着相同的输入字符串，从它的链首出发直到链尾并且同步地从NFA链条的链首 出发直到链尾，它的下一个状态的子集始终包含NFA链条的下一个状态；

定义“自循环状态”，它是转移到自身的出边的数目超过了一定的阈值的状态，阈值大 小为10；

定义DFA状态i和的DFA状态j之间的“共享边”和“非共享边”，若对于某个输入字符， 状态i和状态j各有一条出边经过该字符转移到某个相同的目的状态，则这两条出边是状态i 和状态j之间的“共享边”；若对于某个输入字符，状态i和状态j各有一条出边经过该字符 转移到不同的目的状态，则状态i的这条出边是关于状态j的“非共享边”，且状态j的这条 出边是关于状态i的“非共享边”；

定义两个DFA状态的“相似度”，它的取值是这两个DFA状态之间的共享边的数目；

定义DFA状态间的“模板”关系，模板关系是一种单向的关系，每个DFA状态至多只有一 个模板状态，若状态i以状态j为模板，则状态i在TCAM中只需要存储其关于状态j的非共享边；

定义DFA状态的“副本ID”，它用于区分来源于同一个NFA链条的不同DFA链条副本上的DFA 状态；

定义DFA状态的“私有ID”，它用于区分DFA链条内部来源于不同NFA状态的DFA状态；

每个DFA状态均用一对状态ID进行编号，即副本ID和私有ID组成的状态对，每个DFA状态 有且仅有唯一的(副本ID，私有ID)对；

识别NFA中的所有链条及这些NFA链条在DFA中复制产生的的副本链条，根据NFA链条上的 状态和它们的副本DFA链条上的状态之间的对应关系，为每个DFA状态分配一个唯一的(副本 ID，私有ID)对，并且为除自循环状态以外的每一个DFA状态分配一个模板状态。

该实施例提供的一种基于NFA链条和DFA链条为DFA状态分配状态ID对的方法包括：

A、为“自循环状态”分配ID对：自循环状态各自分配一个唯一的副本ID，且分配一个相 同的私有ID，即0，以下步骤开始递增分配私有ID，自循环状态的ID对不受下述步骤影响；

B、为“注册状态”分配副本ID：每个DFA链条都被标记为某个NFA链条的ID，若DFA链条 上的状态也被标记为此相同的NFA链条ID，则这个状态称之为该DFA链条的“成员状态”，每 次迭代处理一条DFA链条，其步骤如下：

对每个DFA链条，找出与其上所有的成员状态“相似度”之和最大的自循环状态，如果该 自循环状态的副本ID已被分配给某个DFA链条作为其上所有成员状态的副本ID，且该DFA链条 与当前DFA链条被标记为相同的NFA链条ID，则将当前DFA链条上的所有成员状态标记为“未注 册状态”，并结束本次迭代；

分配该自循环状态的副本ID作为链条上所有成员状态的副本ID；

为“注册状态”分配私有ID，其迭代步骤如下：同时考虑所有被标记为同一个NFA链条ID 的DFA链条，每个DFA链条上的注册状态本质上是这个NFA链条上某个状态的副本，所有对应同 一个NFA状态的DFA成员状态，若它们同为非接收状态状态或者接收的规则完全一致，则被分 配一个新的相同的私有ID；

为“未注册状态”分配副本ID，每个未注册状态均被预先分配一个“深度”值，即从起 始状态开始到达该未注册状态的所经历的最少的状态转移步数，自循环状态的深度为0，将 所有的自循环状态和未注册状态组织成多个树，每个树都以一个自循环状态为根，每个未注 册状态仅能以深度更小的状态作为父结点，树上边的权重为边所连通的两个状态之间的“相 似度”，首先为每一个自循环状态生成一个树，作为树根，然后依次迭代按深度从小到大处 理每一个未注册状态：

若当前状态与某个树中的深度更小的状态共享的边数最多，则将当前状态加入到这个树 中，并以树中这个深度更小共享边数最多的状态为父结点；

将树根的副本ID分配给当前状态作为其副本ID；

为“未注册状态”分配私有ID：每个未注册状态依次分配一个新的私有ID。

该实施例提供的一种为DFA状态分配“模板”状态的方法包括：

全部的DFA状态被划分成多个状态集合，每个集合包含的是全部拥有相同“私有ID”的状 态，且该集合以这个私有ID命名；

定义“亲属状态”，如果两个状态分属于两个状态集合，且它们共享相同的副本ID，则 它们互为彼此的亲属状态；

定义两个状态集合的“相似度”，它的取值是两个状态集合间所有的亲属状态之间的相 似度之和；

对于私有ID为K的状态集合，若私有ID为J的状态集合同时满足下述条件，则状态集合K 的所有状态都各自选择它们在状态集合J中的亲属状态作为模板状态：

J＜K；

对于集合K中的每一个状态，其在集合J中都存在一个亲属状态；

在所有满足上述两个条件的候选状态集合中，集合J与集合K的相似度最大；

私有ID为0的状态，即自循环状态，不为之分配模板。

步骤S104、基于上述DFA的状态编号方法和状态间的模板关系，在TCAM中对DFA状态进行 编码。

基于所述重新编号后的所述DFA的状态和所述DFA状态间的模板关系，在TCAM中对DFA状态 进行重新编码。

定义字符串之间的“匹配”和“覆盖”关系，给定两个由比特“0”、“1”或“*”组成 的字符串，分别记为T和P，如果字符串T和P的长度一样，且对于每一位比特，T在该位上的比 特值等于脏该位上的比特值或者脏该位上的比特值为“*”，则称字符串T“匹配”字符串P， 且称字符串P“覆盖”字符串T；

每一个在DFA中出现的副本ID，其在TCAM中均有唯一的副本ID编码；

每一个在DFA中出现的私有ID，其在TCAM中均有唯一的私有ID编码；

每一个DFA状态，其在TCAM中均有有唯一的(副本ID编码，私有ID编码)对；

对于存在“模板”关系的两个DFA状态i和j，若状态i以状态j为模板，则状态j的私有ID 编码覆盖状态i的私有ID编码。

该实施例提供的一种在TCAM中对副本ID和私有ID进行编码的方法包括：

1、对副本ID进行编码：

无论注册状态还是非注册状态，它们的副本ID都是某个自循环状态的副本ID，故只需对 自循环状态的副本ID进行编码；

对DFA中对所有的自循环状态的子集取并集，副本ID编码的长度即为该并集的大小，即在 副本ID编码中为并集中的每个NFA状态分配一位比特；

对每一个自循环状态，若其子集中的NFA状态出现在此并集中，其比特位置“1”，否则 置“0”；

对在所有副本ID编码中取值总是相同的多个比特位，可只编码其中的一位。

2、对私有ID进行编码：

DFA状态间的模板关系将所有的DFA状态组织成多个树，每个树均以一个自循环状态作为 根，每个状态均以它的模板状态为父结点；

为每个私有ID分配一个“子编码”，如果一个状态有N个子结点，则这N个子结点所需的 子编码比特数为每个子结点分配一个长度为n的互不相同的子编码；全“0” 的编码保留不分配，叶子结点的子编码为空；私有ID相同的状态分配的子编码必须相同；

每个状态的私有ID的编码即为它所有祖先结点的子编码与自身子编码的拼接，即从树根 开始到每个状态，该状态的初始私有ID编码为空，沿途依次在后面拼接上所访问的父结点的 子编码，最后拼接上该状态的子编码，作为该状态的私有ID编码；

为使私有ID编码的长度一致，取最长的私有ID编码的长度，在所有的私有ID编码后面拼 接上全“*”以扩展到统一的最长的长度。

步骤S105、基于上述TCAM中的状态编码方法，在TCAM中对DFA的状态转移边进行编码。

TCAM的源状态域由“副本ID域”和“私有ID域”两个子域组成，分别用于存储源状态的 副本ID编码和私有ID编码；

TCAM的源状态域允许存储比特“*”，能够被搜索关键词中的比特“0”或“1”匹配，因 此在不改变TCAM的语义的前提下，源状态域可以将其存储的状态编码的部分比特位置“*”；

TCAM的目的状态域由“副本ID域”和“私有ID域”两个子域组成，“副本ID域”用于存 储目的状态的副本ID编码和源状态的副本ID编码的异或结果，“私有ID域”用于存储目的状 态的私有ID编码；

TCAM的目的状态域仅存储比特“0”或“1”；

TCAM的搜索关键词由源状态域和输入字符域拼接而成，其中源状态域由副本ID域和私有 ID域组成，TCAM的搜索关键词仅包含比特“0”或“1”；

一条DFA状态转移边都可以表示为一个TCAM条目，DFA状态转移边由三部分组成，即源状 态域，输入字符域和目的状态域；源状态域在TCAM中编码成该状态的副本ID的编码和私有ID 的编码的连接，输入字符域在TCAM中编码成该字符的ASCII二进制码，目的状态域在TCAM中 编码为源状态的副本ID编码(若该编码中包含比特*，则将比特*替换成比特0)和目的状态的 副本ID编码(若该编码中包含比特*，则将比特*替换成比特0)的异或结果与私有ID的编码的 连接；

给定搜索关键词，TCAM返回对应的目的状态域，对于目的状态域中的副本ID域，须将它 的值替换为搜索关键词中的副本ID域的值与目的状态域中的副本ID域的值进行异或的结果；

每个DFA状态只需存储它关于其模板状态的非共享边，若一个状态没有模板状态，则它需 要存储其全部的状态转移边；

存在模板关系的两个DFA状态生成的TCAM条目之间的顺序如下：若状态i以状态j为模板， 则状态i的状态转移边都必须存储在状态j的状态转移边之前，反之若状态j以状态i为模板， 则状态j的状态转移边都必须存储在状态i的状态转移边之前；

不存在模板关系的两个DFA状态生成的TCAM条目之间的顺序是任意的。

步骤S106、对TCAM条目进行压缩。

状态内的TCAM条目压缩：根据不同的TCAM条目共享相同的目的状态域、源状态域，对输 入字符域进行合并，从而减少单个状态所占用的TCAM条目；其过程如下：若存在共享相同的 目的状态域、源状态域的两个条目i和j且i和j的输入字符域只相差一个比特，则在条目i的输 入字符域中，将与条目j相差的比特位的值置为“*”，删除条目j，如此反复直到不存在这样 的两个条目为止；

状态间的TCAM条目压缩：根据不同的TCAM条目共享相同的目的状态域、输入字符域、源 状态域的私有ID域，对源状态域的副本ID域进行合并，从而减少不同状态所占用的TCAM条目； 其过程如下：若存在共享相同的目的状态域、输入字符域、源状态域的私有ID域的两个条目i 和j且i和j的源状态域的副本ID域只相差一个比特，则在条目i的副本ID域中，将与条目j相差 的比特位的值置为“*”，删除条目j，如此反复直到不存在这样的两个条目为止；在上述过 程中未参与压缩的条目，改变其异或标志位，可再执行一次状态间压缩。

步骤S107、将源状态域和输入字符域的拼接构成TCAM的搜索关键词，按照所述搜索关键 字在所述DFA的所有TCAM条目中进行搜索，获取搜索得到的目的状态域。

TCAM的搜索关键词由源状态域和输入字符域拼接而成，其中源状态域由副本ID域和私有 ID域组成，TCAM的搜索关键词仅包含比特“0”或“1”。

按照所述搜索关键字在所述DFA的所有TCAM条目中进行搜索，获取搜索得到的目的状态 域，一次DFA状态转换只需要一次TCAM并行查找即可完成。将所述目的状态域中的副本ID域的 值与所述搜索关键词中的副本ID域的值进行异或，将所述异或结果作为所述目的状态域中的 最终的副本ID域的值。

以下实施例均采用两个正则表达式ab[^h]*cd的和ef[^h]*c[hH]进行说明，按照正则表 达式的书写规则，正则表达式ab[^h]*cd用于识别如下特征的字符串：首先匹配ab，接下来是 除字符h以外的任意多个字符，接下来是cd；正则表达式ef[^h]*c[hH]用于识别如下特征的 字符串：首先匹配ef，接下来是除字符h以外的任意多个字符，接下来是字符c，接下来是字 符h或者H。这两个正则表达式匹配的字符串可以出现在输入文本中的任意位置。

实施例二

使用Thompson算法将正则表达式转化为一个标准的NFA，并随后使用子集构造法以及 Hopcroft算法将这个NFA转化成一个状态数最少的DFA。

图2所示是用于匹配正则表达式ab[^h]*cd的和ef[^h]*c[hH]的NFA，圆圈为NFA状态， 箭头为NFA的状态转移边。状态0是起始状态，状态13和状态14是接收状态，接收状态用双圈 表示。

定义NFA的“ε边”，它是不消耗任何输入字符转移到新状态的边；图2中的状态0、状态 5、状态6、状态7和状态8有ε边；

定义“ε-NFA”，它是存在着ε边的NFA；图2的NFA即为一个ε-NFA；

定义NFA的“组合边”，它是将所有从同一个NFA状态出发，到达同一个目的NFA状态，但 代表不同输入字符的出边组合而成的一条边，该组合边上的输入字符为一个字符集，为所有 组合前的边上的输入字符的集合，下述文字中提到到的NFA的边均指组合边；如图2中的状态 12有一条到状态14的边，边上的字符集为{h，H}，图2中的状态5有一条到状态7的边，边上的 字符集为除字符h以外的所有字符的集合；

定义“NFA链条”，它由若干NFA状态组成，除链尾状态外，链条上的每个状态均通过唯 一的非ε出边转移到链条上的下一个状态，链条上的所有状态从链首到链尾形成链式的有序 的结构；图2中有4个NFA链条：由状态1、状态3和状态5组成的链条，状态1经过非ε出边(识 别字符a)转移到状态3，状态3经过非ε出边(识别字符b)转移到状态5，这个链条记为 其余三个NFA链条分别为由状态2、状态4和状态6组成的链条由状 态9、状态11和状态13组成的链条由状态10、状态12和状态14组成的链条

图3所示是用于匹配正则表达式ab[^h]*cd的和ef[^h]*c[hH]的DFA，圆圈为DFA状态， 箭头为DFA的状态转移边，DFA状态分别用整数ID从0到15表示。状态0是起始状态，状态9、状 态11、状态12、状态14和状态15是接收状态，接收状态用双圈表示。

定义“DFA状态的NFA子集”，根据NFA到DFA的转化关系，一个DFA状态本质上代表的是 原NFA所有状态的集合的一个子集，这个NFA子集称之为该“DFA状态的NFA子集”，或简称为 该“DFA状态的子集”，DFA状态的子集可以在NFA转化为DFA的子集构造过程中记录下来；图 4所示的是图3中的DFA状态与它们所对应的NFA子集，图4第一列为DFA状态，第四列为“DFA 状态的子集”；

定义“DFA链条”，它是一条NFA链条在DFA中的一份副本，即它的链首的子集包含NFA 链条的链首，沿着相同的输入字符串，从它的链首出发直到链尾并且同步地从NFA链条的链首 出发直到链尾，它的下一个状态的子集始终包含NFA链条的下一个状态；

如图3，状态0、状态1和状态3构成一个DFA链条，记为它是NFA链条在DFA中的一个副本，对比图4可知，DFA状态0、DFA状态1和DFA状态3的NFA子集分别包含了NFA 状态1、NFA状态3和NFA状态5，且它们通过相同的字符串ab连接成为链式结果；状态4、状态7 和状态10也构成一个DFA链条，记为它是NFA链条的另一个副本；

定义“自循环状态”，它是转移到自身的出边的数目超过了一定的阈值的状态，阈值的 大小为10；如图3，状态0、状态3、状态4和状态10为DFA的自循环状态，以粗线圆圈表示；

定义DFA状态i和的DFA状态j之间的“共享边”和“非共享边”，若对于某个输入字符， 状态i和状态j各有一条出边经过该字符转移到某个相同的目的状态，则这两条出边是状态i 和状态j之间的“共享边”；若对于某个输入字符，状态i和状态j各有一条出边经过该字符 转移到不同的目的状态，则状态i的这条出边是关于状态j的“非共享边”，且状态j的这条 出边是关于状态i的“非共享边”；

定义两个DFA状态的“相似度”，它的取值是这两个DFA状态之间的共享边的数目；

定义DFA状态间的“模板”关系，模板关系是一种单向的关系，每个DFA状态至多只有一 个模板状态，若状态i以状态j为模板，则状态i在TCAM中只需要存储其关于状态j的非共享边；

如图3，虚线箭头表示状态间的模板关系用，虚线箭头到达端的状态为虚线箭头起始端的 状态的“模板”状态，从状态出发的实线箭头表示该状态关于其模板状态的“非共享边”， 例如状态1有一条虚线箭头到达状态0，表示状态1以状态0为模板，状态1关于状态0只有一条 “非共享边”，即实线箭头表示的经过字符b转移到状态3的边；

定义DFA状态的“副本ID”，它用于区分来源于同一个NFA链条的不同DFA链条副本上的DFA 状态；

图4的第二列所示为DFA状态的副本ID，如为区分DFA副本链条中的状态1和DFA 副本链条中的状态7，状态0和状态7分配了不同的副本ID；

定义DFA状态的“私有ID”，它用于区分DFA链条内部来源于不同NFA状态的DFA状态；

图4的第三列所示为DFA状态的私有ID，如为区分DFA链条中的状态5和状态9， 它们分配了不同的私有ID；

每个DFA状态均用一对状态ID进行编号，即副本ID和私有ID组成的状态对，每个DFA状态 有且仅有唯一的(副本ID，私有ID)对；如图4所示，每个状态都分配了唯一的(副本ID，私 有ID)对。

实施例三

该实施例提供的一种识别NFA中的链条的方法包括：

找到所有的NFA链首状态，即无任何非ε入边的NFA状态；如图2，状态1、状态2、状态9、 状态10可以作为链首状态；

依次从每个链首状态出发开始扩展链条：如果当前NFA状态有一条非ε出边到达下一个 NFA状态，且下一个NFA状态没有ε边指向该链条上已经扩展的状态，则扩展链条至下一个NFA 状态，并将下一个NFA状态作为当前状态，继续按上述方法扩展链条；否则，停止扩展该链条； 如从图2中的链首状态1出发开始扩展链条，状态1有一条非ε出边到达状态3，且状态3无ε边， 故扩展链条至状态3；状态3经过字符b扩展只状态5；状态5尝试扩展至状态7，但状态7有ε边 指向链条上的状态5，故停止扩展链条；最终得到的链条为

每个NFA链条都赋予一个唯一的链条ID。

图2中最终可识别出四个NFA链条：可依次分配链条ID为0、1、2、3。

实施例四

该实施例提供的一种根据NFA链条识别DFA中的链条的方法包括：

若当前DFA状态的子集包含某个NFA链条的链首并且当DFA状态尚未标记过，则将此DFA 状态标记为当前NFA链条的ID，且将该NFA链条的链首作为当前NFA状态，开始扩展一个新的DFA 链条，将此DFA链条标记为当前NFA链条的ID；

如图3所示，从状态0开始遍历，由图4可知状态0的子集为{0，1，2}，包含了NFA链条 的链首状态1和NFA链条的链首状态2，故以状态0为链首，依次扩展这 两个NFA链条在DFA中的副本链条的链首状态，以下步骤以扩展的NFA链条的副本链 表为例进行说明，将状态0标记为NFA链条的ID(值为0)，且将正在扩展的DFA副 本链条标记为NFA链条ID(值为0)；

其步骤如下：

若当前NFA状态不存在一条非ε出边到达下一个NFA状态，则结束本次迭代；否则，对于 这条非ε出边上的字符集，检查以下条件是否同时满足：

当前DFA状态对其中超过或等于一半的的字符都存在一条出边到达同一个新的不在当前 DFA链表上的DFA状态，称这个新的DFA状态为“下一个DFA状态”；

图3中的状态0经过字符a到达下一个状态(状态1)；

下一个DFA状态的子集包含了下一个NFA状态；

图3中的状态1的子集为{0，1，2，3}，包含了NFA链条的下一个状态3；

下一个DFA状态不是自循环状态；

图3中的状态1不是自循环状态；

下一个DFA状态与当前DFA状态的相似度超过一定的阈值(128)；

图3中的状态1与状态0的相似度为255，超过了阈值；

若以上条件不能同时满足，则结束本次迭代；否则，扩展DFA链条至下一个DFA状态，将 下一个DFA状态作为当前DFA状态，将下一个NFA状态作为当前NFA状态；

在图3中，链条从状态0经过字符a的转移边扩展至状态1；

若当前DFA状态尚未标记过，则将其标记为当前NFA链条的ID，同时将当前DFA链条标记为 当前NFA链条的ID，重复本次迭代的步骤；

图3中的状态1标记为NFA链条ID为0；

重复迭代步骤，当状态1通过字符b检查能否扩展到状态3时，由于状态3是自循环状态， 故该链条未扩展至状态3(状态3未被标记)。为便于说明，本实施例以及下文仍将由状态0 和状态1组成的链条记作DFA链条若其上的状态被标记的NFA链条ID与该链条被标 记的链条ID一致，则这个状态属于该链条，否则不属于。其他链条也采用上述同样的方式标 记；

每个DFA链条上的状态都被标记为某个NFA链条的ID，称这些状态为“注册状态”；不属 于任何DFA链条的DFA状态则被称之为“未注册状态”。

在图3中，当依次识别出DFA链条和后，开始从状态4为链首扩展NFA链条的副本链 表，当扩展至状态8之后，状态8对应于NFA链条上的状态12，NFA状态12到达下一个NFA状态14 的转移边上的字符集为[hH]，按ASCII值从小到大检查字符集[hH]中的字符，确定其中一 半的字符(即字符H)到达下一个状态(状态11)，故链条扩展至状态11，从而继续扩展得到 DFA链条

图3中可识别出八个DFA链条：依次被标记为NFA链条ID 为0、1、2、1、0、3、2、3。状态0、1和状态4、7被标记为NFA链条ID 0，状态2和状态6被标 记为NFA链条ID 1，状态3、5、9和10、13、14被标记为NFA链条ID 2，状态8、11和状态13、 15被标记为NFA链条ID 3。DFA中唯一的未注册状态为状态12，未被标记为任何NFA链条ID，其 余状态为注册状态。

实施例五

该实施例提供的一种为每个DFA状态分配一个唯一的(副本ID，私有ID)对的方法包括：

图5所示的是经过状态重新分配ID后的DFA，每个状态均有一个唯一的(副本ID，私有ID) 对，如图5所示，每个状态用两位数字标识，从左起第一位数字为该状态的副本ID，第二位数 字为该状态的私有ID。

为“自循环状态”分配ID对：自循环状态各自分配一个唯一的副本ID，且分配一个相同 的私有ID，即0，以下步骤从1开始递增分配私有ID，自循环状态的ID对不受下述步骤影响；

图4中四个自循环状态0、3、4、10在图5中依次分配ID对为(0，0)、(1，0)、(2，0)、 (3，0)；

为“注册状态”分配副本ID：每个DFA链条都被标记为某个NFA链条的ID，若DFA链条上的 状态也被标记为此相同的NFA链条ID，则这个状态称之为该DFA链条的“成员状态”，每次迭 代处理一条DFA链条，其步骤如下，以图4中的链条为例，该链条被标记为NFA 链条ID 0，链条上的成员状态为0和1：

对每个DFA链条，找出与其上所有的成员状态“相似度”之和最大的自循环状态，如果该 自循环状态的副本ID已被分配给某个DFA链条作为其上所有成员状态的副本ID，且该DFA链条 与当前DFA链条被标记为相同的NFA链条ID，则将当前DFA链条上的所有成员状态标记为“未注 册状态”，并结束本次迭代；

如果两个DFA链条上的成员状态都与某个自循环状态的相似度之和最大，且这两个DFA链条被 标记为相同的NFA链条ID，会导致两个链条上的状态在随后的过程中被分配相同的副本ID和私 有ID，为保征ID对的唯一性，故将其中一条链条的成员状态转化为未注册状态；图4中的状态 0和1与自循环状态0之间的相似度之和最大，且自循环状态0的副本ID尚未被分配给其他任何 链条；

分配该自循环状态的副本ID作为链条上所有成员状态的副本ID；图4中的状态0的副本ID (值为0)被分配给状态3作为它的副本ID；

为“注册状态”分配私有ID，其迭代步骤如下：同时考虑所有被标记为同一个NFA链条ID 的DFA链条，每个DFA链条上的注册状态本质上是这个NFA链条上某个状态的副本，所有对应同 一个NFA状态的DFA成员状态，若它们同为非接收状态状态或者接收的规则完全一致，则被分 配一个新的相同的私有ID；

在图4中，同时考虑被标记为NFA链条ID为0的两个DFA副本链条：和 状态1和状态7被共同分配了私有ID 1；同时考虑被标记为NFA链条ID为2的两 个DFA副本链条：和状态5和状态13被共同分配了私有ID 2，状 态9和状态14都是接收规则ab[^h]*cd的接收状态，被共同分配了私有ID 3；同时考虑被标记 为NFA链条ID为1的两个DFA副本链条：和状态2和状态6被共同分配 了私有ID 4；同时考虑被标记为NFA链条ID为3的两个DFA副本链条：和 状态8被分配了私有ID 5，状态11和状态15都是接收规则ef[^h]*c[hH]的 接收状态，被共同分配了私有ID 6；

为“未注册状态”分配副本ID，每个未注册状态均被预先分配一个“深度”值，即从起 始状态开始到达该未注册状态的所经历的最少的状态转移步数，自循环状态的深度为0，将 所有的自循环状态和未注册状态组织成多个树，每个树都以一个自循环状态为根，每个未注 册状态仅能以深度更小的状态作为父结点，树上边的权重为边所连通的两个状态之间的“相 似度”，首先为每一个自循环状态生成一个树，作为树根，然后依次迭代按深度从小到大处 理每一个未注册状态：

若当前状态与某个树中的深度更小的状态共享的边数最多，则将当前状态加入到这个树 中，并以树中这个深度更小共享边数最多的状态为父结点；

将树根的副本ID分配给当前状态作为其副本ID；

图4的DFA只有一个未注册状态(状态12)，状态12和自循环状态0的相似度最大，故状态 12加入到以状态0为根的树中；

为“未注册状态”分配私有ID：每个未注册状态依次分配一个新的私有ID。图4的状态7 分配了一个新的私有ID 7。

通过以上步骤，图4的状态都分配了一个唯一的(副本ID，私有ID)对，如图5的状态标 志所示，也如图3的第二列和第三列所示。

实施例六

该实施例提供的一种为DFA中的状态分配“模板”状态的方法包括：

全部的DFA状态被划分成多个状态集合，每个集合包含的是全部拥有相同“私有ID”的状 态，且该集合以这个私有ID命名；

如图6所示，图5中的全部DFA状态被划分成8个状态集合，分别命名为集合0～7，每个圆 圈代表一个状态集合，圆圈内部标志为该集合的私有ID，该集合包含的状态标注于圆圈的上 方或下方，DFA状态采用和图5一样的标注方式，即用两位数字表示，第一位数字表示状态的 副本ID，第二位数字表示状态的私有ID；

定义“亲属状态”，如果两个状态分属于两个状态集合，且它们共享相同的副本ID，则 它们互为彼此的亲属状态；

图5和图6中的状态00、01、04、07互为亲属状态；状态10、12、13、14互为亲属状态； 状态20、21、25、26互为亲属状态；状态30、32、33、36互为亲属状态；

定义两个状态集合的“相似度”，它的取值是两个状态集合间所有的亲属状态之间的相 似度之和；

如图6中的状态集合1与状态集合0之间的相似度为：亲属状态01与00的相似度之和加上亲 属状态21与20的相似度，状态集合0中的状态00和30由于在状态集合1中不存在对应的亲属状 态，故不参与状态集合1与状态集合0之间的相似度的计算；

对于私有ID为K的状态集合，若私有ID为J的状态集合同时满足下述条件，则状态集合K 的所有状态都各自选择它们在状态集合J中的亲属状态作为模板状态：

J＜K；

对于集合K中的每一个状态，其在集合J中都存在一个亲属状态；

在所有满足上述两个条件的候选状态集合中，集合J与集合K的相似度最大；

本实例中，状态集合1～7中的状态均选择状态集合0中的状态作为模板状态，如图6所示， 虚线表示状态间的模板关系；

私有ID为0的状态，即自循环状态，不为之分配模板。

以上实例说明了如何利用NFA和DFA的内在链式结构特征，为DFA的状态重新分配ID(副本 ID和私有ID)，并确定状态间的模板关系。完成如上准备之后，以下实例说明如何在TCAM中 对状态进行编码，如何将DFA存储到TCAM中以及如何压缩TCAM的条目数。

实施例七

该实施例提供的一种在TCAM中存储图5中的状态00的转移边的方法包括：

如图7所示，DFA的状态转移边存储在一个TCAM和一个与之附属的SRAM中，一个“TCAM条 目”由存储在TCAM中的“源状态域”、“输入字符域”和存储在附属的SRAM中的“目的状态 域”所组成；“源状态”域和“读入字符”域是由“0”、“1”和“*”组成的字符串，“目 的状态”域是“0”和“1”组成的字符串。

用TCAM存储该DFA，在不经过任何压缩的情况下，每个状态需要256个TCAM条目(因为ASCII 字符有256个)，由于TCAM可以存储“*”，使得TCAM可以用较少的条目数表示一个状态的转 移边。图5中的状态00经字符a到达目的状态01，经字符e到达目的状态04，经其它字符均返回 自身。

为清晰表示，下文中，状态在TCAM中的编码均以下划线标注。虽然TCAM存储的是比特“0”、 “1”、“*”，附属的SRAM中存储的是比特“0”和“1”，但为方便表示，下文中的文字说 明以及附图中，状态ID的编码有时会简写为状态的ID值，输入字符的编码有时简写为输入字 符的值，下划线标记的即为编码形式的值。TCAM条目用“(源状态ID或其编码)(读入字符 值或其ASCII编码)→(目的状态ID或其编码)”，其中编码形式用下划线表示，如图7中 的第一个TCAM条目，记为“100 000 a→2”。

假定已知状态00的编码为“100 000”，状态01的编码为“100 001”，状态04的编码为 “100 100”，则如图7所示，只需要3个TCAM条目即可表示状态00的转移边。

将DFA的源状态编码和输入字符编码拼接作为TCAM的搜索关键词，在所有匹配的条目中， TCAM返回最高(即最前)的结果(存储在附属的SRAM中的对应的目的状态编码)，一次DFA 状态转换只需要一次TCAM并行查找；如图7所示，假定在DFA的匹配过程中，当前状态为00， 根据输入字符分三种情况：若输入字符为a，则搜索关键词为“100 001 a”，在TCAM中并行 查找，搜索关键词会同时匹配第一个条目和第三个条目，TCAM返回第一个条目，输出存储在 SRAM中的结果“100 001”，即状态01；若输入字符为e，则搜索关键词为“100 001 e”，在 TCAM中并行查找，搜索关键词会同时匹配第二个条目和第三个条目，TCAM返回第二个条目， 输出存储在SRAM中的结果“100 100”，即状态04；若输入字符为a和e以外的任意字符，则在 TCAM中并行查找，搜索关键词仅匹配第三个条目，TCAM返回存储在SRAM中的结果“100 000”， 即状态00。

用TCAM存储DFA，使得状态转换可以通过TCAM的并行查找来完成，而且一次状态转换仅需 要一次并行查找。图7只是一个引子，用于说明TCAM如何存储单个DFA状态的转移边，TCAM更 具体的结构将在后面的实施例中说明。

实施例八

该实施例提供的一种在TCAM中对副本ID和私有ID进行编码的方法包括：

对副本ID进行编码：

无论注册状态还是非注册状态，它们的副本ID都是某个自循环状态的副本ID，故只需对 自循环状态的副本ID进行编码；对图5中的状态，只需对自循环状态00、10、20、30的副本ID 0、1、2、3进行编码；

对DFA中对所有的自循环状态的子集取并集，副本ID编码的长度即为该并集的大小，即在 副本ID编码中为并集中的每个NFA状态分配一位比特；如图3所示，对图5中的四个自循环状态 00、10、20、30的子集取并集，即{0，1，2，5，6，7，8，9，10}，按NFA状态ID从小到大， 为其中每一个NFA状态分配一位比特，则副本ID编码长度为9；

对每一个自循环状态，若其子集中的NFA状态出现在此并集中，其比特位置“1”，否则 置“0”；

由图3知，状态00的NFA子集为{0，1，2}，则其副本ID编码为“111000000”，类似的， 状态10的副本ID编码为“111101010”，状态20的副本ID编码为“111010101”，状态30的 副本ID编码为“111111111”；

对在所有副本ID编码中取值总是相同的多个比特位，可只编码其中的一位； 在上一个步骤分配的四个副本ID编码中，状态0，1，2总是同时出现在编码中，类似的，状态 5，7，9以及状态6，8，10也总是同时出现在编码，故只需为每一组状态分配一个编码即可， 最终自循环状态00、10、20、30的副本ID 0、1、2、3分别编码为“100”、“110”、“101”、 “111”，如图8所示；

对私有ID进行编码：

DFA状态间的模板关系将所有的DFA状态组织成多个树，每个树均以一个自循环状态作为 根，每个状态均以它的模板状态为父结点；

为每个私有ID分配一个“子编码”，如果一个状态有N个子结点，为了区分这N个子结点 以及它们的父结点，所需的子编码比特数为每个子结点分配一个长度为 n的互不相同的子编码；全“0”的编码保留不分配，叶子结点的子编码为空；私有ID相同的 状态分配的子编码必须相同；

为保证私有ID相同的状态分配相同的子编码，可基于图6所示的状态集合之间的模板状态 进行编码，图6所示共8个结点，一个根结点和7个叶子结点，故需要个比特， 私有ID为1～7的状态分别被分配子编码001～111；

每个状态的私有ID的编码即为它所有祖先结点的子编码与自身子编码的拼接，即从树根 开始到每个状态，该状态的初始私有ID编码为空，沿途依次在后面拼接上所访问的父结点的 子编码，最后拼接上该状态的子编码，作为该状态的私有ID编码；

为使私有ID编码的长度一致，取最长的私有ID编码的长度，在所有的私有ID编码后面拼 接上全“*”以扩展到统一的最长的长度。

如图9所示，每个私有ID均分配了三位比特的编码，其中私有ID 0补齐“*”得到一个全 “*”的编码。

实施例九

图10所示为对图5的整个DFA进行编码后的TCAM，该实施例提供的一种在TCAM中对DFA状态 转移边进行编码的方法包括：

TCAM条目的源状态域存储在TCAM部分，由“副本ID域”和“私有ID域”两个子域组成， 分别用于存储源状态的副本ID编码和私有ID编码；

TCAM条目的源状态域允许存储比特“*”，能够被搜索关键词中的比特“0”或“1”匹配， 因此在不改变TCAM的语义的前提下，源状态域可以将其存储的状态编码的部分比特位置“*”；

TCAM条目的目的状态域存储在附属的SRAM中，由“副本ID域”和“私有ID域”两个子域 组成，“副本ID域”用于存储目的状态的副本ID编码和源状态的副本ID编码的异或结果，“私 有ID域”用于存储目的状态的私有ID编码；

TCAM的目的状态域仅存储比特“0”或“1”；

TCAM的搜索关键词由源状态域和输入字符域拼接而成，其中源状态域由副本ID域和私有 ID域组成，TCAM的搜索关键词仅包含比特“0”或“1”；

一条DFA状态转移边都可以表示为一个TCAM条目，DFA状态转移边由三部分组成，即源状 态，输入字符和目的状态；源状态在TCAM中编码成该状态的副本ID的编码和私有ID的编码的 连接，输入字符在TCAM中编码成该字符的ASCII二进制码，目的状态在TCAM中编码为源状态 的副本ID编码(若该编码中包含比特*，则将比特*替换成比特0)和目的状态的副本ID编码(若 该编码中包含比特*，则将比特*替换成比特0)的异或结果与私有ID的编码的连接；

如图10中的第一个条目“100 001 b→010 000 1”表示图5中的状态01经过字符b转移 到了一个目的状态10，因为异或标志位(最后一位)为“1”，需对源状态的的副本ID编码(“100”) 与目的状态的副本ID编码(“110”)做异或，异或的结果(“010”)存储在目的状态域的 副本ID域；若异或标志位为“0”，这个状态转移边将表示为“100 001 b→110 000 0”；

如图10中的第三个条目“100****→000 000 1”表示图5中的状态00经过除字符a和e 以外的任意字符转移到了自身(状态00)，目的状态域的副本ID域存储的是源状态的副本ID 编码(“100”)与目的状态的副本ID编码(“100”)的异或结果，状态00的私有ID编码是 “***”，但目的状态域只能存储比特“0”和“1”，故在目的状态域将私有ID编码中的“*” 全部替换成“0”，由于在分配私有ID编码的过程中为所有的父结点预留了全“0”的“子编 码”，故将私有ID编码中的“*”全部替换成“0”不会导致和其他状态的私有ID编码产生歧 义；

给定搜索关键词，TCAM返回对应的目的状态域，对于目的状态域中的副本ID域，须将它 的值替换为搜索关键词中的副本ID域的值与目的状态域中的副本ID域的值进行异或的结果；

如图10中的第一个条目“100 001 b→010 000 1”表示图5中的状态01经过字符b转移 到了一个目的状态，若搜索关键词匹配并输出第一个条目，根据目的状态域的异或标志位(最 后一位)为“1”，可知目的状态域的副本ID域存储的是源状态的副本ID编码与目的状态的副 本ID编码的异或结果，为获得真实的目的状态的副本ID编码，只需将搜索关键词中的副本ID 域(“100”)与目的状态的副本ID域(“010”)做异或，异或的结果(“110”)即为真实 的目的状态的副本ID编码，因此可知目的状态为图5中的状态10；

每个DFA状态只需存储它关于其模板状态的非共享边，若一个状态没有模板状态，则它需 要存储其全部的状态转移边；

图5中的状态01以状态00为模板，故状态01只需存储其关于状态00的非共享边，图10的第 一个条目即用于存储状态01的非共享边；状态00没有模板状态，故它需存储所有的256条边， 由于空间所限，无法在图10中列出状态00的所有的256个TCAM条目，故利用TCAM可以存储“*” 的能力，在图10中仅用三个条目存储状态00的所有的256条边，即图10所示的第3～5个TCAM 条目，对状态00的条目的压缩方法将在后面的实施例中予以说明；

存在模板关系的两个DFA状态生成的TCAM条目之间的顺序如下：若状态i以状态j为模板， 则状态i的状态转移边都必须存储在状态j的状态转移边之前，反之若状态j以状态i为模板， 则状态j的状态转移边都必须存储在状态i的状态转移边之前；若状态i和状态j之间不存在模 板关系，则状态i的状态转移边和状态j的状态转移边之间的顺序是任意的；

如图10所示，图5中的状态01以状态00为模板，故状态01的TCAM条目必须放置于状态00 的条目之前，其余具有模板状态的状态也遵循同样的顺序放置它们的条目；

不存在模板关系的两个DFA状态生成的TCAM条目之间的顺序是任意的。

在实施例7中对状态的私有ID进行编码时，根据DFA状态间的模板关系将所有的DFA状态 组织成多个树，每个树均以一个自循环状态作为根，每个状态均以它的模板状态为父结点。 因此图5中的DFA被组织成了四棵树，对于每课树，树上所有的状态和树的根状态共享相同的 副本ID，不同树上的状态副本ID不相同。图10所示TCAM的条目划分成了四个块(此处划分为 块仅为方便说明，TCAM实际存储的条目并未划分为块)，每个块对应存储一颗树上所有状态 的转移边，自上至下起，分别存储的是根状态为图5中状态00、状态10、状态20、状态30的树 的转移边。每个块内的TCAM条目的顺序均满足“每个状态的条目放置于其模板状态的条目之 前”。

实施例十

该实施例提供的一种对TCAM条目进行压缩的方法的包括：

状态内的TCAM条目压缩：根据不同的TCAM条目共享相同的目的状态域、源状态域，对输 入字符域进行合并，从而减少单个状态所占用的TCAM条目。如图10所示，原本状态00需要存 储为所有的256个字符存储所有的256个条目，但采用状态内压缩以后，仅需第3～5个条目即 可存储状态00的所有条目，即在状态00的压缩前的256个条目中，找到出现次数最多的目的状 态域的值，即“000 000 1”，生成一个新的条目作为“默认条目”，默认条目的输入字符 域为全“*”，默认条目的目的状态域为这个出现次数最多的值(状态00的默认条目即为“100*** *→000 000 1”)，默认条目存储为最后一个条目；在原256个条目中，删去所有目的 状态域为默认条目的目的状态域的值的条目；若剩下的条目中存在如下两个条目i和j：i和j 的目的状态域相同且输入字符域只相差一个比特，则在条目i的输入字符域，将与条目j相差 的比特位的值置为“*”，删除条目j，如此反复直到不存在这样的两个条目为止。经过上述 步骤，状态00最终只需要三个条目。

状态间的TCAM条目压缩：根据不同的TCAM条目共享相同的目的状态域、输入字符域、源 状态域的私有ID域，对源状态域的副本ID域进行合并，从而减少不同状态所占用的TCAM条目；

为方便进行状态间压缩，将图10的TCAM的条目重新排序成如图11所示的TCAM条目，即将 私有ID域相同的TCAM条目放置在相邻的位置，图11的排序结果未改变TCAM的语义，因为：对 于私有ID相同的状态，根据实施例7中对私有ID编码的方法，如果它们存在模板状态，则它们 的模板状态共享相同的私有ID，故只需在排序时满足：将它们的模板状态的条目放置在它们 自身的条目之下；

状态间压缩过程如下：若存在共享相同的目的状态域、输入字符域、源状态域的私有ID域的 两个条目i和j：i和j的源状态域的副本ID域只相差一个比特，则在条目i的副本ID域中，将与 条目j相差的比特位的值置为“*”，删除条目j，如此反复直到不存在这样的两个条目为止。

图11的TCAM经过状态间压缩和状态内压缩后最终的结果如图12所示。可进一步利用异或 指示位压缩TCAM条目，所有TCAM条目的异或标志位的值初始均置为“1”，对于在状态间压缩 过程中未参与合并的条目(即不存在另一个条目与之共享相同的目的状态域、输入字符域、 源状态域的私有ID域且在源状态域的副本ID域只相差一个比特)，将它们的异或标志位的值 置为“0”，同时将它们的目的状态域的副本ID域改为直接存储目的状态的副本ID编码，之后 对图12中的TCAM再执行一次状态间压缩，结果如图13所示。

本实施例说明，对于一个状态数为16的DFA，本发明只需要14个TCAM条目即可存储，条目 数少于DFA状态数，本发明的积极效果不限于本实施例。

实施例十一

该实施例提供了一种基于TCAM的DFA的匹配装置，其具体结构如图14所示，包括如下的模 块：

DFA链式结构识别模块141，用于将DFA的每个状态用若干三态内容寻址存储器TCAM条目表 示，每个TCAM条目由源状态域、输入字符域和目的状态域三个域组成，基于生成所述DFA的非 确定性有穷状态自动机NFA中的链式结构，以及所述NFA和所述DFA之间的内在链式结构特征， 识别出所述DFA中的链式结构；

重编码处理模块142，根据所述DFA中的链式结构对所述DFA的状态进行重新编号和编码， 在TCAM中对所述DFA的状态转移边进行重新编码；

搜索匹配模块143，用于以具体的所述源状态域和输入字符域的拼接作为搜索关键词，按 照所述搜索关键字在所述DFA的所有TCAM条目中进行搜索，将搜索得到的目的状态域作为输出 结果。

具体的，所述的DFA链式结构识别模块141，还用于执行如下的步骤：

步骤1、根据所述DFA所表达的正则表达式构建一个ε-NFA和与之等价的DFA，所述ε-NFA 表示存在着ε边的NFA，所述NFA的ε边表示不消耗任何输入字符转移到新状态的边；

步骤2、识别所述ε-NFA中的链条；

找到所有的NFA链首状态，即无任何非ε入边的NFA状态；

依次从每个NFA链首状态出发开始扩展链条：如果当前NFA状态有一条非ε出边到达下一 个NFA状态，且下一个NFA状态没有ε边指向该链条上已经扩展的状态，则扩展链条至下一个 NFA状态，并将下一个NFA状态作为当前状态，继续按上述方法扩展链条；否则，停止扩展该 链条；

每个NFA链条都赋予一个唯一的链条ID；

步骤3、由ε-NFA构造一个标准的状态数最小化的DFA，并且记录每个DFA状态的NFA子集；

步骤4、若当前DFA状态的子集包含某个NFA链条的链首并且当DFA状态尚未标记过，则 将此DFA状态标记为当前NFA链条的ID，且将该NFA链条的链首作为当前NFA状态，开始扩展一 个新的DFA链条，将此DFA链条标记为当前NFA链条的ID，其步骤如下：

若当前NFA状态不存在一条非ε出边到达下一个NFA状态，则结束本次迭代；否则，对于 这条非ε出边上的字符集，检查以下条件是否同时满足：

当前DFA状态对其中超过或等于一半的的字符都存在一条出边到达同一个新的不在当前 DFA链表上的DFA状态，称这个新的DFA状态为“下一个DFA状态”；

下一个DFA状态的子集包含了下一个NFA状态；

下一个DFA状态不是自循环状态；

下一个DFA状态与当前DFA状态的相似度超过一定的阈值(128)；

若以上条件不能同时满足，则结束本次迭代；否则，扩展DFA链条至下一个DFA状态，将 下一个DFA状态作为当前DFA状态，将下一个NFA状态作为当前NFA状态；

若当前DFA状态尚未标记过，则将其标记为当前NFA链条的ID，同时将当前DFA链条标记为 当前NFA链条的ID，重复本次迭代的步骤；

步骤5、每个DFA链条上的状态都被标记为某个NFA链条的ID，称这些状态为“注册状态”； 不属于任何DFA链条的DFA状态则被称之为“未注册状态”。

具体的，所述的重编码处理模块142，还用于执行如下的步骤：

步骤6、根据所述DFA中的链式结构对所述DFA的状态进行重新编号，同时建立所述DFA状 态间的模板关系；

步骤7、基于所述重新编号后的所述DFA的状态和所述DFA状态间的模板关系，对所述DFA 的状态进行重新编码；

所述的步骤6具体包括：

TCAM的源状态域由副本ID域和私有ID域两个子域组成，分别用于存储源状态的副本ID编 码和私有ID编码；根据NFA链条上的状态和它们的副本DFA链条上的状态之间的对应关系，为 每个DFA状态分配一个唯一的(副本ID，私有ID)对；

A、为自循环状态分配ID对：自循环状态各自分配一个唯一的副本ID，且分配一个相同的 私有ID；

B、为注册状态分配副本ID：每个DFA链条都被标记为某个NFA链条的ID，若DFA链条上的 状态也被标记为此相同的NFA链条ID，则这个状态称之为该DFA链条的“成员状态”，每次迭 代处理一条DFA链条，其步骤如下：

对每个DFA链条，找出与其上所有的成员状态“相似度”之和最大的自循环状态，如果该 自循环状态的副本ID已被分配给某个DFA链条作为其上所有成员状态的副本ID，且该DFA链条 与当前DFA链条被标记为相同的NFA链条ID，则将当前DFA链条上的所有成员状态标记为“未注 册状态”，并结束本次迭代；

分配该自循环状态的副本ID作为链条上所有成员状态的副本ID；

为“注册状态”分配私有ID，其迭代步骤如下：同时考虑所有被标记为同一个NFA链条ID 的DFA链条，每个DFA链条上的注册状态本质上是这个NFA链条上某个状态的副本，所有对应同 一个NFA状态的DFA成员状态，若它们同为非接收状态状态或者接收的规则完全一致，则被分 配一个新的相同的私有ID；

为“未注册状态”分配副本ID，每个未注册状态均被预先分配一个“深度”值，即从起 始状态开始到达该未注册状态的所经历的最少的状态转移步数，自循环状态的深度为0，将 所有的自循环状态和未注册状态组织成多个树，每个树都以一个自循环状态为根，每个未注 册状态仅能以深度更小的状态作为父结点，树上边的权重为边所连通的两个状态之间的“相 似度”，首先为每一个自循环状态生成一个树，作为树根，然后依次迭代按深度从小到大处 理每一个未注册状态：

若当前状态与某个树中的深度更小的状态共享的边数最多，则将当前状态加入到这个树 中，并以树中这个深度更小共享边数最多的状态为父结点；

将树根的副本ID分配给当前状态作为其副本ID；

为“未注册状态”分配私有ID：每个未注册状态依次分配一个新的私有ID。

所述的步骤7具体包括：

每一个在DFA状态中出现的副本ID，其在TCAM中均有唯一的副本ID编码；

每一个在DFA状态中出现的私有ID，其在TCAM中均有唯一的私有ID编码；

每一个DFA状态，其在TCAM中均有唯一的副本ID编码，私有ID编码对；

对于存在模板关系的两个DFA状态i和j，若状态i以状态j为模板，则状态j的私有ID编码 覆盖状态i的私有ID编码。

具体的，所述的重编码处理模块142，还用于将TCAM的目的状态域由“副本ID域”和“私 有ID域”两个子域组成，“副本ID域”用于存储目的状态的副本ID编码和源状态的副本ID编 码的异或结果，“私有ID域”用于存储目的状态的私有ID编码；

TCAM的目的状态域仅存储比特“0”或“1”；

一条DFA状态转移边都表示为一个TCAM条目，所述TCAM条目的源状态域在TCAM中编码成该 源状态的副本ID的编码和私有ID的编码的连接，输入字符域编码成该字符的ASCII二进制码， 目的状态域编码为源状态的副本ID编码和目的状态的副本ID编码的异或结果与私有ID的编码 的连接；

每个DFA状态只需存储该DFA状态关于其模板状态的非共享边，若一个DFA状态没有模板状 态，则该DFA状态需要存储其全部的状态转移边；

存在模板关系的两个DFA状态生成的TCAM条目之间的顺序如下：若状态i以状态j为模板， 则状态i的状态转移边都必须存储在状态j的状态转移边之前，反之若状态j以状态i为模板， 则状态j的状态转移边都必须存储在状态i的状态转移边之前；

不存在模板关系的两个DFA状态生成的TCAM条目之间的顺序是任意的。

进一步地，所述的装置还可以包括：

TCAM条目缩减模块144，用于若存在共享相同的目的状态域、输入字符域、源状态域的私 有ID域的两个TCAM条目i和j，且i和j的源状态域的副本ID域只相差一个比特，则在TCAM条目i 的副本ID域中，将与TCAM条目j相差的比特位的值置为“*”，删除TCAM条目j。

应用本发明实施例的装置进行DFA匹配的具体处理过程与前述方法实施例类似，此处不再 赘述。

本领域普通技术人员可以理解实现上述实施例方法中的全部或部分流程，是可以通过计 算机程序来指令相关的硬件来完成，所述的程序可存储于一计算机可读取存储介质中，该程 序在执行时，可包括如上述各方法的实施例的流程。其中，所述的存储介质可为磁碟、光盘、 只读存储记忆体(Read-Only Memory，ROM)或随机存储记忆体(Random Access Memory，RAM) 等。

综上所述，本发明实施例通过对DFA状态ID重新编号以反映DFA中链式结构副本的特征； 最终基于重新编号的状态ID，在TCAM中通过对DFA的状态转移边进行编码和压缩，使得DFA中 的副本链式结构在TCAM中能够被合并，以达到减少存储空间的目。

本发明实施例可以在不牺牲匹配速度的前提下突破DFA状态数指数膨胀的问题，所需的 TCAM条目数能够少于DFA的状态数，从而大大减少了DFA所需的存储空间。

以上所述，仅为本发明较佳的具体实施方式，但本发明的保护范围并不局限于此，任何 熟悉本技术领域的技术人员在本发明揭露的技术范围内，可轻易想到的变化或替换，都应涵 盖在本发明的保护范围之内。因此，本发明的保护范围应该以权利要求的保护范围为准。