http://qs321.pair.com?node_id=289152

hi monks, here comes another implementation of the Levenshtein Distance; a distance metric which measures the similarities of strings.

Info and some other implementations can be found at Levenshtein distance: calculating similarity of strings.

At the moment I need to compare two sets of strings where each set consists of approximately 2000 strings, which means approximataley 3-4 million measurements. Thus I wrote this code, in which I tried to minimize the memory usage, to make it more efficient.

sub ldist { my @s = split //, shift; my @t = split //, shift; return scalar @t if scalar @s == 0; return scalar @s if scalar @t == 0; my (@prevColumn, @currColumn); @prevColumn = 0..scalar(@t); for my $s (0..$#s) { @currColumn = ( $s + 1 ); for my $t (0..$#t) { push @currColumn, min( $currColumn[$t] + 1 , $prevColumn[$t+1] + 1 , $prevColumn[$t] + ($s[$s] eq $t[$t] ? 0 : 1) ); } @prevColumn = @currColumn; } pop @currColumn } sub min { my $min = shift; for (@_) { $min = $_ if $_ < $min; } $min; }