12

以下を考えると...

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

4 に答える 4

16

これがクリーンアップされたソリューションです。これにより、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))
于 2010-03-24T20:24:06.860 に答える
10

リストはここでは非常に扱いにくく、非効率的であることは言うまでもありません。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、代わりに s を使用できますが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
于 2009-09-21T08:49:26.627 に答える
1

もっときれいな方法があると確信しています（ありました！ブライアンの答えを見てください）：

(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 を使用することを選択したことに注意してください。子がないことを示すために空のリストを維持する必要はありません。部分文字列の同一性が保持されないため、実際にこのようにすることは正しくありません。

于 2009-09-21T05:57:16.753 に答える
1

一般的なアプローチとして、これが私がすることです：

  • トライを作成し、トライに新しい要素を挿入する関数をいくつか書いてください。
  • 新しいトライを作成します。
  • 入力リストを反復処理し、各要素をトライに挿入します。

この問題は、再帰的な実装に非常に適しています。できればそれを目指します。

于 2009-09-21T03:28:34.293 に答える