pruning-radix-trie

pruning-radix-trie is a Go library that implements the Pruning Radix Trie, an augmented compressed trie that orders nodes based upon the maximum rank of the items in their subtree. This allows it to quickly search and find k elements with the highest rank. You decide what the rank is for each item.

The most obvious use case would be autocomplete: Finding the top 10 used words with a given prefix is cheap with this data structure.

import ptrie "olympos.io/container/pruning-radix-trie"

To use it, import the library to your Go project by issuing

$ go get olympos.io/container/pruning-radix-trie

Usage

The library contains in practice two functions you use to interact with it:

• FromItems, which is used to build an immutable pruning radix trie, and
• PTrie.FindTopK to find the top k ranked items with a given prefix

If performance is a concern, you can use PTrie.FindTopKFast to shave off an allocation, but for most use cases, that isn’t necessary.

Here’s a small standalone example of how you can use it:

package main

import (
	"fmt"

	ptrie "olympos.io/container/pruning-radix-trie"
)

type empty struct{}

func main() {
	trie := ptrie.FromItems([]ptrie.Item[empty]{
		{Term: "hello", Rank: 1000},
		{Term: "hi", Rank: 871},
		{Term: "howdy", Rank: 70},
		{Term: "goodbye", Rank: 918},
	})

	top := trie.FindTopK("h", 4)
	for _, res := range top {
		fmt.Printf("%s (rank %d)\n", res.Term, res.Rank)
	}
	// hello (rank 1000)
	// hi (rank 871)
	// howdy (rank 70)
}