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 RAMLCS-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.