论文导读：Rete算法是一个快速的模式匹配算法，它通过形成一个Rete网络进行模式匹配，利用基于规则的系统的两个特征，即时间冗余性（Temporalredundancy）和结构相似性（structural similarity），提高系统模式匹配效率。这里，σ作用在某个模式的结果称为模式实例，σ作用在整个规则的结果称为规则实例。3、模式匹配算法的任务是：给定规则库，根据工作存储器的当前状态，通过与规则模式的匹配，把可满足规则送入冲突集，把不可满足的规则从冲突集中删去。
关键词：Rete算法，智能防火墙，规则，快速，匹配
Rete算法是一个快速的模式匹配算法，它通过形成一个Rete网络进行模式匹配，利用基于规则的系统的两个特征，即时间冗余性（Temporalredundancy）和结构相似性（structural similarity），提高系统模式匹配效率。
一、模式匹配的基本概念
1、可满足规则：一个规则称为可满足的，若规则的每一模式均能在当前工作存储器中找到可匹配的事实，且模式之间的同一变量能取得统一的约束值。形式化地说，规则
if P1,P2,…Pmthen A1,A2,…An
称为可满足的，若存在一个通代σ，使得对每一个模式Pi，在工作存储器中有一个元素Wi满足
Piσ=Wii=1,2,3 …m
这里，σ作用在某个模式的结果称为模式实例，σ作用在整个规则的结果称为规则实例。在专家系统中，可满足的规则称为标志规则。
2、冲突集：由全体规则实例构成的集合称为冲突集，也称上程表。免费论文参考网。
3、模式匹配算法的任务是：给定规则库，根据工作存储器的当前状态，通过与规则模式的匹配，把可满足规则送入冲突集，把不可满足的规则从冲突集中删去。
二、Rete算法的依据和基本思想
Rete算法快速匹配的重要依据是：
1、时间冗余性。免费论文参考网。工作存储器中的内容在推理过程中的变化是缓慢的，即在每个执行周期中，增删的事实只占很小的比例，因此，受工作存储器变化而影响的规则也只占很小的比例。由产生式系统的折射性，只要在每个执行周期中记住哪些事实是已经匹配的，需要考虑的就仅仅是修改的事实对匹配过程的影响。
2、结构相似性。许多规则常常包含类似的模式和模式组。
Rete算法的基本思想是：保存过去匹配过程中留下的全部信息，以空间代价来换取产生式系统的执行效率。
三、Rete匹配网络结构与过程
Rete算法的核心是建立Rete匹配网络结构，其由模式网络和连接网络两部分构成。其中，模式网络记录每一模式各域的测试条件，每一测试条件对应于网络的一个域结点，每一模式的所有域结点依次连起来，构成模式网络的一条匹配链。
Rete网络匹配过程由模式网络上的模式匹配和连接网络上的部分匹配构成。在模式网络的机器内部表示中，我们把共享一个父结点的所有结点表示成一条共享链。同时，把每一模式匹配链中的结点表示成一条下拉链，于是，每一结点由共享链和下拉链指向其后继结点，模式网络就是一棵可以使用典型遍历算法进行测试的二叉树。
四、智能防火墙Rete算法设计
Rete快速匹配算法，函数Rete设计为:取IP地址、端口号各部分折叠、异或运算后，以Rete长度取模。免费论文参考网。算法如下(无关或部分无关称为集合A，相关、包含相等和相等的称为集合B):
1、Addr=sa+da sa:源地址 da:目的地址
2、Port=sp+dp sp:源端口号 dp:目的端口号
int Rete(long addr, int port)
{int addrxor,key；\地址折叠异或
addrxor=(addr&～(～0﹤﹤16))∧((addr﹥﹥16)&～(～0﹤﹤16))；
key=addrxor∧port； \与端口异或
return(key % max)； }\max为Rete表长度
防火墙初始化时，首先从规则集A用该散列函数构造Rete表R为
Void Initialization(RULE-SET A){
FOR(r∈A)DO{ \r为每条规则
idx=Rete(r.addr,r.port)；
R[idx]=&r； \R代表规则集合A
}}
因为Rete表的长度有限，但是如果设计太大会浪费存储空间，也降低了查找速度，所以免不了会出现冲突。解决冲突的方法是:如果两条规则经过散列后落到同一位置，则把这两条规则按照插入顺序组成一个链表结构。主要算法如下:
if(R[Rete(r.addr,r.port)]=NULL)\R为Rete表,r为规则
R[Rete(r.addr,r.port)]=&r；\没有冲突，则插入Rete表
Else{J=R[Rete(r.addr,r.port)]；\冲突解决方法
while (j->next!=NULL) {j=j->next；} \插入链表末尾
j->next=&r;}
数据包匹配流程：当防火墙收到一个数据包以后，用算法Match查找规则集(A和B)。
Match(IP-Packet p) { \p为数据包
Int idx=Rete(p.addr,p.port) ； \首先用Rete算法查找A类规则
IF (R[idx].addr≧p.addr&& R[idx].port=p.port) \找到匹配规则
return R[idx] ；
Else {int idex I =halfquery(p.addr) ； \利用折半查找索引表
J=L[indexl] ； \L代表规则集合B
While(j!=NULL){\顺序匹配找到的规则链
IF (Matchrule(p)) return j； \ Matchrule为规则匹配函数
Else j=j->next；
}}
Return(Norulematch)；
}
参考文献：
[1] 闫丽萍，潘正运. RETE算法的改进与实现.微计算机信息，2006 (36）
[2] 庞伟正，金瑞琪，王成武. 一种规则引擎的实现方法.哈尔滨工程大学学报，2005(03)
[3] 江建国，张景中. 基于Rete算法的几何自动推理系统. 四川大学学报（工程科学版）， 2006(03)
|
