fast-levenshtein :rocket:

Fastest levenshtein implementation in Go.

Measure the difference between two strings.

note: this implementation is currently not threadsafe and it assumes that the runes only go up to 65535. This will be fixed soon.

Download

$ go get github.com/ka-weihe/fast-levenshtein

Usage

package main

import (
    "fmt"
    "github.com/ka-weihe/fast-levenshtein"
)

func main() {
    s1 := "fast"
    s2 := "fastest"
    distance := levenshtein.Distance(s1, s2)
    fmt.Printf("The distance between %s and %s is %d.\n", s1, s2, distance)
    // => The distance between fast and fastest is 3.
}

Benchmarks

kaweihe is this package. It is 15 times faster for strings of length 64 compared to the second fastest package:

Benchmark/4/kaweihe-12             88651         12858 ns/op           0 B/op          0 allocs/op
Benchmark/4/agniva-12              34550         32099 ns/op        7984 B/op        499 allocs/op
Benchmark/4/arbovm-12              31778         49311 ns/op       23952 B/op        499 allocs/op
Benchmark/4/dgryski-12             34489         37951 ns/op       23952 B/op        499 allocs/op
Benchmark/8/kaweihe-12             51102         22806 ns/op           0 B/op          0 allocs/op
Benchmark/8/agniva-12              17876         66867 ns/op       15968 B/op        499 allocs/op
Benchmark/8/arbovm-12              12945        104283 ns/op       39920 B/op        499 allocs/op
Benchmark/8/dgryski-12             11898         92959 ns/op       39920 B/op        499 allocs/op
Benchmark/16/kaweihe-12            26749         43723 ns/op           0 B/op          0 allocs/op
Benchmark/16/agniva-12              6129        195921 ns/op       23952 B/op        499 allocs/op
Benchmark/16/arbovm-12              3370        356006 ns/op       71856 B/op        499 allocs/op
Benchmark/16/dgryski-12             3242        371193 ns/op       71856 B/op        499 allocs/op
Benchmark/32/kaweihe-12            12588         93955 ns/op           0 B/op          0 allocs/op
Benchmark/32/agniva-12              1604        767277 ns/op       39920 B/op        499 allocs/op
Benchmark/32/arbovm-12               838       1434373 ns/op      143712 B/op        499 allocs/op
Benchmark/32/dgryski-12              837       1427871 ns/op      143712 B/op        499 allocs/op
Benchmark/64/kaweihe-12             6538        180181 ns/op           0 B/op          0 allocs/op
Benchmark/64/agniva-12               422       2827182 ns/op      327344 B/op       1497 allocs/op
Benchmark/64/arbovm-12               219       5449945 ns/op      542912 B/op       1497 allocs/op
Benchmark/64/dgryski-12              219       5457779 ns/op      542912 B/op       1497 allocs/op

License

This project is licensed under the MIT License - see the LICENSE.md file for details