Clojure：如何生成'trie'？

Question

給出下面...

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

你會如何將其轉換爲這個線索？

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

Answer 1

這是一個清理解決方案。這修正了Brian的add-to-trie方法的一個錯誤，因爲它目前依賴於你以遞增長度順序插入seqs。它也允許通過前綴查詢trie，這是一個常見的用例。

請注意，此處的內存使用率較高，因爲它將值存儲在trie的葉節點中，因此您可以執行搜索。

(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

按照一般的做法，這裏就是我會做：

• 寫幾個函數來創建一個線索，並插入新的元素融入一個線索。
• 創建一個新的trie。
• 遍歷輸入列表並將每個元素插入到trie中。

這個問題很好地適用於遞歸實現。如果可能，我會盡力爭取。

Answer 3

我敢肯定有一個漂亮的方式（有見布賴恩的答案是更好！）：

(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））））

請注意，我選擇使用nil作爲根節點，並且沒有打擾空列表來表示沒有孩子。實際上這樣做是不正確的，因爲它不保留子字符串的身份。

Answer 4

列表在這裏非常笨拙，更不用說效率低下了。在Clojure中，更適合使用向量和哈希映射並進行設置。使用哈希地圖：

(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))) 

如果你想它來打印排序，你可以使用sorted-map！而非，但你必須編寫自己的assoc-in所使用排序版本下的整個方式映射。在任何情況下：

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