git clone 'https://github.com/peterhil/btrie.git'
————————————————————————- Branch trie - a generic trie implementation with branch widths ————————————————————————- Version: 0.2.1 Initial Common Lisp version: 2010-08-01
This trie implementation has an original idea of “branch width” invented by Peter Hillerström on 14 of November 2008. Branch width of a trie node tells how many branches go through that node. Widths can be used to calculate probabilites for different suffixes.
Notes about this implementation
About tries generally:
Trie, or prefix tree, is an ordered tree data structure that is used to store an associative array where the keys are usually strings.
Unlike a binary search tree, no node in the tree stores the whole key associated with that node instead, its position in the tree shows what key it is associated with.
All the descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string. Looking up a key of length m takes worst case O(m) time.
More information about tries: http://en.wikipedia.org/wiki/Trie