# Compare similarity or levenshtein distance between each line pair within a file?

I'd like to find the most similar line pair contained within a file, using something like levenshtein distance. For instance, given a file along the lines of:

``````What is your favorite color?
Who was the 8th president?
Who was the 9th president?
``````

…it would return lines 3 & 4 as the most similar line pair.

Ideally, I would like to be able to calculate the top X most similar lines. So, using the example above, the second most similar pair would be lines 1 & 2.

I wasn't familiar with Levenshtein distances, but Perl has a module for computing Levenshtein distances, so I wrote a simple perl script to compute the distances of each combination of pairs of lines in the input, then print them in increasing "distance", subject to a "top X" (N) parameter:

``````#!/usr/bin/perl -w
use strict;
use Text::Levenshtein qw(distance);
use Getopt::Std;

our \$opt_n;
getopts('n:');
\$opt_n ||= -1; # print all the matches if -n is not provided

my @lines=<>;
my %distances = ();

# for each combination of two lines, compute distance
foreach(my \$i=0; \$i <= \$#lines - 1; \$i++) {
foreach(my \$j=\$i + 1; \$j <= \$#lines; \$j++) {
my \$d = distance(\$lines[\$i], \$lines[\$j]);
push @{ \$distances{\$d} }, \$lines[\$i] . \$lines[\$j];
}
}

# print in order of increasing distance
foreach my \$d (sort { \$a <=> \$b } keys %distances) {
print "At distance \$d:\n" . join("\n", @{ \$distances{\$d} }) . "\n";
last unless --\$opt_n;
}
``````

On the sample input, it gives:

``````\$ ./solve.pl < input
At distance 1:
Who was the 8th president?
Who was the 9th president?

At distance 3:

At distance 21:
Who was the 8th president?
Who was the 9th president?
Who was the 8th president?
Who was the 9th president?
``````

and showing the optional parameter:

``````\$ ./solve.pl -n 2 < input
At distance 1:
Who was the 8th president?
Who was the 9th president?

At distance 3: