Ir al contenido

¿Existe el compresor perfecto?

Ante el problema de enviar por mail archivos algo pesados, mayores a los que los sistemas de correo permiten enviar, es común intentar “comprimir” esos archivos para así hacerlos más “livianos” y lograr nuestro propósito. A veces nos pasa que son tan pesados que no hay forma de enviarlos aún comprimidos, ya que no quedan lo suficientemente reducidos. Alguien me dijo alguna vez: “bueno, ¿por qué no los comprimís otra vez?” Interesante…

¿Qué es comprimir?

Después de todo, ¿qué significa comprimir un archivo digital? Para la mayoría de las personas, la palabra comprimir tiene un claro significado mecánico, y tiende a imaginar que un archivo puede “comprimirse” en el mismo sentido que uno “comprime” un abrigo para que entre de una buena vez en el placard. Claro que un archivo no es algo “plástico” (ni siquiera es una cosa sólida) que uno pueda apretar, a pesar de lo cual uno de los programas más populares que usamos para ello tiene por ícono una pequeña prensa. Así que… ¿qué le pasa a un archivo cuando se comprime? En pocas palabras, se trata de guardar la misma información utilizando menos bits que el archivo original, mediante un proceso reversible que me permita más tarde recuperar ese archivo original. La razón que hace esto posible es otra cuestión; por el momento vayamos a nuestro tema.

Uno puede legítimamente sospechar que el proceso de compresión no puede repetirse indefinidamente logrando siempre comprimir más en cada paso; si así fuera, podría reducir cualquier archivo a unos pocos bits. Sería genial tener todas las imágenes, páginas web, videos y música que existen en internet en un pen drive… Por otra parte, si fuera posible alguien lo habría hecho ya; como nadie lo hizo, debe haber una imposibilidad. Sabemos que hay muchos métodos (algoritmos) de compresión disponibles: algunos generales que sirven para cualquier tipo de archivo, como ZIP, RAR, etc., mientras que otros son específicos para cierto tipo de contenido (MPEG para video, FLAC y MP3 para audio). Casi todos ellos tienen la posibilidad de elegir el grado de compresión, por lo cual podemos probar con varios ajustes y quedarnos con el que mejor comprime. En cualquier caso, comprimido ya el archivo, ¿qué pasa si lo comprimimos otra vez?

Segundas partes nunca fueron buenas…

Para nuestra sorpresa, la segunda compresión no sólo no reduce el tamaño del archivo, sino que lo aumenta. La razón es que un método de compresión bien diseñado debe ser capaz de encontrar una mínima secuencia de bits a partir de la cual el archivo original puede reconstruirse; una vez encontrada debe “empaquetar” esta secuencia en el archivo comprimido, pero además debe incluir otros datos, por ejemplo el nombre del archivo original, su fecha de creación o modificación, etc., es decir sus metadatos. Tenemos entonces que

Archivo comprimido = Secuencia mínima de bits del archivo original + metadatos

Luego, una segunda compresión nos daría

Segundo archivo comprimido = (Secuencia mínima de bits del archivo original + metadatos) + metadatos

lo que muestra claramente que este segundo archivo comprimido tendrá un tamaño superior al primero. El aumento es relativamente pequeño, ya que los metadatos suelen ser una ínfima cantidad de datos comparados con el archivo original. En el siguiente experimento tomé un archivo Photoshop .psd (que suelen comprimir bien, es decir, la primera compresión logra una buena reducción) y lo sometí a compresiones sucesivas. Este es el resultado:

ArchivoTamañoCompresión relativa al anterior
Original22.404.024 bytes-
Primera compresión14.925.081bytes-33%
Segunda compresión14.928.614 bytes+0,02%
Tercera compresión14.933.345 bytes+0,03%

Claro que aquí la diferencia es pequeña, poco más de 3 kB entre la primera y segunda compresión, pero los archivos vueltos a comprimir efectivamente aumentan su tamaño.

Uno podría objetar que la culpa la tienen los metadatos. En parte sí, pero si los omitiéramos a lo sumo lograríamos que el tamaño de archivo se mantuviera constante, no logrando ninguna compresión efectiva.

¿Es posible crear un compresor perfecto?

