integercoding.pl - simple encoding and decoding using integer codings
Example code to encode and decode numbers into binary strings using various integer codings.
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)) ); }
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.
encode_
$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.
decode_
$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;
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.
Dana Jacobsen <dana@acm.org>
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
To install Data::BitStream, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Data::BitStream
CPAN shell
perl -MCPAN -e shell install Data::BitStream
For more information on module installation, please visit the detailed CPAN module installation guide.