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 le Dr 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 PhD de 1979 et dans une publication de 1982. Rete est devenu la base de nombreux systèmes experts tels que Clips, Jess, JBoss Rules, et Soar.

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é « REET », « REE-tee » ou, en Europe, « re-tay » 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. On a depuis conçu d'autres algorithmes, basés sur Novel d'une part et Rete d'autre part, qui exigent moins de mémoire.

Description

L'algorithme de Rete fournit une description logique généralisée d'une implémentation de la fonctionnalité responsable de l'association des tuples de données (« faits ») contre des productions (« règles ») dans un système de production de filtrage par motif (pattern matching, une catégorie de moteur de règle). Une production se compose d'une ou plusieurs conditions et d'un ensemble d'actions qui peuvent être entreprises pour chaque ensemble complet de faits répondant aux conditions.

Des conditions testent les attributs des faits, y compris le type specifiers/identifiers. L'algorithme de Rete montre les caractéristiques principales suivantes :

• il réduit ou élimine certains types de redondance par l'utilisation du partage de nœud ;
• il stocke les correspondances partielles quand l'exécution se rejoint entre différents types de fait. Ceci, alternativement, permet à des systèmes de production d'éviter la réévaluation complète de tous les faits chaque fois que des changements sont effecués dans la « working memory » du système de production. Au lieu de cela, le système de production doit évaluer seulement les changements (deltas) dans la « working memory » ;
• il permet une libération efficace des éléments de mémoire quand des faits sont retirés de la « working memory ».

L'algorithme de Rete est largement répandu pour mettre en application la fonctionnalité de matching les moteurs de « pattern matching » qui exploitent un cycle « match-resolve-act » (« correspondre-résoudre-agir ») pour assurer le chaînage avant et l'inférence.

Alpha Network

Beta Network

Résolution de conflits

• Portail de l’informatique