Jit
Enthusiast computational biologist with business dream !!!
Our Sponsors
Perl script for calculate Levenshtein distance
By Jit 2581 days ago
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};
}
