Trie

Usage

Prefix Search

import "github.com/joway/trie"

dict := map[string]interface{}{
		"/abc": "2",
		"/a":   "1",
		"/ac":  "3",
		"/b":   "4",
		"/bc":  "5",
		"/bca": "6",
		"/ba":  "7",
		"/cba": "8",
}

tree := trie.Build(dict)

prefix, val := tree.PrefixSearchString("/a")

Prettify Output

output := tree.Prettify()
fmt.Println(output)

*->/->a->b->c
||  |  ->c
||  ->b->a
||  |  ->c->a
||  ->c->b->a

Document

GoDoc

Benchmark

BenchmarkBuild-8                                    2000            814677 ns/op          555392 B/op       7377 allocs/op
BenchmarkTrie_AddWord-8                         100000000               12.6 ns/op             0 B/op          0 allocs/op
BenchmarkTrie_PrefixSearchString-8               5000000               267 ns/op              32 B/op          1 allocs/op
BenchmarkTrie_PrefixSearch-8                    10000000               156 ns/op               0 B/op          0 allocs/op

Benchmark Comparison

https://github.com/derekparker/trie

BenchmarkTrie_AddWord_DTrie-8                   20000000               108 ns/op             112 B/op          2 allocs/op
BenchmarkTrie_PrefixSearchString_DTrie-8         2000000               732 ns/op             160 B/op          9 allocs/op