levenshtein

Go implementations for the Levenshtein Distance.

There are existing packages that implement Levenshtein Distance, I have created this package for learning.

Overview

Implementations:

• Full Matrix - the Wagner-Fischer algorithm for computing the Levenshtein Distance, which utilizes dynamic programing.
• Two Rows - an optimization for the Wagner-Fischer algorithm, which takes only two matrix rows regardless of the input. this is the most performant implementation in this package.
• Recursive - the original implementaion. an inefficient implementation, created for learning purposes.

When using this package, you should use the Distance - alias for the Two Rows implementaion.

Example

Using this package:

go get github.com/rotemhoresh/levenshtein

d := levenshtein.Distance("kitten", "sitting")
fmt.Printf("edit distance between 'kitten' and 'sitting' is %d", d)

// Output:
// edit distance between 'kitten' and 'sitting' is 3

Testing and Benchmarking

Test and Benchmark fucntions are available for all implementations.

# test
go test

# benchmark
go test -bench=. -benchmem

License

MIT