Rete Algorithm Description
By research on a week, there is a certain understanding of the rule engine. Now write something to communicate with everyone, this paper mainly describes the REE algorithm. My writing is not very good, if there is anything I have not understood or wrong, please leave a message.
First of all, my post borrowed from a very popular post, as if I came from 9cbs; there is a little, I don't want to do too much noun, because I am not a very deep person, defrauling is not very afraid. Joke.
Ok, now we start.
First introduce some posts for the regular engine.
1, from Java video network
Http://forum.javaeye.com/viewtopic.php?t=7803&postdays=0&portR=asc&Start=0
2, the most original description of the RETE algorithm, I don't know where to find it, you want people can leave E-mail.
3. A doctoral graduation papers in CMU, personal feeling very good, my many points of view come from here, people who want to send me Mail Mailto: ipointer@163.com
Next, the term is unified, and the terms in many materials are very confusing.
1. Facts facts, when we implement, there will be an fact library. Use f.
2, a model of the pattern template, the facts, all facts in all fact libraries must meet one of the templates. Expressed with P.
3, Conditions Conditions, Components of Rules. A template in the template library must also be met. Expressed with C. We can understand the relationship between FACTS, PATTERNS, and Conditions. Patterns is an interface that Conditions is a class that implements this interface, and FACTS is an instance of this class.
4, Rules rules, consisting of one to multiple conditions. Generally use the And or OR to connect Conditions. Use R.
5, Actions action, activate the action of a Rule execution. We are not discussive here.
6, there are some terms, such as: Working-Memory, Production-Memory, with the concept of the concept.
7, there are some, such as: alpha-network, beta-network, join-node, we will use it below, let go, discuss it.
Quoted on the online popular example, I don't think I understand, I will explain it with my thoughts.
Assume that there are three rules in rule memory
IF a (x) and b (x) and c (y) THEN ADD D (X)
IF a (x) and b (y) and d (x) THEN ADD E (X)
IF a (x) and b (x) and e (x) Then Delete a (x)
The RETE algorithm will first compile the rules into the following tree architecture sorting network
The work memory content and the order are {A (1), A (2), B (2), B (3), B (4), C (5)}, when the work memory is sequentially entered into the network, Preface is stored in a qualified node until the preconcentration of the premium rules is inference. In terms of the above example, finally D (2) is pushed.
Let us analyze this example.
Template library: (this example has only one template, there are different examples in the original description of the algorithm, usually we will define Facts, Patterns, Condition in the form of tuple, tuples.
P: (? A,? X) where A may represent a certain operation, such as A, B, C, D, E; X represent the parameters of the operation. Look at this template is not already described all the facts.
Category Library: (The first representative of the Yuan Group represents the actual operation, the second representative "C1: (a,
C2: (B,
C3: (C,
C4: (d,
C5: (e,
C6: (B,
UND: (Second Representative Real Parts)
F1: (a, 1)
F2: (a, 2)
F3: (b, 2)
F4: (B, 3)
F5: (B, 4)
F6: (C, 5)
Rules Library:
R1: C1 ^ C2 ^ C3
R2: C1 ^ C2 ^ C4
R3: C1 ^ C2 ^ C5
Some people may question R1: C1 ^ C2 ^ C3, not described, original:
IF a (x) and c (y) THEN ADD D (X), A = B relationship. But please take a closer look, this is already defined in the conditional library.
Below I will describe the implementation of the REE algorithm in the rule engine.
First, we have to set some rules. According to these rules, our engine can compile a tree structure, which is a simple manifestation in the picture, in fact, it is not this when it is realized.
This is the time of Beta-Network, according to Rules, we can determine Beta-Network, below, I will draw Beta-Network in this example, in order to describe, I also draw alpha-network.
In the figure above, the part of the left is Beta-Network, and the right side is Alpha-Network, the circle is join-node.
From the above figure, we can verify that in the beta-network, the contents of Rules, where R1, R2, R3 share many BM and JOIN-NODE, which is because there are common parts in these rules, so that Accelerate the speed of Match.
On the right, the alpha-network is built according to the fact library, where the Node in the ALPHA-NETWORK node is based on each Condition, engaged in the Match in the real library, this process is static, that is, during the process of compiling building networks It has been established. As long as the fact library is stable, there is no substantially change, the RETE algorithm performs efficiency should be very high, the reason is that ALPHA-NETWORK is built through static compilation. We can verify that the facts that meet C1 are indeed W1, W2.
Let's take a look at how this algorithm is running, that is, how to determine the activated Rules. Traverse from Top-Node, to a Join-Node, configured with the Node of AM for C1, run to the Match C1 node. At this time, the content of the MATCH C1 node is: W1, W2. Continue to the AM for C2 (all possible combinations should be W1 ^ W3, W1 ^ W4, W1 ^ W5, W2 ^ W3, W2 ^ W4, W2 ^ W5), because C1 ^ C2 requires the same parameters, so The content of MATCH C1 ^ C2 is: W2 ^ W3. Continue, there is a fan-out, only one join-node can be activated, because the AM next to it is only one non-empty. Therefore, only R1 is activated.
To solve the problem of low efficiency, we can use HashTable to solve this problem.