Lo notable de este asunto es que, por bueno que sea el método de compresión elegido, siempre habrá un archivo que ese método no pueda comprimir (en el ejemplo mencionado ya encontré uno; basta tomar como “archivo original” el primer archivo comprimido; si le quito la extensión, para que nadie sospeche que ya está “comprimido”,  y se lo doy a otra persona para que lo comprima utilizando el mismo método, le pasará lo que a mí: obtendrá un archivo comprimido más grande). Esto sugiere que no es posible diseñar un compresor que comprima cualquier archivo. Esta drástica afirmación puede demostrarse: los invito a seguirme.

Como dijimos, comprimir un archivo significa encontrar una representación del mismo que utilice menos bits. Supongamos un archivo de n bits de tamaño; comprimirlo significa crear otro que pueda revertirse al original y que tenga menos de n bits. Planteado así, un método de compresión cualquiera equivale a establecer una relación entre todos los archivos de hasta n bits (que llamaríamos el conjunto A de los archivos originales) y todos los archivos de menos de n bits (que sería el conjunto B de todos los archivos comprimidos posibles a partir de A). Nuestra condición de que el método sea reversible implica que cada elemento del primer conjunto tiene uno y sólo un representante en el otro; de esta forma, dado un archivo comprimido, siempre podremos establecer cuál es el archivo original que le dio origen.

A-B
Un método de compresión visto como un “mapeo” entre los archivos “originales” (A) y los archivos comprimidos (B). Necesitamos que en B haya por lo menos tantos elementos como en A.

Hasta acá todo bien, pero ¿es posible hacer esto siempre? Para saberlo es necesario que en el conjunto B haya (por lo menos) tantos elementos como en el A. Así que vamos a contarlos. Para simplificar, limitémonos a archivos de tamaño fijo. Un archivo de n bits se puede crear de 2n maneras diferentes; para ver la rezón, pensemos que si tuviera un sólo bit habría dos “archivos” posibles, conteniendo “0” o “1”; si tuviera dos bits, para cada posible primer bit hay dos posibles segundos bits, es decir 2*2 posibilidades (“00”, “01”, “10”, “11”); luego, un archivo de n bits tiene 2*2*2…*2 (n veces) posibilidades, y ésa es la cantidad de archivos diferentes de ese tamaño.

Por otro lado, ¿cuántos archivos de menos de n bits existen? Para los matemáticos calcular esto es una pavada, pues se trata de la suma de una serie geométrica. Para no espantar al lector no matemático, hagamos un cálculo simple aprovechando el análisis anterior. Contemos cuántos archivos hay de exactamente 1, 2, 3, etc. bits y sumemos. La tabla siguiente muestra este cálculo:

Cantidad n de bits del archivo originalCantidad de archivos de n bits de longitud
(Conjunto A)
Total de archivos de longitud estrictamente menor a n bits
(Conjunto B)
"Déficit" de B comparado con A
121 = 2Ninguno2 - 0 = 2
222 = 424 - 2 = 2
323 = 82 + 4 = 68 - 6 = 2
424 = 162 + 4 + 8 = 1416 - 14 = 2
525 = 322 + 4 + 8 + 16 = 3032 - 30 = 2
626 = 642 + 4 + 8 + 16 + 32 = 6264 - 62 = 2
727 = 1282 + 4 + 8 + 16 + 32 + 64 = 126128 - 126 = 2

¿Qué significa este resultado? Como el conjunto de archivos comprimidos (B) tiene 2 elementos menos que el conjunto de archivos originales (A), para un tamaño fijo de bits y cada conjunto de archivos de ese tamaño, dos de ellos (como mínimo) no podrán comprimirse; si así fuera, necesariamente existirían al menos dos archivos originales distintos que darían como resultado el mismo archivo comprimido y no habría forma de revertir el proceso: no podríamos diferenciar los originales.

Este análisis parece indicar que no puede existir un compresor de archivos “perfecto” que comprima cualquier archivo, en el sentido estricto del término, aunque si sólo dos de ellos no pudieran comprimirse no sería para tanto. De todas formas, alguien podría objetar que este razonamiento no es realista, ya que los archivos que usamos en la vida diaria no son ni remotamente de longitud fija. En efecto, las cosas cambian si se consideran archivos de longitud arbitraria. Un análisis más completo teniendo en cuenta esta cuestión muestra que, a partir de tamaños de unos pocos bits, no más de un tercio de los archivos podrán ser comprimidos. Dicho en otras palabras: en promedio, dos de cada tres archivos creados al azar no podrán comprimirse.

