Calculer efficacement des éléments minimaux sur des ensembles partiellement ordonnés

Question

J'ai une liste d'ensembles que je voudrais trier dans un ordre partiel basé sur la relation de sous-ensemble.

En fait, je n’exige pas la commande complète, seulement les éléments minimaux.

Si je ne me trompe pas, chaque élément minimal doit définir un composant distinct du graphique respectif - et ce composant doit être un semi-treillis.

Quel serait le moyen le plus pratique, le plus efficace en termes d'espace et de temps, de résoudre ce problème ?Peut-être existe-t-il un moyen qui ne nécessite pas de construire l’intégralité du graphique ?Peut-être existe-t-il un algorithme connu sous une meilleure terminologie que celle que j’ai naïvement décrite ci-dessus ?

Je suis conscient que les exigences de temps et d'espace sont sous-spécifiées ci-dessus, mais je serais heureux de recevoir toutes suggestions, qu'elles se révèlent optimales ou non...

Arrière-plan:Je construis actuellement une base de données graphique complète qui contient toutes les arêtes entre les ensembles, puis je recherche les nœuds qui n'ont pas de généralisations, mais c'est assez compliqué, lent et nécessite beaucoup d'espace (disque).La liste mentionnée ci-dessus contient environ 100 millions d'ensembles.

Answer 1

Une approche consiste à trier les ensembles en augmentant la taille, puis effectuez à plusieurs reprises les éléments suivants: Prenez la première définie dans la liste, de la sortie et retirez de la liste de tous les supersets. Cela émettra tous les ensembles minimaux. Le temps d'exécution est $ o (nk) $ set de comparaisons plus $ o (n \ journal n) $ étapes pour tri, où $ n $ est le nombre d'ensembles que vous avez et $ k $ est le numéro d'éléments minimaux. Ou, pour le mettre un autre moyen, si chaque ensemble contient $ M $ éléments, le temps d'exécution sera approximativement $ o ( n (k + \ journal n) m) $ étapes de base.

Pourquoi trier par taille? C'est une optimisation. Le plus petit ensemble est garanti (il n'y a pas de cardinalité plus petite dans la liste, aucun de ses sous-ensembles ne peut être dans la liste), de sorte que la taille est une astuce utile pour identifier un ensemble qui doit sûrement être minimal.

Sans tri par taille, le temps de fonctionnement du pire des cas est susceptible de finir par $ o (n ^ 2) $ set comparaisons (ou $ O (n ^ 2 m) $ étapes de base), qui est pire lorsque $ k \ ll n $ .

---

Voici une version optimisée de cet algorithme. Laissez $ M $ être une structure de données qui stocke un ensemble d'ensembles, comme une trie: par exemple, le jeu $ \ {1,3,6,7 \} $ correspond au mot 1367 $ et est stocké dans la trie en conséquence. Initialement, $ M $ est vide. Répétez les informations suivantes: Prenez le jeu suivant $ S $ de la liste; Vérifiez si un ensemble dans $ m $ est un sous-ensemble de $ s $ ; sinon, insérez $ s $ dans $ m $ ; Enfin, supprimez $ s $ dans la liste (ou avancez votre pointeur à l'élément suivant de la liste). L'opération "Check ..." peut être effectuée de manière assez efficace à l'aide d'une traversée récursive de la trie. À la fin, une fois que vous avez suivi toute la liste, la sortie $ m $ .

Le temps de fonctionnement du pire des cas de l'algorithme optimisé reste le même. En pratique, le temps d'exécution pourrait être considérablement amélioré, peut-être aussi vite que $ O (NM) $ étapes de base dans certains cas si vous avez de la chance (mais ne comptez pas dessus). Vous pouvez essayer les deux et voir qui fonctionne mieux dans la pratique sur le type de charge de travail que vous gérez.

Answer 2

J'ai trouvé une solution dans cet article, p.12.

