trie

README

trie: The fast and flexible Trie Tree implementation

The Trie Tree implementation in Go. It has flexible interface and works fast as Radix Tree implementation.

This is basically an implementation of the algorithm described in 簡単なトライ - LINE ENGINEERING. I really appreciate the amazing ideas and the clear and easy-to-understand explanation.

Benchmark

Run make bench to run it locally.

Exact Match

The task is to determine whether a string matches one of all Wikipedia titles.

Package	Time	Objects Allocated
acomagu/trie	1090 ns/op	0 allocs/op
sauerbraten/radix	2445 ns/op	0 allocs/op
dghubble/trie	2576 ns/op	0 allocs/op
hashicorp/go-immutable-radix	3660 ns/op	0 allocs/op
derekparker/trie	4010 ns/op	0 allocs/op
armon/go-radix	11745 ns/op	0 allocs/op
kkdai/radix	18809 ns/op	0 allocs/op
tchap/go-patricia/patricia	21498 ns/op	0 allocs/op

Longest Prefix

The task is to answer which of all Wikipedia titles can be the longest prefix of a string.

Package	Time	Objects Allocated
acomagu/trie	140 ns/op	0 allocs/op
hashicorp/go-immutable-radix	159 ns/op	0 allocs/op
tchap/go-patricia/patricia	252 ns/op	0 allocs/op
derekparker/trie	2374 ns/op	0 allocs/op
sauerbraten/radix	3264938 ns/op	0 allocs/op
armon/go-radix	22129827 ns/op	1 allocs/op

(dghubble/trie and kkdai/radix don't have way to do.)

Build

The task is to prepare Trie/Radix Tree with all of the Wikipedia titles.

Package	Time	Objects Allocated
sauerbraten/radix	118959250 ns/op	408564 allocs/op
acomagu/trie	542902000 ns/op	421906 allocs/op
dghubble/trie	609406300 ns/op	1136281 allocs/op
derekparker/trie	1046705400 ns/op	1801539 allocs/op
armon/go-radix	1750312500 ns/op	1446050 allocs/op
kkdai/radix	2280362300 ns/op	1742841 allocs/op
tchap/go-patricia/patricia	2898335700 ns/op	1150947 allocs/op
hashicorp/go-immutable-radix	7614342400 ns/op	45097986 allocs/op

Examples

The common preparation for each examples:

keys := [][]byte{
	[]byte("ab"),
	[]byte("abc"),
	[]byte("abd"),
}
values := []interface{}{1, 2, 3}
t := trie.New(keys, values)

New() takes keys and values as the arguments. values[i] is the value of the corresponding key, keys[i].

Exact Match

v, ok := t.Trace([]byte("abc")).Terminal()
fmt.Println(v, ok) // => 2 true

Playground

Longest Prefix

var v interface{}
var match bool
for _, c := range []byte("abcxxx") {
	if t = t.TraceByte(c); t == nil {
		break
	}
	if vv, ok := t.Terminal(); ok {
		v = vv
		match = true
	}
}

fmt.Println(v, match) // => 2 true

Playground

No special function to get longest prefix because it can be implemented yourself easily using the existing methods.

Documentation

Overview

Example (LongestPrefix)

package main

import (
	"fmt"

	"github.com/acomagu/trie"
)

func main() {
	keys := [][]byte{
		[]byte("ab"),
		[]byte("abc"),
		[]byte("abd"),
	}
	values := []interface{}{1, 2, 3}
	t := trie.New(keys, values)

	var v interface{}
	var match bool
	for _, c := range []byte("abcxxx") {
		if t = t.TraceByte(c); t == nil {
			break
		}
		if vv, ok := t.Terminal(); ok {
			v = vv
			match = true
		}
	}

	fmt.Println(v, match)
}

Output:
2 true

Example (Match)

package main

import (
	"fmt"

	"github.com/acomagu/trie"
)

func main() {
	keys := [][]byte{
		[]byte("ab"),
		[]byte("abc"),
		[]byte("abd"),
	}
	values := []interface{}{1, 2, 3}
	t := trie.New(keys, values)

	v, ok := t.Trace([]byte("abc")).Terminal()
	fmt.Println(v, ok)
}

Output:
2 true

Index

• type Tree
  • func New(keys [][]byte, values []interface{}) Tree
  • func (t Tree) Children() []byte
  • func (t Tree) Predict() []interface{}
  • func (t Tree) Terminal() (interface{}, bool)
  • func (t Tree) Trace(path []byte) Tree
  • func (t Tree) TraceByte(c byte) Tree

Examples

• Package (LongestPrefix)
• Package (Match)
• Tree.Terminal

Types

type Tree

type Tree []node

Tree implements an immutable trie tree.

func New

func New(keys [][]byte, values []interface{}) Tree

New builds new Tree from keys and values. The len(keys) should equal to len(values).

func (Tree) Children

func (t Tree) Children() []byte

Children returns the bytes of all direct children of the root of t. The result is sorted in ascending order.

func (Tree) Predict

func (t Tree) Predict() []interface{}

Predict returns the all values in the tree, t. The complexity is proportional to the number of nodes in t(it's not equal to len(t)).

func (Tree) Terminal

func (t Tree) Terminal() (interface{}, bool)

Terminal returns the value of the root of t. The second return value indicates whether the node has a value; if it is false, the first return value is nil. It returns nil also when the t is nil.

Example

package main

import (
	"fmt"

	"github.com/acomagu/trie"
)

func main() {
	keys := [][]byte{[]byte("aa")}
	values := []interface{}{1}
	t := trie.New(keys, values)

	t = t.TraceByte('a') // a
	fmt.Println(t.Terminal())

	t = t.TraceByte('a') // aa
	fmt.Println(t.Terminal())

	t = t.TraceByte('a') // aaa
	fmt.Println(t.Terminal())

}

Output:
<nil> false
1 true
<nil> false

func (Tree) Trace

func (t Tree) Trace(path []byte) Tree

Trace returns the subtree of t whose root is the node traced from the root of t by path. It doesn't modify t itself, but returns the subtree.

func (Tree) TraceByte

func (t Tree) TraceByte(c byte) Tree

TraceByte is shorthand for Trace([]byte{c}).