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

你如何将它转化为这种trie树结构？

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

- Johnny

Answer 1

这是一个经过整理的解决方案。它修复了Brian的加入字典树方法中的一个错误，因为它目前依赖于您按递增长度顺序插入序列。它还允许通过前缀查询字典树，这是常见的用例。

请注意，由于它将值存储在字典树的叶节点中以便进行搜索，因此这里的内存使用率更高。

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

- Greg Fodor

---

那么，如果您始终使用相同数量的密钥，那么Brian的版本应该是可以的，我猜。 - Johnny

你的 prefix-matches 定义使用了一个名为 map-filter 的函数，但标准库中并没有这个函数。我试图逆向工程它的功能，但并不明显。你能发一下它的定义吗？ - Rory O'Kane

map-filter与核心库中的keep类似。 - NielsK

我已经对你提到的 bug 在 @Brian's answer 中进行了最小程度的修复。 - Thumbnail

你选择同时包含 :val 键和 :terminal 键，是否有特别的原因？因为只有终端节点才有 :val 条目。 - Eric Auld

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

- Brian Carper

---

非常好的答案，并强调我的代码实际上忽略了子字符串问题。我建议稍微修改一下in-trie函数： (defn in-trie? [trie x] (:terminal (get-in trie x) false))user=> (in-trie? trie '(1 2 4)) false这样可以使它成为一个真正的谓词，并避免使用splice语法。 - Timothy Pratley

也许是 ::terminal，如果我们正在尝试具有 :terminal 的序列？ - Thumbnail

我已经修复了@GregFooter发现的错误。随意撤销编辑。与@TimothyPratley不同，我发现你使用unquote-splicing很有帮助，因为它显示它作为数据操作 - 而不是陷入宏体中。 - Thumbnail

Answer 3

我相信有更好的方法（确实有！请看Brian的答案，它更好）：

(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 (15)) (5 (9))) (3))))

请注意，我选择使用“nil”作为根节点，并没有保留空列表来表示没有子节点。实际上，这样做是不正确的，因为它不会保留子字符串的身份。

- Timothy Pratley

---

谢谢。看到常见问题的代码可以帮助掌握一种语言的习惯用法。 - Johnny

没问题，看看Brian的答案吧，那个更符合习惯用语并且正确。 - Timothy Pratley

Answer 4

一般来说，这是我的做法：

• 编写几个函数来创建 Trie 并将新元素插入到 Trie 中。
• 创建一个新的 Trie。
• 遍历输入列表并将每个元素插入到 Trie 中。

这个问题非常适合使用递归实现。如果可能的话，我会尝试使用递归。

- Greg Hewgill