Codificación de bytes pares

La codificación de bytes pares es un forma simple de comprimir datos. Consiste en reemplazar los pares de bytes más comunes por un byte que no esté presente en los datos originales. Se requiere de una tabla de «emplazamiento» o «reconstrucción» que contenga los pares de bytes originales y el que los remplaza.

Algoritmo

Supóngase que se debe codificar el siguiente texto:

aaabaaabac

El par "aa", que ocurre con frecuencia en el texto, es remplazado por un byte que no es usado en el texto, por ejemplo "Z". Así, en la tabla de reconstrucción está:

Z $\longleftarrow$ aa

Y el texto, entonces:

ZabZabac

El par "Za" ocurre con frecuencia, por lo que tendrá que ser remplazado con un byte que no sea usado en el texto, por ejemplo "Y" (en este caso "Za" puede ser remplazada por "Z", siempre que cada ocurrencia de "Z" sea posteriormente remplazada). La tabla de reconstrucción es entonces:

Z $\longleftarrow$ aa Y $\longleftarrow$ Za

Y el texto:

YbYbac

Otra vez más, se remplaza el byte más frecuente:

Z $\longleftarrow$ aa Y $\longleftarrow$ Za X $\longleftarrow$ Yb

Y el texto:

XXac

Este texto no debe ser recomprimido con el mismo método, ya que no hay un par de bytes que se repitan más de una vez. En el caso de que se remplace XX por X se estaría aumentando el tamaño del archivo en 2 bytes de más. Para descomprimir el texto simplemente se remplazan los pares de bytes en orden inverso.

• Datos: Q5776051