CODEWITHSUNDEEP
javascriptalgorithmmathlevenshtein-distance
PeakGen
PeakGen

Reputation: 23035

Understanding Levenshtein distance

I am having a trouble in underdstandig the method Levenshtein distance. It says that levenshtein distance is the amount of operations it takes to get from string 1 to string 2. OK, so have a look at the below code.

  // Compute the edit distance between the two given strings
function getEditDistance(a, b) {
  if(a.length === 0) return b.length; 
  if(b.length === 0) return a.length; 

  var matrix = [];

  // increment along the first column of each row
  var i;
  for(i = 0; i <= b.length; i++){
    matrix[i] = [i];
  }

  // increment each column in the first row
  var j;
  for(j = 0; j <= a.length; j++){
    matrix[0][j] = j;
  }

  // Fill in the rest of the matrix
  for(i = 1; i <= b.length; i++){
    for(j = 1; j <= a.length; j++){
      if(b.charAt(i-1) == a.charAt(j-1)){
        matrix[i][j] = matrix[i-1][j-1];
      } else {
        matrix[i][j] = Math.min(matrix[i-1][j-1] + 1, // substitution
                                Math.min(matrix[i][j-1] + 1, // insertion
                                         matrix[i-1][j] + 1)); // deletion
      }
    }
  }

  return matrix[b.length][a.length];
};

This code is in Javascript.

Now imaging that I am going to pass the below 2 sentences.

1. welcome to planet earth.
2. welcome sea.

First sentence got more letters than the second sentence. So Now I need to know the difference between these 2. So, when passing parameters to the above function, is there any order? (like "pass the sentence with more letters to the first parameter. pass the sentence with less letters to the second parameter"). Or is there no any order? As far as I know there is no order, but after a session today I got confused!

Update

Basically this formula is designed to calculate "how many operations are required to change the sentence with less words into the sentence with more words. Is my understanding correct?

Upvotes: 2

Views: 1965

Answers (1)

IVlad
IVlad

Reputation: 43477

First sentence got more letters than the second sentence. So Now I need to know the difference between these 2. So, when passing parameters to the above function, is there any order? (like "pass the sentence with more letters to the first parameter. pass the sentence with less letters to the second parameter"). Or is there no any order? As far as I know there is no order, but after a session today I got confused!

There is no order you need to keep. You can pass the strings (sentences) in any order you wish.

Basically this formula is designed to calculate "how many operations are required to change the sentence with less words into the sentence with more words. Is my understanding correct?

Yes, you can think of it like that. To be more exact, the Levenshtein Distance measures the difference between two sequences. In your case, it will determine the minimum number of characters that need to be added, deleted or changed in order for one of the strings (either of them) to be turned into the other.

Upvotes: 3

Related Questions