Graal Forums  

Go Back   Graal Forums > Development Forums > NPC Scripting > Code Gallery
FAQ Members List Calendar Search Today's Posts Mark Forums Read

Reply
 
Thread Tools Search this Thread Display Modes
  #1  
Old 10-28-2009, 05:06 AM
WhiteDragon WhiteDragon is offline
Banned
Join Date: Feb 2007
Posts: 1,002
WhiteDragon is a splendid one to beholdWhiteDragon is a splendid one to beholdWhiteDragon is a splendid one to beholdWhiteDragon is a splendid one to beholdWhiteDragon is a splendid one to behold
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.stemp.t) {
  
temp.temp.s.length();
  
temp.temp.t.length();
  
  
temp.= new[temp.m][temp.n];
  for (
temp.0temp.<= temp.mtemp.i++) {
    
temp.d[temp.i][0] = temp.i;
  }
  for (
temp.0temp.<= temp.ntemp.j++) {
    
temp.d[0][temp.j] = temp.j;
  }
  
  for (
temp.1temp.<= temp.ntemp.j++) {
    for (
temp.1temp.<= temp.mtemp.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] + 1temp.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 
Reply With Quote
  #2  
Old 10-28-2009, 05:17 PM
fowlplay4 fowlplay4 is offline
team canada
fowlplay4's Avatar
Join Date: Jul 2004
Location: Canada
Posts: 5,200
fowlplay4 has a reputation beyond reputefowlplay4 has a reputation beyond reputefowlplay4 has a reputation beyond reputefowlplay4 has a reputation beyond reputefowlplay4 has a reputation beyond reputefowlplay4 has a reputation beyond reputefowlplay4 has a reputation beyond reputefowlplay4 has a reputation beyond reputefowlplay4 has a reputation beyond reputefowlplay4 has a reputation beyond reputefowlplay4 has a reputation beyond repute
Any practical Graal usage for this?
__________________
Quote:
Reply With Quote
  #3  
Old 10-28-2009, 05:21 PM
coreys coreys is offline
N-Pulse Assistant Manager
coreys's Avatar
Join Date: Mar 2005
Posts: 2,180
coreys has a spectacular aura about
Send a message via AIM to coreys Send a message via MSN to coreys Send a message via Yahoo to coreys
Quote:
Originally Posted by fowlplay4 View Post
Any practical Graal usage for this?
Not a single bit.
Reply With Quote
  #4  
Old 10-28-2009, 11:21 PM
WhiteDragon WhiteDragon is offline
Banned
Join Date: Feb 2007
Posts: 1,002
WhiteDragon is a splendid one to beholdWhiteDragon is a splendid one to beholdWhiteDragon is a splendid one to beholdWhiteDragon is a splendid one to beholdWhiteDragon is a splendid one to behold
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.
Reply With Quote
  #5  
Old 10-28-2009, 11:24 PM
Tigairius Tigairius is offline
The Cat
Tigairius's Avatar
Join Date: Jan 2007
Location: Missouri, USA
Posts: 4,240
Tigairius has a brilliant futureTigairius has a brilliant futureTigairius has a brilliant futureTigairius has a brilliant futureTigairius has a brilliant futureTigairius has a brilliant futureTigairius has a brilliant futureTigairius has a brilliant future
Quote:
Originally Posted by WhiteDragon View Post
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.
__________________


“Shoot for the moon. Even if you miss, you'll land among the stars.”
Reply With Quote
  #6  
Old 10-29-2009, 12:58 AM
fowlplay4 fowlplay4 is offline
team canada
fowlplay4's Avatar
Join Date: Jul 2004
Location: Canada
Posts: 5,200
fowlplay4 has a reputation beyond reputefowlplay4 has a reputation beyond reputefowlplay4 has a reputation beyond reputefowlplay4 has a reputation beyond reputefowlplay4 has a reputation beyond reputefowlplay4 has a reputation beyond reputefowlplay4 has a reputation beyond reputefowlplay4 has a reputation beyond reputefowlplay4 has a reputation beyond reputefowlplay4 has a reputation beyond reputefowlplay4 has a reputation beyond repute
Quote:
Originally Posted by WhiteDragon View Post
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.
Ah, this could prove some use to me and my data search function for Zodiac's npcserver.
__________________
Quote:
Reply With Quote
  #7  
Old 10-29-2009, 10:40 PM
pokeSMOT pokeSMOT is offline
Registered User
Join Date: Jun 2006
Posts: 35
pokeSMOT is on a distinguished road
Quote:
Originally Posted by Tigairius View Post
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?
Reply With Quote
  #8  
Old 10-29-2009, 10:54 PM
Skyld Skyld is offline
Script-fu
Skyld's Avatar
Join Date: Jan 2002
Location: United Kingdom
Posts: 3,914
Skyld has much to be proud ofSkyld has much to be proud ofSkyld has much to be proud ofSkyld has much to be proud ofSkyld has much to be proud ofSkyld has much to be proud of
Send a message via AIM to Skyld
Quote:
Originally Posted by pokeSMOT View Post
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.
__________________
Skyld
Reply With Quote
  #9  
Old 10-29-2009, 10:57 PM
DustyPorViva DustyPorViva is offline
Will work for food. Maybe
DustyPorViva's Avatar
Join Date: Sep 2003
Location: Maryland, USA
Posts: 9,589
DustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond repute
Send a message via AIM to DustyPorViva Send a message via MSN to DustyPorViva
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(st) {
  
temp.s.length();
  
temp.t.length();
  
  
temp.= new[m][n];
  for (
temp.0<= mi++) d[i][0] = i;
  for (
temp.0<= nj++) d[0][j] = j;
  
  for (
temp.1<= nj++) {
    for (
temp.1<= mi++) {
      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] + 1d[i-1][j-1] + 1)
                     );
      }
    }
  }
  return 
d[m-1][n-1];

Reply With Quote
  #10  
Old 10-29-2009, 11:57 PM
Skyld Skyld is offline
Script-fu
Skyld's Avatar
Join Date: Jan 2002
Location: United Kingdom
Posts: 3,914
Skyld has much to be proud ofSkyld has much to be proud ofSkyld has much to be proud ofSkyld has much to be proud ofSkyld has much to be proud ofSkyld has much to be proud of
Send a message via AIM to Skyld
Quote:
Originally Posted by DustyPorViva View Post
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!
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.
__________________
Skyld
Reply With Quote
  #11  
Old 10-30-2009, 02:52 AM
WhiteDragon WhiteDragon is offline
Banned
Join Date: Feb 2007
Posts: 1,002
WhiteDragon is a splendid one to beholdWhiteDragon is a splendid one to beholdWhiteDragon is a splendid one to beholdWhiteDragon is a splendid one to beholdWhiteDragon is a splendid one to behold
Quote:
Originally Posted by pokeSMOT View Post
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 View Post
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!
I personally sacrifice some neatness for clarity. I try to always explicitly define what scope I'm working in.
Reply With Quote
Reply

Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT +2. The time now is 03:47 PM.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2024, vBulletin Solutions Inc.
Copyright (C) 1998-2019 Toonslab All Rights Reserved.