Algoritmos de compresion

Solo disponible en BuenasTareas
  • Páginas : 6 (1327 palabras )
  • Descarga(s) : 0
  • Publicado : 31 de enero de 2011
Leer documento completo
Vista previa del texto
Un ejemplo simple del algoritmo LZW de compresión
Dado que el algoritmo sirve para comprimir cualquier secuencia de bits, independientemente de si es texto o cualquier otro tipo de información, el ejemplo a continuación no ha sido traducido del original en inglés. En él se supone que los textos a comprimir se componen solamente de letras mayúsculas sin espacios, para lo cual bastan (en inglés)26 códigos, del 1 al 26, para las mayúsculas más un código (en este caso se ha adoptado el cero, aunque en la práctica el 0 es un carácter válido) para representar el fin de archivo, que se ha representado gráficamente por el símbolo #. El texto a comprimir es:
-------------------------------------------------
TOBEORNOTTOBEORTOBEORNOT#
y el proceso de compresión quedarepresentado por la tabla siguiente. Para interpretarla, se sugiere ignorar la representación binaria, que se incluye simplemente para contabilizar el tamaño del archivo de salida. Los códigos del 1 al 26 se corresponden con caracteres simples 1 = A, 2 = B, ... 26 = Z y 27 = "fin de archivo". Del 28 en adelante cada código representa más de un carácter.
-------------------------------------------------Carácter: Código emitido Entrada en el diccionario:
-------------------------------------------------
(salida):
-------------------------------------------------

-------------------------------------------------
T 20 = 10100
-------------------------------------------------
O 15= 01111 28: TO
-------------------------------------------------
B 2 = 00010 29: OB
-------------------------------------------------
E 5 = 00101 30: BE
-------------------------------------------------
O 15 = 01111 31: EO <--- se agotaron los códigos de 5 bits-------------------------------------------------
R 18 = 010010 32: OR <--- se comienza a usar códigos de 6 bits
-------------------------------------------------
N 14 = 001110 33: RN
-------------------------------------------------
O 15 = 001111 34: NO
-------------------------------------------------
T20 = 010100 35: OT
-------------------------------------------------
TO 28 = 011100 36: TT
-------------------------------------------------
BE 30 = 011110 37: TOB
-------------------------------------------------
OR 32 = 100000 38: BEO
-------------------------------------------------TOB 37 = 100101 39: ORT
-------------------------------------------------
EO 31 = 011111 40: TOBE
-------------------------------------------------
RN 33 = 100001 41: EOR
-------------------------------------------------
OT 35 = 100011 42: RNO-------------------------------------------------
# 0 = 000000 43: OT#

Codificacion Huffman
En ciencias de la computación y teoría de la información, la codificación Huffman es un algoritmo usado para compresión de datos. El término se refiere al uso de una tabla de códigos de longitud variable para codificar un determinado símbolo (como puede ser un caracter en un archivo), donde la tabla ha sidorellenada de una manera específica basándose en la probabilidad estimada de aparición de cada posible valor de dicho símbolo. Fue desarrollado por David A. Huffman mientras era estudiante de doctorado en el MIT, y publicado en "A Method for the Construction of Minimum-Redundancy Codes".
La técnica utilizada es el propio algoritmo de Huffman. Consiste en la creación de un árbol binario en el que se...
tracking img