Есть две строки: $line1 и $line2
Нужно сделать максимально быстрое сравнение этих строк:
1) разный регистр, буквы ё/е, пробелы - за разницу не считаются (функция simplify());
2) если в строках есть небольшие отличия (расстояние Левенштейна от 0 до 4), то вывести в лог
если же отличия более существенные, то не нужно.
Проблема в том, что этот алгоритм адски медленно работает. Нужно сравнивать несколько десятков тысяч пар строк. Первичный отсев производится с помощью более быстрой функции index, но все равно слишком медленно работает все 
Как можно ускорить код?
| Код |
$simp_line1 = simplify($line1);
$simp_line2 = simplify($line2);
if (index ($simp_line1, $simp_line2) < 0){
$result = levenstein($simp_gname, $simp_kname);
if ($result > 0 && $result < 4){
print LOG "$line1\n$line2\n\n"
}
}
sub levenstein($$){
my @A=split //, lc shift;
my @B=split //, lc shift;
my @W=(0..@B);
my ($i, $j, $cur, $next);
for $i (0..$#A){
$cur=$i+1;
for $j (0..$#B){
$next=min(
$W[$j+1]+1,
$cur+1,
($A[$i] ne $B[$j])+$W[$j]);
$W[$j]=$cur;
$cur=$next;
}
$W[@B]=$next;
}
return $next;
}
sub min($$$){
if ($_[0] < $_[2]){pop @_} else {shift @_}
return $_[0] < $_[1]? $_[0]:$_[1];
}
sub simplify{
local $a = $_[0];
$a = lc($a);
$a =~ tr/ё/е/;
$a =~ s/[ ]+//g;
return $a;
}
|
|