Mcom1 U2 A2 Luhm

Introduccin
Actualmente, el poder de procesamiento de los procesadores se incrementa ms rpido

que la capacidad de almacenamiento y es ms veloz que los anchos de banda de las redes,
porque estos ltimos requieren cambios enormes en las infraestructuras de
telecomunicacin.
Por lo tanto, para compensar esto, es ms comn el procedimiento de reducir el tamao
de los datos al explotar el poder de procesamiento de los procesadores, que incrementar
la capacidad de almacenamiento y de transmisin de datosLa compresin RLE o Run-
length encoding es una forma muy simple de compresin de datos en la que secuencias de
datos con el mismo valor consecutivas son almacenadas como un nico valor ms su
recuento. Esto es ms til en datos que contienen muchas de estas "secuencias"; por
ejemplo, grficos sencillos con reas de color plano, como iconos y logotipos.
La codificacin run-length realiza una compresin de datos sin prdidas y es muy utilizado
en imgenes de 8 bits indexadas (en un principio fue utilizado para imgenes en blanco y
negro). No funciona tan bien en imgenes donde vara constantemente el color de los
pixels como fotografas, aunque JPEG lo utiliza de forma efectiva en los coeficientes que
quedan despus de transformar y cuantificar bloques de imgenes. Posteriormente ha
formado la base de otros sistemas de compresin como por ejemplo el CCITT grupo 3 1D

Es el ms simple y a la vez el ms ineficiente .Lo incluyo aqu porque se podra considerar
que utiliza un diccionario deslizante para predecir el siguiente carcter de la entrada.
Realmente se le considera ya algo "primitivo". Adems hay diferentes formas de
implementarlo, todas ellas patentadas. Busca repeticiones consecutivas de un mismo
smbolo y lo que hace es almacenar en un byte el nmero de esas repeticiones
consecutivas y en el segundo byte el escribe el smbolo. Como ejemplo:

17 48

(el byte 48 se repite 17 veces)Demuestra gran eficiencia cuando hay un alto nmero de
repeticiones consecutivas de un determinado byte. La unidad bsica seran dos bytes, el
primero indica el nmero de veces que se repite el segundo. Bsicamente se utiliza para
crear archivos tipo BMP o PCX sin gradaciones de color. Era utilizado por el ARC, entre
otros.

http://neo.lcc.uma.es/evirtual/cdd/tutorial/presentacion/rle.html
http://es.kioskea.net/contents/714-la-compresion-de-datos

Variable-Length Encoding
En la teora de codificacin el Variable-Length Encoding es un cdigo que se asigna
smbolos de la fuente a un nmero variable de bits.

Los Variable-Length Encoding pueden permitir que las fuentes que se comprimen y
descomprimen con cero error (compresin sin prdida de datos) y aun as ser ledos de
nuevo smbolo a smbolo. Con la estrategia de codificacin del derecho una fuente
independiente e idnticamente distribuidos, se puede comprimir casi arbitrariamente
cerca de su entropa. Esto est en contraste con los mtodos de codificacin de longitud
fija, para lo cual slo es posible la compresin de datos para grandes bloques de datos, y
ningn tipo de compresin ms all del logaritmo del nmero total de posibilidades
vienen con un finito (aunque quiz arbitrariamente pequeo) probabilidad de fracaso.

Variable-Length Encoding los pueden anidarse estrictamente en orden decreciente de
generalidad que los cdigos no singulares, cdigos nicamente descifrables y cdigos de
prefijo . Los cdigos prefijo son siempre nicamente descifrable , y estos a su vez son
siempre no singular :

Los cdigos no singulares

Un cdigo es no singular si cada smbolo de origen se asigna a una cadena de bits no vaca
diferente , es decir, el mapeo de smbolos de la fuente de cadenas de bits es inyectiva .

Por ejemplo, el mapeo M_1 = \ { \ , a \ mapsto 0, b \ mapsto 0, c \ mapsto 1 \, \ } no es no
singular , porque tanto "a" y "b" mapa a la misma cadena de bits " 0 " ; cualquier
extensin de esta asignacin generar una prdida ( sin prdida) de codificacin . Tal
codificacin singular todava puede ser til cuando cierta prdida de informacin es
aceptable (por ejemplo, cuando se utiliza dicho cdigo en audio o de compresin de vdeo
, donde una codificacin con prdida se convierte equivalente a la cuantizacin fuente ) .
Sin embargo , el mapeo m_2 = \ { \ , a \ mapsto 1 , b \ mapsto 011 , c \ mapsto 01110 , d \
mapsto 1110, e \ mapsto 10011 \, \ } es no singular ; su extensin generar una
codificacin sin prdida , que ser til para la transmisin de datos en general ( pero esta
caracterstica no siempre es necesaria ) . Tenga en cuenta que no es necesario para el
cdigo no singular para ser ms compacta que la fuente (y en muchas aplicaciones, un
cdigo ms grande es til , por ejemplo, como una forma de detectar y / o recuperarse de
codificacin o de transmisin de errores , o en aplicaciones de seguridad para proteger
una fuente de manipulacin indetectable ) .

