README
¶
levenshtein
-- import "github.com/dvirsky/levenshtein"
Usage
type SparseAutomaton
type SparseAutomaton struct {
}
SparseAutomaton is a naive Go implementation of a levenshtein automaton using sparse vectors, as described and implemented here: http://julesjacobs.github.io/2015/06/17/disqus-levenshtein-simple-and-fast.html
func NewSparseAutomaton
func NewSparseAutomaton(s string, maxEdits int) *SparseAutomaton
NewSparseAutomaton creates a new automaton for the string s, with a given max edit distance check
func (*SparseAutomaton) CanMatch
func (a *SparseAutomaton) CanMatch(v sparseVector) bool
CanMatch returns true if there is a possibility that feeding the automaton with more steps will yield a match. Once CanMatch is false there is no point in continuing iteration
func (*SparseAutomaton) IsMatch
func (a *SparseAutomaton) IsMatch(v sparseVector) bool
IsMatch returns true if the current state vector represents a string that is within the max edit distance from the initial automaton string
func (*SparseAutomaton) Start
func (a *SparseAutomaton) Start() sparseVector
Start initializes the automaton's state vector and returns it for further iteration
func (*SparseAutomaton) Step
func (a *SparseAutomaton) Step(state sparseVector, c byte) sparseVector
Step returns the next state of the automaton given a pervios state and a character to check
func (*SparseAutomaton) Transitions
func (a *SparseAutomaton) Transitions(v sparseVector) []byte
type Trie
type Trie struct {
}
Trie holds a trie representation of a dictionary of words, for fuzzy matching against it
func NewTrie
func NewTrie() *Trie
NewTrie creates a new empty trie
func (*Trie) Exists
func (t *Trie) Exists(s string) bool
Exists returns true if a string exists as it is in the trie
func (*Trie) FuzzyMatches
func (t *Trie) FuzzyMatches(s string, maxDist int) []string
FuzzyMatches returns all the words in the trie that are with maxDist edit distance from s
func (*Trie) Insert
func (t *Trie) Insert(s string)
Insert adds a string to the trie
type MinTree
type MinTree struct {
mafsa.MinTree
root *MinTreeNode
}
func NewMinTree([]string) (*MinTree, error)
func NewMinTree([]string) (*MinTree, error)
Creates a new MinTree from a sorted list of strings. The list must be sorted because that is what the mafsa package expects.
func NewMinTreeWrite([]string, io.Writer) (*MinTree, error)
func NewMinTreeWrite(words []string, wr io.Writer) (*MinTree, error) {
Creates a new MinTree from a sorted list of strings. The list must be sorted because that is what the mafsa package expects. After the MinTree has been successfully created, the function also writes it to the io.Writer.
func LoadMinTree(io.Reader) (*MinTree, error)
func LoadMinTree(r io.Reader) (*MinTree, error)
LoadMinTree loads a MinTree from an io.Reader.
func (mt *MinTree) FuzzyMatches(string, int) []string
func (mt *MinTree) FuzzyMatches(s string, maxDist int) []string
FuzzyMatches returns all the words in the MinTree that are with maxDist edit distance from s
Documentation
¶
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type MinTree ¶
func LoadMinTree ¶
LoadMinTree loads a MinTree from an io.Reader.
func NewMinTree ¶
Creates a new MinTree from a sorted list of strings. The list must be sorted because that is what the mafsa package expects.
func NewMinTreeWrite ¶
Creates a new MinTree from a sorted list of strings. The list must be sorted because that is what the mafsa package expects. After the MinTree has been successfully created, the function also writes it to the io.Writer.
type MinTreeNode ¶
type MinTreeNode struct {
mafsa.MinTreeNode
// contains filtered or unexported fields
}
type SparseAutomaton ¶
type SparseAutomaton struct {
// contains filtered or unexported fields
}
SparseAutomaton is a naive Go implementation of a levenshtein automaton using sparse vectors, as described and implemented here: http://julesjacobs.github.io/2015/06/17/disqus-levenshtein-simple-and-fast.html
func NewSparseAutomaton ¶
func NewSparseAutomaton(s string, maxEdits int) *SparseAutomaton
NewSparseAutomaton creates a new automaton for the string s, with a given max edit distance check
func (*SparseAutomaton) CanMatch ¶
func (a *SparseAutomaton) CanMatch(v sparseVector) bool
CanMatch returns true if there is a possibility that feeding the automaton with more steps will yield a match. Once CanMatch is false there is no point in continuing iteration
func (*SparseAutomaton) IsMatch ¶
func (a *SparseAutomaton) IsMatch(v sparseVector) bool
IsMatch returns true if the current state vector represents a string that is within the max edit distance from the initial automaton string
func (*SparseAutomaton) Start ¶
func (a *SparseAutomaton) Start() sparseVector
Start initializes the automaton's state vector and returns it for further iteration
func (*SparseAutomaton) Step ¶
func (a *SparseAutomaton) Step(state sparseVector, c byte) sparseVector
Step returns the next state of the automaton given a previous state and a character to check
func (*SparseAutomaton) Transitions ¶
func (a *SparseAutomaton) Transitions(v sparseVector) []byte
type SparseAutomatonRune ¶
type SparseAutomatonRune struct {
SparseAutomaton
// contains filtered or unexported fields
}
SparseAutomatonRune is almost identical to SparseAutomaton except that it operates on runes instead of bytes
func NewSparseAutomatonRune ¶
func NewSparseAutomatonRune(s string, maxEdits int) *SparseAutomatonRune
NewSparseAutomatonRune creates a new automaton for the string s, with a given max edit distance check
func (*SparseAutomatonRune) IsMatch ¶
func (a *SparseAutomatonRune) IsMatch(v sparseVector) bool
IsMatch returns true if the current state vector represents a string of runes that is within the max edit distance from the initial automaton string
func (*SparseAutomatonRune) Step ¶
func (a *SparseAutomatonRune) Step(state sparseVector, r rune) sparseVector
StepRune returns the next state of the automaton given a previous state and a rune to check
func (*SparseAutomatonRune) Transitions ¶
func (a *SparseAutomatonRune) Transitions(v sparseVector) []rune
type Trie ¶
type Trie struct {
// contains filtered or unexported fields
}
Trie holds a trie representation of a dictionary of words, for fuzzy matching against it
Example ¶
trie := NewTrie()
trie.Insert("banana")
trie.Insert("bananas")
trie.Insert("cabana")
trie.Insert("cabasa")
fmt.Println(trie.FuzzyMatches("banana", 2))
// XOutput:
// [banana bananas cabana]
Output:
func (*Trie) FuzzyMatches ¶
FuzzyMatches returns all the words in the trie that are with maxDist edit distance from s
Source Files