You may be solving the wrong problem altogether. If your word list is very large (as I suspect it is), you'll be calculating a huge set of values. For many problems, you won't need the entire matrix. It may be better to compute them as needed and store them in the array when computed. That way, you compute only the ones you want, and once only. Something like:

sub get_similarity {
    my $i = shift;
    my $j = shift;

    # Matrix is symmetric around x==y
    ($i,$j) = ($j,$i) if $i > $j;

    return $sim[$i][$j] if defined $sim[$i][$j];

    $sim[$i][$j] = similarity($words[$i], $words[$j]);
}
[download]

Extra credit if you:

• Use a hash instead of an array.
• Tie your array or hash to a dbm file so you keep your values between runs...