Suchen einer Teilmenge einer Menge in einer Sammlung von Mengen

Welche Datenstrukturen würden Sie empfehlen, die eine Sammlung von Teilmengen von und die folgenden Vorgänge unterstützen? $\{1, \dots, n\}$

$insert(S)$ : Fügt in die Sammlung ein. $S$
$query(S)$ : Gibt true zurück, wenn in der Sammlung vorhanden ist, so dass , andernfalls false. $S'$ $S' \subset S$

Mein Hauptkriterium wäre die praktische Zeiteffizienz.

ds.data-structures Caleb Poucher
quelle

Empfehlung erfordert Kriterien. Was sind Ihre Kriterien? Zum Beispiel Einfachheit, Raum oder Zeit? Je spezifischer Sie sind, desto wahrscheinlicher erhalten Sie Antworten, die für Sie nützlich sind.

Tsuyoshi Ito

Sie haben Recht, danke, dass Sie darauf hingewiesen haben. Mein Hauptkriterium wäre die praktische Zeiteffizienz.

Caleb Poucher

Wissen Sie, wie viele Einfügungen Sie im Verhältnis zur Anzahl der Abfragen vornehmen werden? Es ist möglich, eine enorme Datenstruktur (exponentielle Größe in

) zu erstellen , mit der Sie eine Menge

-Zeit abfragen können. Wenn andererseits

die Gesamtzahl der eingefügten Teilmengen ist, können Sie eine naive Suche ohne zusätzlichen Speicher in

-Zeit durchführen. Alles dazwischen, denke ich, wird ein Kompromiss sein.

n

$n$

S

$S$

O (n)

$O(n)$

m

$m$

O (n m)

$O(nm)$

James King

Die Anzahl der Abfragen ist viel größer als die der Einfügungen (möglicherweise um den Faktor

). Ich habe überlegt, die Mengen als Punkte in

darzustellen und Bereichsbäume zu verwenden, aber es würde auch zu einer Größe führen, die in

exponentiell ist . Ich frage mich, ob es eine Möglichkeit gibt, den Exponentialfaktor in

für Einfügungen und den linearen Faktor in

für Abfragen zu vermeiden .

100

$100$

{0, 1}^{n}

$\{0,1\}^n$

n

$n$

n

$n$

m

$m$

Caleb Poucher

Haben Sie eine Vorstellung davon, was

und

könnten?

n

$n$

m

$m$

James King

Antworten:

Ihr Problem klingt für mich sehr nach Information Retrieval (IR). Dort haben Sie eine Sammlung von Wortsätzen (auch als Dokumente bezeichnet) und möchten nicht nur die Existenz finden, sondern auch alle Sätze / Dokumente, die die Abfragebedingung erfüllen.

Da es sich bei den gesetzten Elementen um Zahlen handelt, können Sie die scheinbare Struktur nutzen, sodass ein Signaturindex von großem Nutzen wäre.

Ich würde empfehlen, einen Blick auf IR-Artikel zu werfen, insbesondere in Bezug auf Wörterbuchstrukturen wie Bäume, aber beachten Sie, dass Speicherplatz normalerweise ein Problem für diese Systeme darstellt, während dies für Ihren Fall möglicherweise kein Problem darstellt.

Chazisop
quelle

Ein guter Punkt, dies ist in der Tat der Suche nach Begriffen in Dokumenten sehr ähnlich, und die häufigste Art der Lösung besteht darin, eine sogenannte invertierte Datei zu verwenden , die wie der Index eines Buches funktioniert. Sie suchen jeden Begriff in Ihrer Abfrage in der invertierten Datei und erhalten eine Liste / einen Satz von Dokumenten, die diesen Begriff enthalten. Sie schneiden dann diese Listen, um das Ergebnis zu erhalten. (Sie könnten zum Beispiel eine Hash-Tabelle verwenden, um Element-IDs zu sortierten Listen von Set-IDs zuzuordnen; die Sortierung hilft bei der Schnittmenge.)

Magnus Lie Hetland

Sie könnten einen Suchbaum verwenden. Kein „Standard“, wie er für geordnete Universen (reelle Zahlen, Strings…) verwendet wird, sondern ein allgemeinerer Typ, wie er vom GiST- Projekt angedeutet wird . Es gibt Suchbäume für räumliche Abfragen sowie solche, die auf den metrischen Axiomen basieren , um metrische (Entfernungs-) Räume zu indizieren. Die allgemeine Idee (von der der intervallorientierte Ansatz "kleiner als / größer als" gewöhnlicher, geordneter Suchbäume eine Spezialisierung ist) besteht darin, den Datensatz in Teilmengen zu zerlegen, normalerweise hierarchisch. Diese Hierarchie von Teilmengen wird (offensichtlich) durch einen Baum dargestellt, in dem die Kinder jedes Knotens Teilmengen darstellen und jeder Knoten eine Form von Prädikat hatHiermit können Sie überprüfen, ob es eine Überlappung zwischen der für Ihre Abfrage relevanten (konzeptionellen) Gruppe von Objekten und den in diesem Teilbaum gefundenen Objekten (dh der Teilmenge) gibt.

