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 ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
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
Source Files
Directories
¶
| Path | Synopsis |
|---|---|
|
pkg
|
|
|
fixvec
package fixvec provides a vector representation of value using fixed bits
|
package fixvec provides a vector representation of value using fixed bits |
|
rsdic
Package rsdic provides a rank/select dictionary supporting many basic operations in constant time using very small working space (smaller than original).
|
Package rsdic provides a rank/select dictionary supporting many basic operations in constant time using very small working space (smaller than original). |
|
vecstring
package vecstring provides a space-efficient representation of a vector of strings of variable length.
|
package vecstring provides a space-efficient representation of a vector of strings of variable length. |