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)

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

Joined: Sep 26, 2012
Posts: 76

posted

0

Oh my goodness that was not suppose to go in this forum. It is pseudo code. Please move it to a more appropriate forum for me.

Oy, curse you and your algorithm problems that are somehow so much more interesting than what I'm 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

Joined: Sep 26, 2012
Posts: 76

posted

0

here are some test cases greg

HELLO
HELLO
0
DOG
DOGS
1
COMUTER
COMPUER
2
CAT
DOG
6
CAT
BAT
2
TUDAY
THRDAY
3
MARKET
BASKETBALL
8
CALIFORNIA
NEWYORK
13
CONSTITUTION
DECLARATIONOF
15

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).

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.