• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Altered Levenshtein distance Algorithm

 
Ranch Hand
Posts: 76
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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)
}
 
Bartender
Posts: 4179
22
IntelliJ IDE Python Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
Sheriff
Posts: 3063
12
Mac IntelliJ IDE Python VI Editor Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
Sheriff
Posts: 3837
66
Netbeans IDE Oracle Firefox Browser
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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).
 
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Too difficult a question for “beginning java”. Let’s try the General computing forum.
 
Greg Charles
Sheriff
Posts: 3063
12
Mac IntelliJ IDE Python VI Editor Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
reply
    Bookmark Topic Watch Topic
  • New Topic