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.[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 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.
Nachteile
Die hohe Geschwindigkeit des Algorithmus geht zu Lasten des genutzten Speichers.
Einzelnachweise
- ↑ Charles Forgy: Rete: A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem. In: Artificial Intelligence, vol. 19, pp. 17–37, 1982.
- ↑ Vorlesungsscript zum Rete-Algorithmus (PDF; 86 kB)
- ↑ Lars Wunderlich: Java Rules Engines. Entwicklung von regelbasierten Systemen. entwickler.press, Frankfurt/Main 2006, ISBN 3-935042-75-2.