Data::BitStream::Code::Taboo - A Role implementing Taboo codes
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 preceeding 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
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 lexigraphically ordered. For most purposes these are not important.
Insert one or more values as block taboo codes using the binary string
$taboo as the terminator. Returns 1.
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.
taboo is a binary string, meaning it is a string comprised exclusively of
'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
'0' then one-based unary coding is used (e.g. a string of
1 bits followed by a
'1' then zero-based unary coding is used (e.g. a string of
0 bits followed by a
Dana Jacobsen <email@example.com>
Copyright 2012 by Dana Jacobsen <firstname.lastname@example.org>
This program is free software; you can redistribute it and/or modify it under the same terms as Perl itself.