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方法的一个错误,因为它当前依赖于你以增加的长度顺序插入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

列表在这里非常笨拙,更不用说低效了.在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-maps代替,但你必须编写你自己的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