typeahead

package module

v0.0.0-...-b7c560b Latest Latest Go to latest Published: Nov 10, 2018 License: Apache-2.0 Imports: 3 Imported by: 1

Details

Valid go.mod file

The Go module system was introduced in Go 1.11 and is the official dependency management solution for Go.
Redistributable license

Redistributable licenses place minimal restrictions on how software can be used, modified, and redistributed.
Tagged version

Modules with tagged versions give importers more predictable builds.
Stable version

When a project reaches major version v1 it is considered stable.
Learn more about best practices

Repository

github.com/alextanhongpin/typeahead

Links

Open Source Insights

README ¶

go-ahead

A text autocompleter with golang. The goal is to create a google-like autocomplete. Based on some research done, it seems like google is implementing it using radix/patricia tree. The implementation here is probably a slightly more naive version than what google has.

Radix tree is more storage efficient than a trie (?).

Another interesting implementation is the typeahead by Facebook.

Installation

$ go get github.com/alextanhongpin/typeahead

TODO

Create an actual server that can add new search suggestions.
Improve the scoring/ranking algorithm.
Look into a better way to identify performance issue
Perform testing with quickcheck
Persist datastructure using gob encoding
Load the complete words dataset
Add context and include auto-correct capabilities
Find ways to stream new data to increment the count and effectiveness of the radix trie

References

http://dhruvbird.com/autocomplete.pdf

Documentation ¶

Index ¶

Constants
Variables
func GetBit(key string, n int) int
func TrieContains(trie *Trie, target string) bool
type Edge
- func NewEdge(key []byte, value interface{}) Edge
- func (e Edge) String() string
type Node
- func NewNode() Node
- func (n Node) IsLeaf() bool
- func (n Node) Print(depth int)
type Root
- func New() *Root
- func (r *Root) Find(key []byte) map[string]Edge
- func (r *Root) FindRecursive(key []byte) [][]byte
- func (r *Root) Insert(key []byte, value interface{})
type TernaryNode
- func NewTernaryNode(char rune, endword bool) *TernaryNode
type TernaryTree
- func NewTernaryTree() *TernaryTree
- func (t *TernaryTree) Add(s string)
- func (t *TernaryTree) Contains(str string) bool
- func (t *TernaryTree) Search(str string) (result []string)
- func (t *TernaryTree) Traverse() (result []string)
type Trie
- func NewTrie(key string) *Trie
- func TrieInsert(trie *Trie, key string) *Trie
type TrieNode
- func NewTrieNode(key string) *TrieNode
- func (n *TrieNode) Add(key string)
- func (n *TrieNode) IsLeaf() bool
- func (n *TrieNode) Print(i int)
- func (n *TrieNode) Search(key string) []string
- func (n *TrieNode) String() string

Constants ¶

View Source

const TrieBase = 2

Variables ¶

View Source

var BitsPerByte = 8

http://www.cs.yale.edu/homes/aspnes/pinewiki/RadixSearch.html?highlight=%28CategoryAlgorithmNotes%29 PerByte = 8

Functions ¶

func GetBit ¶

func GetBit(key string, n int) int

func TrieContains ¶

func TrieContains(trie *Trie, target string) bool

Types ¶

type Edge ¶

type Edge struct {
	Count   int
	Key     []byte
	Value   interface{}
	Node    Node
	Endword bool
}

Edge represents the edge of a node.

func NewEdge ¶

func NewEdge(key []byte, value interface{}) Edge

NewEdge creates a new Edge with the given key value pair.

func (Edge) String ¶

func (e Edge) String() string

type Node ¶

type Node struct {
	Edges []Edge
}

Node holds an array of edge.

func NewNode ¶

func NewNode() Node

NewNode returns a new node value.

func (Node) IsLeaf ¶

func (n Node) IsLeaf() bool

IsLeaf returns true if the node does not have any edges.

func (Node) Print ¶

func (n Node) Print(depth int)

Print iteratively prints all the node edges.

type Root ¶

type Root struct {
	Node Node
}

Root represents the root of the radix tree.

func New ¶

func New() *Root

New returns a new tree.

func (*Root) Find ¶

func (r *Root) Find(key []byte) map[string]Edge

Find searches for the edge of the node that matches the given prefix.

func (*Root) FindRecursive ¶

func (r *Root) FindRecursive(key []byte) [][]byte

func (*Root) Insert ¶

func (r *Root) Insert(key []byte, value interface{})

Insert adds a key value pair into the tree.

type TernaryNode ¶

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

func NewTernaryNode ¶

func NewTernaryNode(char rune, endword bool) *TernaryNode

type TernaryTree ¶

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

func NewTernaryTree ¶

func NewTernaryTree() *TernaryTree

func (*TernaryTree) Add ¶

func (t *TernaryTree) Add(s string)

Add adds the item to the tree recursively.

func (*TernaryTree) Contains ¶

func (t *TernaryTree) Contains(str string) bool

func (*TernaryTree) Search ¶

func (t *TernaryTree) Search(str string) (result []string)

Search implements an autocomplete for ternary search tree.

func (*TernaryTree) Traverse ¶

func (t *TernaryTree) Traverse() (result []string)

type Trie ¶

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

func NewTrie ¶

func NewTrie(key string) *Trie

func TrieInsert ¶

func TrieInsert(trie *Trie, key string) *Trie

type TrieNode ¶

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

func NewTrieNode ¶

func NewTrieNode(key string) *TrieNode

func (*TrieNode) Add ¶

func (n *TrieNode) Add(key string)

func (*TrieNode) IsLeaf ¶

func (n *TrieNode) IsLeaf() bool

func (*TrieNode) Print ¶

func (n *TrieNode) Print(i int)

Print prints the whole tree.

func (*TrieNode) Search ¶

func (n *TrieNode) Search(key string) []string

func (*TrieNode) String ¶

func (n *TrieNode) String() string

Source Files ¶

View all Source files

Directories ¶

Path	Synopsis
cmd

?	: This menu
/	: Search site
f or F	: Jump to
y or Y	: Canonical URL