ed

Documentation

Overview

ed package provides some functions for generalized edit-distance calculation.

String calculates the standard edit-distance, and StringFull returns an extra longest-common-string.

EditDistance calculates the generalized edit-distance, and EditDistanceFull returns extra matching infomation. Base is a helper type using as a base type for Interface implementations.

EditDistanceF and EditDistanceFFull are similar to EditDistance and EditDistanceFull, but using parameter and functions instead of an interface. This is sometimes more easy to use. ConstCost is a helper function.

Index

• func ConstCost(cost int) func(int) int
• func EditDistance(in Interface) int
• func EditDistanceF(lenA, lenB int, costOfChange func(iA, iB int) int, costOfDel func(iA int) int, ...) int
• func EditDistanceFFull(lenA, lenB int, costOfChange func(iA, iB int) int, costOfDel func(iA int) int, ...) (dist int, matA, matB []int)
• func EditDistanceFull(in Interface) (dist int, matA, matB []int)
• func String(a, b string) int
• func StringFull(a, b string) (dist int, lcs string)
• func Ternary(cond bool, vT, vF int) int
• type Base
  • func (b *Base) CostOfDel(iA int) int
  • func (b *Base) CostOfIns(iB int) int
  • func (b *Base) LenA() int
  • func (b *Base) LenB() int
• type Interface

Examples

• EditDistanceF
• String

Functions

func ConstCost

func ConstCost(cost int) func(int) int

ConstCost returns a const-function whose return value is the specified cost. This is useful for EditDistanceF and EditDistanceFFull if the del/ins cost is constant to positions.

func EditDistance

func EditDistance(in Interface) int

EditDistance returns the edit-distance defined by Interface.

The time complexity is O(mn) where m and n are lengths of a and b, and space complexity is O(n).

func EditDistanceF

func EditDistanceF(lenA, lenB int, costOfChange func(iA, iB int) int, costOfDel func(iA int) int, costOfIns func(iB int) int) int

EditDistanceFunc returns the edit-distance defined by parameters and functions.

The time complexity is O(mn) where m and n are lengths of a and b, and space complexity is O(n).

Example

a, b := "abcd", "bcde"
d := EditDistanceF(len(a), len(b), func(iA, iB int) int {
	return Ternary(a[iA] == b[iB], 0, 1)
}, ConstCost(1), ConstCost(1))
fmt.Println(a, b, d)

Output:

abcd bcde 2

func EditDistanceFFull

func EditDistanceFFull(lenA, lenB int, costOfChange func(iA, iB int) int, costOfDel func(iA int) int, costOfIns func(iB int) int) (dist int, matA, matB []int)

EditDistanceFFull returns the edit-distance and corresponding match indexes defined by parameters and functions. Each element in matA and matB is the index in the other list, if it is equal to or greater than zero; or -1 meaning a deleting or inserting in matA or matB, respectively.

The time and space complexity are all O(mn) where m and n are lengths of a and b.

NOTE if detailed matching information is not necessary, call EditDistance instead because it needs much less memories.

func EditDistanceFull

func EditDistanceFull(in Interface) (dist int, matA, matB []int)

EditDistanceFull returns the edit-distance and corresponding match indexes defined by Interface. Each element in matA and matB is the index in the other list, if it is equal to or greater than zero; or -1 meaning a deleting or inserting in matA or matB, respectively.

The time and space complexity are all O(mn) where m and n are lengths of a and b.

NOTE if detailed matching information is not necessary, call EditDistance instead because it needs much less memories.

func String

func String(a, b string) int

String calculates the edit-distance between two strings. Input strings must be UTF-8 encoded.

The time complexity is O(mn) where m and n are lengths of a and b, and space complexity is O(n).

Example

fmt.Println(String("abcde", "bfdeg"))

fmt.Println(StringFull("abcde", "bfdeg"))

Output:

3
3 bde

func StringFull

func StringFull(a, b string) (dist int, lcs string)

String calculates the edit-distance and longest-common-string between two strings. Input strings must be UTF-8 encoded.

The time and space complexity are all O(mn) where m and n are lengths of a and b.

NOTE if detailed matching information is not necessary, call String instead because it needs much less memories.

func Ternary

func Ternary(cond bool, vT, vF int) int

Ternary returns vT if cond equals true, or vF otherwise.

Types

type Base

type Base struct {
	LA, LB, Cost int
}

Base is a helper type which defines LenA, LenB, CostOfDel and CostOfIns methods.

func (*Base) CostOfDel

func (b *Base) CostOfDel(iA int) int

Interface.CostOfDel

func (*Base) CostOfIns

func (b *Base) CostOfIns(iB int) int

Interface.CostOfIns

func (*Base) LenA

func (b *Base) LenA() int

Interface.LenA

func (*Base) LenB

func (b *Base) LenB() int

Interface.LenB

type Interface

type Interface interface {
	// LenA returns the lenght of the source list
	LenA() int

	// LenB returns the lenght of the destination list
	LenB() int

	// CostOfChange returns the change cost from an item in the source list at iA to an item in the destination list at iB
	CostOfChange(iA, iB int) int

	// CostOfDel returns the cost of deleting an item in the source list at iA
	CostOfDel(iA int) int

	// CostOfIns returns the cost of inserting an item in the destination list at iB
	CostOfIns(iB int) int
}

Interface defines a pair of lists and the cost for each operation.