Because you are compressing sequences of bits rather than bytes I am not convinced that you will see a saving in space. It will depend on whether you have longish sequences of contiguous ones or zeros. If there are many short runs or singletons, your array of counts is likely to take more space than the vector. Unless I'm misunderstanding something, you need to have runs of more than eight ones or zeros before you break even if representing each count as a signed character; it gets worse if having to use shorts or longs.

Packing the array as signed characters would cater for up to 256128 contiguous ones or 255127 contiguous zeros. The following code uses a regex against a string representation of the vector but a pure vec solution as suggested by BrowserUk would be better. However, it illustrates my point.

use strict;
use warnings;

use 5.010;

my $vector = pack q{N*}, 0x01020304, 0x11121314;

my $bitStr = unpack q{b*}, $vector;
say $bitStr;
say q{=} x 20;

my $rcSign = do {
   my $val = $bitStr =~ m{^1} ? 1 : -1;
   sub { $val *= -1 }
   };

my @posns = ( 0 );
my @lengths;

while ( $bitStr =~ m{(?x)
   (?:
   (?<=0)(?=1)
   |
   (?<=1)(?=0)
   |
   (?=\z)
   )}g )
{
    push @posns, pos $bitStr;
    push @lengths, ( $posns[ -1 ] - shift @posns ) * $rcSign->();
}

my $rle = pack q{c*}, @lengths;

say q{Length of vector           - }, length $vector;
say q{Length of packed RLE array - }, length $rle;
say q{=} x 20;

say qq{@lengths};
my @restored = unpack q{c*}, $rle;
say qq{@restored};
say q{=} x 20;

[download]

The output.

1000000001000000110000000010000010001000010010001100100000101000
====================
Length of vector           - 8
Length of packed RLE array - 24
====================
-1 8 -1 6 -2 8 -1 5 -1 3 -1 4 -1 2 -1 3 -2 2 -1 5 -1 1 -1 3
-1 8 -1 6 -2 8 -1 5 -1 3 -1 4 -1 2 -1 3 -2 2 -1 5 -1 1 -1 3
====================

[download]

As I say, I may be misunderstanding something or your vector might consist of very long contiguous runs. I'd be interested to know whether you will see a benefit using RLE.

Update: Corrected the senior moment with maximum -ve and +ve values that can be held in a byte.

Cheers,

JohnGG

In reply to Re: Run length encode a bit vector by johngg
in thread Run length encode a bit vector by Anonymous Monk

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.