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 "111111100" is encoded as the list of numbers 0, 7 in an inversion list. This module begins the list with the start of the run of 1's, so if the first 2 bits in the string are 0, the first entry in the list will be a 2 (where we find the first bit that is 1). The last number will always be the length of the string, so that we know where to end it.

Inversion lists are very efficient. 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.

This module stores inversion lists in an offset-based format which has some nice properties, for instance searching is fast and you can easily do boolean operations on two inversion lists stored in the offset-based format.

EXPORT

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

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

AUTHOR

Teodor Zlatanov <tzz@lifelogs.com>

SEE ALSO

perl.