Recientemente me topé con el siguiente artículo interesante que afirma comprimir eficientemente conjuntos de datos aleatorios en siempre más del 50%, independientemente del tipo y formato de los datos.
Básicamente, usa números primos para construir de manera única una representación de fragmentos de datos de 4 bytes que son fáciles de descomprimir dado que cada número es un producto único de números primos. Para asociar estas secuencias con los números primos, utiliza un diccionario.
Mi pregunta es:
- ¿Es esto realmente factible como lo sugieren los autores? Según el documento, sus resultados son muy eficientes y siempre comprimen los datos a un tamaño más pequeño. ¿No será enorme el tamaño del diccionario?
- ¿No podría usarse esto para volver a comprimir iterativamente los datos comprimidos usando el mismo algoritmo? Es obvio, y se ha demostrado, que tales técnicas (donde los datos comprimidos se vuelven a comprimir tantas veces como sea posible, reduciendo drásticamente el tamaño del archivo) son imposibles; de hecho, no habría biyección entre el conjunto de todos los datos aleatorios y los datos comprimidos. Entonces, ¿por qué parece que esto sería posible?
- Incluso si la técnica aún no es perfecta, obviamente se puede optimizar y mejorar mucho. ¿Por qué esto no es más conocido / estudiado? Si de hecho estas afirmaciones y resultados experimentales son ciertos, ¿no podría esto revolucionar la informática?
Respuestas:
Eso es imposible. No puede comprimir datos aleatorios , necesita algo de estructura para aprovechar. La compresión debe ser reversible, por lo que no puede comprimir todo en un 50% porque hay muchas menos cadenas de longitud que las de longitud n .n/2 n
Hay algunos problemas importantes con el documento:
Utilizan 10 archivos de prueba sin ninguna indicación de su contenido. ¿Los datos son realmente aleatorios? ¿Cómo se generaron?
Afirman alcanzar relaciones de compresión de al menos el 50%, mientras que sus datos de prueba muestran que alcanzan como máximo el 50%.
¿Qué? Los números primos son números primos independientemente de la base.
Problema # 1 con descompresión: la factorización prima es un problema difícil, ¿cómo lo hacen de manera eficiente?
Problema # 2 con descompresión ( este es el pateador ): multiplican los números primos juntos, pero al hacerlo pierdes cualquier información sobre el orden, ya que . No creo que sea posible descomprimir en absoluto usando su técnica.2⋅5=10=5⋅2
No creo que este artículo sea muy bueno.
fuente
Voy a remitirme a Tom van der Zanden, quien parece haber leído el periódico y descubrió una debilidad en el método. Si bien no leí el documento en detalle, pasando del resumen y la tabla de resultados, parece una afirmación ampliamente creíble.
Lo que afirman es una relación de compresión consistente del 50% en los archivos de texto (no "todos los archivos"), que señalan que es casi lo mismo que LZW y aproximadamente un 10% peor que la codificación Huffman (presumiblemente de orden cero). Comprimir archivos de texto en un 50% no es difícil de lograr utilizando métodos razonablemente simples; Es una tarea de pregrado en muchos cursos de informática.
Estoy de acuerdo en que el documento no es muy bueno como investigación publicada, y no creo que hable bien de los revisores que esto fue aceptado. Además de los obvios detalles faltantes que hacen que los resultados sean imposibles de reproducir (por ejemplo, qué eran los archivos de texto), y no hay ningún intento de vincularlo al campo de compresión, no tiene sentido que realmente entiendan lo que está haciendo su algoritmo.
El sitio web de la conferencia afirma una relación de aceptación de 1: 4, lo que hace que te preguntes qué rechazaron.
fuente
Usted pregunta:
Sí, por supuesto. Incluso para su ejemplo seleccionado a mano ("THE FOX SILVER FOX JUMPS OVER THE LAZY DOG"), no logran la compresión, porque el diccionario contiene cada subcadena de 4 bytes del texto (menos 4 bytes por la repetición de " EL ") ... y la versión" comprimida "del texto tiene que incluir el diccionario completo más toda esta basura de números primos.
Una vez más, parece tener una buena comprensión intuitiva de la situación. Se ha dado cuenta intuitivamente de que ningún esquema de compresión puede ser efectivo en todas las entradas, porque si lo fuera, podríamos aplicarlo una y otra vez para comprimir cualquier entrada a un solo bit, ¡y luego a la nada!
Para decirlo de otra manera: una vez que haya comprimido todos sus archivos .wav a .mp3, no obtendrá ninguna mejora en el tamaño del archivo comprimiéndolos. Si su compresor MP3 ha hecho su trabajo, no quedará ningún patrón para que explote el compresor ZIP.
(Lo mismo se aplica al cifrado: si tomo un archivo de ceros y lo cifro de acuerdo con mi algoritmo criptográfico de elección, es mejor que el archivo resultante no sea compresible , ¡o de lo contrario mi algoritmo de cifrado está filtrando "patrón" en su salida!)
Estas afirmaciones y resultados experimentales no son ciertos.
Como Tom van der Zanden ya señaló, el "algoritmo de compresión" de Chakraborty, Kar y Guchait es defectuoso porque no solo no logra ninguna relación de compresión, sino que también es irreversible (en matemáticas, "no biyectivo"): hay Una multitud de textos que todos "comprimen" a la misma imagen, porque su algoritmo es básicamente multiplicación y la multiplicación es conmutativa.
Debe sentirse bien porque su comprensión intuitiva de estos conceptos lo llevó a la conclusión correcta al instante. Y, si puede perder el tiempo, debe sentir lástima por los autores del artículo que claramente pasaron mucho tiempo pensando en el tema sin entenderlo en absoluto.
El directorio de archivos un nivel por encima de la URL que publicó contiene 139 "documentos" de esta misma calidad, todos aparentemente aceptados en las "Actas de la Conferencia Internacional sobre Investigación Emergente en Computación, Información, Comunicación y Aplicaciones". Esto parece ser una conferencia simulada del tipo habitual. El propósito de tales conferencias es permitir a académicos fraudulentos reclamar "publicación en una revista", al tiempo que permite que organizadores sin escrúpulos ganen mucho dinero. (Para obtener más información sobre conferencias falsas, consulte este hilo de reddit o varias publicaciones de StackExchange sobre el tema ). Existen conferencias falsas en todos los campos. Simplemente aprenda a confiar en sus instintos y no creer todo lo que lee en un "procedimiento de conferencia", y lo hará bien.
fuente
La entropía limita efectivamente el rendimiento de la compresión sin pérdidas más fuerte posible. Por lo tanto, no existe un algoritmo que pueda comprimir conjuntos de datos aleatorios en siempre más del 50%.
fuente
Los métodos de compresión, que son restaurables, en general encuentran un patrón y lo reexpresan de manera simplista. Algunos son muy inteligentes, otros muy simples. En algún momento no hay patrón. Los procesos han 'hervido' los datos establecidos en su patrón único más simple. Cualquier intento de compresión desde ese punto en adelante da como resultado un conjunto de datos más grande o diluye la unicidad. En los esquemas de compresión de números mágicos siempre hay un defecto, o un poco de mano, o pérdida. desconfíe de cualquier proceso que afirme que realiza el último WinZip o RAR.
fuente