¿Qué es el algoritmo de Run-Length Encoding?

El algoritmo Run-Length Encoding, o RLE, comprime datos que contienen una gran cantidad de repeticiones consecutivas de un mismo valor o símbolo. En lugar de almacenar cada valor o símbolo por separado, la codificación RLE almacena el valor o símbolo repetido junto con la longitud de la repetición.

Por ejemplo, si tenemos la cadena de caracteres “AAABBBCCCC”, la codificación RLE la representaría como “A3B3C4”. Encontrarás ejemplos donde primera se encuentra el número y a continuación el carácter, siendo “3A3B4C” su equivalencia. En este caso, el valor “A” se repite tres veces, el valor “B” se repite tres veces y el valor “C” se repite cuatro veces.

La codificación RLE es muy simple de implementar y es útil para comprimir datos que contienen repeticiones consecutivas de un mismo valor o símbolo. Sin embargo, no es adecuada para comprimir datos que no tienen patrones repetitivos claros. Además, la compresión que se puede lograr con RLE puede ser limitada en comparación con otros algoritmos de compresión más avanzados.

Aquí puedes ver una implementación usando Python:

def rle_encode(data: str) -> str:
    # Función auxiliar recursiva que toma la cadena de entrada y un índice
    def rle_helper(data: str, i: int) -> str:
        # Verificar si ya se ha llegado al final de la cadena de entrada
        if i >= len(data):
            return ""
        # Contar la cantidad de repeticiones consecutivas del carácter en la posición actual i
        def count_sequence(data, i):
            if i + 1 >= len(data) or data[i] != data[i + 1]:
                return 1
            count = count_sequence(data, i + 1)
            return count + 1
        count = count_sequence(data, i)
        # Si la cantidad de repeticiones es 1, simplemente agregar el carácter a la cadena comprimida
        if count == 1:
            return data[i] + rle_helper(data, i + 1)
        # Si la cantidad de repeticiones es mayor que 1, agregar la cantidad y el carácter a la cadena comprimida
        else:
            return data[i] + str(count) + rle_helper(data, i + count)

    # Llamada inicial a la función auxiliar con el índice inicial 0
    return rle_helper(data, 0)

Y aquí su uso.

data = "AAABBBCCCC"
compressed_data = rle_encode(data)
print(compressed_data)
# A3B3C4

No obstante, algoritmos como el de deflación o el basado en el LZ77, que aprovecha las secuencias de cadenas de caracteres, suelen ser utilizados por sistemas de compresión más avanzados en la actualidad.

En conclusión, aplicar Run-Length Encoding sigue siendo igual de útil para resolver pequeños problemas o crear soluciones minimalistas de compresión. Además nos ayuda a comprender como resuelven otros algoritmos de compresión sus dificultades de implementación. Podríamos considerarlo un recurso elemental que todo programador con aspiraciones a senior debería conocer, como secuencia Fibonacci o el algoritmo de ordenamiento burbuja.