/ 
Data-BitStream-0.08
River stage zero No dependents
/ integercoding.pl

NAME

integercoding.pl - simple encoding and decoding using integer codings

DESCRIPTION

Example code to encode and decode numbers into binary strings using various integer codings.

SYNOPSIS

Command line examples:

echo "15" | perl integercoding.pl -encode omega
echo "00010001110111" | perl integercoding.pl -decode delta

Subroutine examples:

print "$_ encoded in gamma is ", encode_gamma($_), "\n"  for (1 .. 10);

my $delta_str = encode_delta(317);
my $fib_str = encode_fib( decode_delta( $delta_str ) );
print "fib str: $fib_str encodes ", decode_fib($fib_str), "\n";

Print out a table of code sizes:

printf("%7s   %7s  %7s  %7s  %7s  %7s  %7s\n",
       "Value", "Unary", "Binary", "Gamma", "Delta", "Omega", "Fib");
my @vals = (1..5);
push @vals, $vals[-1]*2, $vals[-1]*4, $vals[-1]*10  for (1..5);
foreach my $n (@vals) {
  printf("%7d   %7s  %7s  %7s  %7s  %7s  %7s\n",
         $n, $n+1, base_of($n)+1,
         length(encode_gamma($n)), length(encode_delta($n)),
         length(encode_omega($n)), length(encode_fib($n))     );
}

FUNCTIONS

The encode_ methods take a single unsigned integer as input and produce a string of 0 and 1 characters representing the bit encoding of the integer using that code.

$str = encode_unary(8);    # die unless $str eq '000000001';
$str = encode_gamma(8);    # die unless $str eq '0001000';
$str = encode_delta(8);    # die unless $str eq '00100000';
$str = encode_omega(8);    # die unless $str eq '1110000';
$str = encode_fib(8);      # die unless $str eq '000011';

The decode_ methods take a single binary string as input and produce an unsigned integer output decoded from the bit encoding.

$n = decode_unary('000000000000001');  # die unless $n == 14;
$n = decode_gamma('0001110');          # die unless $n == 14;
$n = decode_delta('00100110');         # die unless $n == 14;
$n = decode_omega('1111100');          # die unless $n == 14;
$n = decode_fib(  '1000011');          # die unless $n == 14;

SEE ALSO

The CPAN module Data::BitStream includes these codes and more.

Peter Elias, "Universal Codeword Sets and Representations of the Integers", IEEE Trans. Information Theory, Vol 21, No 2, pp 194-203, Mar 1975.

Peter Fenwick, "Punctured Elias Codes for variable-length coding of the integers," Technical Report 137, Department of Computer Science, The University of Auckland, Auckland, New Zealand, December 1996.

http://en.wikipedia.org/wiki/Unary_coding
http://en.wikipedia.org/wiki/Elias_gamma_coding
http://en.wikipedia.org/wiki/Elias_delta_coding
http://en.wikipedia.org/wiki/Elias_omega_coding
http://en.wikipedia.org/wiki/Fibonacci_coding

AUTHORS

Dana Jacobsen <dana@acm.org>

COPYRIGHT

Copyright 2011 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.

See http://www.perl.com/perl/misc/Artistic.html