algorithm - data - lossless compression
En términos simples, ¿cómo se implementa comúnmente la compresión? (5)
Así que últimamente he estado pensando en cómo podría implementarse la compresión, y lo que he postulado hasta ahora es que podría estar usando un tipo de HashTable de claves de ''firma de byte'' con valores de ubicación de memoria donde debería estar esa ''firma de byte'' Sustituido en la expansión del elemento comprimido en cuestión.
¿Está esto lejos de la verdad?
¿Cómo se implementa típicamente la compresión? No se necesita una página de respuesta, solo en términos simples está bien.
Compruebe en.wikipedia.org/wiki/Data_compression página wiki ...
Los algoritmos de compresión sin pérdida usualmente explotan la redundancia estadística de tal manera que representan los datos del remitente de manera más concisa y sin errores. La compresión sin pérdida es posible porque la mayoría de los datos del mundo real tienen redundancia estadística. Por ejemplo, en el texto en inglés, la letra ''e'' es mucho más común que la letra ''z'', y la probabilidad de que la letra ''q'' vaya seguida de la letra ''z'' es muy pequeña.
Otro tipo de compresión, llamada compresión de datos con pérdida o codificación perceptiva, es posible si se acepta cierta pérdida de fidelidad. En general, una compresión de datos con pérdida se guiará por la investigación sobre cómo las personas perciben los datos en cuestión. Por ejemplo, el ojo humano es más sensible a las variaciones sutiles en la luminancia que a las variaciones en el color. La compresión de imágenes JPEG funciona en parte al "redondear" parte de esta información menos importante. La compresión de datos con pérdida proporciona una forma de obtener la mejor fidelidad para una cantidad determinada de compresión. En algunos casos, se desea una compresión transparente (imperceptible); en otros casos, la fidelidad se sacrifica para reducir la cantidad de datos tanto como sea posible.
Los esquemas de compresión sin pérdida son reversibles, por lo que los datos originales se pueden reconstruir, mientras que los esquemas con pérdida aceptan cierta pérdida de datos para lograr una compresión más alta.
Sin embargo, los algoritmos de compresión de datos sin pérdida siempre fallarán para comprimir algunos archivos; de hecho, cualquier algoritmo de compresión necesariamente no podrá comprimir ningún dato que no contenga patrones discernibles. Por lo tanto, los intentos de comprimir los datos que ya se han comprimido (los archivos de texto generalmente se pueden comprimir más después de ser comprimidos, debido a la menor cantidad de símbolos), dan como resultado una expansión, al igual que los intentos de comprimir todos los datos, excepto los más cifrados.
En la práctica, la compresión de datos con pérdida también llegará a un punto donde la compresión de nuevo no funcionará, aunque un algoritmo extremadamente con pérdida, como, por ejemplo, la eliminación del último byte de un archivo, siempre comprimirá un archivo hasta el punto en que esté vacío. .
Un ejemplo de compresión sin pérdida frente a pérdida es la siguiente cadena:
25.888888888Esta cadena se puede comprimir como:
25.[9]8Interpretada como "veinticinco punto 9 ochos", la cadena original se recrea perfectamente, solo se escribe en una forma más pequeña. En un sistema con pérdidas, utilizando
26en su lugar, los datos originales se pierden, en beneficio de un tamaño de archivo más pequeño.
En términos MUY simples, una forma común de compresión es un http://en.wikipedia.org/wiki/Dictionary_coder . Esto implica reemplazar cadenas repetidas más largas por otras más cortas.
Por ejemplo, si tiene un archivo que se parece a esto:
"Monday Night","Baseball","7:00pm"
"Tuesday Night","Baseball","7:00pm"
"Monday Night","Softball","8:00pm"
"Monday Night","Softball","8:00pm"
"Monday Night","Baseball","5:00pm"
Serían aproximadamente 150 caracteres, pero si realizas una sustitución simple de la siguiente manera: A = "Lunes por la noche", B = "Martes por la noche", C = "Béisbol", D = "Softball", E = "7: 00pm ", F =" 8:00 pm ", G = 5: 00pm"
Entonces el mismo contenido podría ser codificado como:
A,C,E
B,C,E
A,D,F
A,D,F
A,C,G
Usando en 25 caracteres! Un observador inteligente también podría ver cómo reducir esto fácilmente a 15 caracteres si asumimos algunas cosas más sobre el formato del archivo. Obviamente, existe la sobrecarga de la clave de sustitución, pero a menudo los archivos muy grandes tienen muchas de estas sustituciones. Esta puede ser una forma muy eficiente de comprimir archivos grandes o estructuras de datos y aún así permitir que sean legibles para los humanos.
Los algoritmos de compresión intentan encontrar subsecuencias repetidas para reemplazarlos con una representación más corta.
Tomemos la cadena de 25 bytes de largo, Blah blah blah blah blah! (200 bits) de una explicación del algoritmo de desinflado, por ejemplo.
Enfoque ingenuo
Un enfoque ingenuo sería codificar cada carácter con una palabra clave de la misma longitud. Tenemos 7 caracteres diferentes y, por lo tanto, necesitamos códigos con la longitud de ceil(ld(7)) = 3 . Nuestras palabras de código pueden verse así:
000 → "B"
001 → "l"
010 → "a"
011 → "h"
100 → " "
101 → "b"
110 → "!"
111 → not used
Ahora podemos codificar nuestra cadena de la siguiente manera:
000 001 010 011 100 101 001 010 011 100 101 001 010 011 100 101 001 010 110
B l a h _ b l a h _ b l a h _ b l a !
Eso solo necesitaría 25 · 3 bits = 75 bits para la palabra codificada más 7 · 8 bits = 56 bits para el diccionario, por lo tanto, 131 bits (65.5%)
O para secuencias:
00 → "lah b"
01 → "B"
10 → "lah!"
11 → not used
La palabra codificada:
01 00 00 00 00 10
B lah b lah b lah b lah b lah!
Ahora solo necesitamos 6 · 2 bits = 12 bits para la palabra codificada y 10 · 8 bits = 80 bits más 3 · 8 bits = 24 bits para la longitud de cada palabra, por lo tanto, 116 bits (58.0%).
Código de Huffman
El código de Huffman se usa para codificar caracteres / subcadenas más frecuentes con un código más corto que los menos frecuentes:
5 × "l", "a", "h"
4 × " ", "b"
1 × "B", "!"
// or for sequences
4 × "lah b"
1 × "B", "lah!"
Un posible código de Huffman para eso es:
0 → "l"
10 → "a"
110 → "h"
1110 → " "
11110 → "b"
111110 → "B"
111111 → "!"
O para secuencias:
0 → "lah b"
10 → "B"
11 → "lah!"
Ahora nuestro Blah blah blah blah blah! se puede codificar para:
111110 0 10 110 1110 11110 0 10 110 1110 11110 0 10 110 1110 11110 0 10 110 1110 11110 0 10 110 111111
B l a h _ b l a h _ b l a h _ b l a h _ b l a h !
O para secuencias:
10 0 0 0 0 11
B lah b lah b lah b lah b lah!
Ahora, el primer código solo necesita 78 u 8 bits en lugar de 25 · 8 = 200 bits como lo ha hecho nuestra cadena inicial. Pero todavía tenemos que agregar el diccionario donde se almacenan nuestros personajes / secuencias. Para nuestro ejemplo por carácter necesitaríamos 7 bytes adicionales (7 · 8 bits = 56 bits) y nuestro ejemplo por secuencia necesitaría nuevamente 7 bytes más 3 bytes para la longitud de cada secuencia (por lo tanto, 59 bits). Eso resultaría en:
56 + 78 = 134 bit (67.0%)
59 + 8 = 67 bit (33.5%)
Los números reales pueden no ser correctos. Por favor, siéntase libre de editar / corregirlo.
Los algoritmos de compresión sin pérdida traducen cada entrada posible en salidas distintas, de tal manera que las entradas más comunes se traducen en salidas más cortas. Es matemáticamente imposible comprimir todas las entradas posibles; de lo contrario, tendrías varias entradas A y B comprimidas en la misma forma, de modo que cuando lo descomprimas, ¿regresas a A o regresas a B? En la práctica, la información más útil tiene cierta redundancia y esta redundancia se ajusta a ciertos patrones; por lo tanto, los datos pueden comprimirse de manera útil porque los casos que se expanden cuando los comprimes no surgen naturalmente.
La compresión con pérdida, por ejemplo, la que se usa en la compresión JPEG o MP3, funciona al aproximar los datos de entrada mediante una señal que puede expresarse en menos bits que la original. Cuando lo descomprimes, no obtienes el original, pero por lo general obtienes algo lo suficientemente cerca.