Codificación de longitud de ejecución

En este artículo veremos cómo funciona el algoritmo de codificación de longitud de ejecución, para qué se utiliza y cómo implementar sus funciones de codificación y decodificación en Python.

La codificación de longitud de ejecución (RLE) es una forma muy simple de compresión de datos en la que se proporciona un flujo de datos como entrada (es decir, «AAABBCCCC») y la salida es una secuencia de recuentos de valores de datos consecutivos en una fila (es decir, » 3A2B4C «). Este tipo de compresión de datos no tiene pérdidas, lo que significa que cuando se descomprimen, todos los datos originales se recuperarán cuando se descodifiquen. Su simplicidad tanto en la codificación (compresión) como en la decodificación (descompresión) es una de las características más atractivas del algoritmo.

Aquí puede ver un ejemplo simple de una secuencia («ejecución») de datos en su forma original y codificada:

Los datos de entrada:

AAAAAAFDDCCCCCCCAEEEEEEEEEEEEEEEEE

Datos resultantes:

6A1F2D7C1A17E

En este ejemplo, pudimos comprimir los datos de 34 caracteres a 13.

Como habrás notado, cuantos más valores consecutivos en una fila, más espacio ahorramos en la compresión resultante. Por otro lado, si tiene una secuencia de datos que cambia con frecuencia entre valores (es decir, «BEFEFADED»), no ahorraremos mucho espacio en absoluto. De hecho, incluso podríamos aumentar el tamaño de nuestros datos, ya que una sola instancia de un carácter da como resultado 2 caracteres (es decir, «A» se convierte en «1A») en la salida de la codificación.

Debido a esto, RLE solo es bueno para ciertos tipos de datos y aplicaciones. Por ejemplo, el Cámara pixy, que es una cámara robótica que le ayuda a rastrear objetos fácilmente, utiliza RLE para comprimir datos de video etiquetados antes de transferirlos desde el dispositivo de cámara integrado a una aplicación externa. A cada píxel se le asigna una etiqueta de «sin objeto», «objeto 1», «objeto 2», etc. Esta es la codificación perfecta para esta aplicación debido a su simplicidad, velocidad y capacidad para comprimir los datos de la etiqueta de baja entropía.

Codificación

Para codificar una cadena de datos, su código deberá recorrer cada carácter de los datos y contar las ocurrencias. Una vez que vea un carácter que es diferente del carácter anterior, agregará el número de ocurrencias y el carácter a su codificación.

A continuación, encontrará una implementación simple en Python:

# rle-encode.py

def rle_encode(data):
    encoding = ''
    prev_char=""
    count = 1

    if not data: return ''

    for char in data:
        # If the prev and current characters
        # don't match...
        if char != prev_char:
            # ...then add the count and character
            # to our encoding
            if prev_char:
                encoding += str(count) + prev_char
            count = 1
            prev_char = char
        else:
            # Or increment our counter
            # if the characters do match
            count += 1
    else:
        # Finish off the encoding
        encoding += str(count) + prev_char
        return encoding

A partir de los comentarios, debería poder saber lo que sucede a lo largo del código. De lo contrario, sería un buen ejercicio ejecutar el código con un depurador y verlo en acción.

Continuando con el mismo archivo anterior, aquí hay un ejemplo del código que se está ejecutando:

encoded_val = rle_encode('AAAAAAFDDCCCCCCCAEEEEEEEEEEEEEEEEE')
print(encoded_val)

Y la salida:

$ python rle-encode.py
6A1F2D7C1A17E

Descodificación

Decodificar un flujo de datos codificado en RLE es incluso más fácil que codificarlo. Como antes, itera a través del flujo de datos un carácter a la vez. Si ve un carácter numérico, agréguelo a su count, y si ve un carácter no numérico, agregue count de esos caracteres a su decodificación, que se devuelve a la persona que llama una vez que itera a través de toda la entradadata.

Aquí está el algoritmo implementado en Python:

# rle-decode.py

def rle_decode(data):
    decode=""
    count=""
    for char in data:
        # If the character is numerical...
        if char.isdigit():
            # ...append it to our count
            count += char
        else:
            # Otherwise we've seen a non-numerical
            # character and need to expand it for
            # the decoding
            decode += char * int(count)
            count=""
    return decode

Podemos ejecutar este código en la misma salida que obtuvimos de nuestra codificación:

decoded_val = rle_decode('6A1F2D7C1A17E')
print(decoded_val)

Y la salida es la misma que nuestra entrada original a la función de codificación:

$ python rle-decode.py
AAAAAAFDDCCCCCCCAEEEEEEEEEEEEEEEEE

Tenga en cuenta que esta implementación no realiza ninguna comprobación de errores para garantizar que tenemos un flujo de datos RLE válido. Si alguno de los datos de entrada no está formateado correctamente, es probable que encuentre un error.