Levenshtein distance question
1) Why are we adding 1 to this line?
d[i-1, j] + 1, // deletion
d[i, j-1] + 1, // insertion
Line
if s[i] = t[j] then cost := 0
else cost := 1
should I consider the length of the deleted / bottom words, or am I missing something?
2) Also, the comments indicate deletion and insertion. Am I correct in thinking that it checks for deleted characters in both words (integers j / i representing the length of words), because a smaller value will represent deleted characters.
The code used is here (because it is pseudocode and I have no language issues, this thread does not belong to any language category):
http://www.iterasi.net/openviewer.aspx?sqrlitid=z0cloj7xhk-ce0f72v4cjq
a source to share
1) These lines calculate the distance in case of deletion, in case of insertion, and those that use "value" in case of replacement ...
deletion and insertion are effectively "1" in the distance calculation, hence +1.
We can believe that there was a replacement only if the characters differ from "cost = 0", if both characters are equal ...
The new distance is the minimum distance between these three hypotheses, so you don't always add 1 ...
2) if I calculated the distance between "FooBar" and "FoBaWhatever" I have some character stripping, even if the second line is longer than the first ...
Of course, if the second line is shorter than the second (FooBar -> FoBa), I will find some deletions, but I don't know in advance where they are ...
a source to share
Have you read http://www.merriampark.com/ld.htm ?
You are calculating the cost of the transformation - the number of insertions and deletions - it takes one row to be another.
This "cost" for conversion indicates the distance between the two lines.
How about exchanges? This is the Damerau-Levenshtein algorithm , which is different. Enabling exchanges doesn't make things much better.
The bottom line is to create a matrix between two words and calculate column by column - the "distance" from each letter of each word to each letter of the other word. The bottom right corner of this matrix is the total distance, including all letters.
Question 1)
The cell "above" reflects the history of changes, and the character for this line is (usually) different from this, so this cell is a deletion in relation to it.
The cell "to the left" reflects the history of changes, and the nature for this column is (usually) different from this, so this cell is nested relative to it.
The only time that would normally be wrong is with triple-letter words. Rare in English.
Comparison of rows and columns is either 0 or 1.
The minimum history plus one change and the actual cost of the change is the applicable cost.
Question 2)
Variables i
and j
are not threads. They are positions in the comparison matrix. "Insert" and "Delete" is the action required to convert one word to another. The number of insert / delete actions is the distance between words.
a source to share