Structure de données pour définir l'intersection?

Existe-t-il une structure de données qui gère une collection d'ensembles (d'ensembles de sols finis) prenant en charge les opérations suivantes? Tout temps de fonctionnement sublinéaire sera apprécié?

1. Initiez un ensemble vide.
2. Ajoutez un élément à un ensemble.
3. Étant donné deux ensembles, indiquez s'ils se croisent.

Si chaque ensemble conserve un enregistrement des autres ensembles existants et que vous avez un total de $s > 0$ ensembles, vous pouvez facilement transformer n'importe quelle structure de données pour une collection ( par exemple, les arbres de recherche binaire, etc. ) en une où vous pouvez avoir la récupération de un élément de l'intersection de deux ensembles dans le temps $O(\log s)$ .

• Chaque ensemble doit avoir un identifiant unique provenant d'un ensemble totalement ordonné. Si vous nommez explicitement vos ensembles $S_1, S_2, \ldots$ alors l'identifiant pourrait simplement être l'index.

• Vous devez implémenter un "registre" des ensembles; une structure de données qui conserve une collection de tous les ensembles que vous avez définis. Le registre doit être implémenté sous la forme d'une structure de données d'arbre de recherche, pour permettre une récupération facile ( par exemple  si vous souhaitez supprimer l'ensemble) et une traversée en temps linéaire des ensembles.

• Chaque ensemble conserve également un "index" de chacun des autres ensembles - pas une copie d'entre eux, mais plutôt une structure de données qui est indexée par les étiquettes des autres ensembles. Cet index sera utilisé pour maintenir, pour chaque ensemble S k , un arbre de recherche binaire de tous les éléments de S j ∩ S k . (Les deux ensembles S j et S k partagent une copie de cet arbre de recherche.)$S_j$$S_k$$S_j \cap S_k$$S_j$$S_k$

Initialisation

Initialisation d'un ensemble est constitué de O ( 1 ) opérations pour initialiser l'arbre de ses éléments, O ( s ) les opérations que l' initialisation ( la copie du registre) l'indice pour l'ensemble T et O ( s log s ) opérations que vous parcourez le registre pour ajouter T dans les indices de chacun des autres ensembles S j . Dans l'index de T , nous créons des arbres de recherche représentant T ∩ S j = $T = \varnothing$$O(1)$$O(s)$$T$$O(s \log s)$$T$$S_j$$T$$T \cap S_j = \varnothing$pour les autres ensembles ; nous copions le même pointeur pour l'indice de S j .$S_j$$S_j$

Ajout d'un élément à un ensemble $T$

L'ajout de à l'ensemble T prend le temps O ( log n T ) comme d'habitude, où n T = | T | . Nous testons également l'appartenance de x dans chacun des autres ensembles S 1 , S 2 , … , ce qui prend du temps O ( log n S 1 + log n S 2 + ⋯ ) ⊆ O ( s log $x \in V$$T$$O(\log n_T)$$n_T = |T|$$x$$S_1, S_2, \ldots$ où n = | V | est la taille de l'univers (ou du plus grand ensemble S j ) et s est le nombre d'ensembles dans le registre. Pour chaque série S j de telle sorte que x ∈ S j , également insérer x dans l'index de l'ensemble S j ∩ T . Pour chacun de ces ensembles S j , il faut O ( log s + log n T ) pour rechercher S

$$O(\log n_{S_1} + \log n_{S_2} + \cdots) \subseteq O(s \log n) ,$$ $n = |V|$$S_j$$s$$S_j$$x \in S_j$$x$$S_j \cap T$$S_j$$O(\log s + \log n_T)$$S_j$dans l'indice de et insérer x dans S j ∩ T ; sur tous les ensembles S 1 , S 2 , … cela prend du temps O ( s log s + s log n T ) . Si nous supposons que le nombre d'ensembles S j est bien inférieur à la taille de l'univers V (c'est-à-dire si nous supposons s ≪ n ), le temps total pour l'insertion d'élément est alors O ( s log n $T$$x$$S_j \cap T$$S_1, S_2, \ldots$$O(s \log s + s \log n_T)$$S_j$$V$$s \ll n$$O(s \log n)$.

Si vous ne permettez pas de doublons dans les jeux, nous pouvons gagner du temps dans le cas où déjà en renonçant à l'épreuve d'adhésion et les insertions pour les autres ensembles T . "Insertion" dans le cas où x est déjà présent ne prend alors que le temps O ( log n T ) .$x \in S$$T$$x$$O(\log n_T)$

Test d'intersection

L'indice de chaque ensemble est maintenu avec précision afin de permettre une évaluation rapide de l' intersection ou non de deux ensembles et S k . Pour un ensemble S j , simplement en vérifiant son index pour l'ensemble S k , nous pouvons non seulement déterminer dans le temps O ( log s ) si S j intersecte S k , mais nous pouvons également récupérer un arbre binaire contenant l'ensemble entier S j ∩ S k .$S_j$$S_k$$S_j$$S_k$$O(\log s)$$S_j$$S_k$$S_j \cap S_k$

Suppression d'élément

Pour supprimer un élément d'un ensemble T , nous le supprimons non seulement de l'arbre de recherche de T lui-même, mais de chacune des intersections S j ∩ T pour les ensembles S j dans son index. Cela prend le temps O ( s log n T ) , où n T = | T | .$x$$T$$T$$S_j \cap T$$S_j$$O(s \log n_T)$$n_T = |T|$

Définir la suppression

En raison de la surcharge de recherche dans le registre, si vous disposez de plusieurs ensembles, il peut être souhaitable de supprimer les ensembles une fois qu'ils ne sont plus nécessaires. En parcourant l'ensemble du registre, nous pouvons supprimer de l'index de tous les autres ensembles S j dans le temps O ( s n T ) , dominé par le coût de la suppression de l'arbre de recherche représentant S j ∩ T pour chacun des autres ensembles S j , où n T = | T | .$S$$S_j$$O(sn_T)$$S_j \cap T$$S_j$$n_T = |T|$

Remarques

Si vous vous attendez à n'implémenter qu'un nombre constant d'ensembles, les temps d'exécution ci-dessus se réduisent à:

• initialisation: $O(1)$

• insertion d'élément: $O(\log n)$

• test d'intersection (et récupération de l'intersection): $O(1)$

• suppression d'élément: $O(\log n_T)$

• supprimer la définition: $O(n_S)$

où est la taille du plus grand ensemble du registre et n T = | T | pour l'ensemble T sur lequel vous opérez.$n$$n_T = |T|$$T$

Si vous vous attendez à avoir des ensembles , où V est votre univers, vous pouvez avoir besoin d'une structure de données différente si vous voulez que ces opérations fonctionnent en temps sub-linéaire. Cependant, si vous avez des paires d'ensembles dont vous savez que vous ne testerez jamais l'intersection, vous pourrez peut-être réduire la taille de l'index pour les ensembles (en n'incluant aucun ensemble dont vous allez tester l'intersection) ou utiliser plusieurs registres ( un pour chaque collection d'ensembles dont vous pourriez tester l'intersection). En fait, un registre n'est utile que si vous voulez un contrôle centralisé pour vous assurer que chaque paire d'ensembles a un enregistrement les uns des autres dans l'index: il peut être pratique dans certains cas, lors de l'initialisation d'un ensemble S , d'enregistrer simplement$O(|V|)$$V$$S$ad hoc chaque nouvel ensemble dans les indices des autres ensembles dont l'intersection avec S vous intéresse.$T$$S$

Il existe des structures de données qui vous permettent de le faire en moins de temps linéaire, même pour les entrées du pire des cas. Voir http://research.microsoft.com/pubs/173795/vldb11intersection.pdf (et les références des articles qui s'y trouvent).

Si vos deux ensembles S et T ont une grande intersection et que vous avez un dictionnaire pour S, la recherche d'éléments de T dans un ordre aléatoire devrait rapidement vous donner un élément commun. Le cas le plus difficile est lorsque la taille de l'intersection est 0 ou 1.

Habituellement, le langage de programmation de votre choix prendra en charge une structure de données avec des éléments uniques. En général, il existe trois approches populaires: les arbres, les hachages et les bitmasks. Les éléments d'arbre doivent être comparables, les éléments de hachage doivent être lavables et les éléments de masque de bits doivent avoir un moyen de conversion en entiers.

Un ensemble d'arbres prend en charge l'insertion dans O (log n) et les tests d'intersection dans le pire cas O (n log n).

Un ensemble de hachage prend en charge l'insertion dans Amortized O (1 * h) où «h» est le temps d'exécution de l'algorithme de hachage et le test d'intersection dans le pire cas O (n).

Les ensembles de masques de bits ne sont généralement pas utilisés comme des ensembles d'arbres et de hachage.

Si votre cas autorise de fausses réponses positives, j'utiliserais le filtre Bloom avec une seule fonction de hachage.

Vous pouvez l'implémenter comme suit:

Initier un ensemble vide

• $B$$n$$n$

Ajoutez un élément à un ensemble.

• $B[hash(element)]=1$

Étant donné deux ensembles (B1, B2), indiquez s'ils se croisent.

• $B1$ $AND$ $B2$ $=$ $0$

Complexité

• $n$$O(1)$