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 número 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 número 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 descomprimir:

def run_length_decoding(string):
#Inicializamos
    Output = ""
    i = 0
#Revisando:
    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

Selective Run-Lenght Encoding

Un problema común que ocurre al momento de aplicar Run Length Enconding es el tener que ocupar más espacio representando la versión comprimida que el espacio ocupado por el archivo sin comprimir. Esto ocurre cuando no hay símbolos iguales concatenados, lo que causa que una cadena del estilo \(ABCD\) se representaría como \(A1B1C1D1\).

El problema entonces es buscar un método en el cual se puedan identificar de manera efectiva sobre cuales símbolos se debería aplicar Run Lenght Encoding. En el artículo de Peng et al ³ se plantea un criterio base para decidir que símbolos dentro de un texto son adecuados para comprimir por medio de RLE.

\[p_x^2 (b_x + b_r)(N - 1) \geq b_r N_x\]

Donde: - \(p_x\) Es la frecuencia de aparición del símbolo x dentro de la secuencia. - \(b_x\) Es el tamaño en bits del símbolo x. - \(b_r\) Es el tamaño en bits utilizado para representar el número de repeticiones del caracter. - \(N_x\) Es el número de ocurrencias del símbolo x en la secuencia. - \(N\) Es el tamaño total de la secuencia a comprimir.

Notemos que para un \(N\) lo suficientemente grande: \(\frac{N_x}{N-1} \approx p_x\) Por lo que el criterio se simplifica a:

\[p_x \geq \frac{b_r}{(b_x+b_r)}\]

El algoritmo modificado: 1. Construye el arreglo \(G\) en el cual se incluyen solos los símbolos que cumplen el criterio anterior. 2. Analiza la secuencia de entrada, si el símbolo leído existen también dentro de G, se aplica RLE normalmente y se añade a la secuencia de salida. 3. Si el símbolo no existe, se añade sin modificar a la secuencia de salida.

Implementación Selective RLE

La siguiente es una implementación en python del algoritmo selectivo de Run-Lenght Encoding:

from collections import Counter

def selective_rle_compress(sequence, br=4):
    # Step 1: Calculate frequency of each symbol
    frequency = Counter(sequence)
    N = len(sequence)  # Length of the sequence

    # Step 2: Identify symbols suitable for RLE
    G = set()  # Set of symbols to encode with RLE
    for symbol, count in frequency.items():
        px = count / N  # Probability of symbol
        bx = len(bin(ord(symbol))[2:])  # Bit width (assuming ASCII characters)
        if px >= br / (bx + br):
            G.add(symbol)

    # Step 3: Compress the sequence
    compressed = []
    i = 0
    while i < N:
        symbol = sequence[i]
        if symbol in G:
            run_length = 1
            # Count the length of the run
            while i + run_length < N and sequence[i + run_length] == symbol:
                run_length += 1
            compressed.append((symbol, run_length))  # Store symbol and run length
            i += run_length
        else:
            compressed.append((symbol, 1))  # Store symbol directly
            i += 1

    return compressed, G  # Return compressed data and the set of encoded symbols

def selective_rle_decompress(compressed, G):
    # Decompress the sequence based on the encoded data and set G
    decompressed = []
    for symbol, run_length in compressed:
        if symbol in G:
            decompressed.extend(symbol * run_length)
        else:
            decompressed.append(symbol)  # Single symbol, not repeated

    return ''.join(decompressed)

# Example usage
sequence = "AAAABBBCCDDEEE"
compressed_data, G = selective_rle_compress(sequence)
print("Compressed Data:", compressed_data)
print("Encoded Symbols (G):", G)

# Decompression
original_sequence = selective_rle_decompress(compressed_data, G)
print("Decompressed Sequence:", original_sequence)

Complejidades

La complejidad del algoritmo de RLE simple es de O(N), puesto que estamos generando nuestra secuencia comprimida conforme vamos leyendo la secuencia de entrada. Para descomprimir ocurre lo mismo, complejidad O(N), leemos la secuencia comprimida y reconstruimos la secuencia original.

Para Run-Length Enconding selectivo, necesitamos construir el arreglo G de antemano, evaluar si un símbolo cumple la precondición para formar parte de G se realiza en tiempo O(1), pero obtener la frecuencia con la que aparece el símbolo significa un costo temporal de O(n), puesto que recorremos la secuencia entera, enumerando la cantidad de veces que leemos cada símbolo. La segunda parte de este algoritmo es realizar RLE consultando al arreglo G, por lo que el costo temporal es el mismo O(n).

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/ ↩

3. {Peng et al.}{2023}]{2023arXiv231217024P}, "Selective Run-Length Encoding" Peng X., Zhang Y., Peng D., Zhu J., 2023, arXiv, arXiv:2312.17024. doi:10.48550/arXiv.2312.17024 ↩