RLE

Introducción

Run-Length Encoding es un algoritmo simple y eficiente para la compresión de datos. Originalmente desarrollado en la década de los 60¹ con el fin de comprimir señales de televisión. Como su nombre indica, el algoritmo funciona por medio de representar apariciones consecutivas del mismo elemento, con una sola aparición seguida del número de repeticiones.

Definición

Dado un string \(S[1..n]\), un texto de tamaño \(n\), tal que: \(S= AAAAADDDDEEEBBC\) Podemos reducir el tamaño de este texto por medio de aplicar el siguiente algoritmo:

1. Leemos el string
2. Contamos cuantas veces se repite consecutivamente cada caracter.
3. Guardamos cada caracter y su numero de repeticiones.

Sobre nuestro texto \(S\) obtendriamos \(S_c = A5D4E3B2C1\) Transformamos un texto de tamaño \(n =15\) a uno de tamaño \(n_c= 10\) , 33% de compresión.

Para decodificar:

1. Leemos el texto comprimido
2. Escribimos cada caracter el numero indicado de veces.

A partir de \(S_c\) podemos recuperar el texto original \(S=AAAAADDDDEEEBBC\) sin perdida de informacion.

Implementación

El siguiente es un codigo en python para aplicar compresión RLE, obtenida a partir de una modificación de GeeksForGeeks²:

def run_length_encoding(string):
    # Inicializamos
    Output = ""
    count = 1
    #Leyendo el string
    for i in range(1, len(string)):
        if input_string[i] == input_string[i - 1]:
            count += 1
        else:
            Output += input_string[i - 1] + str(count)
            count = 1  
#Por cada caracter en S, comparamos con el caracter anterior, de ser iguales aumentamos el contador, cuando el caracter cambia, añadimos el caracter anterior + su numero de repeticiones al output y reiniciamos el contador.
    Output += input_string[-1] + str(count)
    return Output

# Ejemplo 
S_c = run_length_encoding("AAABBBCCDDDD")
print(S_c)  # Salida: A3B3C2D4

Para decodificar:

def run_length_decoding(string):
#Inicializamos
    Output = ""
    i = 0
#Leyending:
    while i < len(string):
        char = string[i]
        i += 1
        count = ""
        while i < len(string) and string[i].isdigit():
            count += string[i]
            i += 1
        Output += char * int(count)
# Recorremos el string codificado, cuando leemos una letra, la cargamos para expandirla, cuando leemos un numero expandimos la letra cargada durante la cantidad indicada por el numero.
    return Output

Referencias

---

1. A. H. Robinson and C. Cherry, "Results of a prototype television bandwidth compression scheme," in Proceedings of the IEEE, vol. 55, no. 3, pp. 356-364, March 1967, doi: 10.1109/PROC.1967.5493. keywords: Prototypes, Bandwidth, Detectors, Transmitters, TV broadcasting, Shape measurement, Testing, Data mining, Buffer storage, Research and development. ↩

2. https://www.geeksforgeeks.org/run-length-encoding/ ↩