Tried

A trie data structure implementation in Go.

Usage

$ go build
$ ./tried -help
Usage of ./tried:
  -dict string
        File which contains the words registered for autocompletion (default "/usr/share/dict/words")
  -dot
        Dump a dot representation of the trie for graphviz
  -prefix string
        Get a trie that only starts with a prefix
  -words
        Print the words contained in the trie

Graphviz

trie-graph

$ go run main.go | dot -Tpng > graph.png

References

TODO

  • Sort the prefix result by edit distance lev "" s2 = length s2 lev s1 "" = length s1 lev (x:s1) (y:s2) | x == y = lev s1 s2 | x /= y = 1 + min (lev (x:s1) s2) (lev s1 (y:s2))
  • Convert trie to a graphviz dot file
  • Make autocompletion with ncurses
  • Make trie rune comparison case insensitive
  • Optimize by triming the nodes with only one child (radix tree) b -> a -> l -> l -> s -> e to: ba -> ll -> se

GitHub

View Github