Effiziente Algorithmen zum Durchsuchen einer Baumsammlung

9

Ich habe einen großen Datensatz von Bäumen und möchte ihn durch Angabe eines Baumes (verbundener Untergraph) durchsuchen . Die Abfrage sollte alle Vorkommen des Baumes im Datensatz zurückgeben.

Gibt es dafür effiziente Algorithmen?

Ich dachte an so etwas wie Suffix-Arrays, aber die naive Codierung der Bäume als Zeichenfolgen (durch eine feste Durchlaufreihenfolge ihrer Knoten) funktioniert nicht, da der Suchbaum eine beliebige Form haben kann.

AKTUALISIEREN:

Einige Details zu den typischen Fällen, die ich erwarte:

Der Datensatz besteht aus mindestens Zehntausenden Bäumen mit jeweils etwa zwanzig bis dreißig Knoten. Die Bäume sind nicht binär, aber die typische Anzahl der Kinder pro Knoten ist klein (normalerweise nicht größer als vier oder fünf, obwohl sie in einigen entarteten Fällen etwa dreißig erreichen kann). Die Anzahl der Etiketten liegt bei Zehntausenden.

Ich brauche das für NLP-Anwendungen: Jeder Baum ist die Abhängigkeitsanalyse eines Satzes, jeder Knoten repräsentiert ein Wort Occourrence und jeder beschriftet ein Wörterbuchwort (mit etwas Dekoration).

graph-algorithms ds.data-structures tree graph-isomorphism string-search Antonio Valerio Miceli-Barone
quelle
1
Dieser Band enthält eine Diskussion paralleler Algorithmen für den Teilbaumisomorphismus.
Anthony Labarre
1
Entschuldigung, ich dachte, Sie suchen nach einem verbundenen Untergraphen, bei dem es sich notwendigerweise um einen Baum handelt, der in einer bestimmten Baumgruppe vorkommt. Können Sie klarstellen, in welchen Aspekten sich Ihr Problem von dieser Beschreibung unterscheidet?
Anthony Labarre
1
Wissen Sie im Voraus etwas über die Bäume? Binär? Wie viele verschiedene Knotenbezeichnungen erwarten Sie? Einschränkungen bei der Raumeffizienz? Ich frage, denn wenn Sie eine Menge Abfragen für dasselbe Dataset ausführen, könnte eine Lösung eine Art aggressive Indizierung beinhalten.
Eli
1
Kennen Sie sich mit XML Twig Matching aus? Ihr Problem scheint ein Sonderfall zu sein, sodass Sie einfach einen der vorhandenen Algorithmen und Software verwenden können.
Marek Chrobak
2
Ich denke, es ist am besten, die Diagrammstruktur zu ignorieren. Wenn Sie bei einer typischen Abfrage die Struktur verwerfen, wie viele Bäume erwarten Sie mit all diesen Wörtern? Haben Ihre Abfragen Platzhalter oder sind sie genau? Wenn die Wörter in einer Abfrage wie "Die Katze hat den Hut gefressen" lauten, wie viele Diagramme enthalten tatsächlich die Wörter "Katze" und "Hut"? Wenn Sie nur jedes Wort für eine Reihe von Bäumen indizieren und dann alle Mengen schneiden, können Sie das Ergebnis möglicherweise naiv durchsuchen, ohne zu hohe Kosten zu verursachen.
Eli

Antworten:

3

Obwohl nicht speziell auf (verwurzelte) Bäume ausgerichtet, denke ich, dass die G-trie-Datenstruktur in Ihrer Umgebung recht gut funktioniert. Es ist eine Anpassung des Versuchs (zum Suchen von Stringsätzen) an Graphen.

Joshua Grochow
quelle
1

Vor einiger Zeit habe ich Ronald Reads Baumkanonisierungsalgorithmus geschrieben und auf Wikipedia gestellt .

Ich würde eine Hashtabelle für jede interne Knotensignatur erstellen und sie mit einer Liste von Zeigern auf die Teilbäume beschriften, aus denen sie stammen. Es funktioniert jedoch nur bei Baumwipfeln mit echten Blättern.

Chad Brewbaker
quelle