levenshtein

package module
Version: v0.0.0-...-f183c12 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Jun 8, 2021 License: MIT Imports: 2 Imported by: 0

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) Len(k int) int {
	return len(p[k])
}

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

result:

the levenshtein distance = 1

Documentation

Index

Constants

This section is empty.

Variables

View Source
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) Len

func (p BoolSlices) Len(k int) 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 {
	Len(k int) int // k = [0, 1]
	Match(i, j int) bool
}

type RuneSlices

type RuneSlices [2][]rune

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

func (RuneSlices) Len

func (p RuneSlices) Len(k int) int

func (RuneSlices) Match

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

type StringSlices

type StringSlices [2][]string

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

func (StringSlices) Len

func (p StringSlices) Len(k int) int

func (StringSlices) Match

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

Directories

Path Synopsis
examples
utils

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
t or T : Toggle theme light dark auto
y or Y : Canonical URL