view release on metacpan or  search on metacpan

lib/LCS/BV.pm  view on Meta::CPAN

package LCS::BV;

use 5.010001;
use strict;
use warnings;
our $VERSION = '0.14';
#use utf8;

our $width = int 0.999+log(~0)/log(2);

use integer;
no warnings 'portable'; # for 0xffffffffffffffff

sub new {
  my $class = shift;
  # uncoverable condition false
  bless @_ ? @_ > 1 ? {@_} : {%{$_[0]}} : {}, ref $class || $class;
}

# H. Hyyroe. A Note on Bit-Parallel Alignment Computation. In
# M. Simanek and J. Holub, editors, Stringology, pages 79-87. Department
# of Computer Science and Engineering, Faculty of Electrical
# Engineering, Czech Technical University, 2004.

sub LLCS {
  my ($self,$a,$b) = @_;

  #use integer;
  #no warnings 'portable'; # for 0xffffffffffffffff

  # TODO: maybe faster, if we have fewer expensive iterations
  #if (@$a < @$b) {
  #  my $temp = $a;
  #  $a = $b;
  #  $b = $temp;
  #}

  my ($amin, $amax, $bmin, $bmax) = (0, $#$a, 0, $#$b);

  while ($amin <= $amax and $bmin <= $bmax and $a->[$amin] eq $b->[$bmin]) {
    $amin++;
    $bmin++;
  }
  while ($amin <= $amax and $bmin <= $bmax and $a->[$amax] eq $b->[$bmax]) {
    $amax--;
    $bmax--;
  }

  #my %positions;

  if ($amax < $width ) {
    my %positions;
    #$positions{$a->[$_]}  |= 1 << ($_ % $width) for $amin..$amax;
    for ($amin..$amax) { $positions{$a->[$_]} |= 1 << ($_ % $width); }

    my $v = ~0;
    my ($p,$u);

    for ($bmin..$bmax) {
      $p = $positions{$b->[$_]} // 0;
      $u = $v & $p;
      $v = ($v + $u) | ($v - $u);
    }
    return $amin + _count_bits(~$v) + $#$a - $amax;
  }
  else {
    my %positions;
    #$positions{$a->[$_]}->[$_ / $width] |= 1 << ($_ % $width) for $amin..$amax;
    for ($amin..$amax) { $positions{$a->[$_]}->[$_ / $width] |= 1 << ($_ % $width); }

    my $S;
    my @Vs = ();      # $Vs->[$k] = bits;

    my ($p, $u, $carry);

    my $kmax = ($amax+1) / $width;
    $kmax++ if (($amax+1) % $width);

    for (my $k=0; $k < $kmax; $k++ ) { $Vs[$k] = ~0; }

    for my $j ($bmin..$bmax) {
      $carry = 0;
      for (my $k=0; $k < $kmax; $k++ ) {
        $S = $Vs[$k];
        $p = $positions{$b->[$j]}->[$k] // 0;
        $u = $S & $p;             # [Hyy04]
        $Vs[$k] = ($S + $u + $carry) | ($S - $u);
        $carry = (($S & $u) | (($S | $u) & ~($S + $u + $carry))) >> ($width-1) & 1;
      }
    }