aspose file tools*
The moose likes General Computing and the fly likes Altered Levenshtein distance Algorithm Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Engineering » General Computing
Bookmark "Altered Levenshtein distance Algorithm" Watch "Altered Levenshtein distance Algorithm" New topic
Author

Altered Levenshtein distance Algorithm

William Koch
Ranch Hand

Joined: Sep 26, 2012
Posts: 76
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

Joined: Jan 28, 2003
Posts: 3956
    
  17

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

Joined: Oct 01, 2001
Posts: 2771
    
  10

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

Joined: Aug 22, 2010
Posts: 3438
    
  47

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

Joined: Oct 13, 2005
Posts: 36514
    
  16
Too difficult a question for “beginning java”. Let’s try the General computing forum.
Greg Charles
Sheriff

Joined: Oct 01, 2001
Posts: 2771
    
  10

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.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Altered Levenshtein distance Algorithm
 
Similar Threads
can someone please help me
Have Simple Code Snippet, Please Point Out My Error
please help me
please help me
Creating a spell checker - guidance/ideas?