levenshtein

Documentation

Index

• Constants
• func DistanceForMatrix(matrix [][]int) int
• func DistanceForStrings(source []rune, target []rune, op Options) int
• func LogMatrix(source []rune, target []rune, matrix [][]int)
• func MatrixForStrings(source []rune, target []rune, op Options) [][]int
• type EditOperation
  • func (operation EditOperation) String() string
• type EditScript
  • func EditScriptForMatrix(matrix [][]int, op Options) EditScript
  • func EditScriptForStrings(source []rune, target []rune, op Options) EditScript
• type MatchFunction
• type Options

Constants

const (
	Ins = iota
	Del
	Sub
	Match
)

Functions

func DistanceForMatrix

func DistanceForMatrix(matrix [][]int) int

DistanceForMatrix reads the edit distance off the given Levenshtein matrix.

func DistanceForStrings

func DistanceForStrings(source []rune, target []rune, op Options) int

DistanceForStrings returns the edit distance between source and target.

func LogMatrix

func LogMatrix(source []rune, target []rune, matrix [][]int)

LogMatrix outputs a visual representation of the given matrix for the given strings on os.Stderr.

func MatrixForStrings

func MatrixForStrings(source []rune, target []rune, op Options) [][]int

MatrixForStrings generates a 2-D array representing the dynamic programming table used by the Levenshtein algorithm, as described e.g. here: http://www.let.rug.nl/kleiweg/lev/ The reason for putting the creation of the table into a separate function is that it cannot only be used for reading of the edit distance between two strings, but also e.g. to backtrace an edit script that provides an alignment between the characters of both strings.

Types

type EditOperation

type EditOperation int

func (EditOperation) String

func (operation EditOperation) String() string

type EditScript

type EditScript []EditOperation

func EditScriptForMatrix

func EditScriptForMatrix(matrix [][]int, op Options) EditScript

EditScriptForMatrix returns an optimal edit script based on the given Levenshtein matrix.

func EditScriptForStrings

func EditScriptForStrings(source []rune, target []rune, op Options) EditScript

EditScriptForStrings returns an optimal edit script to turn source into target.

type MatchFunction

type MatchFunction func(rune, rune) bool

type Options

type Options struct {
	InsCost int
	DelCost int
	SubCost int
	Matches MatchFunction
}

var DefaultOptions Options = Options{
	InsCost: 1,
	DelCost: 1,
	SubCost: 2,
	Matches: func(sourceCharacter rune, targetCharacter rune) bool {
		return sourceCharacter == targetCharacter
	},
}

DefaultOptions is the default options: insertion cost is 1, deletion cost is 1, substitution cost is 2, and two runes match iff they are the same.