hairetsu

README

hairetsu

hairetsu is a TRIE implementation by double array.

alpha quality : things would change.

feature

• support ExactMatchSearch CommonPrefixSearch
• can use any binary as a label
  • including \0
  • Some other implementations treat \0 as the end of string, so that they can't use keys including \0 as a label.
• can customize the character code of the label
• can use as a key value store
  • can store 30bit uint value as a leaf

how to use

build byte based TRIE and query

func TestByteTrie(t *testing.T) {
	data := [][]byte{
		[]byte("aa"),
		[]byte("aaa"),
		[]byte("ab"),
		[]byte("abb"),
		[]byte("abc"),
		[]byte("abcd"),
		[]byte("b"),
		[]byte("ba"),
		[]byte("bb"),
		[]byte("c"),
		[]byte("cd"),
		[]byte("cddd"),
		[]byte("ccd"),
		[]byte("ddd"),
		[]byte("eab"),
		[]byte("日本語"),
		[]byte{math.MaxUint8, 0, math.MaxInt8},
	}

	trie, err := hairetsu.NewByteTrieBuilder().BuildSlice(data)
	assert.NoError(t, err)

	for i, x := range data {
		actual, err := trie.ExactMatchSearch(x)
		assert.NoError(t, err, x)
		assert.Equal(t, node.Index(i), actual)
	}

	ng := [][]byte{
		[]byte("a"),
		[]byte("aac"),
	}

	for _, x := range ng {
		_, err := trie.ExactMatchSearch(x)
		assert.Error(t, err, x)
	}

	target := []byte("abcedfg")
	is, err := trie.CommonPrefixSearch(target)
	assert.NoError(t, err)

	n := 0
	for _, x := range data {
		if bytes.HasPrefix(target, x) {
			n++
		}
	}

	assert.Equal(t, n, len(is))
}

build rune based trie and query

func TestRuneTrie(t *testing.T) {
	data := []string{
		"aa",
		"aaa",
		"ab",
		"abb",
		"abc",
		"abcd",
		"b",
		"ba",
		"bb",
		"c",
		"cd",
		"cddd",
		"ccd",
		"ddd",
		"eab",
		"日本語",
	}

	trie, err := hairetsu.NewRuneTrieBuilder().BuildSlice(data)
	assert.NoError(t, err)

	for i, x := range data {
		actual, err := trie.ExactMatchSearch(x)
		assert.NoError(t, err, x)
		assert.Equal(t, node.Index(i), actual)
	}

	ng := []string{
		"a",
		"aac",
	}

	for _, x := range ng {
		_, err := trie.ExactMatchSearch(x)
		assert.Error(t, err, x)
	}

	target := "abcedfg"
	is, err := trie.CommonPrefixSearch(target)
	assert.NoError(t, err)

	n := 0
	for _, x := range data {
		if strings.HasPrefix(target, x) {
			n++
		}
	}

	assert.Equal(t, n, len(is))
}

test

$ make test

Documentation

Index

• type ByteTrie
  • func NewByteTrie(data da.Nodes) *ByteTrie
  • func (t *ByteTrie) CommonPrefixSearch(key []byte) ([]node.Index, error)
  • func (t *ByteTrie) ExactMatchSearch(key []byte) (node.Index, error)
  • func (t *ByteTrie) WriteTo(w io.Writer) (int64, error)
• type ByteTrieBuilder
  • func NewByteTrieBuilder(opt ...da.Option) *ByteTrieBuilder
  • func (b *ByteTrieBuilder) Build(ks da.Walker) (*ByteTrie, error)
  • func (b *ByteTrieBuilder) BuildSlice(xs [][]byte) (*ByteTrie, error)
• type DictTrie
  • func NewDictTrie(data da.Nodes, dict dict.Dict) *DictTrie
  • func (t *DictTrie) CommonPrefixSearch(key []byte) ([]node.Index, error)
  • func (t *DictTrie) ExactMatchSearch(key []byte) (node.Index, error)
  • func (t *DictTrie) GetDict() dict.Dict
  • func (t *DictTrie) ReadFrom(r io.Reader) (int64, error)
  • func (t *DictTrie) WriteTo(w io.Writer) (int64, error)
• type DictTrieBuilder
  • func NewDictTrieBuilder(opt ...da.Option) *DictTrieBuilder
  • func (b *DictTrieBuilder) Build(ks doublearray.Walker, dict dict.Dict) (*DictTrie, error)
  • func (b *DictTrieBuilder) BuildFromLines(r io.Reader) (*DictTrie, error)
