Advanced Search

Levenshtein distance between words

/ Published in: ActionScript 3
Save to your folder(s)
This is the implementation of the algorithm that computes Levenshtein distance . This is used in different applications as spell checkers.

Expand | Embed | Plain Text

Copy this code and paste it in your HTML 
  1. function levenshteinDistance(s1:String,s2:String):int
  2. {
  3.   var m:int=s1.length;
  4.   var n:int=s2.length;
  5.   var matrix:Array=new Array();
  6.   var line:Array;
  7.   var i:int;
  8.   var j:int;
  9.   for (i=0;i<=m;i++)
  10.   {
  11.    line=new Array();
  12.    for (j=0;j<=n;j++)
  13.    {
  14.      if (i!=0)line.push(0)
  15.      else line.push(j);
  16.    }
  17.    line[0]=i
  18.    matrix.push(line);
  19.   }
  20.   var cost:int; 
  21.   for (i=1;i<=m;i++)
  22.    for (j=1;j<=n;j++)
  23.     {
  24.       if (s1.charAt(i-1)==s2.charAt(j-1)) cost=0
  25.       else cost=1;
  26.       matrix[i][j]=Math.min(matrix[i-1][j]+1,matrix[i][j-1]+1,matrix[i-1][j-1]+cost);
  27.     }
  28.   return matrix[m][n]; 
  29. }

Report this snippet


Comments

RSS Icon Subscribe to comments

You need to login to post a comment.