levenshtein

package
v0.3.7 Latest Latest
Warning

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

Go to latest
Published: Aug 2, 2015 License: MIT Imports: 2 Imported by: 0

Documentation

Index

Constants

View Source
const (
	Ins = iota
	Del
	Sub
	Match
)

Variables

This section is empty.

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.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL