syohex/strie.el

simple tries for emacs

strie.el: simple tries for emacs

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.

Commentary:

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.

Setup:

Simply add strie.el to your load path and (require ‘strie) to your .emacs.

Usage:

create a trie

(setq a-trie (strie-new))

add key-value pairs

(strie-add a-trie “one” 1)

(strie-add a-trie “two” “2”)

ensure that the keys appear

(strie-contains? a-trie “one”) -> t

(strie-contains? a-trie “on” ) -> nil

get values

(strie-get a-trie “one”) -> 1

(strie-get a-trie “two”) -> “2”

(strie-get a-trie “twomore”) -> nil

get completions

(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”)

delete a key

(strie-delete a-trie “one”)

(strie-contains? a-trie “one”) -> nil

(strie-get a-trie “one”) -> nil