Advanced Search

Return to Snippet

Revision: 13877
at May 9, 2009 16:40 by mircea16
Initial Code 
function levenshteinDistance(s1:String,s2:String):int
{
  var m:int=s1.length;
  var n:int=s2.length;
  var matrix:Array=new Array();
  var line:Array;
  var i:int;
  var j:int;
  for (i=0;i<=m;i++)
  {
   line=new Array();
   for (j=0;j<=n;j++)
   {
     if (i!=0)line.push(0)
     else line.push(j);
   }
   line[0]=i
   matrix.push(line);
  }
  var cost:int; 
  for (i=1;i<=m;i++)
   for (j=1;j<=n;j++)
    {
      if (s1.charAt(i-1)==s2.charAt(j-1)) cost=0
      else cost=1;
      matrix[i][j]=Math.min(matrix[i-1][j]+1,matrix[i][j-1]+1,matrix[i-1][j-1]+cost);
    }
  return matrix[m][n]; 
}
Initial URL 

                                

                                                            

                                    

                                        

                                        Initial Description
                                        

                                    

                                    
This is the implementation of the algorithm that computes Levenshtein distance . This is used in different applications as spell checkers.

                                

                                                            

                                    

                                        

                                        Initial Title
                                        

                                    

                                    
Levenshtein distance between words

                                

                                                            

                                    

                                        

                                        Initial Tags
                                        

                                    

                                    

                                

                                                            

                                    

                                        

                                        Initial Language
                                        

                                    

                                    
ActionScript 3