trie

Documentation

Overview

Package trie implements a trie data-structure similar to the one described by Donald E Knuth in “Programming Perls”. (Communications of the ACM, Vol. 29, No. 6, June 1986, https://cecs.wright.edu/people/faculty/pmateti/Courses/7140/PDF/cwp-knuth-cacm-1986.pdf).

The trie is suitable for write-once-read-many-times situations. The idea is to spend some effort to create a compact but efficient dictionary for categorical data.

BSD License

Copyright (c) 2020–2021, Norbert Pillmayer

All rights reserved.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.

2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.

3. Neither the name of this software nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

Index

• func T() tracing.Trace
• type Iterator
  • func (ti *Iterator) Next(c int8) int
• type TinyHashTrie
  • func NewTinyHashTrie(size uint8, catcnt int8) (*TinyHashTrie, error)
  • func (trie *TinyHashTrie) AllocPositionForWord(buf []byte) int
  • func (trie *TinyHashTrie) Freeze()
  • func (trie *TinyHashTrie) Iterator() *Iterator
  • func (trie *TinyHashTrie) Stats()

Functions

func T

func T() tracing.Trace

T traces to the global core tracer

Types

type Iterator

type Iterator struct {
	// contains filtered or unexported fields
}

Iterator is a one-off iterator to find an entry in the trie.

func (*Iterator) Next

func (ti *Iterator) Next(c int8) int

Next will advance the iterator to the next prefix of a word to find. if it returns 0, the prefix is not contained in the trie.

type TinyHashTrie

type TinyHashTrie struct {
	// contains filtered or unexported fields
}

TinyHashTrie is a trie where the address range fits into an uint8 and values to store have a small range. The bytes usually will represent some kind of character classes (category).

func NewTinyHashTrie

func NewTinyHashTrie(size uint8, catcnt int8) (*TinyHashTrie, error)

NewTinyHashTrie creates a new trie. size should be a prime number. catcnt must not be greater than 50.

func (*TinyHashTrie) AllocPositionForWord

func (trie *TinyHashTrie) AllocPositionForWord(buf []byte) int

AllocPositionForWord will allocate a position in the trie for a prefix (this is Knuth's `find_buffer`)

func (*TinyHashTrie) Freeze

func (trie *TinyHashTrie) Freeze()

Freeze will make the trie read-only.

func (*TinyHashTrie) Iterator

func (trie *TinyHashTrie) Iterator() *Iterator

Iterator will return an iterator to advance over prefixes of words to find in the trie.

func (*TinyHashTrie) Stats

func (trie *TinyHashTrie) Stats()

Stats print some useful information about the trie on the Info log channel.