Clojure：如何生成'trie'？ [英] Clojure: How to generate a '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'？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！