levenshtein

README

levenshtein

An implementation of the Levenshtein distance for Golang

Sources

Levenshtein distance

Golang

Install

go get github.com/gitchander/levenshtein

Examples

package main

import (
	"fmt"

	lev "github.com/gitchander/levenshtein"
)

func main() {
	var (
		a = "exponential"
		b = "polynomial"
	)
	distance := lev.Strings(a, b)
	fmt.Printf("the levenshtein distance between %q and %q = %d\n", a, b, distance)
}

result:

the levenshtein distance between "exponential" and "polynomial" = 6

Example the distance by words:

package main

import (
	"fmt"
	"strings"

	lev "github.com/gitchander/levenshtein"
)

func main() {
	var (
		line1 = "one two three four"
		line2 = "one two three"
	)
	var (
		a = strings.Fields(line1)
		b = strings.Fields(line2)
	)
	distance := lev.Distance(lev.StringSlices{a, b})
	fmt.Printf("the levenshtein distance between %q and %q = %d\n", a, b, distance)
}

result:

the levenshtein distance between ["one" "two" "three" "four"] and ["one" "two" "three"] = 1

Example with print matrix:

package main

import (
	"fmt"

	lev "github.com/gitchander/levenshtein"
)

func main() {
	var (
		a = []rune("sitting")
		b = []rune("kitten")
	)
	costs := lev.DefaultCosts
	fmt.Print(lev.PrintableMatrix(costs, a, b, ""))
}

result:

. . k i t t e n 
. 0 1 2 3 4 5 6 
s 1 1 2 3 4 5 6 
i 2 2 1 2 3 4 5 
t 3 3 2 1 2 3 4 
t 4 4 3 2 1 2 3 
i 5 5 4 3 2 2 3 
n 6 6 5 4 3 3 2 
g 7 7 6 5 4 4 3 

Example the distance by interfaces:

package main

import (
	"fmt"

	lev "github.com/gitchander/levenshtein"
)

func main() {
	var (
		a = []Person{{"one", 1}, {"two", 2}, {"three", 3}, {"four", 4}}
		b = []Person{{"one", 1}, {"two", 2}, {"three", 3}}
	)
	distance := lev.Distance(PersonSlices{a, b})
	fmt.Printf("the levenshtein distance = %d\n", distance)
}

type Person struct {
	Name string
	Age  int
}

type PersonSlices [2][]Person

var _ lev.Interface = PersonSlices{}

func (p PersonSlices) Lens() (ni, nj int) {
	return len(p[0]), len(p[1])
}

func (p PersonSlices) Match(i, j int) bool {
	return p[0][i] == p[1][j]
}

result:

the levenshtein distance = 1

Documentation

Index

• Variables
• func Bools(a, b []bool) int
• func Distance(v Interface) int
• func DistanceCosts(v Interface, cs Costs) int
• func MakeMatrix(v Interface, cs Costs) [][]int
• func PrintableMatrix(cs Costs, a, b []rune, prefix string) string
• func Recursive(v Interface) int
• func Runes(a, b []rune) int
• func Strings(a, b string) int
• type BoolSlices
  • func (p BoolSlices) Lens() (ni, nj int)
  • func (p BoolSlices) Match(i, j int) bool
• type Costs
• type Interface
• type RuneSlices
  • func (p RuneSlices) Lens() (ni, nj int)
  • func (p RuneSlices) Match(i, j int) bool
• type StringSlices
  • func (p StringSlices) Lens() (ni, nj int)
  • func (p StringSlices) Match(i, j int) bool

Variables

var DefaultCosts = Costs{
	InsCost: 1,
	DelCost: 1,
	SubCost: 1,
}

Functions

func Bools

func Bools(a, b []bool) int

func Distance

func Distance(v Interface) int

func DistanceCosts

func DistanceCosts(v Interface, cs Costs) int

func MakeMatrix

func MakeMatrix(v Interface, cs Costs) [][]int

func PrintableMatrix

func PrintableMatrix(cs Costs, a, b []rune, prefix string) string

func Recursive

func Recursive(v Interface) int

func Runes

func Runes(a, b []rune) int

------------------------------------------------------------------------------

func Strings

func Strings(a, b string) int

Types

type BoolSlices

type BoolSlices [2][]bool

------------------------------------------------------------------------------

func (BoolSlices) Lens

func (p BoolSlices) Lens() (ni, nj int)

func (BoolSlices) Match

func (p BoolSlices) Match(i, j int) bool

type Costs

type Costs struct {
	DelCost int // Delete cost
	InsCost int // Insert cost
	SubCost int // Substitution cost
}

Weights

type Interface

type Interface interface {
	Lens() (ni, nj int)
	Match(i, j int) bool
}

type RuneSlices

type RuneSlices [2][]rune

------------------------------------------------------------------------------

func (RuneSlices) Lens

func (p RuneSlices) Lens() (ni, nj int)

func (RuneSlices) Match

func (p RuneSlices) Match(i, j int) bool

type StringSlices

type StringSlices [2][]string

------------------------------------------------------------------------------

func (StringSlices) Lens

func (p StringSlices) Lens() (ni, nj int)

func (StringSlices) Match

func (p StringSlices) Match(i, j int) bool