• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Altered Levenshtein distance Algorithm

 
William Koch
Ranch Hand
Posts: 76
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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)
}
 
Steve Luke
Bartender
Posts: 4181
22
IntelliJ IDE Java Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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?
 
William Koch
Ranch Hand
Posts: 76
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Greg Charles
Sheriff
Posts: 2993
12
Firefox Browser IntelliJ IDE Java Mac Ruby
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 76
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Martin Vajsar
Sheriff
Posts: 3752
62
Chrome Netbeans IDE Oracle
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Sheriff
Pie
Posts: 50168
79
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Too difficult a question for “beginning java”. Let’s try the General computing forum.
 
Greg Charles
Sheriff
Posts: 2993
12
Firefox Browser IntelliJ IDE Java Mac Ruby
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic