Skip to content

Instantly share code, notes, and snippets.

@jacobkahn
Created January 12, 2020 21:43
Show Gist options
  • Save jacobkahn/d7731ed733d89a3c8a189084766d36e7 to your computer and use it in GitHub Desktop.
Save jacobkahn/d7731ed733d89a3c8a189084766d36e7 to your computer and use it in GitHub Desktop.
Character Levenshtein with two files in Perl
#!/usr/bin/perl
use List::Util qw(min);
sub levenshtein
{
my ($str1, $str2) = @_;
my @ar1 = split ' ', $str1;
my @ar2 = split ' ', $str2;
my @dist;
$dist[$_][0] = $_ foreach (0 .. @ar1);
$dist[0][$_] = $_ foreach (0 .. @ar2);
foreach my $i (1 .. @ar1) {
foreach my $j (1 .. @ar2) {
my $cost = $ar1[$i - 1] eq $ar2[$j - 1] ? 0 : 1;
$dist[$i][$j] = min(
$dist[$i - 1][$j] + 1,
$dist[$i][$j - 1] + 1,
$dist[$i - 1][$j - 1] + $cost
);
}
}
return $dist[@ar1][@ar2];
}
open(my $fh1, "$ARGV[0]");
open(my $fh2, "$ARGV[1]");
chomp(my @strings1=<$fh1>);
chomp(my @strings2=<$fh2>);
foreach my $str1 (@strings1) {
my $mindist=1000;
my $minmatch="MINMATCH";
foreach my $str2 (@strings2) {
my $lev=levenshtein($str1, $str2);
if ($lev < $mindist) {
$mindist=$lev;
$minmatch=$str2
}
}
print "$str1|$minmatch|$mindist\n";
select()->flush();
}
#!/usr/bin/perl
use List::Util qw(min);
sub levenshtein
{
my ($str1, $str2) = @_;
my @ar1 = split //, $str1;
my @ar2 = split //, $str2;
my @dist;
$dist[$_][0] = $_ foreach (0 .. @ar1);
$dist[0][$_] = $_ foreach (0 .. @ar2);
foreach my $i (1 .. @ar1) {
foreach my $j (1 .. @ar2) {
my $cost = $ar1[$i - 1] eq $ar2[$j - 1] ? 0 : 1;
$dist[$i][$j] = min(
$dist[$i - 1][$j] + 1,
$dist[$i][$j - 1] + 1,
$dist[$i - 1][$j - 1] + $cost
);
}
}
return $dist[@ar1][@ar2];
}
open(my $fh1, "$ARGV[0]");
open(my $fh2, "$ARGV[1]");
chomp(my @strings1=<$fh1>);
chomp(my @strings2=<$fh2>);
foreach my $str1 (@strings1) {
my $mindist=1000;
my $minmatch="MINMATCH";
foreach my $str2 (@strings2) {
my $lev=levenshtein($str1, $str2);
if ($lev < $mindist) {
$mindist=$lev;
$minmatch=$str2
}
}
print "$str1|$minmatch|$mindist\n";
select()->flush();
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment