Datenstruktur für Schnittmenge festlegen?

Gibt es eine Datenstruktur, die eine Sammlung von Mengen (von endlichen Mengen) verwaltet, die die folgenden Operationen unterstützt? Jede sublineare Laufzeit wird geschätzt?

1. Initiere ein leeres Set.
2. Fügen Sie einem Set ein Element hinzu.
3. Geben Sie bei zwei Sätzen an, ob sie sich überschneiden.

Wenn in jeder Gruppe eine Aufzeichnung darüber geführt wird, welche anderen Gruppen vorhanden sind, und Sie insgesamt Gruppen haben, können Sie jede Datenstruktur für eine Sammlung ( z. B. binäre Suchbäume usw. ) auf einfache Weise in eine Datenstruktur umwandeln, auf die Sie zugreifen können ein Element der Schnittmenge zweier Mengen in der Zeit O ( log s ) .$s > 0$$O(\log s)$

• Jeder Satz sollte eine eindeutige Kennung von einem vollständig bestellten Satz haben. Wenn Sie Ihre Mengen explizit benennen , könnte der Bezeichner nur der Index sein.$S_1, S_2, \ldots$

• Sie sollten eine "Registrierung" der Sätze implementieren; eine Datenstruktur, die eine Sammlung aller von Ihnen definierten Mengen verwaltet. Die Registrierung sollte als Suchbaum-Datenstruktur implementiert werden, um ein einfaches Abrufen ( z. B.  wenn Sie die Menge löschen möchten) und ein lineares Durchlaufen der Mengen zu ermöglichen.

• Jede Menge auch einen "Index" jeder der anderen Mengen - keine Kopie davon, sondern eine Datenstruktur, die durch die Bezeichnungen der anderen Mengen indiziert wird. Dieser Index wird verwendet, um für jede Menge S k einen binären Suchbaum aller Elemente von S j ≤ S k zu führen . (Die beiden Mengen S j und S k teilen sich eine Kopie dieses Suchbaums.)$S_j$$S_k$$S_j \cap S_k$$S_j$$S_k$

Initialisierung

Initialisierung eines Satzes besteht aus O ( 1 ) Operationen des Tree seiner Elemente zu initialisieren, O ( s ) Operationen wie Sie initialisieren ( das Kopieren aus der Registrierung) der Index für den Satz T und O ( s log s ) Operationen, während Sie die Registrierung durchlaufen, um T zu den Indizes jeder der anderen Mengen S j hinzuzufügen . Im Index von T erstellen wir Suchbäume, die T ∩ S j = $T = \varnothing$$O(1)$$O(s)$$T$$O(s \log s)$$T$$S_j$$T$$T \cap S_j = \varnothing$für die anderen Mengen ; Wir kopieren den gleichen Zeiger für den Index von S j .$S_j$$S_j$

Hinzufügen eines Elements zu einer Menge $T$

Das Addieren von zu der Menge T benötigt wie üblich die Zeit O ( log n T ) , wobei n T = | T | . Wir testen auch die Zugehörigkeit von x in jeder der anderen Mengen S 1 , S 2 , ... , die Zeit 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$ wobei n = | V | ist die Größe des Universums (oder der größten Menge S j ) und s ist die Anzahl der Mengen in der Registrierung. Fügen Sie für jede Menge S j, so dass x ∈ S j ist , auch x in den Index für die Menge S j ∩ T ein . Für jeden solchen Satz S j , nimmt diese O ( log s + log n T ) Zeit, zu sehen 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$im Index von und x in S j ∩ T einzufügen ; über alle Mengen S 1 , S 2 , ... hinweg dauert dies Zeit O ( s log s + s log n T ) . Wenn wir annehmen, dass die Anzahl der Mengen S j viel kleiner ist als die Größe des Universums V (dh wenn wir annehmen, dass s ≪ n ist ), beträgt die Gesamtzeit für das Einfügen des Elements 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)$.

Wenn Sie keine Duplikate in Sets ermöglichen, können wir die Zeit in dem Fall , dass speichern bereits durch den Verzicht auf die Mitgliedschaft Tests und Einfügungen für die anderen Sätze T . "Einfügen" in dem Fall, dass x bereits vorhanden ist, dauert dann nur noch O ( log n T ) .$x \in S$$T$$x$$O(\log n_T)$

