Damerau–Levenshtein distance

Now you'd thing what the hell am I rambling about now, but here's the thing. Reading through my daily dose of programming news in Google Reader I stumbled upon this clever algorithm - the Damerau-Levenshtein distance algorithm. It is used to find the number of steps it would take to transform one string into another using the following operations: insertion, deletion, substitution and trasposition. Or put simply - Damerau-Levenshtein distance is a metric to defining the difference between two strings. The main areas of use are spell-checking (typos etc), DNA difference calculation etc. So I read up on the algorith at the Wiki page and decided to implement it just for the implementation's sake. Having fiddled around with the code for some time it dawned on me - I have this OCD when I perform the exact same operation in my head for two words that have a revelance to whichever situation I happen to be in at a given moment. I also provide a corresponding String extension method. Oh and if anyone hasn't picked it up yet, I mainly write code in C# 3.0 as is the case with this post. So without further ado, I present to you the implementation:

public static class DamerauLevenshtein
{
 public static int DamerauLevenshteinDistanceTo(this string @string, string targetString)
 {
  return DamerauLevenshteinDistance(@string, targetString);
 }

 public static int DamerauLevenshteinDistance(string string1, string string2)
 {
  if (String.IsNullOrEmpty(string1))
  {
   if (!String.IsNullOrEmpty(string2))
    return string2.Length;

   return 0;
  }

  if (String.IsNullOrEmpty(string2))
  {
   if (!String.IsNullOrEmpty(string1))
    return string1.Length;

   return 0;
  }

  int length1 = string1.Length;
  int length2 = string2.Length;

  int[,] d = new int[length1 + 1, length2 + 1];

  int cost, del, ins, sub;

  for (int i = 0; i <= d.GetUpperBound(0); i++)
   d[i, 0] = i;

  for (int i = 0; i <= d.GetUpperBound(1); i++)
   d[0, i] = i;

  for (int i = 1; i <= d.GetUpperBound(0); i++)
  {
   for (int j = 1; j <= d.GetUpperBound(1); j++)
   {
    if (string1[i - 1] == string2[j - 1])
     cost = 0;
    else
     cost = 1;

    del = d[i - 1, j] + 1;
    ins = d[i, j - 1] + 1;
    sub = d[i - 1, j - 1] + cost;

    d[i, j] = Math.Min(del, Math.Min(ins, sub));

    if (i > 1 && j > 1 && string1[i - 1] == string2[j - 2] && string1[i - 2] == string2[j - 1])
     d[i, j] = Math.Min(d[i, j], d[i - 2, j - 2] + cost);
   }
  }

  return d[d.GetUpperBound(0), d.GetUpperBound(1)];
 }
}

What do you guys think, should the presentation of interesting algorithm finds in my blog become a recurring subject? I think it wouldn't hurt.

Peace out,
Mihkel

Need more brains!!!

There's this subject that i find utterly fascinating lately - brain studies. The way neuroscientists study the jelly in our heads is by analyzing patients with very a specific kind of brain damage. They can then understand and locate which part of the brain is responsible for what behaviours.

One of the leading neurologists and my personal favourite in this field is Vilayanur Ramachandran. I've included a bunch of videos of him below. Some keywords of his work - phantom limbs, synesthesia, capgras delusion etc.

I'd like to point out one of these phenomenons - synesthesia. This is something that almost everyone of us possess but are unaware of until someone specifically mentions of its existance. When someone is any type of a synesthete (a person who has synesthesia), their brain has formed connections between seemingly unrelated subjects. For example - i have grapheme a.k.a color synesthesia for numbers and colors. The way this phenomenon manifests itself is when i think of a number i get a sensation of a specific color. Some numbers have very distinct colors while others have rather dull or faded, sometimes even undistinguishable tones.

On a more general term synesthesia allows us to engage in metaphorical thinking. Take for example a statement - "that's a blazin' car". Normal people wouldn't automatically assume that the car is on flames, rather that the car is nice looking. It'd be nice to hear from you, the readers, about your relationship with synesthesia, so feel free to leave a comment.

I've gathered together a portion of videos and articles that do quite well at explaining the peculiarities in our heads. The audio on "Phantoms In The Brain" is a bit off sync, no need to be put off by this.

• TED / Vilayanur Ramachandran: A journey to the center of your mind (great video for introduction)
• Phantoms In The Brain (Episode 1) - part 1/5
• Phantoms In The Brain (Episode 1) - part 2/5
• Phantoms In The Brain (Episode 1) - part 3/5
• Phantoms In The Brain (Episode 1) - part 4/5
• Phantoms In The Brain (Episode 1) - part 5/5
• Phantoms In The Brain (Episode 2) - part 1/5
• Phantoms In The Brain (Episode 2) - part 2/5
• Phantoms In The Brain (Episode 2) - part 3/5
• Phantoms In The Brain (Episode 2) - part 4/5
• Phantoms In The Brain (Episode 2) - part 5/5
• Brain Damage affecting Perception in multiple ways - part 1/2
• Brain Damage affecting Perception in multiple ways - part 2/2
• Man without a memory - Clive Wearing
• 5 Ways Your Brain Is Messing With Your Head

I guess what i'm trying to achieve with this post is to create some interest in people in how the mysterious thing called brain functions. Far too often do we see people who carry symptoms of abnormal brain behaviour get ridiculed and called names by others who lack the knowledge of what's really going on in someone's head. So don't be too quick to judge and jump to conclusions - be open minded, learn and if possible offer some guidance and assistance.

Keeping my mind open,
Mihkel