0

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?
What is your favorite food?
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.

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:
What is your favorite color?
What is your favorite food?

At distance 21:
What is your favorite color?
Who was the 8th president?
What is your favorite color?
Who was the 9th president?
What is your favorite food?
Who was the 8th president?
What is your favorite food?
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:
What is your favorite color?
What is your favorite food?

I wasn't sure how to print the output unambiguously, but the strings are there to be printed however you'd like.

  • Thanks a lot! This ends up being really handy for reducing lists of related questions from disparate sources that overlap in the sense that they are worded differently but essentially duplicate. – Matt V. Jul 28 '17 at 22:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.