Algoritmo de compresión Run Length Encoding

En nuestro blog os hemos hablado de un alto número de programas que podemos utilizar para reducir el tamaño de nuestros archivos y de esta forma poder transportarlos de una forma más sencilla y ahorrando espacio para almacenar más información, pero ¿nos hemos planteado alguna vez como funcionan estos programas por dentro?

Para llevar a cabo la reducción del tamaño de los ficheros, los programas hacen uso de algoritmos de compresión, algoritmos que permiten reducir el tamaño de los archivos sin la perdida de información. Algoritmos de este tipo hay varios, con mejor o peor ratio de compresión, pero hoy os explicaremos como funciona el denominado Run Length Encoding, uno de los más antiguos y sencillos de entender.

Run length Encoding
La idea principal de este algoritmo es muy sencillo. En una secuencia de datos con un mismo valor consecutivos, son almacenados como un único valor seguido de su recuento, tal y como podéis ver en la imagen superior.

El algoritmo Run Length Encoding es uno de los más antiguos que hay en circulación y es muy utilizado para reducir el tamaño de las imágenes de 8 bits indexadas, y se encuadra dentro de los algoritmos que reducen el tamaño sin perder información.

Para poner un ejemplo, pensemos en una imagen donde sólo predomina el blanco y el negro. Ahí nos encontraremos muchos bits seguidos que hacen referencia al color blanco y otros que hacen referencia al negro, por lo que se podría representar de la forma que hemos indicado anteriormente. Para verlo más explícitamente, pensemos en la siguiente secuencia donde B es blanco y N es negro:

BBBBNNBBBNBNNNNNNBBNNNNNBBB

Esa misma secuencia se podría reescribir de la siguiente forma:

4B2N3B1N1B6N2B5N3B

A continuación os dejamos un vídeo donde se explica el funcionamiento de este algoritmo.