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 usa y cómo implementar sus funciones de codificación y decodificación en Python....

En este artículo, repasaremos cómo funciona el algoritmo de codificación de longitud de ejecución, para qué se usa 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 descomprime, todos los datos originales se recuperarán cuando se decodifiquen. Su sencillez 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 un flujo ("ejecutar") de datos en su forma original y forma codificada:

Datos de entrada:

1
AAAAAAFDDCCCCCCCAEEEEEEEEEEEEEEEEE

Datos resultantes:

1
6A1F2D7C1A17E

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

Como te habrás dado cuenta, cuantos más valores consecutivos hay 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"), entonces no ahorraremos mucho espacio. 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, la cámara pixie, que es una cámara robótica que lo ayuda a rastrear fácilmente objetos, usa 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 el datos de etiquetas 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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# 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 qué está sucediendo en todo el código. Si no, 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:

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

Y la salida:

1
2
$ python rle-encode.py
6A1F2D7C1A17E

Decodificació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, lo agrega a su ‘recuento’, y si ve un carácter no numérico, agrega ‘recuento’ de esos caracteres a su decodificación, que se devuelve a la persona que llama una vez que itera a través de todo los datos de entrada.

Aquí está el algoritmo implementado en Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
# 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 el mismo resultado que obtuvimos de nuestra codificación:

1
2
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:

1
2
$ python rle-decode.py
AAAAAAFDDCCCCCCCAEEEEEEEEEEEEEEEEE

Tenga en cuenta que esta implementación no realiza ninguna verificación de errores para garantizar que tengamos un flujo de datos RLE válido. Si alguno de los datos de entrada no tiene el formato correcto, es probable que encuentre un error.