Complejidad Temporal
Mejor: O(n)
Prom: O(n)
Peor: O(n)
La Codificación por Longitud de Racha (RLE) es un algoritmo simple de compresión sin pérdida. Reemplaza repeticiones consecutivas del mismo símbolo por un par (símbolo, conteo).
Cómo funciona:
1. Escanear la entrada de izquierda a derecha
2. Cuando aparece un carácter nuevo, iniciar una racha
3. Seguir contando mientras el siguiente carácter coincida
4. Emitir (carácter, conteo) y continuar tras la racha
Por qué funciona:
Las rachas largas de valores idénticos desperdician espacio si se almacenan de forma ingenua. Codificar la longitud una sola vez captura esa redundancia. La decodificación es la inversa: expandir cada par en count copias del carácter.
Complejidad Temporal:
Mejor: O(n)
Promedio: O(n)
Peor: O(n)
Complejidad Espacial: O(k) donde k es el número de rachas
Propiedades:
- Sin pérdida cuando conteos y símbolos se guardan sin pérdida
- Excelente para bitmaps dispersos, iconos y gráficos simples (BMP RLE, PCX, fax)
- Puede expandir datos sin rachas largas (p. ej. ABABAB alternado)
- A menudo se usa como primera etapa antes de Huffman o codificación aritmética
RLE es una de las ideas de compresión más antiguas que aún se enseñan: fácil de implementar, fácil de visualizar y un bloque dentro de formatos más grandes.
Algoritmos relacionados
Preguntas frecuentes
- ¿Qué es Codificación por Longitud de Racha?
- La Codificación por Longitud de Racha (RLE) es un algoritmo simple de compresión sin pérdida. Reemplaza repeticiones consecutivas del mismo símbolo por un par (símbolo, conteo).
- ¿Cuál es la complejidad de Codificación por Longitud de Racha?
- Tiempo (promedio): O(n) · Espacio: O(k)
- ¿Para quién es este visualizador de Codificación por Longitud de Racha?
- La visualización de Codificación por Longitud de Racha está pensada para nivel principiante, dentro de la categoría Compresión. Ideal para estudiantes, entrevistas técnicas y repaso práctico.
- ¿Qué algoritmos relacionados hay con Codificación por Longitud de Racha?
- En la misma categoría (Compresión) puedes explorar: LZ77, LZW, Huffman Coding. Todos tienen visualización interactiva.