variety-0.2.0.0: integer arithmetic codes
Safe HaskellSafe-Inferred
LanguageHaskell2010

Codec.Elias

Description

Elias codes are prefix codes for positive, non-zero integers with no assumption or limit to their size. For completeness, gamma, delta and omega codes are implemented although for most applications you can get away with only using delta codes:

  • Gamma codes are 1 bit more efficient than delta codes for certain numbers between 1 and 15.
  • Omega codes only become shorter than delta codes for numbers above 1 googol, or \(10^{100}\).

For codes that include the value 0, see Elias.Natural.

Synopsis

Gamma coding

An Elias gamma code consists of the binary expansion of an integer, preceded by the unary encoding of the length of that expansion in zeros.

For example, while the binary expansion of 21 is:

>>> import qualified Codec.Arithmetic.Variety.BitVec as BV
>>> BV.toString $ BV.fromInteger 21
"10101"

its Elias code is:

>>> BV.toString $ enodeGamma 21
"000010101"

where an expansion of \(i\) is always preceeded by \(i-1\) zeros.

encodeGamma :: Integer -> BitVec Source #

Encode a number in a Elias gamma code. Throws an error if the input is not positive and non-zero.

decodeGamma :: BitVec -> Maybe (Integer, BitVec) Source #

Try to decode an Elias gamma code at the head of the given bit vector. If successful, returns the decoded value and the remainder of the BitVec with the value's code removed. Returns Nothing if the bit vector doesn't contain enough bits to specify a number.

Delta coding

An Elias delta code is like an Elias gamma code except that the length is itself coded like a gamma code instead of a unary encoding.

For example, the binary expansion of \(1\,000\,000\)

>>> BV.toString $ BV.fromInteger (10^6)
"11110100001001000000"
>>> length "11110100001001000000"
20

is prefixed with the gamma encoding of 20 and loses its leading bit (which begins every binary expansion):

>>> BV.toString <$> [encodeGamma 20, BV.fromInteger (10^6)]
["000010100","11110100001001000000"]
>>> BV.toString $ encodeDelta 1000000
"0000101001110100001001000000"
>>> length "0000101001110100001001000000"
28

encodeDelta :: Integer -> BitVec Source #

Encode a number in a Elias delta code. Throws an error if the input is not positive and non-zero.

decodeDelta :: BitVec -> Maybe (Integer, BitVec) Source #

Try to decode an Elias delta code at the head of the given bit vector. If successful, returns the decoded value and the remainder of the BitVec with the value's code removed. Returns Nothing if the bit vector doesn't contain enough bits to specify a number.

Omega coding

An Elias omega code is the result of recursively encoding the length of binary expansions in the prefix until a length of 1 is reached. Since binary expansions are written without any leading zeros, a single 0 bit marks the end of the code.

For example:

>>> BV.toString . BV.fromInteger <$> [2,4,19,10^6]
["10","100","10011","11110100001001000000"]
>>> length <$> ["10","100","10011","11110100001001000000"]
[2,3,5,20]
>>> BV.toString $ encodeOmega (10^6)
"1010010011111101000010010000000"
>>> length $ "1010010011111101000010010000000"
31

Note that, while asymptotically more efficient, omega codes are longer than delta codes until around 1 googol, or \(10^{100}\).

encodeOmega :: Integer -> BitVec Source #

Encode a number in a Elias omega code. Throws an error if the input is not positive and non-zero.

decodeOmega :: BitVec -> Maybe (Integer, BitVec) Source #

Try to decode an Elias omega code at the head of the given bit vector. If successful, returns the decoded value and the remainder of the BitVec with the value's code removed. Returns Nothing if the bit vector doesn't contain enough bits to specify a number.