metrics

Documentation

Index

• func CalculateLevenshteinDistance(firstString, secondString string) int

Functions

func CalculateLevenshteinDistance

func CalculateLevenshteinDistance(firstString, secondString string) int

CalculateLevenshteinDistance will take in rwo inputs and give you the edit distance of the two strings.

This is the Wagner–Fischer implementation.

The computation is done via matrixes which is constructed with the following principle.

Each point in the matrix has a corresponding character on the first and second string. Because the strings start at +1 in both x and y axis, the [0][x] and [x][0] cases will always have the value of x. When this isn't the case, the value is determined by the minium value of 3 operations.

1. Deletion, get the value of [y-1][x]. The value of [y-1][x] always gets a default value of +1, this is used to get the correct value for values that are under the "curve", the curve is defined by the values that are "actually" used in order to get the final result, hence the naming curve as it's mostly a linear line down to the last value in the matrix.

2. Insertion, get the value of [y][x-1]. The value of [y][x-1] always gets a default value of +1, this is used to get the correct value for values that are above the "curve"

3. Substitution, get the value of [y-1][x-1]. The value of the previous character of both strings, this can be seen as the "base" cost. This is the only cost who don't get the default +1 added to it's cost. It only get the extra +1 cost when the characters of the string doesn't match.

k > s (Substitution) e > i (Substitution) > g (Insertion) Ex. The distance between "kitten" and "sitting" will be 3.