Beispielsweise könnte für einen räumlichen Baum in der euklidischen Ebene jedes Objekt ein Punkt sein, und die Prädikate könnten Begrenzungsrechtecke sein , die alle Punkte enthalten, die in oder unter diesem Knoten gefunden werden. Wenn eine Abfrage ein Rechteck ist (und Sie alle Punkte in diesem Rechteck finden möchten), können Sie Teilbäume rekursiv entfernen, deren Begrenzungsrechtecke sich nicht mit Ihrer Abfrage überschneiden.

In Ihrem Fall könnten Sie einen Baum erstellen, in dem jeder Knoten eine festgelegte Struktur enthält, mit der Sie erkennen können, ob Ihre Abfrage eine Teilmenge ist. Wenn nicht, kann dieser gesamte Teilbaum entfernt werden, da Ihre Abfrage niemals eine Teilmenge eines der untergeordneten Knoten sein könnte (und sicherlich nicht die Blätter, die wahrscheinlich die wahren Daten darstellen würden).

Im Gegensatz zu normalen Suchbäumen gibt es hier im Allgemeinen keine Garantie für die Suchzeit. Sie werden wahrscheinlich mehrere Zweige besuchen. Selbst wenn Sie einen perfekt ausbalancierten Baum haben, haben Sie wahrscheinlich eine superlogarithmische Laufzeit. Dies ist eher ein heuristischer Ansatz, könnte aber trotzdem effektiv sein.

Um diesen Baum zu erstellen, benötigen Sie eine hierarchische Clustering-Methode, die zu Ihren Daten passt. Das GiST-Projekt hat tatsächlich einen Baum, der dem sehr ähnlich ist, was Sie benötigen, mit einer C-Implementierung (obwohl es prüft, ob sich die Abfrage überschneidet, nicht, ob es sich um eine Teilmenge handelt; sollte leicht zu ändern sein). Der festplattenbasierte, ausgeglichene Baum im B-Baum-Stil von GiST könnte jedoch übertrieben sein. Sie möchten wahrscheinlich nur ähnliche Mengen hierarchisch zusammenfassen, und Sie können dies mit einem handelsüblichen Clustering-Algorithmus tun, der beispielsweise die Hamming-Distanz (oder etwas ausgefalleneres) verwendet. Je ähnlicher die Geschwisterknoten sind, desto „enger“ wird das Begrenzungsprädikat des Elternteils (dh die Menge, die ihre Vereinigung darstellt) - und desto effizienter ist Ihre Suche.

Zusammenfassend ist mein Vorschlag:

Stellen Sie Ihre Mengen dar, damit Sie nach Überlappungen mit Abfragen suchen können (Bitvektoren, Hash-Tabellen).
Gruppieren Sie Ihre Sets hierarchisch, indem Sie einen geeigneten Abstand (z. B. Hamming) und einen Standardalgorithmus verwenden.
Speichern Sie in jedem internen Knoten die Vereinigung der untergeordneten Knotensätze.
Durchlaufen Sie während der Suche rekursiv und beschneiden / ignorieren Sie Teilbäume, deren Wurzeln Mengen haben, die sich nicht mit Ihrer Abfrage überschneiden.

Wenn der Baum dynamisch sein soll, gibt es auch viele Möglichkeiten, dies zu tun. Sie können beispielsweise den Baum rekursiv durchlaufen, den Ort finden, der am besten passt (indem Sie Knoten mit der höchsten Überlappung / kleinsten Hamming-Entfernung durchlaufen) und die Gewerkschaften (Begrenzungsprädikate) aktualisieren, während Sie fortfahren. Löschungen sind vielleicht etwas kniffliger; Sie können Objekte einfach als fehlend markieren und dann Teilbäume (oder die gesamte Struktur) neu erstellen, wenn die Anzahl der markierten Objekte einen bestimmten Schwellenwert erreicht.

Ob dies für Ihre Anwendung gut funktioniert, kann von vornherein schwer zu sagen sein, sollte aber experimentell leicht zu überprüfen sein. Außerdem gibt es viel Raum für Optimierungen.

Magnus Lie Hetland
quelle