Eine Datenstruktur für Baumgruppen.

10

Versuche ermöglichen die effiziente Speicherung von Elementlisten. Die Präfixe werden gemeinsam genutzt, um Platz zu sparen.

Ich suche nach einem ähnlichen Weg, um Bäume effizient zu lagern. Ich möchte in der Lage sein, die Mitgliedschaft zu überprüfen und Elemente hinzuzufügen. Es ist auch wünschenswert zu wissen, ob ein gegebener Baum ein Teilbaum einiger gespeicherter Bäume ist oder ob es einen gespeicherten Baum gibt, der ein Teilbaum des gegebenen Baums ist.

Ich würde normalerweise ungefähr 500 unausgeglichene Binärbäume mit einer Höhe von weniger als 50 speichern.

BEARBEITEN

Meine Anwendung ist eine Art Modellprüfer, der eine Art Memoisierung verwendet. Stellen Sie sich vor Ich habe einen Zustand und die folgenden Formeln: f = φ und g = ( φ & psgr; ) mit φ ein komplexes Unterformel zu sein, und sich vorstellen , ich möchte zunächst wissen , ob f in hält s . Ich überprüfe, ob ϕ gilt und nach einem langen Prozess erhalte ich, dass dies der Fall ist. Jetzt möchte ich wissen, ob g in s gilt . Ich möchte mich daran erinnern, dass f gilt und dass g fsf=ϕg=(ϕψ)ϕfsϕgsfgfso dass ich in s fast sofort ableiten kann . Umgekehrt, wenn ich bewiesen habe, dass g nicht in t hält , dann möchte ich sagen, dass f nicht fast sofort in t hält .gs
gtft

Wir können eine Teilordnung auf Formeln aufbauen und haben iff g f . Für jeden Zustand s speichern wir zwei Sätze von Formeln; L ( s ) speichert die maximalen Formeln, die gelten, und l ( s ) speichert die minimalen Formeln, die nicht gelten. Wenn ich nun einen Zustand s und eine Formel g gebe , kann ich sehen, ob f L ( s ) , f g oder ob f l ( s )gfgfsL(s)l(s)sgfL(s),fg In diesem Fall bin ich fertig und weiß direkt, ob g in s gilt .fl(s),gfgs

Derzeit sind und l als Listen implementiert, und dies ist eindeutig nicht optimal, da ich alle gespeicherten Formeln einzeln durchlaufen muss. Wenn meine Formeln Sequenzen wären und die Teilreihenfolge "ein Präfix von" wäre, könnte sich ein Versuch als viel schneller erweisen. Leider haben meine Formeln eine baumartige Struktur, die auf ¬ , , einem Modaloperator und atomaren Sätzen basiert .Ll¬,

Wie @Raphael und @Jack hervorheben, könnte ich die Bäume sequentiellisieren, aber ich befürchte, dass dies das Problem nicht lösen würde, da die Teilreihenfolge, an der ich interessiert bin, nicht "ist ein Präfix von" entspricht.

Abdallah
quelle
Nur eine kurze Idee: Haben Sie versucht, Bäume zu sequenzieren (eine Durchquerung in der richtigen Reihenfolge durchzuführen, die besuchten Knoten entsprechend aufzulisten und spezielle Elemente für Auf- und Abwärtsbewegungen hinzuzufügen) und diese in einem Versuch zu speichern? Dies würde natürlich "nur" in gewissem Sinne die Überprüfung auf linke Teilbäume ermöglichen.
Raphael
2
STTS(T)S(T)S
1
Schauen Sie sich die Begriffsindizierung an .
Starblue
1
Eine andere schnelle Idee wäre, alle Bäume t1, t2, .. in einem großen Baum T zu speichern und sich für jede Kante die Baumgruppe zu merken, zu der sie gehört. Um dann zu bestimmen, ob f ein Teilbaum eines der gespeicherten Bäume ist, bestimmen Sie zuerst, ob f ein Teilbaum in T ist, und wenn ja, schneiden Sie dann alle Kantenbeschriftungssätze dieses Teilbaums. Die Antwort lautet Ja, wenn die Kreuzung nicht leer ist. (Sie können auch die beiden Schritte kombinieren).
Martin B.

Antworten:

5

