trie

Documentation

Index

• type Trie
  • func NewTrie(keys []string, chars *ValidChars) (*Trie, error)
  • func (ss *Trie) HasPrefix(word string) bool
• type ValidChars
  • func NewValidChars(validChars []byte) (v *ValidChars)
  • func (v *ValidChars) IsValidChar(c byte) bool
  • func (v *ValidChars) Size() int

Types

type Trie

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

Trie is a succinct, sorted and static string set impl with compacted trie as storage. The space cost is about half lower than the original data.

Implementation

It stores sorted strings in a compacted trie(AKA prefix tree). A trie node has at most 256 outgoing labels. A label is just a single byte. E.g., [ab, abc, abcd, axy, buv] is represented with a trie like the following: (Numbers are node id)

^ -a-> 1 -b-> 3 $
  |      |      `c-> 6 $
  |      |             `d-> 9 $
  |      `x-> 4 -y-> 7 $
  `b-> 2 -u-> 5 -v-> 8 $

Internally it uses a packed []byte and a bitmap with `len([]byte)` bits to describe the outgoing labels of a node,:

^: ab  00
1: bx  00
2: u   0
3: c   0
4: y   0
5: v   0
6: d   0
7: ø
8: ø
9: ø

In storage it packs labels together and bitmaps joined with separator `1`:

labels(ignore space): "ab bx u c y v d"
label bitmap:          0010010101010101111

Finally leaf nodes are indicated by another bitmap `leaves`, in which a `1` at i-th bit indicates the i-th node is a leaf:

leaves: 0001001111

func NewTrie

func NewTrie(keys []string, chars *ValidChars) (*Trie, error)

NewTrie creates a new *Trie struct, from a slice of sorted strings.

func (*Trie) HasPrefix

func (ss *Trie) HasPrefix(word string) bool

HasPrefix query for a word and return whether a prefix of the word is in the Trie.

type ValidChars

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

func NewValidChars

func NewValidChars(validChars []byte) (v *ValidChars)

func (*ValidChars) IsValidChar

func (v *ValidChars) IsValidChar(c byte) bool

func (*ValidChars) Size

func (v *ValidChars) Size() int