def count(e,L):
    """
    gibt die Haeufigkeit des Vorkommens des Elements e in der Liste L zurueck
    """
    return len([y for y in L if e==y])

def sort2(T):
    """
    sortiert die Liste T von 2-Tupeln nach der zweiten Komponente
    """
    if len(T) <= 1:
        return T
    else:
        return sort2([t for t in T[1:] if t[1] > T[0][1]]) + \
               [T[0]] + \
               sort2([t for t in T[1:] if t[1] <= T[0][1]])     

def freq(s):
    """
    gibt eine absteigend sortierte Liste von Tupeln (Zeichen,rel. Haeufigkeit)
    zurueck
    """
    m = set(s) # Menge der vorkommenden Zeichen
    T = [(ch,count(ch,s)) for ch in m]
    return sort2(T)

def htree(s):
    """
    gibt den Huffman-Baum zum String s als Liste zurueck
    """
    b = freq(s)
    while len(b) > 1:
        b = b[:-2]+[((b[-2],b[-1]),b[-2][1]+b[-1][1])]   
        b = sort2(b)
    return b

def codetab(s):
    """
    gibt zu einem String s die Code-Tabelle zurueck
    """
    code = {}           # Dictionary    
    t = htree(s)[0]     # Baum besteht nur aus einem Tupel
    c = ''              # Code
    stack = [(t,c)]     # Teilbaum und Teilcode auf Stack legen
    while len(stack) > 0:
        t = stack[-1][0]
        c = stack[-1][1]
        stack = stack[:-1]
        if type(t[0]) == str:
           code.update({t[0]:c})
        else:
            stack = stack+[(t[0][0],c+'0')]
            stack = stack+[(t[0][1],c+'1')]       
    return code

def encode(s,codetab):
    """
    codiert einen String s mit der Codetabelle codetab
    """
    code = ''
    for ch in s:
        code = code+codetab[ch]
    return code

def decode(code,codetab):
    """
    decodiert den code mit Hilfe der Codetabelle codetab
    """
    s = ''
    while len(code) > 0:
        for ch in codetab:
            wert = codetab[ch]
            n = len(wert)
            if wert == code[:n]:
                s = s + ch
                code = code[n:]
                break
    return s