Vielleicht möchten Sie sich g-try ansehen . Dies ist im Wesentlichen die Datenstruktur, nach der Sie suchen, die jedoch für die Verwendung mit allgemeinen Diagrammen anstelle von nur Bäumen konzipiert ist. Daher bin ich mir nicht sicher, ob G-Versuche gute theoretische Garantien haben - ich denke, sie verwenden einen Graph-Kanonisierungsalgorithmus als Unterprogramm -, aber in der Praxis scheinen sie gut zu funktionieren.

(Haben Sie keine Angst, dass es in dem verlinkten Artikel um "Netzwerkmotive in biologischen Netzwerken" geht: Der g-trie ist eine vollkommen gute abstrakte Datenstruktur für Grafiken.)

Joshua Grochow
quelle
4

Eine besondere Form davon ist die Persistenz : Siehe Artikel Erstellen von Datenstrukturen durch Driscoll, Sarnak, Sleator & Tarjan und Planar Point Location mit persistenten Suchbäumen von Sarnak & Tarjan, in denen Familien verwandter Bäume gespeichert werden.

Jack
quelle
1
Vielen Dank für die Referenzen. Ich kann im Moment nicht darauf zugreifen, Datenstrukturen persistent zu machen, aber ich bin mit dem Konzept der Persistenz einigermaßen vertraut. Ich sehe jedoch nicht, wie ich die Beharrlichkeit nutzen kann, um mein Problem zu lösen. Ich möchte eigentlich Wörterbücher verwenden, die Bäume auf Boolesche Werte abbilden, und derselbe Baum könnte ein Schlüssel für verschiedene Werte in verschiedenen Wörterbüchern sein.
Abdallah
1
Da ich nicht sicher war, was Ihre Anwendung war, habe ich Ihre Analogie zu Versuchen ausgelöst, bei denen Zeichenfolgen durch gemeinsame Nutzung von Präfixen gespeichert werden. Ihr Kommentar, dass "derselbe Baum ein Schlüssel für unterschiedliche Werte in unterschiedlichen Wörterbüchern sein könnte", scheint jedoch auch nicht zu Versuchen zu passen. Vielleicht möchten Sie nur eine Sammlung von Signaturen für einen Baum (und alle seine Teilbäume), die Sie nachschlagen können? (zB mit katalanischen Zahlen für Binärbäume oder Prufer-Codes für beschriftete Bäume.)
Jack
1

Das klingt ein bisschen wie ein Wald ( unzusammenhängende Wälder ) ...

Die Kosten für das Einfügen werden durch eine als Rang nach Vereinigung bezeichnete Technik und die Suchoperation unter Verwendung der Pfadkomprimierung amortisiert . Ich weiß, dass es auch eine dauerhafte Version dieser Struktur gibt, die von Sylvain Conchon und Jean-Christophe Filliâtre entwickelt wurde, aber ich habe keine Ahnung, ob dies die gleiche ist wie die, die Jack erwähnt ...

Rehno Lindeque
quelle
0

In "Purely Functional Data Structures" (1998) schlägt Chris Okasaki Versuche von Binärbäumen unter Verwendung der Typaggregation vor (10.3.2).

Ich weiß nicht, ob dies sofort hilft; Die dort angegebene Lösung ist möglicherweise nicht direkt implementierbar.

Raphael
quelle
0

Im Programmierjargon: Wenn Sie die Bäume aus gängigen Unterausdrücken / Bäumen / DAGs erstellen, hätten Sie ein schönes kompaktes Modell. So gerichtete azyklische Graphen. Dann würde eine Reihe von Bäumen ausreichen.

öffentliche Klasse Tree {String operation; Baum [] Teilbäume;

public int compareTo(Tree rhs) {
    if (rhs == null) return false;
    int cmp = operation.compareTo(rhs.operation);
    if (cmp == 0) {
        cmp = Arrays.compareTo(subtrees, rhs.subtrees);
    }
    return cmp;
}

...}

Map commonSubExpressions = new HashMap ();

Tree get (String expressionSyntax) {Tree t = neuer Tree (); t.operation = ...; t.subtrees = ... rekursiver Aufruf, um auf Unterausdrücke zuzugreifen; Baum t2 = commonSubExpressions.get (t); if (t2 == null) {t2 = t; commonSubExpressions.put (t2, t2); } return t2; }}

Joop Eggen
quelle