Hace mucho tiempo leí un artículo de periódico en el que un profesor de algún tipo dijo que en el futuro podremos comprimir datos a solo dos bits (o algo así).
Por supuesto, esto no es correcto (y podría ser que mi memoria de lo que él dijo exactamente no es correcta). Es comprensible que no sea práctico comprimir una cadena de 0 y 1 a solo dos bits porque (incluso si fuera técnicamente posible), demasiados tipos diferentes de cadenas terminarían comprimiéndose a los mismos dos bits (ya que solo tenemos '01 'y' 10 'para elegir).
De todos modos, esto me hizo pensar en la viabilidad de comprimir una cadena de longitud arbitraria de 0 y 1 de acuerdo con algún esquema. Para este tipo de cadena, ¿existe una relación conocida entre la longitud de la cadena (la relación entre 0 y 1 probablemente no importa) y la compresión máxima?
En otras palabras, ¿hay alguna manera de determinar cuál es la longitud mínima (la más pequeña posible) a la que se puede comprimir una cadena de 0 y 1?
(Aquí estoy interesado en la compresión matemática máxima, no en lo que actualmente es técnicamente posible).
fuente
Respuestas:
La complejidad de Kolmogorov es un enfoque para formalizar esto matemáticamente. Desafortunadamente, calcular la complejidad de Kolmogorov de una cadena es un problema indiscutible. Ver también: Aproximación de la complejidad de Kolmogorov .
Es posible obtener mejores resultados si analiza la fuente de la cadena en lugar de la cadena en sí . En otras palabras, a menudo la fuente puede modelarse como un proceso probabilístico, que elige aleatoriamente una cadena de alguna manera, de acuerdo con alguna distribución. La entropía de esa distribución le indica la mejor compresión matemáticamente posible (hasta una pequeña constante aditiva).
Sobre la imposibilidad de una compresión perfecta, también puede interesarle lo siguiente.
fuente
Además, en muchos casos no nos importa la reconstrucción exacta . Esto se llama compresión con pérdida , y es cómo se comprimen la música y los videos. En este caso, el límite inferior indicado anteriormente no se cumple, pero puede encontrar otros límites inferiores.
fuente
Aquí hay un esquema simple que puede comprimir cadenas de bits arbitrarias sin pérdidas, con el resultado más pequeño siendo solo un bit:
SI la cadena es una coincidencia idéntica para la grabación de la novena sinfonía, cuarto movimiento de Beethoven, en formato AAC que se almacena en el disco duro de mi computadora, entonces la salida es un solo bit '0'.
SI la cadena es otra cosa, la salida es un solo bit '1', seguido de una copia idéntica de la cadena original.
Este esquema reduce una entrada posible a exactamente un bit y aumenta la longitud de todas las demás entradas. Hay un principio general: si un algoritmo de compresión puede asignar cualquier cadena de entrada a una cadena comprimida, y hay un algoritmo de descompresión coincidente que asigna cualquier cadena comprimida a la cadena original, y el algoritmo de compresión asigna cualquier entrada a una cadena más corta, entonces debe asignar algunas cadenas de entrada a cadenas más largas.
fuente
Para cada esquema de compresión que se te ocurra, es posible producir datos que no serán comprimibles por él. Entonces, incluso si su esquema de compresión es muy eficiente con algunos tipos de datos, nunca se comprimirá de manera consistente a una cierta proporción.
La forma de producir un ejemplo de datos no comprimibles para un algoritmo de compresión particular es simple: tomar cualquier tipo de datos y ejecutarlos a través del algoritmo de compresión repetidamente, hasta que el tamaño ya no disminuya.
Entonces, la compresibilidad de una cadena de bits no es realmente una función de la longitud de la cadena, sino de su complejidad en relación con el algoritmo de compresión.
fuente
Existe un algoritmo interesante y completamente diferente que utilizan los sistemas de respaldo empresariales. La idea es que si tiene una compañía con 10,000 computadoras, muchas de estas computadoras contendrán muchos archivos idénticos. Por ejemplo, un correo electrónico enviado a todos en la empresa podría terminar como un archivo idéntico en cada disco duro.
Por lo tanto, un sistema de copia de seguridad que intenta hacer una copia de seguridad de un archivo obviamente debe intentar comprimir el archivo para ahorrar espacio, pero primero el sistema de copia de seguridad comprueba si ya se ha guardado un archivo absolutamente idéntico. Entonces, en lugar de hacer una copia de seguridad de todo , todo lo que hace el sistema de copia de seguridad es, por ejemplo, recordar que tiene el número de archivo 1,487,578 en el sistema de copia de seguridad en su disco duro.
Esto es especialmente eficiente, por ejemplo, cuando 10,000 usuarios tienen un sistema operativo y aplicaciones idénticos instalados. Para usuarios individuales no es muy útil en absoluto.
fuente