Breaking

Post Top Ad

Your Ad Spot

viernes, 14 de junio de 2019

Codificación de longitud de ejecución

En este artículo repasaremos 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 conteos 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 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 un flujo ("ejecución") de datos en su forma original y codificada:
Datos de entrada :
AAAAAAFDDCCCCCCCAEEEEEEEEEEEEEEEEE  
Datos de salida :
6A1F2D7C1A17E  
En este ejemplo pudimos comprimir los datos de 34 caracteres hasta 13.
Como habrá notado, mientras más valores consecutivos haya en una fila, más espacio ahorraremos en la compresión resultante. Por otro lado, si tiene una secuencia de datos que cambia con frecuencia entre los valores (es decir, "BEFEFADED"), 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 Pixy , que es una cámara robótica que le ayuda a rastrear fácilmente los objetos, usa RLE para comprimir los datos de video etiquetados antes de transferirlos desde el dispositivo de cámara integrado a una aplicación externa. Cada píxel recibe 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 tendrá que recorrer cada carácter de los datos y contar las ocurrencias. Una vez que vea un carácter que sea diferente del carácter anterior, adjuntará 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, debe poder decir lo que está pasando a lo largo del código. Si no es así, 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. Al igual que antes, recorres el flujo de datos un carácter a la vez. Si ve un carácter numérico, luego lo agrega a su count, y si ve un carácter no numérico, entonces agrega countesos caracteres a su decodificación, que se devuelve a la persona que llama una vez que se repite en todas las entradas data.
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 tengamos un flujo de datos RLE válido. Si alguno de los datos de entrada no está formateado correctamente, es probable que encuentre un error.

No hay comentarios.:

Publicar un comentario

Dejanos tu comentario para seguir mejorando!

Post Top Ad

Your Ad Spot

Páginas