本文介绍了Clojure:如何生成'trie'?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
给定以下...
(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())))))))
解决方案这里有一个清理的解决方案。这修复了Brian的add-to-trie方法,因为它目前依赖于以递增长度顺序插入seq。它还允许通过前缀查询trie,这是一个常见的用例。
请注意,这里的内存使用率较高,因为它将值存储在树的叶节点因此您可以执行搜索。
(defn add-to-trie [trie x]
(assoc-in trie x($)
(b)
如果值为x,则返回true存在于指定的trie中
(:terminal(get-in trie x)false))
(defn prefix-matches [trie prefix]
与指定的trie中指定的前缀匹配
(keep:val(tree-seq map?vals(get-in trie prefix))))
(defn build- coll]
在指定的seq coll中创建一个字符串的值
(reduce add-to-trie {} coll))
Given the following...
(def inTree '((1 2) (1 2 3) (1 2 4 5 9) (1 2 4 10 15) (1 2 4 20 25)))
How would you transform it to this trie?
(def outTrie '(1 (2 () (3 ()) (4 (5 (9 ())) (10 (15 ())) (20 (25 ()))))))
解决方案Here's a cleaned up solution. This fixes a bug Brian's add-to-trie method since it's currently dependent upon you inserting the seqs in increasing-length order. It also allows querying the trie by prefix, which is a common use case.
Note the memory usage here is higher since it stores the values in the leaf nodes of the trie so you can perform searches.
(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))
这篇关于Clojure:如何生成'trie'?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!