Documentation
¶
Index ¶
- Constants
- func LevenshteinMatch(s1, s2 []byte, k int) bool
- type 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 )
Variables ¶
This section is empty.
Functions ¶
func LevenshteinMatch ¶
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 (*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.
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.
Source Files