數據結構來表示一棵樹的路徑沒有冗餘

考慮下面的樹結構中的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}}

來源

2016-04-24 Anton Harald

我相信DAWG對於你的問題是矯枉過正的。你的路徑後綴幾乎不會被共享。所以使用trie應該足夠了（這實際上是你的嵌套哈希映射方法）。它也是pretty easy to generate it in clojure。

來源

2016-04-24 20:00:36 OlegTheCat

我想你可以使用一個"deterministic acyclic finite state automaton (DAFSA) also called a directed acyclic word graph (DAWG)"。

在您的數據中，所有路徑都包含一組字符串（或單詞）。每條葉子的路徑都會代表一條偶數的路徑。

來源

2016-04-24 19:42:39

感謝您的鏈接。文章雖然很一般。你可以在Clojure中提供一個例子嗎？也許突出顯示與嵌套哈希映射方法相比的優勢。文章稱這些路徑爲「字符串」 - 這很有趣。它讓我想起了正則表達式：上面可以表達爲「（23 [01] | 40）」，但我不確定這是否是一個實際的實現。 –

不幸的是，我沒有一個例子，我只是覺得這個解決方案值得一提。我想更簡單的解決方案（就像OlegTheCat提供的解決方案）對你來說就足夠了。 DAWG用於以非常緊湊的方式表示字符串的全部字典（來自某些字母表的字詞，在您的案例中作爲路徑中的索引）。如果你想要代表一個非常大的這樣的路徑，DAWG可能是一個不錯的選擇。 –

數據結構來表示一棵樹的路徑沒有冗餘

回答

相關問題