Our Sponsors



Download BioinformaticsOnline(BOL) Apps in your chrome browser.




Perl script for calculate Levenshtein distance

  • Public
By Jit 2303 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}; }