# Altered Levenshtein distance Algorithm

William Koch

Ranch Hand

Posts: 76

posted 4 years ago

How can I change this algorithm so the distance only takes into account insertions.

For example: If I have the words CAT and BAT you would need to insert a B in CAT and a C in BAT for the words to be equal so the distance would be 2. The actual algorithm below returns 1 because it allows you to substitute(it also allows for removal). Is there anyway to change the algorithm below to ONLY do insertion? And can anyone provide insight on it?

int LevenshteinDistance(string s, string t)

{

int len_s = length(s), len_t = length(t)

if(len_s == 0) then return len_t

if(len_t == 0) then return len_s

if(s[len_s-1] == t[len_t-1]) then cost = 0

else cost = 1

return minimum(LevenshteinDistance(s[0..len_s-1], t) + 1,

LevenshteinDistance(s, t[0..len_t-1]) + 1,

LevenshteinDistance(s[0..len_s-1], t[0..len_t-1]) + cost)

}

For example: If I have the words CAT and BAT you would need to insert a B in CAT and a C in BAT for the words to be equal so the distance would be 2. The actual algorithm below returns 1 because it allows you to substitute(it also allows for removal). Is there anyway to change the algorithm below to ONLY do insertion? And can anyone provide insight on it?

int LevenshteinDistance(string s, string t)

{

int len_s = length(s), len_t = length(t)

if(len_s == 0) then return len_t

if(len_t == 0) then return len_s

if(s[len_s-1] == t[len_t-1]) then cost = 0

else cost = 1

return minimum(LevenshteinDistance(s[0..len_s-1], t) + 1,

LevenshteinDistance(s, t[0..len_t-1]) + 1,

LevenshteinDistance(s[0..len_s-1], t[0..len_t-1]) + cost)

}

posted 4 years ago

Clearly that isn't Java code, so it probably will cause some confusion with folks because it is in the Beginning Java forum. Can you tell me what language it is, so maybe we can move it to a forum where it will appear more familiar to folks?

Steve

William Koch

Ranch Hand

Posts: 76

posted 4 years ago

Oy, curse you and your algorithm problems that are somehow so much more interesting than what I'm

You probably see that one or more of the 1s in the algorithm have to change to 2s to reflect the increased cost of making a substitution. I am fairly confident that no other modifications are necessary. I'll leave it to you to work out if it's one 1 or if it's more than one. If you have any test cases with known answers, post them here and I'll check my theory.

*supposed*to be working on!You probably see that one or more of the 1s in the algorithm have to change to 2s to reflect the increased cost of making a substitution. I am fairly confident that no other modifications are necessary. I'll leave it to you to work out if it's one 1 or if it's more than one. If you have any test cases with known answers, post them here and I'll check my theory.

William Koch

Ranch Hand

Posts: 76

posted 4 years ago

I'm not sure about it, Greg. If the cost of substitutions is increased, then there perhaps could be cases in which the shortest path under original algorithm (say, three substitutions; cost 3 originally, but 6 in the modified algorithm) could be more costly than another path under modified algorithm (say, two insertions and two deletions - cost 4 in both versions).

Campbell Ritchie

Marshal

Posts: 52581

119

posted 4 years ago

My algorithm worked for all the examples that William provided. That is, it gave the right answers. The performance degrades quickly, and the last example ran for more than an hour before giving a result. That wouldn't be acceptable in a real-world application.

@Martin -- I'm not sure either, but I can't come up with any counter-examples. I'm not even sure that the scenario you outline is possible, but I can't prove it.

@Martin -- I'm not sure either, but I can't come up with any counter-examples. I'm not even sure that the scenario you outline is possible, but I can't prove it.

It is sorta covered in the JavaRanch Style Guide. |