NAME

Algorithm::InversionList - Perl extension for generating an inversion list from a bit sequence.

SYNOPSIS

use Algorithm::InversionList;
my $data = "Random data here";
my @inv = invlist($data);
print "The inversion list is: @inv\n";

my $out = data_from_invlist(@inv);
print "From data [$data] we reconstructed [$out]\n";

DESCRIPTION

Inversion lists are data structures that store a sequence of bits as the numeric position of each switch between a run of 0 and 1 bits. Thus, the data "1111111" is encoded as the number 7 in an inversion list.

Inversion lists are very efficient when the "run" of bits is longer than the size of the scalar required to hold that run of bits. Because of the way that Perl stores scalars and lists and the various architectures to which Perl has been ported, there is no definitive rule as to what's the exact proportion of bit runs to bitstring length required to make inversion lists efficient. Generally, if you see long runs of repeated 0 or 1 bits, an inversion list may be appropriate.

EXPORT

invlist($DATA): Generate an inversion list from a scalar data string

data_from_invlist(@LIST): Generate the data back from an inversion list

invlist_from_bitstring($BSTRING): Same as invlist(), but expects a bit string

bitstring_from_invlist(@LIST): Same as data_from_invlist(), but returns a bit string

AUTHOR

Teodor Zlatanov <tzz@lifelogs.com>

SEE ALSO

perl.