avec P. BAZET (DEA [Baz92]) Nous avons élaboré un nouvel algorithme de compilation du filtrage d'arbres
avec règle de priorité spécifique et n
uds d'arité variable décrits par
des constructeurs commutatifs [Baz92]. Ces deux caractéristiques
distinguent ce travail de ceux qu'on trouve habituellement dans la
littérature.
A partir des modèles d'entrée, cet algorithme produit une représentation
intermédiaire dans laquelle chaque modèle d'entrée est représenté par un
ou plusieurs modèles incompatibles, ce qui permet de se ramener au cas de
modèles d'arité fixe. Ensuite, il construit un arbre de décision
représentant les différentes étapes du filtrage, optimisé pour minimiser le
temps d'exécution. En particulier, à chaque étape de filtrage où c'est
possible, il détermine un index, c'est-à-dire un des fils du n
ud
courant qu'il faut absolument examiner pour déterminer quel modèle filtre
l'arbre. La méthode employée est une amélioration et une adaptation à la
priorité spécifique de celle de PUEL et SUAREZ. Nous conjecturons
que ce nouvel algorithme est au moins aussi efficace en temps et en place que
ses prédécesseurs.
Cet algorithme a été encapsulé dans un module aux interfaces bien définies et faciles à utiliser, écrit en C. Ce travail forme la base du micro-système de transformation d'arbres que nous avons développé dans le cadre du projet COMPARE mais n'est pas limité à cette application.