trie

README

Go-Autocomplete-Trie

An autocompl... library for Go by Vivino.

What Is it

Go-Autocomplete-Trie is a simple, configurable autocompletion library for Go. Simply build a dictionary with a slice of strings, optionally configure, and then search.

How to Use

Make a default Trie like so:

t := trie.New()

The default Trie has fuzzy search enabled, string normalisation enabled, a default levenshtein scheme and is case insensitive by default.

Next, just add some strings to the dictionary.

t.Insert("Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday")

Next, search.

t.SearchAll("wdn")

-> []string{"Wednesday"}

Levenshtein is enabled by default.

t.SearchAll("urs")

-> []string{"Thursday", "Tuesday"}

To turn off the features...

t.WithoutLevenshtein().WithoutNormalisation().WithoutFuzzy().CaseSensitive()

Now...

t.SearchAll("urs")

-> []string{}

t.SearchAll("Thu")

-> []string{"Thursday"}

Documentation

Overview

Package trie provides a data structure for autocompletion searching of strings.

Example

t := New()
t.Insert("Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday")

results := t.SearchAll("wdn")
fmt.Println(results)

results2 := t.SearchAll("tsd")
fmt.Println(results2)

Example (NoFeatures)

t := New().CaseSensitive().WithoutFuzzy().WithoutLevenshtein().WithoutNormalisation()
t.Insert("Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday")

results := t.SearchAll("t")
fmt.Println(results)

results2 := t.SearchAll("T")
fmt.Println(results2)

Output:

[]
[Thursday Tuesday]

Index

• type Trie
  • func New() *Trie
  • func (t *Trie) CaseInsensitive() *Trie
  • func (t *Trie) CaseSensitive() *Trie
  • func (t *Trie) CustomLevenshtein(scheme map[uint8]uint8) *Trie
  • func (t *Trie) DefaultLevenshtein() *Trie
  • func (t *Trie) Insert(entries ...string)
  • func (t *Trie) Search(search string, limit int) []string
  • func (t *Trie) SearchAll(search string) []string
  • func (t *Trie) WithFuzzy() *Trie
  • func (t *Trie) WithNormalisation() *Trie
  • func (t *Trie) WithoutDuplicate() *Trie
  • func (t *Trie) WithoutFuzzy() *Trie
  • func (t *Trie) WithoutLevenshtein() *Trie
  • func (t *Trie) WithoutNormalisation() *Trie

Examples

• Package
• Package (NoFeatures)

Types

type Trie

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

Trie is a data structure for storing common prefixes to strings for efficient comparison and retrieval.

func New

func New() *Trie

New creates a new empty trie. By default fuzzy search is on and string normalisation is on. The default levenshtein scheme is on, where search strings of len 1-2 characters allow no distance, search strings of length 3-4 allow a levenshtein distance of 1, and search strings of length 5 or more runes allow a levenshtein distance of two.

func (*Trie) CaseInsensitive

func (t *Trie) CaseInsensitive() *Trie

CaseInsensitive sets the Trie to use case insensitive search.

func (*Trie) CaseSensitive

func (t *Trie) CaseSensitive() *Trie

CaseSensitive sets the Trie to use case sensitive search.

func (*Trie) CustomLevenshtein

func (t *Trie) CustomLevenshtein(scheme map[uint8]uint8) *Trie

CustomLevenshtein sets up a custom levenshtein scheme. WARNING, this function will panic if the scheme is invalid. A valid scheme is a series of pairs of search string length -> levenshtein distance. There must be one entry with zero as search string length.

func (*Trie) DefaultLevenshtein

func (t *Trie) DefaultLevenshtein() *Trie

DefaultLevenshtein sets the trie to use the default levenshtein scheme.

func (*Trie) Insert

func (t *Trie) Insert(entries ...string)

Insert inserts strings into the Trie

func (*Trie) Search

func (t *Trie) Search(search string, limit int) []string

Search will return all complete words in the trie that have the search string as a prefix, taking into account the Trie's settings for normalisation, fuzzy matching and levenshtein distance scheme.

func (*Trie) SearchAll

func (t *Trie) SearchAll(search string) []string

SearchAll is just like Search, but without a limit.

func (*Trie) WithFuzzy

func (t *Trie) WithFuzzy() *Trie

WithFuzzy sets the Trie to use fuzzy matching on search.

func (*Trie) WithNormalisation

func (t *Trie) WithNormalisation() *Trie

WithNormalisation sets the Trie to use normalisation on search. For example, Jurg will find Jürgen, Jürg will find Jurgen.

func (*Trie) WithoutDuplicate

func (t *Trie) WithoutDuplicate() *Trie

ShowHitOnly sets result show hits instead get all.

func (*Trie) WithoutFuzzy

func (t *Trie) WithoutFuzzy() *Trie

WithoutFuzzy sets the Trie not to use fuzzy matching on search.

func (*Trie) WithoutLevenshtein

func (t *Trie) WithoutLevenshtein() *Trie

WithoutLevenshtein sets the Trie not to allow any levenshtein distance between between the search string and any matches.

func (*Trie) WithoutNormalisation

func (t *Trie) WithoutNormalisation() *Trie

WithoutNormalisation sets the Trie not to use normalisation on search. for example Jurg won't find Jürgen, Jürg won't find Jurgen.