NAME

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

VERSION

version 0.08

DESCRIPTION

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

Taboo codes are described in Steven Pigeon's 2001 PhD Thesis as well as his paper "Taboo Codes: New Classes of Universal Codes."

The block methods implement a slight modification of the taboo codes, wherein zero is encoded as the taboo pattern with no preceding bits. This causes no loss of generality and lowers the bit count for small values.

An example using '11' as the taboo pattern (chunk size n=2):

      value        code          binary         bits
          0           t                    11    2
          1          0t                  0011    4
          2          1t                  0111    4
          3          2t                  1011    4
          4         00t                000011    6
  ..     12         22t                101011    6
         13        000t              00000011    8
  ..     64       0220t            0010100011   10
  ..  10000  000012220t  00000000011010100011   20

These codes are a more efficient version of comma codes, as they allow leading zeros.

The unconstrained taboo codes are not implemented yet. However, the generalized Fibonacci codes are a special case of taboo codes (using a taboo pattern of all ones and a different bit ordering). The lengths of the codes will be identical in all cases, so it is recommended to use them if possible. What unconstrained taboo codes offer over generalized Fibonacci codes is the ability to have any ending pattern and having the prefix be lexicographically ordered. For most purposes these are not important.

METHODS

Provided Object Methods

put_blocktaboo($taboo, $value)

put_blocktaboo($taboo, @values)

Insert one or more values as block taboo codes using the binary string $taboo as the terminator. Returns 1.

get_blocktaboo($taboo)

get_blocktaboo($taboo, $count)

Decode one or more block taboo 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.

Parameters

The parameter taboo is a binary string, meaning it is a string comprised exclusively of '0' and '1' characters. The length is the chunk size in bits, and must be between 1 and 16. Using '00' gives the codes from table 2 of Pigeon's paper (where the chunk size n=2 and the taboo pattern is the two-bits '00').

If taboo is '0' then one-based unary coding is used (e.g. a string of 1 bits followed by a 0). If taboo is '1' then zero-based unary coding is used (e.g. a string of 0 bits followed by a 1).

Required Methods

read

write

These methods are required for the role.

SEE ALSO

Steven Pigeon, "Taboo Codes: New Classes of Universal Codes", 2001.

Data::BitStream::Code::Fibonacci

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.