Levenshtein distance of two strings in Perl.

levenshtein.pl

sub levenshtein_dist {

   my ($str1, $str2) = @_;
   my ($len1, $len2) = (length $str1, length $str2);

   if ($len1 == 0) {
       return $len2;
   }
   if ($len2 == 0) {
       return $len1;
   }

   my %mat;

   for (my $i = 0; $i <= $len1; ++$i) {
       $mat{0}{$i} = $i;
       $mat{1}{$i} = 0;
   }

   my @ar1 = split //, $str1;
   my @ar2 = split //, $str2;

   for (my $j = 1; $j <= $len2; ++$j) {
       my $p = $j % 2;
       my $q = ($j + 1) % 2;
       $mat{$p}{0} = $j;
       for (my $i = 1; $i <= $len1; ++$i) {
           my $cost = 0;
           if ($ar1[$i-1] ne $ar2[$j-1]) {
               $cost = 1;
           }
           $mat{$p}{$i} = min($cost + $mat{$q}{$i-1},
               $mat{$p}{$i-1} + 1, $mat{$q}{$i} + 1);
       }
   }

   return $mat{$len2%2}{$len1};
}