wx

README

wx

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 wx 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)