Safe Haskell | Safe-Inferred |
---|---|
Language | Haskell2010 |
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
- encodeGamma :: Integer -> BitVec
- decodeGamma :: BitVec -> Maybe (Integer, BitVec)
- encodeDelta :: Integer -> BitVec
- decodeDelta :: BitVec -> Maybe (Integer, BitVec)
- encodeOmega :: Integer -> BitVec
- decodeOmega :: BitVec -> Maybe (Integer, BitVec)
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.