compression - por - son métodos de compresión de datos digitales html
¿Por qué los datos se pueden comprimir una sola vez? (10)
El problema de la compresión sin pérdida es básicamente, ¿cómo se puede expresar esta información de manera más sucinta? Por ejemplo, podría observar que en el texto anterior, el carácter "e" suele ir seguido de un espacio y un carácter sustituto y raro de ese patrón. De manera similar, un espacio seguido de una "t" podría ser reemplazado por una secuencia diferente y poco común, y la siguiente secuencia de dos "s": es lo mismo podría acortarse. Cuando UrunOutOf commN se sustituye, Ucann no puede continuar con ninguna otra manera (o Umay tiene que cambiar para cambiar la estrategia de sustitución de patrones).
Por lo tanto, el proceso de compresión toma una parte de los datos binarios A y genera una parte más pequeña de los datos binarios B ¿Qué características de B hacen que no pueda pasar por este proceso nuevamente?
En primer lugar, esto solo se aplica a la compresión sin pérdida. La compresión con pérdida (como jpg), teóricamente se puede aplicar una y otra vez. Por supuesto, la calidad del material comprimido cae cada vez.
Para la compresión sin pérdida, podemos pensar en la compresión como una rutina que toma algunos datos y la transforma a otra forma (A-> B). Como no tiene pérdidas, debemos poder tomar B e ir A <-B. Si seguimos esto, significa que si tomamos cada secuencia de 4 bits (16 patrones) y los comprimimos, debemos obtener 16 resultados diferentes. Eso significa que en promedio, no se realizó ninguna compresión!
La compresión aprovecha el hecho de que, para ciertos tipos de datos, algunas secuencias de datos son menos comunes. Estas formas menos comunes se harán más grandes cuando se comprimen. Las formas más comunes para las que hemos elegido nuestro esquema se volverán más pequeñas . En promedio, los mensajes son del mismo tamaño o más grandes.
Yendo un paso más allá, si repetimos la compresión del mismo mensaje, en promedio no cambiará de tamaño (nuevamente, este es el mejor caso).
La compresión funciona reconociendo patrones y diciendo "este patrón está aquí, aquí y aquí, así que lo guardaré una vez y recordaré colocarlo allí y allá cuando me descomprima".
La mayoría de los patrones quedarían atrapados en la primera compresión. Puede lograr una mayor compresión después de la compresión, pero ... no quedan muchos patrones.
Los datos tienen algo que se llama entropía: la cantidad de información nueva que proporciona cada bit nuevo. Por ejemplo, 10101010101010101010 tiene una entropía baja porque no necesita el siguiente bit para saber qué viene después. Un algoritmo de compresión perfecto se comprimiría a la máxima entropía, por lo que cada bit proporciona información y, por lo tanto, no se puede eliminar, lo que hace que el tamaño sea mínimo.
No es cierto que los datos que ya están comprimidos no puedan comprimirse nuevamente. Si toma un archivo de 1 millón de ceros y lo comprime usando gzip , el archivo comprimido resultante es de 1010 bytes. Si vuelve a comprimir el archivo comprimido, se reducirá aún más a solo 75 bytes.
$ python >>> f = open(''0.txt'', ''w'') >>> f.write(''0''*1000000) >>> f.close() >>> $ wc -c 0.txt 1000000 0.txt $ gzip 0.txt $ wc -c 0.txt.gz 1010 0.txt.gz $ mv 0.txt.gz 0.txt $ gzip 0.txt $ wc -c 0.txt.gz 75 0.txt.gz
La razón por la que es poco probable que la compresión funcione dos veces es porque el proceso de compresión elimina la redundancia. Cuando tiene menos redundancia, es más difícil comprimir aún más el archivo.
No es que se pueda comprimir solo una vez, es que hay un tamaño mínimo para que pueda comprimir cualquier dato antes de comenzar a perder fragmentos (como lo hace con un archivo jpg o MP3 de baja calidad). La mayoría de los algoritmos de compresión en estos días son lo suficientemente buenos como para que una sola pasada te permita obtener un porcentaje del mismo por lo que una segunda vez no vale la pena sino que no es posible.
Para entender el tamaño mínimo sin leer demasiada teoría, piense en una pregunta con dos respuestas posibles Sí y No. Lo más pequeño que puede hacer este resultado es un bit único donde 0 = No y 1 = Sí (o viceversa). Incluso eso ha hecho un montón de suposiciones (que la persona que recibe los datos ya comprende esta codificación, por ejemplo).
En un nivel más complejo, lo mismo es cierto para todos los demás datos. En una situación en la que tenga ocho respuestas posibles, todas igualmente probables (esto es importante), el tamaño mínimo es de tres bits: el número más pequeño de bits para permitirle ocho opciones (000, 001, 010, 011, 100, 101, 110). , 111).
Hay algunas cosas inteligentes que puede hacer para reducirlo un poco en ciertas circunstancias (por ejemplo, utiliza un número menor de bits para respuestas muy comunes a costa de necesitar más de lo que podría ser necesario para otros menos comunes pero a un promedio general más bajo) ) pero en última instancia, hay una cantidad mínima de almacenamiento necesaria para contener la información.
Para cualquier número N, hay 2 ^ (N + 1) -1 diferentes archivos de entrada posibles de longitud N bits o más cortos. Si cada archivo de entrada diferente producirá un archivo de salida diferente, entonces para cada archivo de entrada posible de longitud k que pueda reducirse a una longitud más corta, debe haber al menos un archivo más corto que se alargue.
Para una respuesta muy académica a esta pregunta, eche un vistazo a Information Etropy ! Sin embargo, si eres como yo, el artículo hará que te duela la cabeza.
Una respuesta más simple: suponga que podría comprimir una y otra vez, digamos por un factor de 10 cada vez. Podría comprimir Wikipedia a un gigabyte, luego a 100M, luego a 10M ... haga esto 9 veces y estará en un byte. Si toda la información en Wikipedia se pudiera comprimir en un byte, la gente no habría necesitado escribirla, podría haber expandido uno de los 256 bytes posibles, uno de ellos habría sido el contenido de Wikipedia :)
Una respuesta un poco más sensata: el texto es redundante : hay información en esos bytes que podrían expresarse con mayor precisión. El artículo de Wikipedia menciona el hecho de que ''q'' es seguido casi siempre por ''u'', por ejemplo. ''E'' ocurre más a menudo que ''T''. Etcétera. De manera similar, en un programa, a menudo se encuentra 0 con más frecuencia que cualquier otro número. Esta consistencia puede ser explotada y ''exprimida''. Pero una vez que has hecho eso una vez, la redundancia original se ha ido. El archivo comprimido apenas tiene más ''bits desperdiciados''.
Puede comprimir los datos tanto como desee, pero el efecto podría no ser lo que desea. Después del primer nivel de compresión, si ejecuta el mismo algoritmo en él, probablemente no se comprima lo suficiente como para que valga la pena.
Piensa en esto, aquí están tus datos:
1001 0011 1110 0100 0011 1001
Usaré un compresor inventado para tokenizar por nybble (4 bits) los datos como tales:
si es 1001, comprímalo como 101, ya que no nybble comienza con 101 y 1001 ocurre dos veces si 0011, comprímalo como 110 ya que no nybble comienza con 110 y 0011 ocurre dos veces
Después de la compresión:
101 110 1110 0100 110 101 o 1011 1011 1001 0011 0101
En realidad, esto no funcionaría en el mundo real, pero como puede imaginar, podría comprimirlo nuevamente ya que aún son datos binarios.
La siguiente compresión hace esto:
si 1011, comprime como 111
Después de la compresión: 111 111 1001 0011 0101 o 1111 1110 0100 1101 01
Pero como puede ver, ya no hay duplicados de nybbles, por lo que el compresor que utilicé no tendría nada más que comprimir.
Una vez más, esto no es un compresor real, solo una manera fácil de entender el concepto.
Tome una hoja de papel y dóblela: la ha comprimido en un 50%. Ahora hazlo de nuevo y sigue intentándolo. ¿Observe cómo se hace cada vez más difícil y en algún momento debe detenerse?
La compresión de datos sufre de los mismos límites. Claro, puede comprimirlo nuevamente y puede ahorrar un poco más de espacio, pero es un claro ejemplo de rendimientos decrecientes: cada nuevo intento de compresión requiere más esfuerzo para lograr mejoras marginales.