GitHub - acomagu/trie: The fast and flexible Trie Tree implementation in Go.

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.

Import Path

github.com/acomagu/trie/v2

Benchmark

Run make bench to run it locally. The latest benchmark result is here.

Exact Matching

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

Longest Prefix

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

(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.

Examples

The common preparation for each example:

import (
	"fmt"

	"github.com/acomagu/trie/v2"
)

keys := [][]byte{
	[]byte("ab"),
	[]byte("abc"),
	[]byte("abd"),
}
values := []int{1, 2, 3} // The type of value doesn't have to be int. Can be anything.
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 int
var match bool
for _, c := range []byte("abcxxx") {
	if t = t.TraceOne(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.