Posted By

mircea16 on 05/09/09


Tagged


Versions (?)

Who likes this?

3 people have marked this snippet as a favorite

macKaminski
Pingpongbal
toxin20


Levenshtein distance between words


 / Published in: ActionScript 3
 

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

  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  

You need to login to post a comment.