Sea A(n) el número de archivos de longitud n, B(n) el número de archivos de longitud estrictamente menor a n (por lo tanto potenciales candidatos a versiones comprimidas de los primeros) y C(n) el número de archivos disponibles para el resultado de la compresión de un archivo de longitud n no empleados por la compresión de un archivo de longitud menor, es decir, la cantidad efectiva disponible luego de quitar los archivos “ocupados” en compresiones de archivos de menor tamaño.

Con estas definiciones podemos establecer que la cantidad de archivos comprimidos potenciales C(n) para archivos de longitud n es igual a los potenciales de menor longitud B(n) menos los comprimidos ya empleados en archivos de longitud menor C(n – 1), lo que conduce a la relación de recurrencia

C(n) = B(n) – C(n – 1)

Para resolverla, basta observar que B(n) = 2n – 2 (sea por resolver la suma geométrica resultante o por inspección de la tabla anterior) y que C(1) = 0 (no es posible comprimir “archivos” de 1 bit). Resolviendo progresivamente para C(n) tenemos

C(2) = B(2) – C(1)

C(3) = B(3) – C(2) = B(3) – [B(2) – C(1)] = B(3) – B(2) + C(1)

C(4) = B(4) – C(3) = B(4) – [B(3) – B(2) + C(1)] = B(4) – B(3) + B(2) – C(1)

C(5) = B(5) – C(4) = B(5) – [B(4) – B(3) + B(2) – C(1)] = B(5) – B(4) + B(3) – B(2) + C(1)

lo que conduce a la expresión siguiente, teniendo en cuenta que C(1) = 0 y que podemos completar la serie de B con B(1) ya que también es cero:

C(n) = (-1)n ∑ (-1)k B(k)

donde la sumatoria sobre el índice k se extiende de 1 a n.

Reemplazando B(k), según la definición,  resulta

C(n) = (-1)n ∑ (-1)k (2k – 2) = (-1)n [ ∑ (-2)k  – 2∑(-1)k ]

Como la suma geométrica ∑ qk entre 1 y n equivale a q.(1 – qn)/(1-q), resulta

C(n) = (-1)n .{ (-2).[1 – (-2)n]/[1 – (-2)] + 2.[1 – (-1)n]/[1 – (-1)] } = (-1)n. { (-2/3).[1 – (-2)n] + [1 – (-1)n]/[1 – (-1)] }

Para resolver esta expresión es necesario separar los casos de n par y n impar. Poniendo primero para el caso par n = 2k, (-1)n = 1

C(2k) = (-2/3).(1 – 22k) = (2/3).(22k – 1)

Para el caso impar, poniendo n = 2k – 1, (-1)n = -1

C(2k – 1) = (-1).[ (-2/3).(1 + 22k – 1) + 2 ] = (2/3).(22k – 1 + 1) – 2

Se observa claramente que, para valores moderados a grandes de n, ambos casos tienden a

C(n) ≈ (2/3).2n

Por otro lado, la cantidad de archivos A'(n) de longitud no mayor a n viene dado por

A'(n) = A(n) + B(n) = 2n + 2n – 2 = 2.2n – 2 = 2n + 1 – 2

que para valores moderados a grandes de n tiende a

A'(n) ≈ 2n + 1

La fracción C(n)/A'(n) de archivos que pueden comprimirse resulta

C(n)/A'(n) ≈ [ (2/3).2]/[ 2n + 1 ] ≈ 1/3

Otra manera de expresar este resultado es que la probabilidad de que un archivo creado al azar pueda comprimirse no excede de un tercio.

Esto parece contradecir lo que sucede normalmente: en general nuestros archivos se pueden comprimir más o menos, pero no solemos llegar a una situación donde no logramos reducir el tamaño aunque sea un poco. La razón de que no lo observemos radica en que los archivos reales (textos, imágenes, videos, audio, programas) no están creados “al azar”; contienen información con cierta estructura y, en muchos casos, cierta redundancia, lo que hace posible la compresión.

Publicado enDelirios matemáticosGeneral

Se el primero en comentar

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *