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.

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Partition refinement » (voir la liste des auteurs).