Created
July 20, 2010 14:08
-
-
Save robertofraile/483003 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
""" | |
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() |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment