NAME

LCS::BV - Bit Vector (BV) implementation of the Longest Common Subsequence (LCS) Algorithm

SYNOPSIS

use LCS::BV;

$object = LCS::BV->new;
@lcs    = $object->LCS(\@a,\@b);

$llcs   = $object->LLCS(\@a,\@b);

$positions = $object->prepare(\@a);
$llcs      = $object->LLCS_prepared($positions,\@b);

ABSTRACT

LCS::BV implements Algorithm::Diff using bit vectors and is faster in most cases, especially on strings with a length shorter than the used wordsize of the hardware (32 or 64 bits).

DESCRIPTION

CONSTRUCTOR

• new()

  Creates a new object which maintains internal storage areas for the LCS computation. Use one of these per concurrent LCS() call.

METHODS

• LLCS(\@a,\@b)

  Return the length of a Longest Common Subsequence, taking two arrayrefs as method arguments. It returns an integer.

• LCS(\@a,\@b)

  Finds a Longest Common Subsequence, taking two arrayrefs as method arguments. It returns an array reference of corresponding indices, which are represented by 2-element array refs.

• prepare(\@a)

  For comparison of the same sequence @a many times against different sequences @b it can be faster to prepare @a. It returns a hashref of positions. This works only on object mode.

• LLCS_prepared($positions,\@b)

  Return the length of a Longest Common Subsequence, with one side prepared. It returns an integer. It is two times faster than LLCS().

EXPORT

None by design.

STABILITY

Until release of version 1.00 the included methods, names of methods and their interfaces are subject to change.

Beginning with version 1.00 the specification will be stable, i.e. not changed between major versions.

REFERENCES

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.

SPEED COMPARISON

Intel Core i7-4770HQ Processor
Intel® SSE4.1, Intel® SSE4.2, Intel® AVX2
4 Cores, 8 Threads
2.20 - 3.40 GHz
6 MB Cache
16 GB DDR3 RAM

LCS-BV/xt$ perl 50_diff_bench.t

LCS: Algorithm::Diff, Algorithm::Diff::XS, LCS, LCS::BV

LCS: [Chrerrplzon] [Choerephon]

            Rate      LCS:LCS    AD:LCSidx AD:XS:LCSidx   LCS:BV:LCS

LCS:LCS 9225/s -- -72% -87% -88% AD:LCSidx 33185/s 260% -- -53% -58% AD:XS:LCSidx 70447/s 664% 112% -- -12% LCS:BV:LCS 79644/s 763% 140% 13% --

LCS: [qw/a b d/ x 50], [qw/b a d c/ x 50]

           Rate      LCS:LCS    AD:LCSidx   LCS:BV:LCS AD:XS:LCSidx

LCS:LCS 49.5/s -- -37% -96% -99% AD:LCSidx 79.0/s 60% -- -94% -98% LCS:BV:LCS 1255/s 2434% 1488% -- -69% AD:XS:LCSidx 4073/s 8124% 5052% 224% --

LLCS: [Chrerrplzon] [Choerephon]

                 Rate    LCS:LLCS AD:LCS_length AD:XS:LCS_length LCS:BV:LLCS

LCS:LLCS 11270/s -- -70% -70% -92% AD:LCS_length 37594/s 234% -- -1% -75% AD:XS:LCS_length 38059/s 238% 1% -- -74% LCS:BV:LLCS 148945/s 1222% 296% 291% --

LLCS: [qw/a b d/ x 50], [qw/b a d c/ x 50]

               Rate     LCS:LLCS AD:LCS_length AD:XS:LCS_length  LCS:BV:LLCS

LCS:LLCS 50.0/s -- -37% -37% -98% AD:LCS_length 79.2/s 58% -- -1% -97% AD:XS:LCS_length 79.8/s 60% 1% -- -97% LCS:BV:LLCS 2357/s 4614% 2874% 2853% --

SOURCE REPOSITORY

http://github.com/wollmers/LCS-BV

SEE ALSO

Algorithm::Diff LCS LCS::Tiny

AUTHOR

Helmut Wollmersdorfer helmut.wollmersdorfer@gmail.com

COPYRIGHT AND LICENSE

Copyright 2014-2020 by Helmut Wollmersdorfer

This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself.