closestmatch 📃

closestmatch is a simple and fast Go library for fuzzy matching an input string to a list of target strings. closestmatch is useful for handling input from a user where the input (which could be mispelled or out of order) needs to match a key in a database. closestmatch uses a bag-of-words approach to precompute character n-grams to represent each possible target string. The closest matches have highest overlap between the sets of n-grams. The precomputation scales well and is much faster and more accurate than Levenshtein.

Getting Started

Install

go get -u -v github.com/schollz/closestmatch

Use

Create a closestmatch object from a list words

// Take a slice of keys, say band names that are similar
// http://www.tonedeaf.com.au/412720/38-bands-annoyingly-similar-names.htm
wordsToTest := []string{"King Gizzard", "The Lizard Wizard", "Lizzard Wizzard"}

// Choose a set of bag sizes, more is more accurate but slower
bagSizes := []int{2}

// Create a closestmatch object
cm := closestmatch.New(wordsToTest, bagSizes)

Find the closest match, or find the N closest matches

fmt.Println(cm.Closest("kind gizard"))
// returns 'King Gizzard'

fmt.Println(cm.ClosestN("kind gizard",3))
// returns [King Gizzard Lizzard Wizzard The Lizard Wizard]

Calculate the accuracy

// Calculate accuracy
fmt.Println(cm.Accuracy())
// ~ 53 % (still way better than Levenshtein which hits 0% with this particular set)

// Improve accuracy by adding more bags
bagSizes = []int{2, 3, 4}
cm = closestmatch.New(wordsToTest, bagSizes)
fmt.Println(cm.Accuracy())
// accuracy improves to ~ 75 %

Save/Load

// Save your current calculated bags
cm.Save("closestmatches.json")

// Open it again
cm2, _ := closestmatch.Load("closestmatches.json")
fmt.Println(cm2.Closest("lizard wizard"))
// prints "The Lizard Wizard"

Accuracy and Speed

closestmatch is more accurate than Levenshtein for long strings (like in the test corpus). If you run go test the tests will pass which validate that Levenshtein performs < 60% accuracy and closestmatch performs with > 98% accuracy.

closestmatch is 6-7x faster than a fast implementation of Levenshtein. Try it yourself with the benchmarks:

cd $GOPATH/src/github.com/schollz/closestmatch && go test -bench=. > closestmatch.bench
cd $GOPATH/src/github.com/schollz/closestmatch/levenshtein && go test -bench=. > levenshtein.bench
benchcmp levenshtein.bench ../closestmatch.bench

which gives something like

benchmark                 old ns/op     new ns/op     delta
BenchmarkNew-8            1.49          624681        +41924799.33%
BenchmarkClosestOne-8     432350        61401         -85.80%
BenchmarkLargeFile-8      122050000     19925964      -83.67%

The New() function is so much faster in levenshtein because there is no precomputation needed (obviously).

Todo

• ClosestN(n int) returns closest n matches
• Function to compare accuracy (for tests?)
• Open should have []int{1,2,3} for the specified substructure lengths, compare different lengths
• Save/Load for precomputation (change Open -> New)
• Use more intuitive variable names + improve documentation
• How does this relate to bag of words?
• Compare to agrep (write a utility)