README
¶
cedar
Package cedar implements an updatable double-array trie and aho corasick.
It is a Go port of cedar (see the paper).
Install
go get github.com/vcaesar/cedar
Usage
package main
import (
"fmt"
"github.com/vcaesar/cedar"
)
func main() {
// Create a new cedar trie.
d := cedar.New()
d.Insert([]byte("ab"), 1)
d.Insert([]byte("abc"), 2)
d.Insert([]byte("abcd"), 3)
fmt.Println(d.Jump([]byte("ab"), 0))
fmt.Println(d.Find([]byte("bc"), 0))
fmt.Println(d.PrefixMatch([]byte("bc"), 0))
fmt.Println(d.ExactMatch([]byte("ab")))
}
Aho-Corasick
Package aho builds an Aho-Corasick automaton on top of the trie for
multi-pattern search. Patterns can be inserted and deleted at any time; the
failure links are rebuilt lazily on the next Match.
package main
import (
"fmt"
"github.com/vcaesar/cedar/aho"
)
func main() {
// NewStrings uses the pattern index as its value,
// or Insert patterns with your own values.
m := aho.NewStrings("he", "she", "his", "hers")
m.Insert([]byte("太阳系"), 100)
text := []byte("ushers 太阳系")
fmt.Println(m.Has(text))
for _, t := range m.Match(text) {
fmt.Printf("value=%d at=%d len=%d key=%q\n", t.Value, t.At, t.Len, m.Key(text, t))
}
// persist the trie as "gob" or "json"
m.SaveToFile("patterns.json", "json")
loaded := aho.New()
loaded.LoadFromFile("patterns.json", "json")
// stream the node ids of the patterns starting with "h"
for id := range loaded.PrefixPredict([]byte("h"), 0, 4) {
fmt.Println(loaded.Cedar().Value(id))
}
// visualise: dot -Tsvg trie.gv -o trie.svg
loaded.DumpGraph("trie.gv")
}
Output:
true
value=1 at=1 len=3 key="she"
value=0 at=2 len=2 key="he"
value=3 at=2 len=4 key="hers"
value=100 at=7 len=9 key="太阳系"
See examples/aho for the full demo (go run ./examples/aho).
License
This is released under the BSD-2 license, following the original license of C++ cedar.
Reference
Documentation
¶
Index ¶
- Constants
- Variables
- type Block
- type Cedar
- func (cd *Cedar) Children(from int, dst []byte) []byte
- func (cd *Cedar) Delete(key []byte) error
- func (cd *Cedar) ExactMatch(key []byte) (int, bool)
- func (cd *Cedar) Find(key []byte, from int) (int, error)
- func (cd *Cedar) Get(key []byte) (value int, err error)
- func (cd *Cedar) GobDecode(data []byte) error
- func (cd *Cedar) GobEncode() ([]byte, error)
- func (cd *Cedar) Insert(key []byte, val int) error
- func (cd *Cedar) Jump(key []byte, from int) (to int, err error)
- func (cd *Cedar) MarshalJSON() ([]byte, error)
- func (cd *Cedar) PrefixMatch(key []byte, n ...int) (ids []int)
- func (cd *Cedar) PrefixPredict(key []byte, n ...int) (ids []int)
- func (cd *Cedar) Size() int
- func (cd *Cedar) UnmarshalJSON(data []byte) error
- func (cd *Cedar) Update(key []byte, value int) error
- func (cd *Cedar) Value(path int) (val int, err error)
- type NInfo
- type Node
Constants ¶
const ( // ValLimit cedar value limit, the values are stored as int32 ValLimit = math.MaxInt32 // NoVal not have value NoVal = -1 )
Variables ¶
var ( // ErrNoKey not have key error ErrNoKey = errors.New("cedar: not have key") // ErrNoVal not have value error ErrNoVal = errors.New("cedar: not have val") // ErrInvalidKey invalid key error ErrInvalidKey = errors.New("cedar: invalid key") // ErrInvalidVal invalid value error ErrInvalidVal = errors.New("cedar: invalid val") // ErrInvalidData malformed serialized trie error ErrInvalidData = errors.New("cedar: invalid data") )
Functions ¶
This section is empty.
Types ¶
type Block ¶
type Block struct {
// contains filtered or unexported fields
}
Block stores the linked-list pointers and the stats info for blocks.
All fields fit in int32 (block indexes are < 2^24, counters are <= 257, and eHead is a node index which is bounded by ValLimit), which halves the per-block footprint compared to int.
type Cedar ¶
type Cedar struct {
// Reduced option the reduced trie
Reduced bool
// contains filtered or unexported fields
}
Cedar holds all of the information about double array trie.
func (*Cedar) Children ¶ added in v0.50.0
Children appends the labels of the edges leaving node `from` to dst, in sibling-chain order, skipping the terminal edge (label 0). Follow an edge with Jump.
func (*Cedar) ExactMatch ¶ added in v0.20.0
ExactMatch to check if `key` is in the dictionary.
func (*Cedar) Find ¶
Find key from double array trie, with `from` as the cursor to traverse the nodes.
func (*Cedar) Jump ¶
Jump jump a node `from` to another node by following the `path`, split by find()
func (*Cedar) MarshalJSON ¶ added in v0.50.0
MarshalJSON implements json.Marshaler.
func (*Cedar) PrefixMatch ¶ added in v0.20.0
PrefixMatch return the collection of the common prefix in the dictionary with the `key`
func (*Cedar) PrefixPredict ¶ added in v0.20.0
PrefixPredict eturn the list of words in the dictionary that has `key` as their prefix
func (*Cedar) Size ¶ added in v0.50.0
Size returns the length of the double array; every node index is below it.
func (*Cedar) UnmarshalJSON ¶ added in v0.50.0
UnmarshalJSON implements json.Unmarshaler.
type NInfo ¶
type NInfo struct {
// contains filtered or unexported fields
}
NInfo stores the information about the trie
type Node ¶
type Node struct {
// contains filtered or unexported fields
}
Node contains the array of `base` and `check` as specified in the paper: "An efficient implementation of trie structures" https://dl.acm.org/citation.cfm?id=146691
Source Files
Directories