Datenstruktur zum Testen aller Teilmengen einer Abfrage auf Mitgliedschaft

Gibt es eine Datenstruktur, die die folgenden Vorgänge effizient unterstützt?

1. Set hinzufügen
2. Fragen Sie ab, ob eine Teilmenge einer Menge hinzugefügt wurde.

Dies könnte mit linearem Overhead implementiert werden, indem jeder hinzugefügte Satz während jeder Abfrage getestet wird. Kann es effizienter umgesetzt werden? Kleine Wahrscheinlichkeiten für falsch positive / negative Ergebnisse sind akzeptabel (z. B. Bloom-Filter-Stil).

Angenommen, alle Ihre Mengen sind endliche Teilmengen von $\mathbb N$. Lassen$S\subseteq \mathcal P( \mathbb N)$ bezeichnen Ihre Menge von Mengen.

Sie möchten zwei Operationen:

• $O_1(S,s')$: Für jeden $s'\subseteq \mathbb N$, hinzufügen $s'$ zu $S$

• $O_2(S,s')$: Für jeden $s'\subseteq \mathbb N$, gibt es einige $s\in S$ damit $s\subseteq s'$?

Hier sind einige Ideen, um die Dinge zu beschleunigen:

• Sie werden testen, ob eine Menge eine Teilmenge einer anderen ist, also sollten Sie wahrscheinlich die Größe beibehalten $|s|$ von jedem Satz $s$ verfügbar in $O(1)$ so dass, wenn Sie testen müssen, ob $s\subseteq s'$Sie überprüfen zunächst, ob $|s|\le |s'|$und wenn nicht, können Sie sofort false zurückgeben. Und das hast du tatsächlich$|s|\le |s'|$Dann führen Sie einfach den normalen langsamen Test aus.

• Beachten Sie, dass, wenn Sie haben $s_1\in S$ und $s_2\in S$, damit $s_1\subseteq s_2$, dann wenn $s_2\subseteq s'$, Sie haben auch $s_1\subseteq s'$. Sie müssen also nicht behalten$s_2$ im $S$ zum $O_2$. So können Sie darstellen$S$ durch eine Reihe von Mengen, so dass $s\in S$ und $s\subsetneq s'$bedeutet . Mit anderen Worten, Sie müssen nur die Mengen in verfolgen , die für die Aufnahme minimal sind. Dies kann ziemlich effizient implementiert werden: Beim Hinzufügen einer Menge für alle Mengen so dass(geordnet nach zunehmendem Kardinal), wenn , dann füge nicht hinzu da es nicht minimal ist (oder bereits in ). Andernfalls addiere und dann zwischen den Mengen so dassEntfernen Sie diese so, dass (weil sie nicht mehr minimal sind).$s'\not \in S$$S$$s'$$s\in S$$|s|\le |s'|$$s\subseteq s'$$s'$$S$$s'$$s\in S$$|s'|<|s|$$s'\subseteq s$

• Behalten Sie eine Menge , die der Vereinigung aller Mengen in . Dann wird anstelle der laufenden , können Sie laufen statt (weil , wenn für einige , , dann da , und, wenn , dann ).$t$$S$$O_2(S,s')$$O_2(S,s'\cap t)$$s\in S$$s\subseteq s'$$s\subseteq t$$s\subseteq s'\cap t$$s\subseteq s'\cap t$$s\subseteq s'\cap t \subseteq s'$

Unter Berücksichtigung dieser Ideen würde ich durch ein Wörterbuch darstellen (implementiert als doppelt verknüpfte Liste von Paaren mit den Schlüsseln in aufsteigender Reihenfolge) so dass eine doppelt verknüpfte Liste ist, die genau das enthält minimale (zur Aufnahme) Mengen in von Kardinal .$S$$(key,value)$$d$$d(k)$$S$$k$

O1(S,s')
  if O2(S,s')
    return
  if d(k) doesn't exist
    d(k) := new_doubly_linked_list()
  add(d(k),s')
  S.t := union(S.t, s')
  for each key k of d so that |s'|+1 <= k
    for s in d(k)
      if subset(s', s)
        remove s

_O2(S,s')
  for each key k of d so that k <= |s'|
    for s in d(k)
      if subset(s,s')
        return true
  return false

O2(S,s')
  return _O2(S,inter(S.t,s'))

(Beachten Sie, dass Sie, obwohl ich es im Code von nicht explizit O1getan habe, eine einzelne Durchquerung der doppelt verknüpften Liste durchführen können, die darstellt d)

Ich denke nicht, dass sich dies im schlimmsten Fall zu sehr verbessert, aber im Durchschnitt sollte es so sein.