• type RuneTrie
  • func NewRuneTrie(data da.Nodes, dict runes.Dict) *RuneTrie
  • func (t *RuneTrie) CommonPrefixSearch(key string) ([]node.Index, error)
  • func (t *RuneTrie) ExactMatchSearch(key string) (node.Index, error)
  • func (t *RuneTrie) GetDict() runes.Dict
  • func (t *RuneTrie) ReadFrom(r io.Reader) (int64, error)
  • func (t *RuneTrie) WriteTo(w io.Writer) (int64, error)
• type RuneTrieBuilder
  • func NewRuneTrieBuilder(opt ...da.Option) *RuneTrieBuilder
  • func (b *RuneTrieBuilder) Build(ks da.Walker, dict runes.Dict) (*RuneTrie, error)
  • func (b *RuneTrieBuilder) BuildFromLines(r io.Reader) (*RuneTrie, error)
  • func (b *RuneTrieBuilder) BuildSlice(xs []string) (*RuneTrie, error)

Types

type ByteTrie

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

func NewByteTrie

func NewByteTrie(data da.Nodes) *ByteTrie

func (*ByteTrie) CommonPrefixSearch

func (t *ByteTrie) CommonPrefixSearch(key []byte) ([]node.Index, error)

func (*ByteTrie) ExactMatchSearch

func (t *ByteTrie) ExactMatchSearch(key []byte) (node.Index, error)

func (*ByteTrie) WriteTo

func (t *ByteTrie) WriteTo(w io.Writer) (int64, error)

type ByteTrieBuilder

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

func NewByteTrieBuilder

func NewByteTrieBuilder(opt ...da.Option) *ByteTrieBuilder

func (*ByteTrieBuilder) Build

func (b *ByteTrieBuilder) Build(ks da.Walker) (*ByteTrie, error)

func (*ByteTrieBuilder) BuildSlice

func (b *ByteTrieBuilder) BuildSlice(xs [][]byte) (*ByteTrie, error)

type DictTrie

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

func NewDictTrie

func NewDictTrie(data da.Nodes, dict dict.Dict) *DictTrie

func (*DictTrie) CommonPrefixSearch

func (t *DictTrie) CommonPrefixSearch(key []byte) ([]node.Index, error)

func (*DictTrie) ExactMatchSearch

func (t *DictTrie) ExactMatchSearch(key []byte) (node.Index, error)

func (*DictTrie) GetDict

func (t *DictTrie) GetDict() dict.Dict

func (*DictTrie) ReadFrom

func (t *DictTrie) ReadFrom(r io.Reader) (int64, error)

func (*DictTrie) WriteTo

func (t *DictTrie) WriteTo(w io.Writer) (int64, error)

type DictTrieBuilder

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

func NewDictTrieBuilder

func NewDictTrieBuilder(opt ...da.Option) *DictTrieBuilder

func (*DictTrieBuilder) Build

func (b *DictTrieBuilder) Build(ks doublearray.Walker, dict dict.Dict) (*DictTrie, error)

func (*DictTrieBuilder) BuildFromLines

func (b *DictTrieBuilder) BuildFromLines(r io.Reader) (*DictTrie, error)

type RuneTrie

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

func NewRuneTrie

func NewRuneTrie(data da.Nodes, dict runes.Dict) *RuneTrie

func (*RuneTrie) CommonPrefixSearch

func (t *RuneTrie) CommonPrefixSearch(key string) ([]node.Index, error)

func (*RuneTrie) ExactMatchSearch

func (t *RuneTrie) ExactMatchSearch(key string) (node.Index, error)

func (*RuneTrie) GetDict

func (t *RuneTrie) GetDict() runes.Dict

func (*RuneTrie) ReadFrom

func (t *RuneTrie) ReadFrom(r io.Reader) (int64, error)

func (*RuneTrie) WriteTo

func (t *RuneTrie) WriteTo(w io.Writer) (int64, error)

type RuneTrieBuilder

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

func NewRuneTrieBuilder

func NewRuneTrieBuilder(opt ...da.Option) *RuneTrieBuilder

func (*RuneTrieBuilder) Build

func (b *RuneTrieBuilder) Build(ks da.Walker, dict runes.Dict) (*RuneTrie, error)

func (*RuneTrieBuilder) BuildFromLines

func (b *RuneTrieBuilder) BuildFromLines(r io.Reader) (*RuneTrie, error)

func (*RuneTrieBuilder) BuildSlice

func (b *RuneTrieBuilder) BuildSlice(xs []string) (*RuneTrie, error)