arithmetic coder (Python recipe) by Andrew Dalke

ActiveState Code (http://code.activestate.com/recipes/306626/)

#  A very slow arithmetic coder for Python.
#
#  "Rationals explode quickly in term of space and ... time."
#              -- comment in Rational.py (probably Tim Peters)
#
# Really.  Don't use this for real work.  Read Mark Nelson's
# Dr. Dobb's article on the topic at
#    http://dogma.net/markn/articles/arith/part1.htm
# It's readable, informative and even includes clean sample code.
#
# Contributed to the public domain
# Andrew Dalke < dalke @ dalke scientific . com >


import sys

import Rational, math
R = Rational.rational

def train(text):
    """text -> 0-order probability statistics as a dictionary

    Text must not contain the NUL (0x00) character because that's
    used to indicate the end of data.
    """
    assert "\x00" not in text
    counts = {}
    for c in text:
        counts[c]=counts.get(c,0)+1
    counts["\x00"] = 1
    tot_letters = sum(counts.values())

    tot = 0
    d = {}
    prev = R(0)
    for c, count in counts.items():
        next = R(tot + count, tot_letters)
        d[c] = (prev, next)
        prev = next
        tot = tot + count
    assert tot == tot_letters

    return d


def encode(text, probs):
    """text and the 0-order probability statistics -> longval, nbits

    The encoded number is rational(longval, 2**nbits)
    """
    minval = R(0)
    maxval = R(1)
    for c in text + "\x00":
        prob_range = probs[c]
        delta = maxval - minval
        maxval = minval + prob_range[1] * delta
        minval = minval + prob_range[0] * delta

    # I tried without the /2 just to check.  Doesn't work.
    # Keep scaling up until the error range is >= 1.  That
    # gives me the minimum number of bits needed to resolve
    # down to the end-of-data character.
    delta = (maxval - minval)/2
    nbits = 0L
    while delta < 1:
        nbits = nbits + 1
        delta = delta << 1
    if nbits == 0:
        return 0, 0
    else:
        avg = (maxval + minval)<<(nbits-1)  # using -1 instead of /2
    # Could return a rational instead ...
    return avg.n//avg.d, nbits  # the division truncation is deliberate


def decode(longval, nbits, probs):
    """decode the number to a string using the given statistics"""
    val = R(longval, 1L<<nbits)
    letters = []
    probs_items = [(c, minval, maxval) for (c, (minval, maxval))
                                 in probs.items()]

    while 1:
        for (c, minval, maxval) in probs_items:
            if minval <= val < maxval:
                break
        else:
            raise AssertionError("not found")

        if c == "\x00":
            break
        letters.append(c)
        delta = maxval - minval
        val = (val - minval)/delta
    return "".join(letters)

if __name__ == "__main__":
    # getopt? optparse? What are they?
    import sys
    trainfilename = sys.argv[1]  # must give a filename
    phrase = sys.argv[2]  # must give text to compress (slowly!)
    probs = train(open(trainfilename).read())
    n, nbits = encode(phrase, probs)
    # +1 for the NUL terminator or equivalent
    print "Orig. %d bits, compr. %d bits, ratio = %3.f%%" % (
        (len(phrase)+1)*8, nbits, (100.*nbits) / (len(phrase)*8+1))
    print n
    new_phrase = decode(n, nbits, probs)
    print "Was it '%s'?" % (new_phrase,)
    if phrase == new_phrase:
        print "Guess so."
    else:
        print "Why not?!"