Rete-Algorithmus

Prinzipbild des Rete-Algorithmus

Der Rete-Algorithmus (rete, lat. für Netz oder Netzwerk) ist ein Algorithmus und Expertensystem zur Mustererkennung und zur Abbildung von Systemprozessen über Regeln. Er wurde vom US-amerikanischen Informatiker Charles Forgy im Rahmen seiner Doktorarbeit an der Carnegie Mellon University entwickelt bzw. die ihn 1979 zum Titel führen sollte.^[1] Der Algorithmus ist frei, da das amerikanische Verteidigungsministerium bei seiner Erstellung hinreichend mit beteiligt war.

Ziele des Algorithmus

Der Rete-Algorithmus wurde unter dem Gesichtspunkt entwickelt, eine sehr effiziente Regelverarbeitung zu gewährleisten.^[2][3] Zudem können auch große Regelsätze noch performant behandelt werden. Bei seiner Entwicklung war er den bestehenden Systemen um den Faktor 3000 überlegen.

Einsatz und Variationen

RETE bildet heutzutage die Grundlage für viele Regelsysteme wie z. B. diverse Prolog-Interpreter oder sogenannte Business Rules Engines, etwa Drools^[4], und hat sich für diese als De-facto-Standard etabliert.

Bislang gibt es zwei direkte Nachkömmlinge Rete II und Rete III. Beide sind ca. 50mal schneller als der ursprüngliche Ansatz. Rete III umfasst ein paar Erweiterungen, die seine Effizienz nochmals leicht erhöhen. Die Entwicklung war eng an die Plattform DEC XCON angelehnt und fand ihre Implementierung zunächst in OPS-Systemen, speziell in OPS2 bzw. später in OPS5. Einsparungen in Millionenhöhe wurden benannt. Das implementierte Regelwerk hatte im Endausbau ca. 10.000 Elemente.

Nachteile

Die hohe Geschwindigkeit des Algorithmus geht zu Lasten des genutzten Speichers.

Einzelnachweise

1. ↑ Charles Forgy: Rete: A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem. In: Artificial Intelligence, vol. 19, pp. 17–37, 1982.
2. ↑ www2.inf.fh-rhein-sieg.de/~pbecke2m/xps/regel2.pdf
3. ↑ Lars Wunderlich: Java Rules Engines. Entwicklung von regelbasierten Systemen. Frankfurt/M.: entwickler.press 2006. ISBN 3-935042-75-2
4. ↑ http://www.jboss.org/drools/