tree

README

wx

Modified from the fork to allow better serialization and severall small modifications. most dependencies has been included due to the needed changes and since they are pretty old.

Much Kudos to original Developer.

wx is a Go library for a succint representation of trie

NOTE: wx is not stable yet. please use this for research only, and DON'T use this for production. I hope that this will be stable soon.

wx stores a set of strings, and supports PrefixMatch and PredictiveMatch operations. Each string is assigned to an unique ID from [0, num), and a user can retrieve a string from ID using Get() method.

Trie tree information and leading edge information is stored using LOUDS representation.

Usage

import "github.com/hillbig/wx"

// To use wx, first prepare the builder by wx.NewBuilder
// and then set keys using Add()
wxb := wx.NewBuilder()
wxb.Add("to")
wxb.Add("tea")
wxb.Add("ten")
wxb.Add("ten") // duplicated key is removed
wxb.Add("i")
wxb.Add("in")
wxb.Add("inn")
wxb.Add("we")

w := wxb.Buid()

fmt.Printf("%d\n", w.Num()) // 7 (Note: duplicated "ten" is not added)

// If found, ok = true, and id corresponds to the unique id assigned by wx
ret, ok := w.ExactMatch("tea cup.")

// Can retrieve string using id
fmt.Printf("I like %s\n", ok, w.Get(id)) // I like tea

// LongestPrefixMatch(str) returns the key that matches the longest prefix of str
key := "tea cup"
ret, ok := w.LongestPrefixMatch(key)
fmt.Printf("%s %s", w.Get(ret.ID), key[0:ret.Len]) // tea tea

// CommonPrefixMatch(str) returns all the keys that match prefix of str
rets := w.CommonPrefixMatch("innnnnn")
for _, r := range rets {
	fmt.Printf("%s\n", w.Get(r.ID))
}
// i
// in
// inn

// Predictivematch(str) returns all the keys whose strict prefix matches to str
ids := w.PredictiveMatch("i")
for _ id := range ids {
	fmt.Printf("%s\n", w.Get(id))
}
// in
// inn

// If you limit the number of returns, use WithLimit versions

w.CommonPrefixMatchWithLimit("innnnnn", 2) // i in
w.PredictiveMatchWithLimit("i", 2) // i in

// Encode to binary representation
bytes, err := vs.MarshalBinary()
newvs := vecstring.New()

// Decode from binary presentation
err := newvs.UnmarshalBinary(bytes)

Documentation

Overview

package tree provides a succinct trie containing a set of strings

Index

• type Builder
  • func NewBuilder() Builder
• type WX
  • func New() WX
• type WXString

Types

type Builder

type Builder interface {
	// Add adds a key to the WX
	// A duplicatad　key is removed.
	Add(key string)

	// Build builds a WX (Builder is not changed)
	Build() WX

	// Num returns the number of registered keys
	Num() uint64

	// TotalByteNum returns the number of bytes of keys.
	TotalByteNum() uint64
}

Builder is used for building WX.

func NewBuilder

func NewBuilder() Builder

type WX

type WX interface {
	// ExactMatch examines whether the query exactly matches to any string in WX,
	// and returns (id, true) if found, or return (0, false)
	ExactMatch(str string) (id uint64, ok bool)

	// LongestPrefixMatch returns the longest key that matches the prefix of query.
	LongestPrefixMatch(str string) (ret WXString, ok bool)

	// CommonPrefixMatch returns the all keys that match the prefix of the query
	CommonPrefixMatch(str string) (ret []WXString)

	// CommonPrefixMatch returns the all keys that match the prefix of the query
	// limit indicates the maximum number of matched keys.
	CommonPrefixMatchWithLimit(str string, limit uint64) (ret []WXString)

	// PredictiveMatch returns the all keys whose prefix matches to the query
	PredictiveMatch(str string) (ids []uint64)

	// PredictiveMatchWithLimit returns the all keys whose prefix matches to the query
	// limit indicates the maximum number of matched keys
	PredictiveMatchWithLimit(str string, limit uint64) (ids []uint64)

	// Get returns the key with ID.
	Get(id uint64) string

	// Num returns the number of keys
	Num() uint64

	// MarshalBinary encodes WX into a binary form and returns the result.
	MarshalBinary() ([]byte, error)

	// UnmarshalBinary decodes WX from a binary form generated MarshalBinary
	UnmarshalBinary([]byte) error
	// contains filtered or unexported methods
}

WX represents a trie containing a set of strings Given a query Q of length m, WX supports various operations on trie in O(m) time. WX is built by using Builder function

func New

func New() WX

type WXString

type WXString struct {
	ID  uint64
	Len uint64
}

WXString represents an internal representation of string in WX Decode key by Get(ID)