【java规则引擎】之Drools之Rete算法
⼀：规则引擎
--->规则引擎的核⼼是Pattern Matcher(模式匹配器)。不管是正向推理还是反向推理，⾸先要解决⼀个模式匹配的问题。
--->对于规则的模式匹配，可以定义为：⼀个规则是⼀组模式的集合。如果事实/假设的状态符合该规则的所有模式，则称为该规则是可满⾜的。模式匹配的任务就是将事实/假设的状态与规则库中的规则⼀⼀匹配，找到所有可满⾜的规则。
⼆：什么是模式匹配
对于模式匹配我们都应该不陌⽣，我们经常使⽤的正则表达式就是⼀种模式匹配。
正则表达式是⼀种“模式（pattern）”，
编程语⾔提供的“正则表达式引擎”就是Pattern Matcher。⽐如python中的re模块。
⾸先输⼊“知识”：re.compile(r'string')，
然后就可以让其匹配（match）事实（字符串）。
最后通过正则表达式引擎可以得到匹配后的结果。
对于规则匹配，通常定义如下：
条件部分，也称为LHS(left-hand side)
事实部分，也称为RHS(right-hand side)择邻而居
牛肉的英语假设系统中有N条规则，平均每个规则的条件部分有P个模式，在某个时点有M个事实需要处理。则规则匹配要做的事情就是：对每⼀个规则r，判断当前的事实o是否满⾜LHS(r)=True，如果满⾜，则将规则r的实例r(o)，即规则+满⾜该规则的事实，加到冲突集中等待处理。通常采取如下过程：
从N条规则中取出⼀条r；
从M个事实中取出P个事实的⼀个组合c；
⽤c测试LHS(r)，如果LHS(r（c）)=True，将RHS(r（c）)加⼊队列中；
苍耳的图片
如果M个事实还存在其他的组合c，goto 3；
取出下⼀条规则r，goto 2；
实际的问题可能更复杂，在规则的执⾏过程中可能会改变RHS的数据，从⽽使得已经匹配的规则实例失效或者产⽣新的满⾜规则的匹配，形成⼀种“动态”的匹配链。
三：模式匹配算法
上⾯的处理由于涉及到组合，过程很复杂。有必要通过特定的算法优化匹配的效率。⽬前常见的模式匹配算法包括Rete、Treat、Leaps，HAL，Matchbox等。
四：Rete算法
Rete算法是⽬前使⽤最⼴泛的规则匹配算法，由Charles L. Forgy博⼠在1979年发明。Rete算法是⼀种快速的Forward-Chaining推理算法，其匹配速度与规则的数量⽆关。 Rete的⾼效率主要来⾃两个重要的假设：
时间冗余性。 facts在推理过程中的变化是缓慢的, 即在每个执⾏周期中，只有少数的facts发⽣变化，因此影响到的规则也只占很⼩的⽐例。所以可以只考虑每个执⾏周期中已经匹配的facts.
转角传感器结构相似性。许多规则常常包含类似的模式和模式组。
Rete算法的基本思想是保存过去匹配过程中留下的全部信息，以空间代价来换取执⾏效率。对每⼀个模式 ，附加⼀个匹配元素表来记录WorkingMemory中所有能与之匹配的元素。当⼀个新元素加⼊到WorkingMemory时, 找出所有能与之匹配的模式, 并将该元素加⼊到匹配元素表中; 当⼀个⽆素从WorkingMemory中删除时，同样找出所有与该元素匹配的模式，并将元素从匹配元素表中删除。 Rete算法接受对⼯作存储器的修改操作描述 ，产⽣⼀个修改冲突集的动作。
Rete算法的步骤如下：
将初始数据（fact）输⼊Working Memory。
使⽤Pattern Matcher⽐较规则（rule）和数据（fact）。
如果执⾏规则存在冲突（conflict），即同时激活了多个规则，将冲突的规则放⼊冲突集合。
解决冲突，将激活的规则按顺序放⼊Agenda。
使⽤规则引擎执⾏Agenda中的规则。重复步骤2⾄5，直到执⾏完毕所有Agenda中的规则。
五：Tread算法
在 Rete算法中 ，同⼀规则连接结点上的寄存器保留了⼤量的冗余结果。实际上, 寄存器中⼤部分信息已经体现在冲突集的规则实例中。因此 ，如果在部分匹配过程中直接使⽤冲突集来限制模式之间的变量约束，不仅可以减少寄存器的数量 ,⽽且能够加快匹配处理效率。这⼀思想称为冲突集⽀撑策略。
考虑增删事实对匹配过程的影响，当向⼯作存储器增加⼀个事实时 ，冲突集中已有的规则实例仍然保留，只是将与该事实匹配的规则实例加⼊到冲突集中; 当从⼯作存储器删去⼀个事实时，不可能有新的规则实例产⽣, 只是将包含该事实的规则实例从冲突集中删去。
基于冲突集⽀撑策略和上述观察, Treat算法放弃了Rete算法中利⽤寄存器保存模式之间变量约束中间结果的思想，对于每⼀个模式 ，除保留原有 a寄存器的外 ，增加两个新链来记录与该模式匹配的增删事实,⼀个叫做增链 (addlist)，另⼀个叫做删链 (deletelist)。当修改描述的操作符为“+”时，临时执⾏部分连接任务；当修改描述的操作符为 “⼀”时，直接删去冲突集中包含该事实的规则实例。
猛龙电影
可恶的老鼠Treat算法的步骤如下：
⾏动 ：根据点⽕规则的 RHS,⽣成修改描述表 CHANGES;
模式匹配：置每⼀模式的删链和增链为空，对 CHANGES的每⼀个修改描述 ，执⾏模式匹配。对于与修改描述中的事实匹配成功的模式，若修改描述的操作符为 “+”, 将该事实加⼊这⼀模式的增链；若修改描述的操作符为 “⼀”，将该事实加⼊这⼀模式的删链。
删去事实的处理：对于任⼀模式链中的每⼀个事实，找到冲突集中所有包含该事实的规则实例，并将这⼀规则实例从冲突集中删去。相应地修改该模式的 a寄存器。
新增事实的处理：对于每⼀模式 ，若其增链⾮空 ，则将增链中的所有事实加⼊该模式的a寄存器 ，并对与新增事实相关的每⼀条规则临时执⾏部分匹配，寻找该规则新的实例。具体做法为:⾸先将第⼀个模式增链中的事实集合与后⼀模式的 a寄存器进⾏连接 , 再将部分连接结果与第三个模式的a寄存器进⾏连接 ,⼀直到所有模式均连接完成为⽌。其中 ,a寄存器的内容包括新增事实。若连接结果⾮空 ，则将找到的规则实例插⼊到冲突集中。
旅途的意义六：Leaps 算法
前向推理引擎，包括LEAPS，都包括了匹配-选择-执⾏（match-lect-action）循环。即，确定可以匹配的规则，选择某个匹配的元组，此元组相应的规则动作被执⾏。重复这⼀过程，直到某⼀状态（如没有更多的规则动作）。RETE和TREAT匹配算法速度慢的原因是，它们把满⾜规则条件的元组都实例化。Leaps算法的最⼤的改进就是使⽤⼀种"lazy"的⽅法来评估条件（conditions），即仅当必要时才进⾏元组的实例化。这⼀改进极⼤的减少了前向推理引擎的时空复杂度，极⼤提⾼了规则执⾏速度。
风流密史
Leaps算法将所有的 asrted 的 facts ，按照其被 asrted 在 Working Memory 中的顺序（ FIFO ），
放在主堆栈中。它⼀个个的检查 facts ，通过迭代匹配 data type 的 facts 集合来找出每⼀个相关规则的匹配。当⼀个匹配的数据被发现时，系统记住此时的迭代位置以备待会的继续迭代，并且激发规则结果（ conquence ）。当结果（ conquence ）执⾏完成以后，系统就会继续处理处于主堆栈顶部的 fact 。如此反复。
Leaps算法的效率可以⽐Rete算法和Tread算法⾼⼏个数量级。
七：其他算法
对于HAL算法和Matchbox算法，使⽤的范围不是很⼴，这⾥不做过多的介绍。
