2016-04-24 12 views
3

Betrachten Sie die folgende Baumstruktur in einem Clojure Code:Datenstruktur zur Darstellung von Pfaden eines Baums ohne Redundanz

(def tree [7 9 [7 5 3 [4 6 9] 9 3] 1 [2 7 9 9]]) 

Die Pfade zu - zum Beispiel - alle geraden Zahlen im Baum sein würde:

[[2 3 0] [2 3 1] [4 0]] 

Dies ist eine Liste von Listen. Jede 'innere' Liste repräsentiert einen absoluten Pfad von der Wurzel des Baumes zu den Blättern von Interesse.

Ich suche jetzt nach einer Datenstruktur, um ein solches Ergebnis ohne Redundanz darzustellen. Wie Sie sehen können, wird beispielsweise das Fragment von [2 3] in zwei Einträgen wiederholt. Ich kam mit einer verschachtelten Hash-Karte, aber vielleicht gibt es etwas einfacher:

{2 {3 {0 true 1 true} 
4 {0 true}} 

Antwort

3

Ich glaube, dass DAWG für Ihr Problem übertrieben ist. Suffixe Ihrer Wege werden kaum geteilt. Daher sollte die Verwendung von trie ausreichen (dies ist eigentlich Ihr Ansatz der geschachtelten Hash-Map). Auch es ist pretty easy to generate it in clojure.

1

Ich glaube, Sie ein "deterministic acyclic finite state automaton (DAFSA) also called a directed acyclic word graph (DAWG)" nutzen könnten.

In Ihren Daten bestehen alle Pfade aus einer Reihe von Strings (oder Wörtern). Jeder Pfad zu einem Blatt würde einen Pfad zu einer geraden Zahl darstellen.

+0

Danke für den Link. Der Artikel ist jedoch sehr allgemein gehalten. Könnten Sie vielleicht ein Beispiel in Clojure geben? Vielleicht den Vorteil gegenüber dem geschachtelten Hash-Map-Ansatz hervorheben. Der Artikel nennt die Pfade "Strings" - das ist interessant. Es erinnerte mich an reguläre Ausdrücke: Das Obige könnte als "(23 [01] | 40)" ausgedrückt werden, aber ich bin mir nicht sicher, ob das eine praktische Umsetzung wäre. –

+0

Leider habe ich kein Beispiel, ich dachte nur, dass diese Lösung erwähnenswert ist. Ich schätze, dass einfachere Lösungen (wie eine von OlegTheCat) für Sie genug sind. DAWGs werden verwendet, um das gesamte Wörterbuch von Strings (Wörter aus einem Alphabet, in Ihrem Fall als Indizes in Ihren Pfaden) auf sehr kompakte Weise darzustellen. Wenn Sie eine große Anzahl solcher Pfade darstellen möchten, ist die DAWG eine gute Wahl. –