A prefix tree implementation in go

Overview

Trie (Prefix tree)

GoReportCard GoDoc

This library is compatible with Go 1.11+

Please refer to CHANGELOG.md if you encounter breaking changes.

Motivation

The goal of this project is to provide serverless prefix tree friendly implementation. where one function can easily building tree and publishing to some cloud storge. Then the second load trie to perform various operations.

Introduction

A trie (prefix tree) is a space-optimized tree data structure in which each node that is merged with its parent. Unlike regular trees (where whole keys are from their beginning up to the point of inequality), the key at each node is compared chunk by chunk,

Prefix tree has the following application:

  • text document searching
  • rule based matching
  • constructing associative arrays for string keys

Character comparision complexity:

  • Brute Force: O(d n k)
  • Prefix Trie: O(d log(k))

Where

  • d: number of characters in document
  • n: number of keywords
  • k: average keyword length

Usage

    trie := ptrie.New()
    for key, value := pairs {
        if err = trie.Put(key, value);err != nil {
            log.Fatal(err)
         }
    }
    //...
    has := trie.Has(key)
    value, has := trie.Get(key)
    //...
    matched := trie.MatchAll(input,  func(key []byte, value interface{}) bool {
        fmt.Printf("matched: key: %s, value %v\n", key, value)
        return true 
    })
    
  1. Building
    trie := ptrie.New()
    
    for key, value := pairs {
         if err = trie.Put(key, value);err != nil {
         	log.Fatal(err)
         }
    }
    
    writer := new(bytes.Buffer)
	if err := trie.Encode(writer);err != nil {
		log.Fatal(err)
	}
	encoded := write.Bytes()
	//write encode data
  1. Loading
    //V type can be any type
    var v *V
    

    trie := ptrie.New()
    trie.UseType(reflect.TypeOf(v))
    if err := trie.Decode(reader);err != nil {
    	log.Fatal(err)
    }
  1. Traversing (range map)
    trie.Walk(func(key []byte, value interface{}) bool {
		fmt.Printf("key: %s, value %v\n", key, value)
		return true
	})
  1. Lookup
    has := trie.Has(key)
    value, has := trie.Get(key)
  1. MatchPrefix
    var input []byte
    ...

    matched := trie.MatchPrefix(input,  func(key []byte, value interface{}) bool {
        fmt.Printf("matched: key: %s, value %v\n", key, value)
        return true 
    })
  1. MatchAll
    var input []byte
    ...

    matched := trie.MatchAll(input,  func(key []byte, value interface{}) bool {
        fmt.Printf("matched: key: %s, value %v\n", key, value)
        return true 
    })

Benchmark

The benchmark count all words that are part of the following extracts:

Lorem Ipsum

  1. Short: avg line size: 20, words: 13
  2. Long: avg line size: 711, words: 551
Benchmark_LoremBruteForceShort-8    	  500000	      3646 ns/op
Benchmark_LoremTrieShort-8          	  500000	      2376 ns/op
Benchmark_LoremBruteForceLong-8     	    1000	   1612877 ns/op
Benchmark_LoremTrieLong-8           	   10000	    119990 ns/op

Hamlet

  1. Short: avg line size: 20, words: 49
  2. Long: avg line size: 41, words: 105
Benchmark_HamletBruteForceShort-8   	   30000	     44306 ns/op
Benchmark_HamletTrieShort-8         	  100000	     18530 ns/op
Benchmark_HamletBruteForceLong-8    	   10000	    226836 ns/op
Benchmark_HamletTrieLong-8          	   50000	     39329 ns/op
Code coverage

GoCover

License

The source code is made available under the terms of the Apache License, Version 2, as stated in the file LICENSE.

Individual files may be made available under their own specific license, all compatible with Apache License, Version 2. Please see individual files for details.

Credits and Acknowledgements

Library Author: Adrian Witas

You might also like...
A Go implementation of a radix tree, that uses binary searches to speed up insert, retrieve and delete operations on dense trees

radixs A Go implementation of a radix tree, that uses binary searches to speed up insert, retrieve and delete operations on dense trees. This implemen

An app with Trie tree and Breve search Implementation CLI and HTTP both 🥳

