Algoritmo de compresión de datos de codificación de longitud de ejecución (RLE)
La codificación de longitud de ejecución (RLE) es una forma simple de compresión de datos sin pérdidas que se ejecuta en secuencias con el mismo valor que ocurre muchas veces consecutivas. Codifica la secuencia para almacenar un solo valor y su recuento.
Por ejemplo, considere una pantalla que contenga texto negro sin formato sobre un fondo blanco sólido. Habrá muchas tiradas largas de píxeles blancos en el espacio en blanco y muchas tiradas cortas de píxeles negros dentro del texto.
WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWWCon un algoritmo de compresión de datos de codificación de longitud de ejecución (RLE) aplicado a la línea de exploración hipotética anterior, se puede representar como 12W1B12W3B24W1B14W. Esto puede interpretarse como una secuencia de doce W’s, una B, doce W’s, Tres B’s, etc.
La idea es ejecutar un escaneo lineal en la string y, para cada carácter distinto, agregar el carácter y su aparición consecutiva en la string de salida.
El algoritmo se puede implementar de la siguiente manera en C++, Java y Python. Tenga en cuenta que el tamaño de salida duplicará el tamaño de entrada en el peor de los casos, por lo que el algoritmo no puede ejecutarse en su lugar. p.ej ABCD —> A1B1C1D1.
C++
|
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 28 29 30 31 32 33 34 35 |
#include <iostream> #include <string> using namespace std; // Realizar el algoritmo de compresión de datos de codificación de longitud de ejecución (RLE) // en la string `str` string encode(string str) { // almacena la string de salida string encoding = ""; int count; for (int i = 0; str[i]; i++) { // cuenta las apariciones del carácter en el índice `i` count = 1; while (str[i] == str[i + 1]) { count++, i++; } // agrega el caracter actual y su conteo al resultado encoding += to_string(count) + str[i]; } return encoding; } int main() { string str = "ABBCCCD"; cout << encode(str); return 0; } |
Resultado:
1A2B3C1D
Java
|
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 28 29 30 31 32 33 34 35 36 37 38 39 40 |
class Main { // Realizar el algoritmo de compresión de datos de codificación de longitud de ejecución (RLE) // en la string `str` public static String encode(String str) { // almacena la string de salida String encoding = ""; // caso base if (str == null) { return encoding; } int count; for (int i = 0; i < str.length(); i++) { // cuenta las apariciones del carácter en el índice `i` count = 1; while (i + 1 < str.length() && str.charAt(i) == str.charAt(i + 1)) { count++; i++; } // agrega el caracter actual y su conteo al resultado encoding += String.valueOf(count) + str.charAt(i); } return encoding; } public static void main(String[] args) { String str = "ABBCCCD"; System.out.print(encode(str)); } } |
Resultado:
1A2B3C1D
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 |
# Realizar el algoritmo de compresión de datos de codificación de longitud de ejecución (RLE) en la string `str` def encode(s): encoding = "" # almacena la string de salida i = 0 while i < len(s): # cuenta las ocurrencias del carácter en el índice `i` count = 1 while i + 1 < len(s) and s[i] == s[i + 1]: count = count + 1 i = i + 1 # agrega el carácter actual y su conteo al resultado encoding += str(count) + s[i] i = i + 1 return encoding if __name__ == '__main__': s = 'ABBCCCD' print(encode(s)) |
Resultado:
1A2B3C1D
La complejidad temporal de la solución anterior es O(n), dónde n es la longitud de la string de entrada y no requiere ningún espacio adicional.
Referencias: Codificación de longitud de ejecución - Wikipedia