hi perlmonks

I have implemented the following perl script that compares each entry of an array1 with all entries of array2 in order to find the longest common subsequence in terms of words. I guess that the script works fine, but it is too slow. Please note that array1 contains 1.000 entries while array2 more than 300.000. Is it possible to make it faster without change the order of array1?

Thanks in advance for your help.

This is my code

#!/usr/bin/perl

use String::LCSS_XS qw( lcss );
use utf8;
use warnings;


my $f1 = shift ; 
my $f2 = shift ; 

open (FILE1, "<:encoding(UTF-8)", "$f1") or die "can't open file '$f1'
+ $!";
open (FILE2, "<:encoding(UTF-8)", "$f2") or die "can't open file '$f2'
+ $!";

my @array1 = <FILE1>;
chomp(@array1);
close (FILE1);

my @array2 = <FILE2>;
chomp(@array2);
close (FILE2);

my $subseq;
my($bestsource, $besttarget, $bestalignment, $bestlength);

for my $i (0 .. $#array1) {
    my $best_subseq = "";
    my $best_subseq_words = 0;
    my $best_subseq_chars = 0;
    my $found = 0;

    for my $j (0 .. $#array2) {

        $subseq = lcssw ("$array1[$i]", "$array2[$j]");

        my $num_words = count_words ($subseq);
        my $num_chars = count_chars ($subseq);

        if ($num_words > $best_subseq_words && $num_chars > $best_subs
+eq_chars) {
            $best_subseq = $subseq;
            $best_subseq_words = $num_words;
            $best_subseq_chars = $num_chars;
            $found = 1;
        }
    }
    
    if ($found == 1) {
        print "$best_subseq is the lcssw of $array1[$i]\n"
    }
}

sub lcssw {
   my ($s1, $s2) = @_;

   my $i;
   my %codes;
   my %words;

   for ($s1, $s2) {
      $_ = join '',
           map { $codes{$_} = chr(++$i) if !exists($codes{$_});
                 $codes{$_}
               }
           $_ =~ /\w+/g;
   }

   my $lcss = lcss($s1, $s2);
   $lcss = "" if (!defined $lcss);

   @words{values %codes} = keys %codes;
   return join ' ', @words{ $lcss =~ /./sg };
}

sub count_words {
    my $line = shift ;
    my @text_words = split(/\s+/, $line);
    return scalar(@text_words); 
}

sub count_chars {
    my $line = shift ;
    my @text_words = split(//, $line);
    return scalar(@text_words); 
}
[download]

---

---

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		&
	<		&lt;
	>		&gt;
	[		&#91;
	]		&#93;

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.