Introduction LifeLongLearner project consists of two different parts. My English Vocabulary My Technical Book Notes All of them provided by me within

 A tree like tool help you to explore data structures in your redis server
A tree like tool help you to explore data structures in your redis server

Redis-view is a tree like tool help you explore data structures in your redis server

AVL tree with some useful extensions written in Go

gocover An AVL tree (Adel'son-Vel'skii & Landis) is a binary search tree in which the heights of the left and right subtrees of the root differ by at

an R-Tree library for Go

rtreego A library for efficiently storing and querying spatial data in the Go programming language. About The R-tree is a popular data structure for e

Just an itsy bitsy b-tree in Go

tinybtree Just an itsy bitsy b-tree. Usage Keys are strings, values are interfaces. Functions Get(key string) (value interface{}, gotten bool) Set(key

Tree algorithms in Golang

Tree Algorithms in Golang This is my humble attempt to share some of the tree algorithms in Golang. Pull requests are always welcome! :) Contents Tree

Simple code just to try out and Binary Tree on Golang.

Character counter | ▮▮▮▮▮▮▮▮ Simple code just to try out and Binary Tree on Golang. Count characters to train openning a file and reading it, as well

Golang channel example with equivalent binary tree
Golang channel example with equivalent binary tree

golang_channel_example_with_equivalent_binary_tree Exercise: Equivalent Binary Trees There can be many different binary trees with the same sequence o

Comments
  • Use Generics

    Use Generics

    Hi,

    I wondered if you are going to update the code to use generics. Someone already forked the repository and did that, apply that commit here as well. See https://github.com/RyuaNerin/ptrie/commit/ec379967f5417c888efa2faa5929945e6261ec69

    Thanks

    opened by lhemala 0
Releases(v0.3.0)
Owner
Viant, Inc
Viant, Inc
Levenshtein distance and similarity metrics with customizable edit costs and Winkler-like bonus for common prefix.

A Go package for calculating the Levenshtein distance between two strings This package implements distance and similarity metrics for strings, based o

AGExt 74 Dec 15, 2022
Data structure and relevant algorithms for extremely fast prefix/fuzzy string searching.

Trie Data structure and relevant algorithms for extremely fast prefix/fuzzy string searching. Usage Create a Trie with: t := trie.New() Add Keys with:

Derek Parker 623 Dec 27, 2022
A prefix-enhanced map in Go

PrefixMap PrefixMap is a prefix-enhanced map that eases the retrieval of values based on key prefixes. Quick Start Creating a PrefixMap // creates the

Alessandro Diaferia 30 Jun 13, 2022
A Merkle Tree implementation written in Go.

Merkle Tree in Golang An implementation of a Merkle Tree written in Go. A Merkle Tree is a hash tree that provides an efficient way to verify the cont

Cameron Bergoon 406 Jan 5, 2023
An yet-another red-black tree implementation, with a C++ STL-like API.

A red-black tree with an API similar to C++ STL's. INSTALLATION go get github.com/yasushi-saito/rbtree EXAMPLE More examples can be fou

Yasushi Saito 18 Apr 25, 2022
An R-tree implementation for Go

rtree This package provides an in-memory R-Tree implementation for Go. It's designed for Tile38 and is optimized for fast rect inserts and replacement

Josh Baker 236 Dec 29, 2022
An immutable radix tree implementation in Golang

go-immutable-radix Provides the iradix package that implements an immutable radix tree. The package only provides a single Tree implementation, optimi

HashiCorp 859 Dec 29, 2022
B-tree implementation for Go

btree btree is a Go implementation of a B-Tree. This project is intended for learning purposes so the code is relatively small (<500LOC) and highly do

Amit Davidson 214 Dec 31, 2022
Go implementation of the van Emde Boas tree data structure: Priority queue for positive whole numbers in O(log log u) time.

vEB Go implementation of the van Emde Boas tree data structure: Priority queue for positive whole numbers in O(log log u) time. Supports the following

null 4 Mar 7, 2022
Go-merkle - Merkle tree implementation in Golang

go-merkle go-merkle implements a simple merkle tree in Golang. It allows to obta

atomixwap 2 Aug 8, 2022