- NAME
- VERSION
- SYNOPSIS
- DESCRIPTION/DISCUSSION
- EXPORTS
- SUBROUTINES
- METHODS

# NAME

Data::Bvec - a module to manipulate integer arrays as bit vectors and "compressed bit strings" (using a simple RLE).

# VERSION

VERSION: 1.01

# SYNOPSIS

```
use Data::Bvec;
my $bv = Data::Bvec::->new( nums=>[1,2,3] );
my $vec = $bv->get_bvec(); # 01110000
my $bstr = $bv->get_bstr(); # '-134'
my $nums = $bv->get_nums(); # [1,2,3]
----
use Data::Bvec qw( :all );
my $vec = num2bit( [1,2,3] ); # 01110000
set_bit( $vec, 4, 1 ); # 01111000
my $bstr = compress bit2str $vec; # '-143'
my $nums = bit2num str2bit uncompress $bstr; # [1,2,3,4]
```

# DESCRIPTION/DISCUSSION

This module encapsulates some simple routines for manipulating Perl bit vectors (putting values in; getting values out), but its main goal is to implement a simple run-length encoding scheme for bit vectors that compresses them into relatively human-readable and flat-file-storable strings.

My use case was wanting to prototype a data indexing system, and I wanted to ease debugging by plopping the bitstrings in a flat file that I could examine directly. (Each bit in a vector represents a record in the database -- true or false whether the term is in that record in the field being indexed.) It has worked well enough that I haven't felt the need to change how the bitstrings are stored (just where they're stored).

The initial version of the module used a different set of base-62 digits. In writing Math::Int2Base, I decided to normalize all the bases from 2 to 62 to use 0-9,A-Z,a-z. It makes the numbers sort correctly (ascii-betically == numerically), and it let me say that A base-16 == A base-36 == A base-62.

So now I'm rewriting this module to use those base conversion routines.

# EXPORTS

Nothing is exported by default. The following may be exported individually; all of them may be exported using the `:all`

tag:

```
- set_bit
- howmany
- bit2str
- str2bit
- bit2num
- num2bit
- compress
- uncompress
```

Examples:

```
use Data::Bvec qw( :all );
use Data::Bvec qw( bit2str str2bit compress uncompress );
```

However, if you only use the object methods, nothing would need to be exported. See below.

# SUBROUTINES

## set_bit( $vec, $num, $zero_or_one )

This is a shallow wrapper around Perl's vec() that simply provides the third parameter (1) to that routine that says we're working with a bit vector.

Normally returns $num, if you care.

### Parameters:

#### $vec

A Perl bit vector stored in the scalar.

#### $num

The number whose bit you want to target in the bit vector.

#### $zero_or_one

The value you want to set the bit to: 0 or 1. If not defined, 1 is assumed.

Examples:

```
my $vec = ""; # empty vector
set_bit $vec, 1, 1; # 01000000
set_bit $vec, 2, 1; # 01100000
set_bit $vec, 3; # 01110000
set_bit $vec, 1, 0; # 00110000
```

## bit2str( $vec )

This routine is a shallow wrapper around unpack() that unpacks a bit vector into a string of '0's and '1's, in preparation for compression.

### Parameters:

#### $vec

A Perl bit vector.

Example:

```
my $vec = "";
set_bit $vec, 4, 1; # 00001000
my $str = bit2str $vec; # '00001000'
```

## str2bit( $str )

This routine is a shallow wrapper around pack() that packs a string of '0's and '1's (following uncompression) into a bit vector.

### Parameters:

#### $str

A string of '0's and '1's, e.g., "00001000".

Example:

` my $vec = str2bit '00001000';`

## num2bit( \@integers )

This routine accepts an array ref of integers and returns a bit vector with those integer's bits turned on.

### Parameters:

#### \@integers

A reference to an array of integers.

Examples:

```
my $vec = num2bit [1,2,3]; # 01110000
my $vec = num2bit [3,2,1]; # 01110000
```

The second example is intended to make clear that the order of the integers in the array is not retained (for obvious reasons), and calling bit2num( $vec ) will always return the integers in ascending order (see bit2num() below).

## bit2num( $vec, $beg, $cnt )

This routine accepts a bit vector and returns an array of integers represented by the 1 bits.

The parameters $beg and $cnt are to support retrieving subsets of integers from a large vector -- in essence, to support "paging" through the set.

In scalar context, returns a reference to the array.

### Parameters:

#### $vec

A bit vector.

#### $beg

The first integer (where the bit is 1) to return. Unlike array subscripts, the $beg positions start with 1, not 0.

#### $cnt

The maximum number of integers (including the first) to return.

Examples:

```
# 0----+----1----+----2----+----3-
my $vec = str2bit '01110011110001111100001111110001';
my $set1 = bit2num $vec, 1, 5; # [ 1, 2, 3, 6, 7 ]
my $set2 = bit2num $vec, 6, 5; # [ 8, 9, 13, 14, 15 ]
my $set3 = bit2num $vec, 11, 5; # [ 16, 17, 22, 23, 24 ]
my $set4 = bit2num $vec, 16, 5; # [ 25, 26, 27, 31 ]
```

## compress( $str )

This routine takes a string of '0's and '1's and compresses it using a simple run-length encoding (RLE). It returns this "compressed bit string".

### Parameters:

