9

如何为 TRIE 创建一个 Clojure 拉链，由嵌套映射表示，键是字母。？

像这样的东西：

{\b {\a {\n {\a {\n {\a {'$ '$}}}}}} \a {\n {\a {'$ '$}}}}

用 2 个单词 'banana' 和 'ana' 表示一个 trie。（如有必要，可以在地图中进行一些更改..）

我尝试将map? vals assoc3 个功能分别传递给拉链。但它似乎不起作用..

我应该使用哪三个功能？

以及基于 zipper 的 insert-into-trie 会是什么样子？

4

2 回答 2

16

map? vals #(zipmap (keys %1) %2)可以，但不支持插入/删除子项（因为子项只是值，您不知道要删除/添加哪个键）。

下面map-zipper确实支持插入/删除，因为节点是 [kv] 对（除了作为映射的根）。

(defn map-zipper [m]
  (z/zipper 
    (fn [x] (or (map? x) (map? (nth x 1))))
    (fn [x] (seq (if (map? x) x (nth x 1))))
    (fn [x children] 
      (if (map? x) 
        (into {} children) 
        (assoc x 1 (into {} children))))
    m))
于 2013-02-22T09:21:07.150 回答
0

@cgrant 提出的解决方案很棒，但隐含地描述了一个树，其中所有分支和叶节点都有一个关联的值（字典中的键），除了根节点，它只是一个没有值的分支。所以，这棵树{"/" nil}，不是一棵只有一个叶子节点的树，而是一棵有匿名根分支和一个有值的叶子节点的树/。在实践中，这意味着树的每次遍历都必须首先执行 a(zip/down t)才能下降根节点。

另一种解决方案是显式地对地图内的根进行建模，也就是说，仅从根处具有单个键的地图创建拉链。例如：{"/" {"etc/" {"hosts" nil}}}

然后可以通过以下方式实现拉链：

(defn map-zipper [map-or-pair]
  "Define a zipper data-structure to navigate trees represented as nested dictionaries."
  (if (or (and (map? map-or-pair) (= 1 (count map-or-pair))) (and (= 2 (count map-or-pair))))
    (let [pair (if (map? map-or-pair) (first (seq map-or-pair)) map-or-pair)]
      (zip/zipper
        (fn [x] (map? (nth x 1)))
        (fn [x] (seq (nth x 1)))
        (fn [x children] (assoc x 1 (into {} children)))
        pair))
    (throw (Exception. "Input must be a map with a single root node or a pair."))))
于 2018-03-03T20:09:37.000 回答