levenshtein

Documentation

Index

• Constants
• func LevenshteinMatch(s1, s2 []byte, k int) bool
• type Levenshtein
  • func New(k, m int, keyword []byte, tokens storage.Tokens) *Levenshtein
  • func (a *Levenshtein) Accept(s State) bool
  • func (a *Levenshtein) Dead(s State) bool
  • func (a *Levenshtein) Matches() iter.Seq[*storage.Token]
  • func (a *Levenshtein) NextSeek(stack []State, key []byte, matched int) []byte
  • func (a *Levenshtein) SmallestTransition(s State, lb int) (byte, bool)
  • func (a *Levenshtein) Start() State
  • func (a *Levenshtein) Step(prev State, c byte) State
• type State

Constants

const (
	MaxLevenshteinLength = 60
	DefaultK             = 1
	DefaultM             = 10
)

Functions

func LevenshteinMatch

func LevenshteinMatch(s1, s2 []byte, k int) bool

LevenshteinMatch reports whether the edit distance between s1 and s2 is <= k. Max supported k is 3. Strings longer than MaxLevenshteinLength return false to prevent DoS via large allocation.

Types

type Levenshtein

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

Levenshtein intersects a Levenshtein automaton (fixed target keyword, max edit distance K) with a byte-sorted tidwall BTreeG[[]byte].

The tree MUST be ordered by bytes.Compare. The whole skip strategy relies on the automaton's byte ordering matching the tree's key ordering.

func New

func New(k, m int, keyword []byte, tokens storage.Tokens) *Levenshtein

func (*Levenshtein) Accept

func (a *Levenshtein) Accept(s State) bool

func (*Levenshtein) Dead

func (a *Levenshtein) Dead(s State) bool

func (*Levenshtein) Matches

func (a *Levenshtein) Matches() iter.Seq[*storage.Token]

Matches yields every term within edit distance k of the keyword, in ascending key order, capped at m. The yielded slice aliases the tree's stored key; copy it if you need to retain or mutate it.

func (*Levenshtein) NextSeek

func (a *Levenshtein) NextSeek(stack []State, key []byte, matched int) []byte

NextSeek: smallest term strictly greater than key that the automaton can still follow. stack[i] is the (non-dead) state after consuming key[:i].

• matched < len(key): key[matched] dead-ended; need a byte > key[matched] here, else backtrack to an earlier position.
• matched == len(key): key fully consumed; try to extend with any byte, else backtrack.

Walking deepest-to-shallowest yields the smallest valid successor (it shares the longest possible prefix with key), so no candidate term is ever skipped.

func (*Levenshtein) SmallestTransition

func (a *Levenshtein) SmallestTransition(s State, lb int) (byte, bool)

SmallestTransition: smallest byte b >= lb whose transition from s is not dead.

func (*Levenshtein) Start

func (a *Levenshtein) Start() State

Start: the row for empty input, [0,1,2,...,n] clamped to k+1.

func (*Levenshtein) Step

func (a *Levenshtein) Step(prev State, c byte) State

Step: transition on one input byte c.

type State

type State []uint8

State is the edit-distance DP row used as the automaton State:

State[i] = min edits to align the input consumed so far against keyword[:i]

Values are clamped to k+1 ("too far"). The automaton consumes the *dictionary term* one byte at a time; the keyword is fixed. Each distinct row is a DFA State; we compute rows lazily instead of materializing the DFA.