Raffinement de partition

Un algorithme de raffinement de partition permet de tenir à jour une famille d'ensembles disjoints S_i. À l'initialisation, cette famille contient un unique ensemble contenant tous les éléments présents dans la structure de données. À chaque étape de l'algorithme, on présente un ensemble X à l'algorithme, et chaque ensemble S_i de la famille qui contient un élément de X est séparé en deux ensembles : l'intersection S_i ∩ X et la différence S_i \ X.

Un tel algorihme peut être réalisé en maintenant à jour des structures de données représentant les informations suivantes^[4],[5]:

1. La suite ordonnée des ensembles S_i de la famille sous une forme qui permet d'insérer de nouveaux ensembles à un endroit quelconque de la suite. Cela peut-être fait par exemple à l'aide d'une liste doublement chaînée.
2. Chaque ensemble S_i comme une collection qui permet une suppression efficace des éléments de la collection. Cela peut-être fait avec une liste doublement chaînée.
3. L'ensemble auquel appartient chaque élément dans la structure de données.

Une manière alternative de représenter la seconde partie de la structure de données est de stocker tous les éléments de tous les ensembles dans un tableau simple ordonné selon l'ensemble auquel ils appartiennent, et en représentant la collection des éléments d'un sous-ensemble S_i par la position des éléments de début et de fin de ce sous-ensemble dans le tableau.

Pour réaliser l'opération de raffinement, on parcourt les éléments d'un ensemble X fixé. Pour chaque élément x de l'ensemble, on détermine l'ensemble S_i qui contient x, et on vérifie qu'aucun autre ensemble n'a été créé pour représenter S_i ∩ X. Si ce n'est pas le cas, on crée un second ensemble et on ajoute S_i à une liste L d'ensembles qui ont été séparés par l'opération.Ensuite, indépendamment de la création d'un nouvel ensemble, on retire x de S_i et on l'ajoute à S_i ∩ X. Dans la représentation où tous les éléments sont stockés dans un tableau simple, déplacer x d'un ensemble à l'autre peut être réalisé en échangeant le contenu de la cellule contenant x avec le dernier élément de S_i, puis en décrémentant l'indice de fin de S_i et l'indice de début du nouvel ensemble S_i ∩ X. Enfin, après que tous les éléments de X aient été traités de cette manière, on parcourt L et on sépare chaque ensemble courant S_i (qui devient S_i \ X) de l'ensemble S_i ∩ X créé à partir de celui-ci, et on les note comme deux nouveaux ensembles créés par l'opération de raffinement.

Le temps pour réaliser une opération de raffinement de cette manière est en O(|X|). Il est indépendant du nombre d'éléments présents dans la famille d'ensembles, ainsi que du nombre total d'ensembles présents dans la structure de données. Par conséquent, le temps pour réaliser une suite de raffinements est proportionnel à la taille totale des ensembles passés en argument à l'algorithme à chaque étape du raffinement.

Une des premières applications du raffinement de partition figure dans l'algorithme de minimisation des automates finis déterministes d'Hopcroft (1971)^[6]. Dans ce problème, l'entrée de l'algorithme est un automate fini déterministe dont on cherche à trouver un automate équivalent ayant un nombre minimum d'états.L'algorithme d'Hopcroft tient à jour une partition des états de l'automate en sous-ensembles, en conservant la propriété que deux états quelconques appartenant à différents ensembles doivent correspondre à des états différents de l'automate en sortie.À l'initialisation, on a deux sous-ensembles, un contenant tous les états d'acceptation de l'automate, et l'autre contenant les états restants.À chaque étape, on choisit un des sous-ensembles S_i et l'un des symboles d'entrée x de l'automate; les sous-ensembles d'états sont raffinés en états pour lesquels la transition étiquetée x mènent à S_i et les états pour lesquels la transition étiquetée x mènent ailleurs.Lorsqu'un ensemble S_i qui a déjà été choisi est séparé par un raffinement, seul le plus petit ensemble des deux sous-ensembles créés doit être choisi à nouveau. Ainsi, chaque état participe aux ensembles X pour O(s log n) étapes de raffinement, et la totalité de l'algorithme prend un temps en O(ns log n), où n est le nombre d'états initiaux et s la taille de l'alphabet^[6].

Sethi (1976)^[7] applique le raffinement de partition à une implémentation de l'algorithme de Coffman-Graham pour le séquençage de tâches parallèle. Sethi montre qu'on peut l'utiliser pour réaliser un tri topologique en ordre lexicographique d'un graphe dirigé acyclique donné en temps linéaire. Cet ordonnancement est une des étapes-clefs de l'algorithme de Coffman-Graham.Dans cette application, les éléments des ensembles de nœuds du graphe en entrée et les ensembles X utilisés dans le raffinement de partition sont les ensembles de voisins des nœuds.Comme le nombre total de voisins de l'ensemble des nœuds du graphe est le nombre de liens du graphe, l'algorithme est en temps linéaire du nombre de liens^[7].

Le raffinement de partition est aussi une étape-clef du parcours en largeur lexicographique, un algorithme de parcours de graphe applicable à la détection des graphes cordaux et plusieurs autres classes de graphes importantes. Ici aussi, les éléments des ensembles sont les nœuds du graphe et l'ensemble X représente l'ensemble des voisins, donc l'algorithme est en temps linéaire en le nombre de liens du graphe^[8],[9].