algorithme de Rete

L'algorithme de Rete est un algorithme performant de filtrage par motif (« pattern matching ») intervenant dans l'implémentation de systèmes de règles de production. L'algorithme a été conçu par Charles L. Forgy de l'université Carnegie-Mellon, tout d'abord publié comme une note de travail en 1974, puis plus tard élaboré dans sa thèse de doctorat en 1979 et dans une publication de 1982. Rete est devenu la base de nombreux systèmes experts tels que Clips, Jess, Drools, Ilog JRules, Soar...etc Une implémentation naïve d'un système expert pourrait vérifier chaque règle en la confrontant aux faits de la base de connaissance, éliminant les règles au fur et à mesure, puis passant à la règle suivante (et rebouclant à la première règle une fois terminé). Même pour des règles et des bases de connaissance de taille réduite, cette approche naïve est bien trop longue. L'algorithme de Rete (habituellement prononcé en Europe, « re-té » d'après la prononciation latine, du latin « rete » pour réseau) fournit la base pour une exécution plus efficace d'un système expert. Un système expert basé sur Rete établit un réseau des nœuds, où chaque nœud (excepté la racine) correspond à un modèle se produisant dans le « côté gauche » d'une règle. Le chemin du nœud racine à un nœud externe (leaf node) définit un « côté gauche » complet de règle. Chaque nœud a une mémoire des faits qui satisfont ce modèle. Cette structure est essentiellement un trie généralisé. Lorsque de nouveaux faits sont affirmés ou modifiés, ils se propagent le long du réseau, annotant les nœuds quand les faits correspondent au modèle. Quand un fait ou une combinaison des faits satisfait tous les modèles d'une règle donnée, un nœud externe (leaf node) est atteint et la règle correspondante est déclenchée. L'algorithme de Rete est conçu pour sacrifier la mémoire au profit de la vitesse. Dans la plupart des cas, l'augmentation de la vitesse par rapport à une implémentation naïve est de plusieurs ordres de grandeur (parce que l'exécution de Rete est théoriquement indépendante du nombre de règles dans le système). Dans les systèmes experts très grands, cependant, l'algorithme de Rete original tend à rencontrer des problèmes de consommation de mémoire. D'autres algorithmes ont depuis été conçus, d'une part basés sur Rete ou d'autre part complètement nouveaux, qui exigent moins de mémoire.