Consider the following tree structure in a Clojure code:
(def tree [7 9 [7 5 3 [4 6 9] 9 3] 1 [2 7 9 9]])
The paths to - for instance - all even numbers in the tree would be:
[[2 3 0] [2 3 1] [4 0]]
This is a list of lists. Each 'inner' list represents an absolute path from the root of the tree to the leaves of interest.
I'm looking now for a data structure to represent such a result without redundancy. As you can see, for instance the fragment of [2 3] is repeated in two entries. I came up with a nested hash-map, but maybe there's something simpler:
{2 {3 {0 true 1 true}
4 {0 true}}
I believe that DAWG is overkill for your problem. Suffixes of your paths are barely going to be shared. So usage of trie should be enough (this is actually your nested hash map approach). Also it's pretty easy to generate it in clojure.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments