Crit-bit Trees: the best way to store sets
1–10 of 42 posts
Re: Crit-bit Trees: the best way to store sets
#2If you're looking for a jvm implementation, there are at least a couple:
https://github.com/rkapsi/patricia-trie https://github.com/jfager/functional-critbit
The latter is my own, with a focus on memory efficiency (by my benchmarks, it uses about 40% less space than patricia-trie for the same data set). Would love to get some extra eyes on it to figure out how to trim it further or speed it up.
Re: Crit-bit Trees: the best way to store sets
#3agl's C translation written in literate programming style:
Re: Crit-bit Trees: the best way to store sets
#4agl's C translation written in literate programming style: PDF: https://github.com/agl/critbit/blob/master/critbit.pdf Repo: https://github.com/agl/critbit
Does 'literate programming style' require the lack of indentation in his source file?
Re: Crit-bit Trees: the best way to store sets
#5> A crit-bit tree for a nonempty prefix-free set S of bit strings has an external node for each string in S; an internal node for each bit string x such that x0 and x1 are prefixes of strings in S; and ancestors defined by prefixes.
And that's a perfect (missing) example for "a picture is worth a thousand words". Then again... this coming from DJB - I should be surprised the description is as verbose as it is.
Re: Crit-bit Trees: the best way to store sets
#6agl's C translation written in literate programming style: PDF: https://github.com/agl/critbit/blob/master/critbit.pdf Repo: https://github.com/agl/critbit
Does 'literate programming style' require the lack of indentation in his source file?
Not sure, maybe that's how CWEB outputs it. Read PDF instead, it has the properly indented code :-)
Re: Crit-bit Trees: the best way to store sets
#7agl's C translation written in literate programming style: PDF: https://github.com/agl/critbit/blob/master/critbit.pdf Repo: https://github.com/agl/critbit
Does 'literate programming style' require the lack of indentation in his source file?
The source file is critbit.w. See " rel="nofollow">http://en.wikipedia.org/wiki/Literate_programming>.
Re: Crit-bit Trees: the best way to store sets
#8If you don't need the add and remove operations, it's possible to reduce the size significantly by applying automata theory:
http://www.n3labs.com/pdf/lexicon-squeeze.pdf
It works extremely well "out of the box" for dictionary words, since the automata enables sharing of both prefixes and suffixes.
Re: Crit-bit Trees: the best way to store sets
#9Also known as a radix tree, I believe.
Re: Crit-bit Trees: the best way to store sets
#10Also known as a radix tree, I believe.
Seems to be so: http://en.wikipedia.org/wiki/Radix_tree