Clojure: come generare un 'trie'?

Question

Data la seguente ...

(def inTree 
'((1 2) 
    (1 2 3) 
    (1 2 4 5 9) 
    (1 2 4 10 15) 
    (1 2 4 20 25))) 

Come ti trasformarlo a questo trie?

(def outTrie 
'(1 
    (2() 
     (3()) 
     (4 (5 
      (9())) 
      (10 
      (15())) 
      (20 
      (25())))))) 

Answer 1

Ecco una soluzione pulita. Questo corregge un bug del metodo add-to-trie di Brian poiché dipende attualmente dall'inserimento dei seq in ordine crescente. Permette anche di interrogare il prefisso trie, che è un caso d'uso comune.

Nota l'utilizzo della memoria qui è più elevato poiché memorizza i valori nei nodi foglia del trie in modo da poter eseguire ricerche.

(defn add-to-trie [trie x] 
    (assoc-in trie x (merge (get-in trie x) {:val x :terminal true}))) 

(defn in-trie? [trie x] 
    "Returns true if the value x exists in the specified trie." 
    (:terminal (get-in trie x) false)) 

(defn prefix-matches [trie prefix] 
    "Returns a list of matches with the prefix specified in the trie specified." 
    (keep :val (tree-seq map? vals (get-in trie prefix)))) 

(defn build-trie [coll] 
    "Builds a trie over the values in the specified seq coll." 
    (reduce add-to-trie {} coll)) 

Answer 2

Come approccio generale, ecco cosa farei:

• scrivere alcune funzioni per creare un trie e per inserire nuovi elementi in un trie.
• Crea un nuovo trie.
• Iterate attraverso l'elenco di input e inserite ciascun elemento nel trie.

Questo problema si presta molto bene a un'implementazione ricorsiva. Lo farei se possibile.

Answer 3

Sono sicuro che ci sia un modo più bello (c'era vedi la risposta di Brian è meglio!):

(defn find-in-trie 
    "Finds a sub trie that matches an item, eg: 
    user=> (find-in-trie '(1 (2) (3 (2))) 3) 
    (3 (2))" 
    [tr item] 
    (first (for [ll (rest tr) :when (= (first ll) item)] ll))) 


(defn add-to-trie 
    "Returns a new trie, the result of adding se to tr, eg: 
    user=> (add-to-trie nil '(1 2)) 
    (1 (2))" 
    [tr se] 
    (cond 
    (empty? se) tr 
    (empty? tr) (add-to-trie (list (first se)) (rest se)) 
    :else (if-let [st (find-in-trie tr (first se))] 
      (cons (first tr) 
        (cons (add-to-trie st (rest se)) 
         (filter (partial not= st) (rest tr)))) 
      (cons (first tr) 
        (cons (add-to-trie (list (first se)) (rest se)) 
         (rest tr)))))) 

(def in '((1 2) 
      (1 2 3) 
      (1 2 4 5 9) 
      (1 2 4 10 15) 
      (1 2 4 20 25))) 

(reduce add-to-trie '(nil) in) 

-> (nil (1 (2 (4 (20 (25)) (10 (15)) (5 ​​(9))) (3))))

Nota che ho scelto di utilizzare nil come nodo radice e non mi sono preoccupato di tenere elenchi vuoti per non indicare figli. Effettuarlo in questo modo non è corretto in quanto non preserva l'identità della sottostringa.

Answer 4

Le liste sono molto maldestre qui, per non dire inefficienti. In Clojure è più idiota usare i vettori e le mappe hash e le serie quando appropriato. Utilizzando hash-mappe:

(def in-tree 
'((1 2) 
    (1 2 3) 
    (1 2 4 5 9) 
    (1 2 4 10 15) 
    (1 2 4 20 25))) 

(defn add-to-trie [trie x] 
    (assoc-in trie `(~@x :terminal) true)) 

(defn in-trie? [trie x] 
    (get-in trie `(~@x :terminal))) 

Se si voleva per stampare ordinato si potrebbe usare sorted-map s, invece, ma avresti dovuto scrivere la propria versione di assoc-in che ha utilizzato le mappe allineati per tutta la strada verso il basso. In ogni caso:

user> (def trie (reduce add-to-trie {} in-tree)) 
#'user/trie 
user> trie 
{1 {2 {4 {20 {25 {:terminal true}}, 10 {15 {:terminal true}}, 5 {9 {:terminal true}}}, 3 {:terminal true}, :terminal true}}} 
user> (in-trie? trie '(1 2)) 
true 
user> (in-trie? trie '(1 2 4)) 
nil 
user> (in-trie? trie '(1 2 4 20 25)) 
true