L'algorithme mentionné ici comme preuve devrait se traduire par le code python suivant :

T = set([]);
for x in X:
    rem = set([]);
    spe = False;
    for a in T:
        rel = oracle(x,a);
        if rel == "x>a":
            spe = True;
            break;
        elif rel == "x<a":
            rem.add(a);
    if not spe:
        T -= rem;
        T.add(x);

J'attends le break être crucial pour l'exécution réelle, il pourrait donc être judicieux de trier X à l'avance pour bénéficier de pauses matinales - mais je n'en suis pas sûr.

Un autre point que je vois ici est que > est censé être irréfléchi, donc x>x ne tient pas.Mais pour ce code, ce serait mieux si c'était le cas.Si a==x, ça casse au lieu de chercher inutilement plus loin.

MISE À JOUR: J'ai maintenant pu tester différentes implémentations en Python.S'il vous plaît, permettez-moi de donner directement le code python, je pense qu'il est suffisamment similaire au pseudocode - et peut-être plus concret pour beaucoup de gens.

Voici la mise en œuvre tirée du document :

def oracle(rep1,rep2):
    if generalizes(rep2,rep1):
        return ">";
    elif generalizes(rep1,rep2):
        return "<";
    return None;

def find_min_els_(repIDs,ID2rep):
    min_els = set([]);
    for x in repIDs:
        spec_of_x = set([]);
        x_is_spec = False;
        for min_el in min_els:
            relation = oracle(ID2rep[x],ID2rep[min_el]);
            if relation == ">":
                x_is_spec = True;
                break;
            elif relation == "<":
                spec_of_x.add(min_el);
        if not x_is_spec:
            min_els -= spec_of_x;
            min_els.add(x);
    return min_els;

Maintenant, cela s'est avéré trop lent et nous pouvons déjà dire, d'après la complexité, que c'est très mauvais si la largeur de l'ordre partiel, c'est-à-dire le nombre m des éléments minimaux devrait être grand.

L’astuce consiste à rendre cet algorithme indépendant de m en évitant de passer par tous les éléments minimaux actuels.Au lieu de cela, nous pouvons profiter du fait que la recherche dans le jeu de résultats est rapide (je suppose que c'est là que le trie entre en jeu).

Pour chaque x, nous générons toutes les généralisations.Or la complexité dépend du nombre de x et de leur taille, mais pas tellement du nombre d'éléments minimaux (seulement O (n log n) ?).Mieux encore, comme nous devons désormais supprimer les éléments non minimaux de la liste initiale d'éléments au lieu de les ajouter, le temps utilisé pour chaque x diminue au lieu d'augmenter au fil de l'exécution.

Voici le code respectif :

def generalizations(spe_rep,gens):
    for el in spe_rep:
        gen_rep = spe_rep - set([el]);
        gen_str = string(gen_rep);
        if not gen_str in gens:
            gens.add(gen_str);
            yield gen_str;
            for x in generalizations(gen_rep,gens):
                yield x;

def find_min_els(repIDs,ID2rep):
    min_els = set(repIDs);
    for x in repIDs:
        for genID in generalizations(ID2rep[x],set([])):
            if genID in min_els:
                min_els.remove(x);
                break;
    return min_els;

Cela utilise une fonction génératrice generalizations() pour éviter de calculer davantage de généralisations de x une fois qu'on en a déjà trouvé dans les éléments minimaux actuels.C'est déjà assez rapide avec mes données, mais cela pourrait peut-être être amélioré en générant d'abord des généralisations plus générales (il faudra tester si cela rend plus rapide) et notamment en générant uniquement des généralisations constituées d'éléments déjà observés dans les éléments minimaux actuels.Par exemple si notre x est {a,b,c}, mais aucun élément minimal actuel n'a c dans celui-ci, nous n'avons pas besoin de générer de sous-ensemble de x cela contient c, c'est à dire.seulement {a,b},{a},{b},{}.