#### $str

A string of '0's and '1's, e.g., "01110".

Note: the length of the string need not be a multiple of 8.

Example:

```
my $bstr;
$bstr = compress '01110000'; # '-134'
my $str = ('1'x100).('0'x30).('1'x6);
$bstr = compress $str; # '+@1cU6'
```

### Compression Scheme

The compression scheme counts the number of consecutive '0's and '1's and concatenates that count (in base-62) to the compressed bit string.

If the first bit is '0', the compressed bit string begins with '-'. If the first bit is '1', it begins with '+'. The digit following that represents that many of those bits. The next digit represents that many of the "other" bits, and so on. (A "digit" matches /[0-9A-Za-z]/.)

So in the first example, '-134' means 1 '0' bit, then 3 '1' bits, then 4 '0' bits, i.e., '01110000'.

The second example includes a 2-digit number, 1c base-62 (100 decimal, as defined by Math::Int2base).

Any multi-digit number is preceded by a non-digit:

```
'@' for a 2-digit number
'#' for 3 digits
'$' for 4 digits
'%' for 5 digits, and
'^' for 6 digits
```

(Mnemonic: look above the numbers on a qwerty keyboard. A 6-digit number will accommodate 32,590,299,105 consecutive bits. If you need more than that, let me know.)

So '+@1cU6' means 1c (100) '1' bits, then U (30) '0' bits, then 6 '1' bits.

## uncompress( $bstr )

This routine uncompresses a compressed bit string (which would have been compressed by the compress() routine above).

It returns a string of '0's and '1's. This string will (normally) then be converted to a bit vector using str2bit() above.

### Parameters:

#### $bstr

A compressed bit string (see compress() above).

Example:

```
my $bstr = '-134';
my $str = uncompress $bstr; # '01110000'
```

## howmany( $vec, $zero_or_one )

This routine returns a count of the 0 or 1 bits in a bit vector.

### Parameters:

#### $vec

A bit vector.

#### $zero_or_one

The value you want a count of: 0 or 1. Defaults to 1 if not given.

Examples:

```
my $vec = str2bit '01010010';
my $ones_count = howmany $vec; # 3
my $zeros_count = howmany $vec, 0; # 5
```

Note that howmany( $vec, 0 ) will include trailing zero bits.

# METHODS

## new()

This constructs a Data::Bvec object. Each object represents a single array of integers stored either as a bit vector, a compressed bit string, or an array.

### Parameters:

All parameters to new() are named.

#### bvec=>$bit_vector

Stores a Perl bit vector in the object.

```
my $vec = str2bit '01110011110001111100001111110001';
my $bv = Data::Bvec::->new( bvec => $vec );
```

#### bstr=>$compressed_bit_string

Stores a compressed bit string in the object.

```
my $bstr = compress bit2str $vec;
my $bv = Data::Bvec::->new( bstr => $bstr );
```

#### nums=>\@integers

Stores an array of integers in the object. The order of the array is retained when stored.

```
my $nums = bit2num $vec;
my $bv = Data::Bvec::->new( nums => $nums );
```

#### bvec2nums=>$bit_vector

Accepts a bit vector and stores it as an array of integers (as $self->{nums}).

` my $bv = Data::Bvec::->new( bvec2nums => $vec );`

#### nums2bvec=>\@integers

Accepts an array of integers and stores it as a bit vector (as $self->{bvec}). The order of the array is not retained.

` my $bv = Data::Bvec::->new( nums2bvec => $nums );`

#### bvec2bstr=>$bit_vector

Accepts a bit vector and stores it as a compressed bit string (as $self->{bstr}).

` my $bv = Data::Bvec::->new( bvec2bstr => $vec );`

#### bstr2bvec=>$compressed_bit_string

Accepts a compressed bit string and stores it as a bit vector (as $self->{bvec}).

` my $bv = Data::Bvec::->new( bstr2bvec => $bstr );`

#### bstr2nums=>$compressed_bit_string

Accepts a compressed bit string and stores it as an array of integers (as $self->{nums}).

` my $bv = Data::Bvec::->new( bstr2nums => $bstr );`

#### nums2bstr=>\@integers

Accepts an array of integers and stores it as a compressed bit string (as $self->{bstr}). The order of the array is not retained.

` my $bv = Data::Bvec::->new( nums2bstr => $nums );`

## get_bvec()

This routine takes no parameters. It returns a bit vector, regardless how the integers are stored. The object is not changed.

` my $vec = $bv->get_bvec();`

## get_bstr()

This routine takes no parameters. It returns a compressed bit string, regardless how the integers are stored. The object is not changed.

` my $bstr = $bv->get_bstr();`

## get_nums( $beg, $cnt )

This routine returns an array of integers, regardless how the integers are stored. The object is not changed.

Note that if the integers are stored as 'nums' (an array), get_nums() will return them in the same order as the array. If they are stored another way, they will be returned in ascending order.

```
my @integers = $bv->get_nums(); # list returned in list context
my $ints = $bv->get_nums(); # aref returned in scalar context
```

### Parameters:

#### $beg

The first integer to return. Unlike array subscripts, the $beg positions start with 1, not 0. If no $beg is given, 1 is assumed.

#### $cnt

The maximum number of integers (including the first) to return. If no $cnt is given, the rest of the integers are returned.