public
Last active

  • Download Gist
EliasOmega.py
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93
"""
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()

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.