Aritmetic coding (python)

De GirinoWiki

#!/usr/bin/python
# coding: iso-8859-15
 
import sys
 
#SIZE_DEF = 16
#BASE_DEF = 2
 
# este parâmetros definemo número de dígitos a serem usados e
# a base desses dígitos. BASE_DEF = 10 indica base decimal.
# BASE_DEF = 2 indica base binária. BASE_DEF = 16, hexadecimal.
# Qualquer valor de base pode ser usado aqui.
SIZE_DEF = 5
BASE_DEF = 10
 
LOW_DEF =  0
HIGH_DEF = BASE_DEF**SIZE_DEF-1
MOD_DEF =  BASE_DEF**(SIZE_DEF-1)
 
 
def count_freq(str):
    """
        Esta função conta a frequência de ocorrência dos
        caracteres no arquivo de entrada.
    """
    size = len(str)
    count = dict()
    for i in range(0, size):
        char = str[i]
        if count.has_key(char):
            count[char] = count[char] + 1
        else:
            count[char] = 1
    return count
 
def build_intervals(count):
    """
        Esta função constrói a tabela de freqüências acumuladas 
        necessária à codificação aritmética.
    """
    begin = 0
    end = 0
    intervals = dict()
    for key in count.keys():
        begin = end
        end = end + count[key]
        intervals[key] = [begin, end]
    return intervals
 
def encode(str):
    """
        Esta função codifica usando codificação aritmética
        uma cadeia de caracteres "str". A implementação usa a 
        técnica descrita em 
        http://pt.wikipedia.org/wiki/Codifica%C3%A7%C3%A3o_aritm%C3%A9tica#C.C3.A1lculo_com_precis.C3.A3o_finita
        para representar a codificação usando precisão finita. Entretanto
        não é utilizada a tecnica descrita para se evitar underflow. Neste
        caso o programa irá falhar entrando em "loop" infinito.
    """
    # calculam-se os intervalos
    intervals = build_intervals(count_freq(str))
    size = len(str)
    low = LOW_DEF
    high = HIGH_DEF
    ret = [] # inicializa o vetor de retorno
    # itera-se sobre todo o arquivo de entrata (str)
    for i in range(0, len(str)):
        char = str[i]
        interval = intervals[char]
        begin = interval[0]
        end = interval[1]
        # recalcula-se o tamanho do intervalo atual
        oldlow = low
        low = oldlow + (high-oldlow+1) * begin/size
        high = oldlow + (high-oldlow+1) * end/size -1
        # caso os primeiros dígitos sejam iguais, podemos
        # eliminá-los da rpresentação finita e emitílos na saída
        while (high / MOD_DEF) == (low / MOD_DEF):
            ret = ret + [high / MOD_DEF]
            high = (high - (MOD_DEF * (high / MOD_DEF))) * BASE_DEF + (BASE_DEF-1)
            low = (low - (MOD_DEF * (low / MOD_DEF))) * BASE_DEF
    # como não nos interessa a "melhor" codificação possível, 
    # podemos usar o limite inferior do intervalo como codificação com
    # muito pouco prejuíso.
    while low > 0:
        ret = ret + [low / MOD_DEF]
        low = (low - (MOD_DEF * (low / MOD_DEF))) * BASE_DEF
    return [ret, intervals, len(str)]
 
def decode(val, intervals, size):
    """
        Esta função é análoga a função "encode", e realiza o processo
        inverso. As mesmas premissas devemser consideradas neste caso.
    """
    # inicializa o arquivo (string) de retorno
    ret = ""
    low = LOW_DEF
    high = HIGH_DEF
    code = 0
    # lemos os primeiros dígitos do código
    for x in val[0:SIZE_DEF]:
        code = code * BASE_DEF + x
    pos = SIZE_DEF
    # e produzimos todos os caracteres da entrada, na saída
    for i in range(0, size):
        # o "index" é a posição na tabela de probabilidades
        # que representa o intervalo atual 
        index = int(((code-low+1)*size-1)/(high-low+1))
        # temos de iterar por toda a tabela par aencontrar o intervalo
        for key in intervals.keys():
            interval = intervals[key]
            begin = interval[0]
            end = interval[1]
            if index >= begin and index < end:
                ret = ret + key
                oldlow = low
                low = oldlow + (high-oldlow+1) * begin/size
                high = oldlow + (high-oldlow+1) * end/size -1
                break
        # e podemos eliminar os primeiros dígitos quando eles forem
        # repetidos, lendo o próximo dígito do código
        while (high / MOD_DEF) == (low / MOD_DEF):
            code = (code - (MOD_DEF * (code / MOD_DEF))) * BASE_DEF
            if pos < len(val):
                code = code + val[pos]
                pos = pos + 1
            high = (high - (MOD_DEF * (high / MOD_DEF))) * BASE_DEF + (BASE_DEF-1)
            low = (low - (MOD_DEF * (low / MOD_DEF))) * BASE_DEF
    return ret
 
str = 'A_ASA_DA_CASA'
encoded = encode(str)
print encoded
decoded = decode(encoded[0], encoded[1], encoded[2])
print decoded