一种不重复表示树路径的数据结构

Question

考虑在Clojure代码中的以下树形结构:

(def tree [7 9 [7 5 3 [4 6 9] 9 3] 1 [2 7 9 9]])

例如，在树中，所有偶数的路径将是：

[[2 3 0] [2 3 1] [4 0]]

这是一个列表的列表。每个“内部”列表表示从树的根到感兴趣的叶子的绝对路径。

我现在正在寻找一种数据结构来表示这样的结果，而不会出现冗余。正如您所看到的，例如[2 3]的片段在两个条目中重复出现。我想到了一个嵌套的哈希映射，但也许有更简单的方法：

{2 {3 {0 true 1 true}
 4 {0 true}}

- Anton Harald

Answer 1

我认为DAWG对于你的问题来说有些过度了。你路径的后缀几乎不会被共享。因此使用trie应该就足够了（这实际上是你嵌套哈希映射的方法）。而且在Clojure中生成它也相当容易。

- OlegTheCat

Answer 2

我认为你可以使用"确定性无环有限状态自动机（DAFSA），也称为有向无环词图（DAWG）。

在您的数据中，所有路径都由一组字符串（或单词）组成。到叶子节点的每条路径都代表到偶数的路径。

- Piotrek Bzdyl

---

谢谢提供链接。虽然文章很通俗易懂，但你能否提供一个Clojure的例子呢？也许可以突出嵌套哈希映射方法的优势。文章将路径称为“字符串”-这很有趣。它让我想起了正则表达式：上面的内容可以表示为“(23 [01] | 40)”，但我不确定这是否是实际实现。 - Anton Harald

很遗憾，我没有例子，我只是觉得这个解决方案值得一提。我猜更简单的解决方案（比如OlegTheCat提供的）对你来说已经足够了。DAWGs被用来以非常紧凑的方式表示整个字符串字典（某些字母表中的单词，在你的情况下是路径中的索引）。如果你想要表示一个非常大的这样的路径集合，DAWG可能是一个不错的选择。 - Piotrek Bzdyl