Rete-Algorithmus

In diesem Artikel fehlen noch folgende wichtige Informationen:

Eine sprachliche Beschreibung des Algorithmus; das Prinzipbild alleine ist nicht aussagekräftig genug

Hilf der Wikipedia, indem du sie recherchierst und einfügst.

Der Rete-Algorithmus (lateinisch rete ‚Netz‘, ‚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, der ihn 1979 zum Titel führen sollte. Der Algorithmus ist frei, da das amerikanische Verteidigungsministerium bei seiner Erstellung hinreichend mit beteiligt war.

Prinzipbild des Rete-Algorithmus

Ziele des Algorithmus

Der Rete-Algorithmus wurde unter dem Gesichtspunkt entwickelt, eine sehr effiziente Regelverarbeitung zu gewährleisten. 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 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. 50-mal 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.

Drools ist ein Beispiel für eine Business-Rule-Engine, die auf dem Rete-Algorithmus basierte. Mittlerweile (ab Version 6.0) ist in Drools ein Nachfolge Algorithmus (PHREAK) aktiv.

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. Vorlesungsscript zum Rete-Algorithmus (PDF; 86 kB)
3. Lars Wunderlich: Java Rules Engines. Entwicklung von regelbasierten Systemen. entwickler.press, Frankfurt/Main 2006, ISBN 3-935042-75-2.
4. Webseite der Business-Rule-Engine Drools