iterativ Trie Konstruieren von einem Baum

Question

Introduction

Die folgende Funktion iterativ durchläuft eine Baumstruktur von verschachtelten Vektoren hergestellt. Es testet jedes Blatt gegen ein Prädikat. Die Pfade zu allen Blättern, die diesen Wahrheitstest bestehen, werden in einer Trie structure zurückgegeben. Letzteres beschreibt alle gefundenen Pfade auf nicht-redundante Weise.

(defn get-trie-of-matches [is? tree] 
    (loop [[tree i path fk] [tree 0 [] nil] 
     accum {}] 
    (cond 
     (>= i (count tree)) ;; end of level/go up 
     (if (nil? fk) accum (recur fk accum)) 

     (vector? (tree i)) ;; level down 
     (recur [(tree i) 0 (conj path i) [tree (inc i) path fk]] accum) 

     (is? (tree i)) ;; match 
     (let [new-accum (assoc-in accum (conj path i) {})] 
     (recur [tree (inc i) path fk] new-accum)) 

     :else ;; next on same level 
     (recur [tree (inc i) path fk] accum)))) 

Weitere Erläuterungen finden Sie unter this post.

Beispiel

Betrachten Sie die folgende Baum

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

auf die Funktion angewendet, even? als Prädikat verwendet:

(get-trie-of-matches even? tree) 
=> {2 {3 {0 {}, 1 {}}}, 4 {0 {}}} 

Das Ergebnis die Zahlen sogar drei Pfade beschreibt in tree. Nämlich 2-3-0, 2-3-1 und 4-0.

Problem

Auch wenn die oben genannte Funktion funktioniert, könnte es bessere Möglichkeiten, die Trie zu konstruieren, während der Baum durchquert. Im Moment ist eine Hash-Karte überschwemmt. Bei jedem Spiel über assoc-in. Der Algorithmus durchquert die Baumstruktur relativ von Ebene zu Ebene, hängt jedoch jeden Pfad global an accum an, was nicht notwendig ist. Auch diese Methode ist nur möglich, da eine Hash-Map verwendet wird. Es könnte jedoch besser sein, eine sequentielle Datenstruktur für die Trie zu verwenden, um weitere Iterationen darüber zu ermöglichen. Dies konnte nicht für die obige Methode übernommen werden.

Frage

Wie kann ein Trie aus der obigen Funktion erstellt wird get-trie-of-matches, ohne sie auf Hash-Karte spezifisch ‚global‘ ‚write‘ Funktionen?

Answer 1

Ich würde vorschlagen, clojure walk api zu betrachten.

Es ermöglicht Ihnen, einige Funktionen rekursiv auf verschachtelte Sammlungen anzuwenden. In diesem Fall könnten Sie postwalk verwenden:

user> (require '[clojure.walk :as w]) 
user> (w/postwalk-demo [1 3 [4 [6] 7] [[8]]]) 
Walked: 1 
Walked: 3 
Walked: 4 
Walked: 6 
Walked: [6] 
Walked: 7 
Walked: [4 [6] 7] 
Walked: 8 
Walked: [8] 
Walked: [[8]] 
Walked: [1 3 [4 [6] 7] [[8]]] 

[1 3 [4 [6] 7] [[8]]] 

Das Wichtigste ist, dass Sie bei jedem Schritt ein beliebiges Element ersetzen:

user> (w/postwalk #(if (coll? %) (reverse %) (inc %)) 
        [1 3 [4 [6] 7] [[8]]]) 

(((9)) (8 (7) 5) 4 2) 

Hier stellen wir alle Zahlen erhöhen, und alle umzukehren, halten die verschachtelte Struktur

Jetzt für Ihre Aufgabe gilt: Sie könnten durch Ihren Baum gehen, nur gerade Zahlen Indizes und nicht leere Sammlungen (z.Sammlungen auch Zahlen enthalten, und nicht leer Sammlungen):

;; helper function 
(defn empty-coll? [item] 
    (and (coll? item) (not (seq item)))) 

(defn make-trie [pred tree] 
    (w/postwalk 
    #(if (coll? %) 
     (keep-indexed (fn [idx item] 
         (cond (empty-coll? item) nil 
          (coll? item) (list idx item) 
          item idx 
          :else nil)) 
        %) 
     (pred %)) 
    tree)) 

in repl:

user> (def tree [7 9 [7 5 3 [4 6 9] 9 3] 1 [2 7 9 9]]) 
#'user/tree 

user> (make-trie even? tree) 
((2 ((3 (0 1)))) (4 (0))) 

user> (make-trie #(> % 7) tree) 
(1 (2 ((3 (2)) 4)) (4 (2 3))) 

Die Struktur ist ähnlich zu Ihrer Karte. In der Tat können Sie eine beliebige Struktur, die Sie mit geringfügigen Änderungen an der Funktion wollen produzieren, zum Beispiel Ihre Map-Struktur:

(defn make-trie-map [pred tree] 
    (w/postwalk 
    #(if (coll? %) 
     (into {} 
      (keep-indexed (fn [idx item] 
          (cond (empty-coll? item) nil 
            (coll? item) {idx item} 
            item {idx {}} 
            :else nil)) 
          %)) 
     (pred %)) 
    tree)) 

user> (make-trie-map even? tree) 
{2 {3 {0 {}, 1 {}}}, 4 {0 {}}}