Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #3068 > unrolled thread

Modified Levenshtein Distance Algorithm

Back to article view | Back to comp.programming

Contents

  Modified Levenshtein Distance Algorithm billmann <willmann817@gmail.com> - 2013-02-20 15:55 -0800
    Re: Modified Levenshtein Distance Algorithm bob <bob@coolfone.comze.com> - 2013-02-21 11:06 -0800
      Re: Modified Levenshtein Distance Algorithm billmann <willmann817@gmail.com> - 2013-02-21 18:51 -0800
        Re: Modified Levenshtein Distance Algorithm bob <bob@coolfone.comze.com> - 2013-02-22 07:29 -0800
    Re: Modified Levenshtein Distance Algorithm "Chris Uppal" <chris.uppal@metagnostic.REMOVE-THIS.org> - 2013-02-22 08:22 +0000
      Re: Modified Levenshtein Distance Algorithm Jongware <jongware@no-spam.plz> - 2013-02-25 11:03 +0100
        Re: Modified Levenshtein Distance Algorithm Jongware <jongware@no-spam.plz> - 2013-02-25 11:06 +0100
          Re: Modified Levenshtein Distance Algorithm bob <bob@coolfone.comze.com> - 2013-02-25 07:24 -0800

#3068 — Modified Levenshtein Distance Algorithm

How can I change this algorithm so the distance only inserts.
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 equals so the distance would be 2.  The actual algorithm would return 1 because it allows you to substitute.  Is there anyway to change the algorithm below to only do insertion?

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

[toc] | [next] | [standalone]

#3076

On Wednesday, February 20, 2013 5:55:10 PM UTC-6, billmann wrote:
> How can I change this algorithm so the distance only inserts.
> 
> 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 equals so the distance would be 2.  The actual algorithm would return 1 because it allows you to substitute.  Is there anyway to change the algorithm below to only do insertion?
> 
> 
> 
> 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)
> 
> }

You say the distance would be 2 between CAT and BAT with just inserts.  Are you sure?

I think you may misunderstand the algorithm.  I believe it is the number of operations on the source word needed to get to the dest word.  So, with just inserts it would still be 1 because you would insert a B into CAT to get BAT.

What in general are you trying to do?

Thanks.

[toc] | [prev] | [next] | [standalone]

#3086

Bob, if you want the words to be the same with just insertion you would need to add a B to one word and a C to the other because they need all the same characters in all the same spot. I cannot replace characters.

[toc] | [prev] | [next] | [standalone]

#3090

On Thursday, February 21, 2013 8:51:17 PM UTC-6, billmann wrote:
> Bob, if you want the words to be the same with just insertion you would need to add a B to one word and a C to the other because they need all the same characters in all the same spot. I cannot replace characters.

So you are talking about making both words BCAT or something similar?

I'm not sure why you would want to do that.

[toc] | [prev] | [next] | [standalone]

#3087

billmann wrote:
> How can I change this algorithm so the distance only inserts.

The edit-distance (various metrics) is related to the "longest common 
subsequence problem" (see your favourite search engine).

In a similar way, the metric you are looking for is related to the "shortest 
common supersequence problem".  Wikipedia has a short article on that

    http://en.wikipedia.org/wiki/Shortest_common_supersequence

and some references.

It's way too early in the morning for me to work out the details but maybe 
that's enough to get you started.

    -- chris 

[toc] | [prev] | [next] | [standalone]

#3103

On 22-Feb-13 9:22 AM, Chris Uppal wrote:
> billmann wrote:
>> How can I change this algorithm so the distance only inserts.
>
> The edit-distance (various metrics) is related to the "longest common
> subsequence problem" (see your favourite search engine).
>
> In a similar way, the metric you are looking for is related to the "shortest
> common supersequence problem".  Wikipedia has a short article on that
>
>      http://en.wikipedia.org/wiki/Shortest_common_supersequence
>
> and some references.
>
> It's way too early in the morning for me to work out the details but maybe
> that's enough to get you started.

Below my Javascript implementation of the basic algorithm on that 
webpage (*not* the speed-optimized algo).
Your example "CAT"/"BAT" returns '3'; is that the value you would expect?

a = prompt("Word 1", "CAT");
b = prompt("Word 2", "BAT");
alert (LCSLength(a,b));

function LCSLength(X, Y)
{
   var i,j,m = X.length, n = Y.length;
   var C = new Array(m+1);
   for (i=0; i<=m; i++)
   {
     C[i] = new Array(n+1);
     C[i][0] = 0;
   }
   for (j=0; j<=n; j++)
   {
     C[0][j] = 0;
   }
   for (i=1; i<=m; i++)
   {
     for (j=1; j<=n; j++)
     {
       if (X[i] == Y[j])
         C[i][j] = C[i-1][j-1] + 1;
       else
         C[i][j] = Math.max(C[i][j-1], C[i-1][j]);
     }
   }
   return C[m][n];
}


[Jw]

[toc] | [prev] | [next] | [standalone]

#3104

On 25-Feb-13 11:03 AM, Jongware wrote:

Oops. Forgot about JS' string handling. Change this line

>        if (X[i] == Y[j])

to this

    if (X[i-1] == Y[j-1])

and then you get a longest common subsequence value of 2 for "BAT/CAT", 
which sounds a bit more logical.

[Jw]

[toc] | [prev] | [next] | [standalone]

#3107

On Monday, February 25, 2013 4:06:49 AM UTC-6, Jongware wrote:
> On 25-Feb-13 11:03 AM, Jongware wrote:
> 
> 
> 
> Oops. Forgot about JS' string handling. Change this line
> 
> 
> 
> >        if (X[i] == Y[j])
> 
> 
> 
> to this
> 
> 
> 
>     if (X[i-1] == Y[j-1])
> 
> 
> 
> and then you get a longest common subsequence value of 2 for "BAT/CAT", 
> 
> which sounds a bit more logical.
> 
> 
> 
> [Jw]

The LCS of those strings is clearly two as it is "AT".

What's not clear is if that's what the OP is really looking for.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web