NAME

Data::BitStream::Code::Additive - A Role implementing Additive codes

VERSION

version 0.08

DESCRIPTION

A role written for Data::BitStream that provides get and set methods for Additive codes. The role applies to a stream object.

If you use the Goldbach codes for inputs more than ~1000, I highly recommend installing Data::BitStream::XS for better performance. While these codes were not designed for large inputs, they work fine, however at large computational costs.

EXAMPLES

  use Data::BitStream;

  my @array = (4, 2, 0, 3, 7, 72, 0, 1, 13);

  $stream->put_goldbach_g1( @array );
  $stream->rewind_for_read;
  my @array2 = $stream->get_goldbach_g1( -1 );

  my @seeds = (2, 16, 46);
  $stream->erase_for_write;
  $stream->put_additive_seeded( \@seeds, @array );
  $stream->rewind_for_read;
  my @array2 = $stream->get_additive_seeded( \@seeds, -1 );

  my @basis = (0,1,3,5,7,8,10,16,22,28,34,40,46,52,58,64,70,76,82,88,94);
  $stream->erase_for_write;
  $stream->put_additive( \@basis, @array );
  $stream->rewind_for_read;
  my @array2 = $stream->get_additive( \@basis, -1 );
=head1 METHODS

Provided Object Methods

put_goldbach_g1($value)

put_goldbach_g1(@values)

Insert one or more values as Goldbach G1 codes. Returns 1. The Goldbach conjecture claims that any even number is the sum of two primes. This coding finds, for any value, the shortest pair of gamma-encoded prime indices that form 2*($value+1).

get_goldbach_g1()

get_goldbach_g1($count)

Decode one or more Goldbach G1 codes from the stream. If count is omitted, one value will be read. If count is negative, values will be read until the end of the stream is reached. In scalar context it returns the last code read; in array context it returns an array of all codes read.

put_goldbach_g2($value)

put_goldbach_g2(@values)

Insert one or more values as Goldbach G2 codes. Returns 1. Uses a different coding than G1 that should yield slightly smaller codes for large values. They will also be almost twice as fast to encode and decode.

get_goldbach_g2()

get_goldbach_g2($count)

Decode one or more Goldbach G2 codes from the stream. If count is omitted, one value will be read. If count is negative, values will be read until the end of the stream is reached. In scalar context it returns the last code read; in array context it returns an array of all codes read.

put_additive_seeded(\@seeds, $value)

put_additive_seeded(\@seeds, @values)

Insert one or more values as Additive codes. Returns 1. Arbitrary values may be given as input, with the basis constructed as needed using the seeds. The seeds should be sorted and not contain duplicates. They will typically be even numbers. Examples include [2,16,46], [2,34,82], [2,52,154,896]. Each generated basis is cached, so successive put/get calls using the same seeds will run quickly.

get_additive_seeded(\@seeds)

get_additive_seeded(\@seeds, $count)

Decode one or more Additive codes from the stream. If count is omitted, one value will be read. If count is negative, values will be read until the end of the stream is reached. In scalar context it returns the last code read; in array context it returns an array of all codes read.

generate_additive_basis($maxval, @seeds)

Construct an additive basis from 0 to $maxval using the given seeds. This allows construction of bases as shown in Fenwick's 2002 paper. The basis is returned as an array. The bases will be identical to those used with the get/put_additive_seeded routines, though the latter allows the basis to be expanded as needed.

put_additive(\@basis, $value)

put_additive(\@basis, @values)

Insert one or more values as 2-ary additive codes. Returns 1. An arbitrary basis to be used is provided. This basis should be sorted and consist of non-negative integers. For each value, all possible pairs (i,j) are found where i + j = value, with the pair having the smallest sum of Gamma encoding for i and j being chosen. This pair is then Gamma encoded. If no two values in the basis sum to the requested value, a range error results.

put_additive(sub { ... }, \@basis, @values)

Insert one or more values as 2-ary additive codes, as above. The provided subroutine is used to expand the basis as needed if a value is too large for the current basis. As before, the basis should be sorted and consist of non-negative integers. It is assumed the basis is complete up to the last element (that is, the basis will only be expanded). The argument to the sub is a reference to the basis array and a value. When returned, the last entry of the basis should be greater than or equal to the value.

get_additive(\@basis)

get_additive(\@basis, $count)

Decode one or more 2-ary additive codes from the stream. If count is omitted, one value will be read. If count is negative, values will be read until the end of the stream is reached. In scalar context it returns the last code read; in array context it returns an array of all codes read.

get_additive(sub { ... }, \@basis, @values)

Decode one or more values as 2-ary additive codes, as above. The provided subroutine is used to expand the basis as needed if an index is too large for the current basis. The argument to the sub is a reference to the basis array and a negative index. When returned, index -$index of the basis must be defined as a non-negative integer.

Parameters

Both the basis and seed arrays are passed as array references. The basis array may be modified if a sub is given (since its job is to expand the basis). It is possible to use a tied array as the basis, but using an expansion callback sub is typically faster.

Required Methods

read

write

get_gamma

put_gamma

These methods are required for the role.

SEE ALSO

Data::BitStream::Code::Fibonacci

Data::BitStream::Code::Gamma

Math::Prime::XS

Peter Fenwick, "Variable-Length Integer Codes Based on the Goldbach Conjecture, and Other Additive Codes", IEEE Trans. Information Theory 48(8), pp 2412-2417, Aug 2002.

AUTHORS

Dana Jacobsen <dana@acm.org>

COPYRIGHT

Copyright 2012 by Dana Jacobsen <dana@acm.org>

This program is free software; you can redistribute it and/or modify it under the same terms as Perl itself.