Graal Forums - Levenshtein Distance

Graal Forums (https://forums.graalonline.com/forums/index.php)

- Code Gallery (https://forums.graalonline.com/forums/forumdisplay.php?f=179)

- - Levenshtein Distance (https://forums.graalonline.com/forums/showthread.php?t=134256702)

WhiteDragon

10-28-2009 05:06 AM

Levenshtein Distance

Calculate the distance between two strings temp.s and temp.t.

This is an implementation of the dynamic programming approach. Time complexity of O(m*n).

For an explanation of the algorithm, see the Wikipedia article.

PHP Code:


		
			
function levenshtein(temp.s, temp.t) {
  temp.m = temp.s.length();
  temp.n = temp.t.length();
  
  temp.d = new[temp.m][temp.n];
  for (temp.i = 0; temp.i <= temp.m; temp.i++) {
    temp.d[temp.i][0] = temp.i;
  }
  for (temp.j = 0; temp.j <= temp.n; temp.j++) {
    temp.d[0][temp.j] = temp.j;
  }
  
  for (temp.j = 1; temp.j <= temp.n; temp.j++) {
    for (temp.i = 1; temp.i <= temp.m; temp.i++) {
      if (temp.s.charat(temp.i-1) == temp.t.charat(temp.j-1)) { 
        temp.d[temp.i][temp.j] = temp.d[temp.i-1][temp.j-1];
      } else {
        temp.d[temp.i][temp.j] = min(temp.d[temp.i-1][temp.j] + 1
                                    , min(temp.d[temp.i][temp.j-1] + 1, temp.d[temp.i-1][temp.j-1] + 1)
                                    );
      }
    }
  }
  return temp.d[temp.m-1][temp.n-1];
}

e.x.,

PHP Code:


		
			
echo(levenshtein("kitten", "sitting")); // echos 3
echo(levenshtein("Saturday", "Sunday")); // echos 3
echo(levenshtein("unixmad", "Stefan")); // echos 5

fowlplay4

10-28-2009 05:17 PM

Any practical Graal usage for this?

coreys

10-28-2009 05:21 PM

Quote:

Originally Posted by fowlplay4 (Post 1534708)

Any practical Graal usage for this?

Not a single bit.

WhiteDragon

10-28-2009 11:21 PM

It could be used anywhere where you wanted to determine if a player entered a command wrong or something to that effect. Normally you'd want to keep the deviation value low if you're doing that.

It was just an exercise though, and I figured it could save someone trouble if they ever needed it.

Anyways, you could just add it onto my pile of useless crap that no one cares about that I've posted in here, like Boyer-Moore, introsort, heapsort, quicksort, bitap, Rijndael, etc.

Tigairius

10-28-2009 11:24 PM

Quote:

Originally Posted by WhiteDragon (Post 1534757)

quicksort

Whoa whoa, be careful what you call useless now. Additionally, I think this function is useful and can be used for many things on Graal.

fowlplay4

10-29-2009 12:58 AM

Quote:

Originally Posted by WhiteDragon (Post 1534757)

Ah, this could prove some use to me and my data search function for Zodiac's npcserver.

pokeSMOT

10-29-2009 10:40 PM

Quote:

Originally Posted by Tigairius (Post 1534758)

Whoa whoa, be careful what you call useless now. Additionally, I think this function is useful and can be used for many things on Graal.

LOL @ the lack of examples! ^_^ <3 jk

Actually, it's a nice looking script.

But I'm curious, every time you use the temp.'chr's, is it required for you to keep saying "temp."? Does GScript not support enumeration?

Skyld

10-29-2009 10:54 PM

Quote:

Originally Posted by pokeSMOT (Post 1534918)

But I'm curious, every time you use the temp.'chr's, is it required for you to keep saying "temp."?

If you prefix all of your variables, there is less confusion. :)

DustyPorViva

10-29-2009 10:57 PM

That's a hell of a lot of temp's though! And is there really a lot of confusion? I mean in this day and age usually if you see a var without a prefix you can undoubtedly know that it is a temp var. And it looks so much neater!

PHP Code:


		
			
function levenshtein(s, t) {
  temp.m = s.length();
  temp.n = t.length();
  
  temp.d = new[m][n];
  for (temp.i = 0; i <= m; i++) d[i][0] = i;
  for (temp.j = 0; j <= n; j++) d[0][j] = j;
  
  for (temp.j = 1; j <= n; j++) {
    for (temp.i = 1; i <= m; i++) {
      if (s.charat(i-1) == t.charat(j-1)) { 
        d[i][j] = d[i-1][j-1];
      } else {
        d[i][j] = min(d[i-1][j] + 1,
                      min(d[i][j-1] + 1, d[i-1][j-1] + 1)
                     );
      }
    }
  }
  return d[m-1][n-1];
}

Skyld

10-29-2009 11:57 PM

Quote:

Originally Posted by DustyPorViva (Post 1534927)

I'd rather see the "temp" prefix so that it's completely clear for someone else who wants to pick up and look at your script.

WhiteDragon

10-30-2009 02:52 AM

Quote:

Originally Posted by pokeSMOT (Post 1534918)

But I'm curious, every time you use the temp.'chr's, is it required for you to keep saying "temp."? Does GScript not support enumeration?

No, it's not required, but I find it increases clarity because of GScript's weird scoping rules.

I do not see how enumerated types are related though.

Quote:

Originally Posted by DustyPorViva (Post 1534927)

I personally sacrifice some neatness for clarity. I try to always explicitly define what scope I'm working in.

All times are GMT +2. The time now is 01:58 AM.