Comprimir información

Veamos como escribir un algoritmo sencillo que permite comprimir información. Imagina que tienes unos datos:

• 📜 AAAAETTTTH: Tenemos una secuencia de datos.
• 📦 A4E1T4H1: Que puede ser comprimida de esta forma. Por ejemplo en vez de AAAA podemos comprimir a A4.

Veamos como implementarlo en comprime. Iteramos toda nuestra secuencia s. Si el siguiente elemento s[i+1] es igual al actual, contamos cuantos iguales hay. Cuando ya no es igual, guardamos la información en comprimido.

def comprime(s):
    comprimido = []
    cuenta = 1

    for i in range(len(s)):
        if i + 1 < len(s) and s[i] == s[i + 1]:
            cuenta += 1
        else:
            comprimido.append((s[i], cuenta))
            cuenta = 1

    return comprimido

Podemos usar la función de la siguiente manera, y este es el resultado.

comprimido = comprime("AAAAETTTTH")
print(comprimido)
# [('A', 4), ('E', 1), ('T', 4), ('H', 1)]

Es importante notar que este algoritmo funciona bien cuando hay mucha información repetida. En el caso contrario, puede ser hasta peor como en el siguiente ejemplo:

• 📜 ABCDEF: La secuencia no tiene nada de redundancia, es decir, no se repite nada.
• 📦 A1B1C1D1E1F1: Nuestro algoritmo de compresión da una salida que es en realidad mayor. No nos sirve.

✏️ Ejercicios:

• Modifica la función comprime para que en vez de devolver una lista de tuple devuelva un str con la misma información.
• Implementa una función descomprime que realice lo contrario. Esto es, dada una secuencia comprimida, la descomprima a la original.