Разработка

Структура всех программ будет одинакова:

sub levenshtein
{
	my ($a, $b)=@_;
	
}

my ($a, $b)=@ARGV;
utf8::decode($_) for $a, $b;
print 1-levenshtein($a, $b)/(length($a)+length($b)), "\n";

Прежде всего определяется процедура levenshtein, которая делает главную работу — вычислает расстояние Левенштейна между двумя строками, передаваемыми её как параметры. Затем она вызывается для двух строк, указанных в командной строке запуска программы. На основе найденного процедурой расстояния вычисляется мера сходства строк, которая отправляется на печать.

Перед вызовом процедуры levenshtein передаваемые ей строки $a и $b проходят дополнительную обработку: для каждой вызывается встроенная процедура utf8::decode, которая преобразует строки из октетной формы в символьную. После этой подготовки строки $a и $b будут кассматриваться как составленные из символов, а не из октетов, что обычно и требуется.

Приводим самоочевидный отрывок кода, который должен быть вместо многоточия в теле процедуры levenshtein:

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);
}

В случае, когда хотя бы одна из строк пуста (else) процедура должна возвратить наибольшую из длин. Для её вычисления мы изящно применили оператор ||. Впрочем, в первоначальном варианте программы вместо него мы использовали оператор or, и программа работала неверно: код return length($a) or length($b) воспринимался как (return length($a)) or length($b) вместо return (length($a) or length($b)), так что length($b) никогда не вычисляется. Оператор or имеет тот же смысл, что и ||, но при этом обладает более низким приоритетом (ниже, чем у return).

Объявляем массив @bellman, в котором будут сохраняться вычисленные значения функции Беллмана. Заполняем верхнюю строчку и левый столбец в этом двумерном массиве:

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];

Информатика-54© А. Н. Швец