nicamente los cdigos descifrables

Un cdigo es nicamente descifrable si su extensin es no singular. El que un cdigo dado
es nicamente descifrable puede decidirse con el algoritmo Sardinas -Patterson.
El M_3 mapeo = \ { \ , a \ mapsto 0, b \ mapsto 01 , c \ mapsto 011 \, \ } es nicamente
descifrable (esto se puede demostrar examinando el seguimiento establecido despus de
cada cadena de bits de destino en el mapa, ya que cada cadena de bits se termina tan
pronto como vemos un bit 0 que no puede seguir cualquier cdigo existente para crear un
cdigo vlido ya en el mapa, pero sin ambigedades inicia un nuevo cdigo ) .
Consideremos de nuevo el m_2 cdigo de la seccin anterior. Este cdigo, que se basa en
un ejemplo encontrado en , [ 1 ] no es nicamente descifrable , ya que la cadena
011101110011 puede interpretarse como la secuencia de palabras de cdigo 01110 hasta
1110 - 011 , pero tambin como la secuencia de palabras de cdigo 011 - 1 a 011 - . 10011
Dos posibles decodificaciones de esta cadena codificada modo se da por cdb y cario. Sin
embargo, dicho cdigo es til cuando el conjunto de todos los posibles smbolos de la
fuente es completamente conocido y finito, o cuando existen restricciones (por ejemplo,
una sintaxis formal) que determinan si los elementos de origen de esta extensin son
aceptables. Estas restricciones permiten la decodificacin del mensaje original mediante la
comprobacin de cul de los posibles smbolos de la fuente asignada a los mismos
smbolos son vlidos bajo esas restricciones.

Los cdigos prefijo

Un cdigo es un cdigo de prefijo si no hay cadena de bits de destino en el mapeo es un
prefijo de la cadena de bits de destino de un smbolo fuente diferente en la misma
asignacin. Esto significa que los smbolos pueden ser decodificados de forma instantnea
despus de recibir la totalidad de su palabra de cdigo. Otros nombres de uso comn para
este concepto son de cdigo libre de prefijo , cdigo instantneo, o cdigo independiente
del contexto .

Construccin del Cdigo Huffman
En ciencias de la computacin y teora de la informacin, la codificacin Huffman es un
algoritmo usado para compresin de datos. El trmino se refiere al uso de una tabla de
cdigos de longitud variable para codificar un determinado smbolo (como puede ser un
carcter en un archivo), donde la tabla ha sido rellenada de una manera especfica
basndose en la probabilidad estimada de aparicin de cada posible valor de dicho
smbolo. 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 codificacin Huffman usa un mtodo especfico para elegir la representacin de cada
smbolo, que da lugar a un cdigo prefijo (es decir, la cadena de bits que representa a un
smbolo en particular nunca es prefijo de la cadena de bits de un smbolo distinto) que
representa los caracteres ms comunes usando las cadenas de bits ms cortas, y
viceversa. Huffman fue capaz de disear el mtodo de compresin ms eficiente de este
tipo: ninguna representacin alternativa de un conjunto de smbolos de entrada produce
una salida media ms pequea cuando las frecuencias de los smbolos coinciden con las
usadas para crear el cdigo. Posteriormente se encontr un mtodo para llevar esto a
cabo en un tiempo lineal si las probabilidades de los smbolos de entrada (tambin
conocidas como "pesos") estn ordenadas.
Para un grupo de smbolos con una distribucin de probabilidad uniforme y un nmero de
miembros que es potencia de dos, la codificacin Huffman es equivalente a una
codificacin en bloque binaria, por ejemplo, la codificacin ASCII. La codificacin Huffman
es un mtodo para crear cdigos prefijo tan extendido que el trmino "codificacin
Huffman" es ampliamente usado como sinnimo de "cdigo prefijo", incluso cuando dicho
cdigo no se ha producido con el algoritmo de Huffman.
Aunque la codificacin de Huffman es ptima para una codificacin smbolo a smbolo
dada una distribucin de probabilidad, su optimalidad a veces puede verse
accidentalmente exagerada. Por ejemplo, la codificacin aritmtica y la codificacin LZW
normalmente ofrecen mayor capacidad de compresin. Estos dos mtodos pueden
agrupar un nmero arbitrario de smbolos para una codificacin ms eficiente, y en
general se adaptan a las estadsticas de entrada reales. Este ltimo es til cuando las
probabilidades no se conocen de forma precisa o varan significativamente dentro del
flujo de datos.

Fuentes
http://neo.lcc.uma.es/evirtual/cdd/tutorial/presentacion/rle.html
http://es.kioskea.net/contents/714-la-compresion-de-datos

Mcom1 U2 A2 Luhm

Cargado por

Copyright:

Formatos disponibles

Mcom1 U2 A2 Luhm

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Mcom1 U2 A2 Luhm

Cargado por

Copyright:

Formatos disponibles

Introduccin

Actualmente, el poder de procesamiento de los procesadores se incrementa ms rpido

También podría gustarte