#!/usr/bin/perl
use warnings;
sub levenshtein
{
my ($a, $b)=@_;
if(length($a) and length($b))
{
if(substr($a, 0, 1) eq substr($b, 0, 1))
{
return levenshtein(substr($a, 1), substr($b, 1));
}
else
{
my $da=levenshtein(substr($a, 1), $b);
my $db=levenshtein($a, substr($b, 1));
return 1+($da<$db? $da: $db);
}
}
else
{
return length($a)||length($b);
}
}
my ($a, $b)=@ARGV;
utf8::decode($_) for $a, $b;
print 1-levenshtein($a, $b)/(length($a)+length($b)), "\n";
#!/usr/bin/perl
use warnings;
sub levenshtein
{
my ($a, $b)=@_;
my $la=length $a;
my $lb=length $b;
my @agenda=([0, 0, 0]);
my $result=INFINITY;
while(@agenda)
{
my ($i, $j, $cost)=@{pop @agenda};
if($i==$la or $j==$lb)
{
$result=$cost+$la+$lb-$i-$j
if $cost+$la+$lb-$i-$j<$result;
next;
}
if(substr($a, $i, 1) eq substr($b, $j, 1))
{
push @agenda, [$i+1, $j+1, $cost];
}
else
{
push @agenda, [$i+1, $j, $cost+1], [$i, $j+1, $cost+1];
}
}
return $result;
}
my ($a, $b)=@ARGV;
utf8::decode($_) for $a, $b;
print 1-levenshtein($a, $b)/(length($a)+length($b)), "\n";
Алгоритм Вагнера — Фишера
#!/usr/bin/perl
use warnings;
sub levenshtein
{
my ($a, $b)=@_;
my @bellman;
my $la=length $a;
my $lb=length $b;
$bellman[$_][0]=$_ for 0..$la;
$bellman[0][$_]=$_ for 0..$lb;
for my $j(1..$lb)
{
for my $i(1..$la)
{
$bellman[$i][$j]=$bellman[$i-1][$j]+1;
$bellman[$i][$j]=$bellman[$i][$j-1]+1
if $bellman[$i][$j]>$bellman[$i][$j-1]+1;
if(substr($a, $i-1, 1) eq substr($b, $j-1, 1))
{
$bellman[$i][$j]=$bellman[$i-1][$j-1]
if $bellman[$i][$j]>$bellman[$i-1][$j-1];
}
}
}
return $bellman[$la][$lb];
}
my ($a, $b)=@ARGV;
utf8::decode($_) for $a, $b;
print 1-levenshtein($a, $b)/(length($a)+length($b)), "\n";