Clojure： 'トライ'を生成するには？次を考える

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メソッドのバグが修正されました。現在、seqを長さの長い順に挿入することに依存しています。また、一般的な使用例である接頭辞によってトライを照会することもできます。

は、あなたが検索を実行できるように、それはトライのリーフノードに値を格納するので、ここでメモリ使用量が高くなっているに注意してください。

(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

、ここで私はどうなるのかです：

• トライを作成し、トライに新しい要素を挿入するためにいくつかの関数を記述します。
• 新しいトライを作成します。
• 入力リストを繰り返し、各要素をトライに挿入します。

この問題は、再帰的な実装に非常によく適しています。私は可能ならばそれを目指します。

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) 

- >（ゼロ（1（2（4（20（25））（10私はルートノードとしてnilを使用することを選択したと子を意味しないように空のリストを維持困っていません（15））（5（9）））（3））））

注意。この方法で実際に行うのは、部分文字列の同一性が保持されないため正しくありません。

Answer 4

リストがない非効率的な言及することは、ここに非常に不器用です。 Clojureでは、適切な場合にベクトルとハッシュマップとセットを使用する方が慣れています。ハッシュマップを使用して：あなたはあなたの代わりにsorted-map Sを使用することができソート印刷するには、それを望んでいた場合

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

ていますが、ソートに使用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