Schnittpunktprüfung

Der Index jedes Satzes wird genau beibehalten, um eine schnelle Beurteilung zu ermöglichen, ob sich zwei Sätze und S k schneiden oder nicht . Für eine Menge S j können wir , indem wir einfach ihren Index für die Menge S k prüfen , nicht nur in der Zeit O ( log s ) bestimmen, ob S j S k schneidet oder nicht , sondern wir können auch einen Binärbaum abrufen, der die gesamte Menge enthält S j ∩ S k .$S_j$$S_k$$S_j$$S_k$$O(\log s)$$S_j$$S_k$$S_j \cap S_k$

Elemententfernung

Um ein Element aus einer Menge T zu löschen , entfernen wir es nicht nur aus dem Suchbaum für T selbst, sondern aus jedem der Schnittpunkte S j ∩ T für die Mengen S j in seinem Index. Dies dauert Zeit O ( s log n T ) , wobei n T = | T | .$x$$T$$T$$S_j \cap T$$S_j$$O(s \log n_T)$$n_T = |T|$

Löschung einstellen

Aufgrund des mit dem Durchsuchen der Registrierung verbundenen Aufwands ist es möglicherweise wünschenswert, Sätze zu löschen, sobald sie nicht mehr benötigt werden. Durch die gesamte Registrierung durchlaufen, können wir löschen aus dem Index aller anderen Sätze S j in der Zeit O ( s n T ) , dominiert von den Kosten für das Löschen der Suchbaum darstellt S j ∩ T für jedes der anderen Sätze S j mit n T = | T | .$S$$S_j$$O(sn_T)$$S_j \cap T$$S_j$$n_T = |T|$

Bemerkungen

Wenn Sie nur mit einer konstanten Anzahl von Sätzen rechnen, reduzieren sich die oben genannten Laufzeiten auf:

• Initialisierung: $O(1)$

• Elementeinfügung: $O(\log n)$

• Kreuzungstest (und Abruf der Kreuzung): $O(1)$

• Elemententfernung: $O(\log n_T)$

• Löschung festlegen: $O(n_S)$

Dabei ist die Größe der größten Menge in der Registrierung und n T = | T | für den Satz T, an dem Sie arbeiten.$n$$n_T = |T|$$T$

$O(|V|)$$V$$S$$T$$S$

Es gibt Datenstrukturen, mit denen Sie dies auch bei Eingaben im ungünstigsten Fall in weniger als linearer Zeit tun können. Siehe http://research.microsoft.com/pubs/173795/vldb11intersection.pdf (und die dort angegebenen Artikel).

Wenn Ihre beiden Mengen S und T einen großen Schnittpunkt haben und Sie ein Wörterbuch für S haben, sollten Sie schnell ein gemeinsames Element finden, indem Sie die Elemente von T in zufälliger Reihenfolge nachschlagen. Der schwierigste Fall ist, wenn die Schnittmenge 0 oder 1 ist.

Normalerweise unterstützt Ihre Programmiersprache eine Datenstruktur mit eindeutigen Elementen. Im Allgemeinen gibt es drei gängige Ansätze: Bäume, Hashes und Bitmasken. Tree-Elemente müssen vergleichbar sein, Hash-Elemente müssen hashbar sein und Bitmask-Elemente müssen eine Art Umwandlung in Ganzzahlen aufweisen.

Ein Tree-Set unterstützt das Einfügen in O (log n) und das Testen von Schnittpunkten in Worst Case O (n log n).

Ein Hash-Set unterstützt das Einfügen in Amortized O (1 * h), wobei 'h' die Laufzeit des Hash-Algorithmus ist, und den Schnittpunkttest in Worst Case O (n).

Bitmaskensätze werden im Allgemeinen nicht wie Baum- und Hash-Sätze verwendet.

Wenn Ihr Fall falsch positive Antworten zulässt, würde ich Bloom Filter mit einer einzelnen Hash-Funktion verwenden.

Sie können es wie folgt implementieren:

Initiere ein leeres Set

• $B$$n$$n$

Fügen Sie einem Set ein Element hinzu.

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

Geben Sie bei zwei Sätzen (B1, B2) an, ob sie sich überschneiden.

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

Komplexität

• $n$$O(1)$