""" | |
Elias Omega code in Python | |
http://en.wikipedia.org/wiki/Elias_omega_coding | |
Peter Elias, "Universal codeword sets and representations of the integers", IEEE Trans. Information Theory 21(2):194-203, Mar 1975. | |
Also known as the log* (or "logstar") code in Rohan Baxter's 1996 PhD thesis. | |
Type 'python EliasOmega.py' to run the tests. | |
""" | |
# A Python function decorator to remember computed values | |
def __memoize(function): | |
memo = {} | |
def wrapper(*args): | |
if args in memo: | |
return memo[args] | |
else: | |
rv = function(*args) | |
memo[args] = rv | |
return rv | |
return wrapper | |
@__memoize | |
def __recursive_encode(n): | |
s = "" | |
if n>1: | |
b = bin(n)[2:] | |
s += __recursive_encode(len(b)-1) + b | |
return s | |
@__memoize | |
def __recursive_decode(s, n): | |
if s[0]=="0": | |
return [n, s[1:]] | |
else: | |
m = int(s[:n+1], 2) | |
return __recursive_decode(s[n+1:], m) | |
def encode(n): | |
"""Encode a string using the Elias Omega code. | |
>>> encode(16) | |
'10100100000' | |
>>> encode(100) | |
'1011011001000' | |
>>> encode(1000) | |
'11100111111010000' | |
>>> encode(1000000) | |
'1010010011111101000010010000000' | |
>>> [encode(n) for n in range(1, 18)] | |
['0', '100', '110', '101000', '101010', '101100', '101110', '1110000', '1110010', '1110100', '1110110', '1111000', '1111010', '1111100', '1111110', '10100100000', '10100100010'] | |
""" | |
return __recursive_encode(n)+"0" | |
def decode(s): | |
"""Decode a string containing a binary number encoded using the Elias Omega code. | |
>>> decode('1011011001000') | |
[100, ''] | |
>>> all([decode(encode(n))[0]==n for n in range(1, 10000)]) | |
True | |
""" | |
return __recursive_decode(s, 1) | |
def codelength(n): | |
"""Calculate the Elias Omega codelength. | |
>>> codelength(17) | |
11 | |
""" | |
return len(encode(n)) | |
def probability(n): | |
"""Approximate the probability of n implied by the Elias Omega code. | |
>>> probability(2)==1/8. | |
True | |
""" | |
return pow(2, -float(codelength(n))) | |
def _test(): | |
import doctest | |
doctest.testmod() | |
if __name__ == "__main__": | |
_test() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment