Raffinement de partition

En algorithmique, le raffinement de partition est une technique pour représenter une partition d'un ensemble comme une structure de données qui permet d'affiner la partition en séparant un ensemble en plusieurs sous-ensembles. En ce sens, ce concept peut-être vu comme dual de la structure de données d'union-find, qui cherche à maintenir une partition en effectuant des opérations de fusion sur des couples d'ensembles.

Le raffinement de partition est un élément essentiel de plusieurs algorithmes efficaces, en théorie des graphes ou en théorie des automates finis, tels que la minimisation d'un automate fini déterministe, l'algorithme de Coffman–Graham pour le séquençage de tâches, ou le parcours en largeur lexicographique des graphes.

Structure de données

Un algorithme de raffinement de partition maintient à jour une famille d'ensemble disjoints S_i. À l'initialisation, cette famille contient un unique ensemble contenant tous les éléments 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.

Such an algorithm may be implemented efficiently by maintaining data structures representing the following information:

• The ordered sequence of the sets S_i in the family, in a form such as a doubly linked list that allows new sets to be inserted into the middle of the sequence
• Associated with each set S_i, a collection of its elements of S_i, in a form such as a doubly linked list or array data structure that allows for rapid deletion of individual elements from the collection. Alternatively, this component of the data structure may be represented by storing all of the elements of all of the sets in a single array, sorted by the identity of the set they belong to, and by representing the collection of elements in any set S_i by its starting and ending positions in this array.
• Associated with each element, the set it belongs to.

To perform a refinement operation, the algorithm loops through the elements of the given set X. For each such element x, it finds the set S_i that contains x, and checks whether a second set for S_i ∩ X has already been started. If not, it creates the second set and add S_i to a list L of the sets that are split by the operation. Then, regardless of whether a new set was formed, the algorithm removes x from S_i and adds it to S_i ∩ X. In the representation in which all elements are stored in a single array, moving x from one set to another may be performed by swapping x with the final element of S_i and then decrementing the end index of S_i and the start index of the new set. Finally, after all elements of X have been processed in this way, the algorithm loops through L, separating each current set S_i from the second set that has been split from it, and reports both of these sets as being newly formed by the refinement operation.

The time to perform a single refinement operations in this way is O(Modèle:PipeXModèle:Pipe), independent of the number of elements in the family of sets and also independent of the total number of sets in the data structure. Thus, the time for a sequence of refinements is proportional to the total size of the sets given to the algorithm in each refinement step.

Applications

An early application of partition refinement was in an algorithm by Modèle:Harvtxt for DFA minimization. In this problem, one is given as input a deterministic finite automaton, and must find an equivalent automaton with as few states as possible. Hopcroft's algorithm maintains a partition of the states of the input automaton into subsets, with the property that any two states in different subsets must be mapped to different states of the output automaton. Initially, there are two subsets, one containing all the accepting states of the automaton and one containing the remaining states. At each step one of the subsets S_i and one of the input symbols x of the automaton are chosen, and the subsets of states are refined into states for which a transition labeled x would lead to S_i, and states for which an x-transition would lead somewhere else. When a set S_i that has already been chosen is split by a refinement, only one of the two resulting sets (the smaller of the two) needs to be chosen again; in this way, each state participates in the sets X for O(s log n) refinement steps and the overall algorithm takes time O(ns log n), where n is the number of initial states and s is the size of the alphabet.

Partition refinement was applied by Modèle:Harvtxt in an efficient implementation of the Coffman–Graham algorithm for parallel scheduling. Sethi showed that it could be used to construct a lexicographically ordered topological sort of a given directed acyclic graph in linear time; this lexicographic topological ordering is one of the key steps of the Coffman–Graham algorithm. In this application, the elements of the disjoint sets are vertices of the input graph and the sets X used to refine the partition are sets of neighbors of vertices. Since the total number of neighbors of all vertices is just the number of edges in the graph, the algorithm takes time linear in the number of edges, its input size.

Partition refinement also forms a key step in lexicographic breadth-first search, a graph search algorithm with applications in the recognition of chordal graphs and several other important classes of graphs. Again, the disjoint set elements are vertices and the set X represent sets of neighbors, so the algorithm takes linear time.

See also

• Refinement (sigma algebra)

References

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « https://en.wikipedia.org/wiki/Partition_refinement » (voir la liste des auteurs).