trie

Documentation

Index

• type ComparableFuzzable
• type DistanceResult
• type DistanceTrees
  • func NewDistanceTrees[T ComparableFuzzable](trees []*Tree[T]) *DistanceTrees[T]
  • func (wt *DistanceTrees[T]) Search(ctx context.Context, searchTerm string) ([]*DistanceResult[T], error)
  • func (wt *DistanceTrees[T]) SetTimer(timer Timer)
• type Fuzzable
• type KeyTermExtractor
• type NoOpTimer
  • func (NoOpTimer) RecordNodeSearchIteration(_ context.Context, _ time.Duration) error
  • func (NoOpTimer) RecordSortTime(_ context.Context, _ time.Duration) error
  • func (NoOpTimer) RecordTreeSearch(_ context.Context, _ time.Duration) error
• type Node
  • func (n *Node[T]) Contains(phrase string) bool
  • func (n *Node[T]) GetKeyTerm() string
  • func (n *Node[T]) GetParentNode() *Node[T]
  • func (n *Node[T]) GetValues() []T
• type Timer
• type Tree
  • func LoadTree[T any](ctx context.Context, items []T, termExtractor KeyTermExtractor[T]) (*Tree[T], error)
  • func (t *Tree[T]) GetLeafNodes() []*Node[T]

Types

type ComparableFuzzable

type ComparableFuzzable interface {
	comparable
	Fuzzable
}

ComparableFuzzable is a combinatory interface of Fuzzable and the comparable keyword

type DistanceResult

type DistanceResult[T any] struct {
	Distances []*int
	Result    T
}

DistanceResult is a result of a fuzzy search, containing the result and the distance from the search term.

type DistanceTrees

type DistanceTrees[T ComparableFuzzable] struct {
	// contains filtered or unexported fields
}

DistanceTrees is a search mechanism supporting fuzzy search across multiple trees, each one weighed lower in priority to the previous one. This allows, for example, the fuzzy searching of assets by their symbol and then by their name, weighing name as lower in priority of a match than the symbol.

func NewDistanceTrees

func NewDistanceTrees[T ComparableFuzzable](trees []*Tree[T]) *DistanceTrees[T]

func (*DistanceTrees[T]) Search

func (wt *DistanceTrees[T]) Search(ctx context.Context, searchTerm string) ([]*DistanceResult[T], error)

Search searches the trees within this DistanceTrees instance for the given search term, returning results with their primary and secondary distances

func (*DistanceTrees[T]) SetTimer

func (wt *DistanceTrees[T]) SetTimer(timer Timer)

SetTimer sets the Timer implementation to be used by this tree to measure its behavior

type Fuzzable

type Fuzzable interface {
	// GetPrimaryDistanceFactor gets the primary distance factor, if any.
	GetPrimaryDistanceFactor() *float64

	// GetSecondaryDistances gets any and all secondary instances in the event of otherwise-equal-weights to be used to elevate
	// the relevance of a term
	GetSecondaryDistances() []*int

	// SortingGroup gets the zero-based index of the sorting group for purposes of determining rank of an asset relative to others.
	// This allows members within a particular sorting group to be ranked relative to each other.
	SortingGroup() int
}

Fuzzable describes an object that can participate in a fuzzy search

type KeyTermExtractor

type KeyTermExtractor[T any] func(context.Context, T) (string, error)

KeyTermExtractor is a function used to, while loading a Node tree, extract the tree placement term from a given value.

type NoOpTimer

type NoOpTimer struct {
}

NoOpTimer is a Timer implementation that doesn't do anything

func (NoOpTimer) RecordNodeSearchIteration

func (NoOpTimer) RecordNodeSearchIteration(_ context.Context, _ time.Duration) error

func (NoOpTimer) RecordSortTime

func (NoOpTimer) RecordSortTime(_ context.Context, _ time.Duration) error

func (NoOpTimer) RecordTreeSearch

func (NoOpTimer) RecordTreeSearch(_ context.Context, _ time.Duration) error

type Node

type Node[T any] struct {
	// contains filtered or unexported fields
}

Node defines a node participating in a trie tree

func (*Node[T]) Contains

func (n *Node[T]) Contains(phrase string) bool

Contains determines if the key term of this node contains the characters of the given phrase in the order given. The key term does not need to contiguously contain the phrase's characters - e.g., if the phrase is 'cal', this will return true if the key term is 'catapult'.

func (*Node[T]) GetKeyTerm

func (n *Node[T]) GetKeyTerm() string

GetKeyTerm gets the string value for which this node represents a word in the tree

func (*Node[T]) GetParentNode

func (n *Node[T]) GetParentNode() *Node[T]

GetParentNode gets this node's parent node; if this is the root node, this will return nil.

func (*Node[T]) GetValues

func (n *Node[T]) GetValues() []T

GetValues gets the values stored within this node.

type Timer

type Timer interface {
	// RecordTreeSearch records the amount of time spent searching the nodes of a single Tree instance.
	RecordTreeSearch(ctx context.Context, searchDuration time.Duration) error
	// RecordNodeSearchIteration records the amount of time spent evaluating an individual Node's candidacy for matching a search phrase.
	RecordNodeSearchIteration(ctx context.Context, searchDuration time.Duration) error
	// RecordSortTime records the amount of time spent sorting the final results in a search operation.
	RecordSortTime(ctx context.Context, sortDuration time.Duration) error
}

Timer defines a means of recording time measurements of operations of a DistanceTrees.

type Tree

type Tree[T any] struct {
	// contains filtered or unexported fields
}

Tree defines a trie tree that only allows bottom-up traversal. This is structured as such because it is assumed that, if a search term does not sufficiently exist in a particular node, then it will not sufficiently exist in parent nodes (e.g., if searching for 'o' and the current node is "BTC", then the parent nodes "BT" and "B" will never satisfy the search term, either). This allows the traversal of the tree to terminate and discard consideration of entire ancestries of nodes in the trie tree.

func LoadTree

func LoadTree[T any](ctx context.Context, items []T, termExtractor KeyTermExtractor[T]) (*Tree[T], error)

LoadTree builds a Trie tree from the given items, using the given termExtractor to extract the tree placement term from each item.

func (*Tree[T]) GetLeafNodes

func (t *Tree[T]) GetLeafNodes() []*Node[T]

GetLeafNodes gets all the leaf nodes of the tree.