Capitulo 15 RESUMEN



COMPRESION DE DATOS

La compresión de datos puede reducir la cantidad de datos enviados o almacenados al eliminar parcialmente la redundancia inherente, esta se crea cuando producimos datos. A través de la compresión de datos, hacemos la transmisión y el almacenaje más eficientes, y al mismo tiempo conservamos la integridad de los datos hasta cierto punto.
La comprensión de datossignifica el envió o almacenamiento de un número pequeño de bits.
Compresión sin perdida

La compresión sin perdida en la compresión de datos sin perdida, se conserva la integridad de los datos. Los datos originales y los datos después de la compresión y descompresión son exactamente iguales. Los datos redundantes se eliminan en la compresión y se añaden durante la descompresión.
Para no perder ni unbit de datos se utilizan 3 métodos: la codificación de longitud de ejecución, la codificación de Huffman y el algoritmo de Lempel Ziv.
El segundo es el más simple, la cual puede utilizarse para comprimir datos hechos de cualquier combinación de símbolos.
La idea general que este método sustenta es remplazar ocurrencias de un símbolo repetidas y consecutivas por una ocurrencia del símbolo y elnúmero de ocurrencias.
Este método puede ser aún más eficiente si los datos utilizan solo dos símbolos ( por ejemplo el 0 y el 1) en su patrón de bits y un símbolo es más frecuente que el otro.
En la codificación de Huffman, usted asigna códigos más cortos a símbolos que ocurren con mayor frecuencia y códigos más largos a aquellos que ocurren con menor frecuencia. Por ejemplo, imagine que tieneun archivo de texto que utiliza solo 5 caracteres ( a, b , c , d , e )


Frecuencia de caracteres
Una vez el establecido el peso de cada carácter, se construye un árbol con base en aquellos valores. Se siguen tres pasos básicos.
1. Se pone todo el conjunto de caracteres en una fila
2. Se encuentran los dos nodos dentro de los pesos más pequeños y se juntan para formar un tercer nodo, el cualdé como resultado un árbol simple de dos niveles
3. Repita el paso 2 hasta que todos los nodos, de cada nivel , se combinen en un solo árbol.
Una vez el árbol este completo, utilícelo para asignar códigos a cada carácter. Primero asigne un valor de 1 bit a cada rama.
Observamos que movimos los nodos de la hoja para hacer que el árbol pareciera un árbol binario.
Codificación

Primero hayque observar que hay un sentido de compresión incluso en este pequeño código ficticio.
Si usted quiere enviar el texto sin utilizar la codificación de Huffman, necesita asignar un código de 3 bits a cada carácter. Enviara más bits de esta manera que si utilizara el método de Huffman.
Segundo hay que tener en cuenta que la belleza de la codificación Huffman radica en que ningún código es elprefijo de otro código.
Decodificación.

Cuando el receptor recibe los primeros dos bits no tiene que esperar al siguiente bit para tomar la decisión. Ningún bit es el prefijo de otro bit.
Esta es la razón por la cual el código de Huffman se llama código instantáneo, el decodificador puede decodificar inequívocamente los bits al instante.

Codificación de Lempel Ziv

La codificación de LempelZiv es un ejemplo de categoría de algoritmos llamada codificación basada en el diccionario.
La idea es crear un diccionario de cadenas utilizado durante la sesión de comunicación. si tanto el emisor como el receptor tienen una copia del diccionario, entonces las cadenas ya encontradas pueden sustituirse por su índice en el diccionario para reducir la cantidad de información transmitida.
Unalgoritmo práctico que utiliza la idea de la codificación adaptativa basada en diccionario es el algoritmo de Lempezl Ziv. Este algoritmo ha pasado por varias versiones. Presentamos la idea básica del algoritmo como un ejemplo pero no ahondamos en los detalles de diferentes versiones e implementaciones.

Compresión en cadena

En esta fase existe la construcción de un diccionario indexado y la...