The Perl Toolchain Summit needs more sponsors. If your company depends on Perl, please support this very important event.
 / 
Data-BitStream-XS-0.08
River stage zero No dependents
1 ++
/ 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