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.

     

    Etiquetas:

    Deja una respuesta

    Tu direcci贸n de correo electr贸nico no ser谩 publicada. Los campos obligatorios est谩n marcados con *