Sistemas de Codificación

Código Braille:

Este conocido código, que permite a los ciegos a leer, fue desarrollado por Louis Braille en 1820, y después de haber sido modificado varias veces, todavía se sigue utilizando hoy en día. Hay disponibles muchos libros en Braille en el National Braille Press. El código Braille se compone de grupos (o celdas) de 3 × 2 puntos cada una, con relieve en papel grueso. Cada uno de los 6 puntos de un grupo pueden ser planos o elevados, lo que implica que el contenido de la información de un grupo es equivalente a 6 bits, siendo posibles por ello un total de 2 6 = 64 grupos. Las letras (Tabla 1.1), dígitos y signos de puntuacion más corrientes no requieren los 64 códigos, por lo que los grupos restantes pueden ser utilizados para codificar las palabras comunes como “and, for, of, the y with” y las cadenas de letras más utilizadas, como “ch, gh, sh, th, wh, ed, er, ou y ow”.

Para optimizar códigos: Una letra es mayúscula, si va precedida del signo Mayúscula; los números tienen la misma representación que las 10 primeras letras (1–2–3–4–5–6–7–8–9–0 se corresponden, respectivamente, con a–b–c–d–e–f–g–h–i–j), y deben ir precedidos del signo Número. Puesto que en las primeras letras, la última fila del codigo es siempre “◦◦”, se aprovecha esta circunstancia para representar las fracciones (las dos primeras filas del código del numerador de la fracción son desplazadas hacia abajo). Se pueden ver los signos especiales comentados, así como algunos ejemplos en la Tabla 1.2c.

1.1: (1) hacer una pregunta, (2) es absolutamente necesario, (3) con previo aviso, (4) punto de ebullición caliente, (5) subir, (6) un examen riguroso, (7) exactamente lo mismo, (8) obsequio, (9) calentador de agua, (10) mi opinión personal, (11) recién nacido, (12) aplazado hasta más tarde, (13) sorpresa inesperada, (14) misterios sin resolver.

Comprensión irreversible de texto:

Algunas veces, es aceptable “comprimir” texto, simplemente desechando alguna información. Esto se conoce como compresión irreversible de texto o compactación. El texto descomprimido no es idéntico al original, por lo que estos métodos no son de propósito general; sólo pueden utilizarse en casos especiales. Una secuencia consecutiva de espacios en blanco, puede reemplazarse por un solo espacio. Esto es aceptable en textos literarios y en la mayor parte del código fuente de programas informáticos; pero no debería ser usado cuando el formato de los datos es tabular. En casos extremos, todos los caracteres, excepto letras y espacios, pueden ser despreciados, y se puede convertir todo el texto, a mayúsculas o minúsculas1 , reduciendo así el número de signos a codificar. De esta manera, un texto en inglés estará compuesto por combinaciones de exactamente 27 símbolos, cada uno de los cuales puede ser codificado con 5 bis, en lugar de los 8 usuales. La razón de compresión es de 5/8 = 0,625, que no es mala, pero se puede mejorar.

Compresión del texto Ad hoc:

Si el texto contiene muchos espacios, pero no están agrupados, se pueden eliminar; sus posiciones, se indican entonces mediante una cadena de bits, que contiene un 0 por cada carácter del texto que no es un espacio y un 1 por cada espacio. Por lo tanto, el texto.

Si el número de espacios en blanco es pequeño, la cadena de bits será dispersa y se pueden emplear los métodos de la Sección 8.5 para comprimiría considerablemente. 

Codificación run-lenght:

La idea básica de este método es la siguiente: Si un dato d aparece n veces consecutivas en el flujo de entrada, se cambian las n ocurrencias con el par único nd. Las n apariciones consecutivas de un elemento de datos se llama run length9 de n, y este enfoque para la compresión de datos se llama codificación run-length o RLE. Aplicamos esta primera idea a la compresión de texto y luego a la compresión de imágenes..

Compresión de texto RLE:

El reemplazo exacto de 2.⊔all⊔is⊔too⊔well con 2.⊔a2⊔is⊔t2⊔we2, es ambiguo y no funciona . Claramente, el descompresor debería tener una manera de expresar que el primer 2 es parte del texto, mientras que los demás indican el número de repeticiones de las letras o y l.

Incluso la cadena 2.⊔a2l⊔is⊔t2o⊔we2l, sigue sin resolver este problema (y además no proporciona compresión alguna). Un camino para resolver este problema es preceder cada repetición con un carácter especial de cambio de código (o código de escape). 

Si usamos @ como carácter de cambio de código, entonces la cadena 2.⊔a@2l⊔is⊔t@2o⊔we@2l, puede ser descomprimida sin ambigüedad. Sin embargo, esta cadena es más larga que la original, ya que sustituye dos letras consecutivas, con tres caracteres. 

Tenemos que adoptar la convención de que sólo se reemplacen por un factor de repetición, aquellos grupos compuestos por tres o más repeticiones de un mismo carácter. La Figura 1.6a es un diagrama de flujo, que explica el funcionamiento de un sencillo compresor de texto run-length. Después de leer el primer elemento —CH—, el contador de caracteres es C = 1, por lo que CH se almacena (SC := guarda CH). Los siguientes elementos se comparan con éste (¿SC = CH?), y si son idénticos, se incrementa el contador de repeticiones (R := R + 1).

Cuando se lee un carácter diferente, la operación depende del valor de R. Si es pequeño, se escribe el carácter grabado —SC— en el archivo comprimido (R veces); se actualiza SC con el último carácter leído, y se reinicia el contador (R := 0), para seguir con el siguiente carácter de la cadena. De lo contrario, se escribe el indicador de cambio de código —@—, seguido por el valor de R y el carácter SC; a continuación se pone a cero R, y se guarda el siguiente elemento del flujo de datos a comprimir —en SC—. 

Todo este ciclo se repite hasta procesar todos los datos. La descompresión también es sencilla. Se muestra en la Figura 1.6b. Se explora la secuencia de entrada hasta encontrar el carácter de cambio de código —@— (todos los caracteres, hasta la aparición de dicho símbolo, se escriben en la salida); inmediatamente después, se lee el contador de repeticiones —n— y el carácter a repetir, escribiendolo en la cadena de salida —n veces—; este proceso se repite hasta que no haya más datos en la entrada.

Codificación relativa:

Esta es otra variante, a veces llamada diferenciación ([Gottlieb et al. 75]). Se utiliza cuando los datos a comprimir, están formados por una serie de números que no difieren en mucho entre sí (e.g., en la telemetría); o bien cuando se componen de cadenas similares. El último caso, se utiliza en la compresión de datos para envío por fax descrita en la Sección 2.13 y también en la compresión LZW (Sección 3.12.4). En la telemetría, se utiliza un detector para recopilar datos a determinados intervalos y transmitirlos a una central para su posterior procesamiento. 

Un ejemplo, es el estudio de la temperatura de un lugar, en el que se realizan mediciones cada hora. Dos temperaturas sucesivas, no difieren mucho normalmente, por lo que el sensor necesita enviar sólo la primera de ellas, seguida por las diferencias. De este modo, la secuencia de temperaturas: 70, 71, 72,5, 73,1,. . . , puede representarse con esta otra: 70, 1, 1,5, 0,6,. . . .. Debido a que las diferencias son pequeñas, se pueden utilizar menos bits para guardar cada número, lo que permite la compresión de los datos.