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}}
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. –
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. –