strie.el provides a simple implementation of the trie data structure. It uses only native elisp data structures, so there are no dependencies to worry about.
Tries are an efficient data structure for the storage of strings. Addition, deletion, and query functions all have O(m) performance, where m is the length of the string to be added/deleted/queried.
They are a natural choice for completing partial strings according to some dictionary.
This implementation also supports key-value storage, which means that a trie can act as a substitute for a dictionary / hash-table.
See http://en.wikipedia.org/wiki/Trie for more details.
Simply add strie.el to your load path and (require ‘strie) to your .emacs.
(setq a-trie (strie-new))
(strie-add a-trie “one” 1)
(strie-add a-trie “two” “2”)
(strie-contains? a-trie “one”) -> t
(strie-contains? a-trie “on” ) -> nil
(strie-get a-trie “one”) -> 1
(strie-get a-trie “two”) -> “2”
(strie-get a-trie “twomore”) -> nil
(strie-add a-trie “only” nil)
(strie-add a-trie “onetime” nil)
(strie-complete a-trie “on”) -> (“only” “one” “onetime”)
(strie-complete a-trie “one”) -> (“one” “onetime”)
(strie-delete a-trie “one”)
(strie-contains? a-trie “one”) -> nil
(strie-get a-trie “one”) -> nil