README
¶
cedar
Package cedar implementes double-array trie and aho corasick
It is implements the cedar and paper by golang.
Install
go get -u 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))
}
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) Delete(key []byte) error
- func (cd *Cedar) ExactMatch(key []byte) (int32, bool)
- func (cd *Cedar) Find(key []byte, from int32) (int32, error)
- func (cd *Cedar) Get(key []byte) (value int32, err error)
- func (cd *Cedar) Insert(key []byte, val int32) error
- func (cd *Cedar) Jump(key []byte, from int32) (to int32, err error)
- func (cd *Cedar) PrefixMatch(key []byte, n ...int) (ids []int32)
- func (cd *Cedar) PrefixPredict(key []byte, n ...int) (ids []int32)
- func (cd *Cedar) Update(key []byte, value int32) error
- func (cd *Cedar) Value(path int32) (val int32, err error)
- type NInfo
- type Node
Constants ¶
const ( // ValLimit cedar value limit ValLimit = int32(^uint32(0) >> 1) // 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") )
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.
Because of type conversion, this version all int16 and int32 uses int, witch will be optimized in the next version.
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) ExactMatch ¶
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) PrefixMatch ¶
PrefixMatch return the collection of the common prefix in the dictionary with the `key`
func (*Cedar) PrefixPredict ¶
PrefixPredict eturn the list of words in the dictionary that has `key` as their prefix
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