Compresión de datos usando números primos

22

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?
Klangen
fuente
55
Como observó, el periódico está haciendo afirmaciones realmente fuertes. Siempre sospeche mucho de tales afirmaciones, especialmente si el artículo se publica en un lugar extraño (los documentos asombrosos que "revolucionan la informática" deberían aparecer en lugares conocidos y respetados, ¿verdad?).
Juho
2
es imposible "comprimir siempre datos aleatorios" basados, por ejemplo, en la teoría de la complejidad de kolmogorov . y una prueba de resistencia es similar a la que ha esbozado. No estoy seguro de si se trata de una interpretación errónea del documento o del documento original. ¿Por qué no destaca dónde entra ese reclamo en particular?
vzn
66
"¿No podría usarse esto para volver a comprimir iterativamente los datos comprimidos usando el mismo algoritmo?" - si. Cualquier algoritmo que afirme ser capaz de comprimir todos los datos arbitrarios puede aplicarse recursivamente a su propia salida, de modo que cualquier dato se comprima a 0 bits. Por lo tanto, esta afirmación es imposible.
Jörg W Mittag
1
@ JörgWMittag Tengo un algoritmo que le permite comprimir un archivo repetidamente a una pequeña cantidad de bits, pero es extremadamente poco práctico. También solo funciona con archivos que comienzan con 1 bit: trate el archivo completo como un número binario grande, decreméntelo y luego descarte los ceros a la izquierda. Para descomprimir, increméntelo, agregando un 1 inicial si es necesario.
user253751
3
Nota personal: no se moleste en enviar ningún trabajo a ninguna revista de Elsevier.
500 - Error interno del servidor

Respuestas:

34

siempre comprima conjuntos de datos aleatorios en más del 50%

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/2n

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%.

Este algoritmo define una estrategia sin pérdidas que utiliza los números primos presentes en el sistema de números decimales.

  • ¿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.25=10=52

No creo que este artículo sea muy bueno.

Tom van der Zanden
fuente
Por lo que entendí, almacenan el orden de las cadenas con la misma multiplicidad en el diccionario. Pero en conjuntos de datos aleatorios, ¿no debería esto generar un diccionario enorme, dado que hay muchas cadenas de 4 bytes con multiplicidad 1 (o multiplicidad igual)?
Klangen
@Pickle En su ejemplo, la cadena "@THE" tiene multiplicidad 2. No veo cómo pueden reconstruir en qué dos lugares debe ir la palabra "the".
Tom van der Zanden
1
Ah, ya veo. Buena observación. De hecho, ese es un problema importante. ¿Cómo se aceptó este artículo para aparecer en la revista? ¿No debería haber una revisión por pares más rigurosa?
Klangen
44
@Pickle Sí, debería haber una revisión más rigurosa. Sin embargo, ese no es siempre el caso, a veces los organizadores de conferencias inexpertos / flojos / incompetentes no logran encontrar revisores a tiempo. Se aceptan múltiples casos de trabajos que contienen galimatías generadas aleatoriamente, y una revista incluso publicó un artículo titulado "Sácame de tu maldita lista de correo" .
Tom van der Zanden
Jajaja eso es asombroso. Pero triste al mismo tiempo.
Klangen
15

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.

Seudónimo
fuente
12

Usted pregunta:

  • ¿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?

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.

  • ¿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?

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!)

  • 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?

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.

Quuxplusone
fuente
Gracias por indicar claramente por qué este documento es una mierda y decir cómo es posible que haya sido escrito en primer lugar y que haya logrado pasar por cualquier tipo de revisión.
vaab
Gracias por tu respuesta concisa. Realmente es triste cuando ni siquiera puedes confiar en que las entradas del diario sean revisadas al menos por algún tipo de persona. Esto realmente arroja mucha luz sobre el hecho de que uno debe estar atento incluso cuando lee "supuestas" publicaciones de revistas científicas. Uno pensaría que tales artículos están sujetos no solo a una "revisión" por pares, sino también a un "análisis" mínimo de pares, como es habitual en tales campos. Espero que esto se convierta en una revelación para varias personas.
Klangen
Hoy aprendí que existen al menos dos patentes estadounidenses sobre "algoritmos de compresión infinita" similares. Ver gailly.net/05533051.html
Quuxplusone el
5

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%.

J.-E. Alfiler
fuente
8
Ni siquiera existe un algoritmo que pueda comprimir conjuntos de datos aleatorios en siempre más de 0.0000001%.
David Richerby
1

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.

SkipBerne
fuente
2
sss
1
@DavidRicherby, entonces su compresión de la cadena vacía produce un conjunto de datos más grande, como afirma SkipBerne. Aún así, creo que su respuesta debería aclarar que se está refiriendo a volver a comprimir la salida anterior utilizando el mismo algoritmo .
Ángel
2
La afirmación de @ Ángel SkipBerne es que existen cadenas que no pueden ser comprimidas por ningún algoritmo (" cualquier intento de compresión desde ese punto en adelante", mi énfasis). Eso es incorrecto por la razón que doy: para cada cadena, existe un algoritmo que comprime esa cadena.
David Richerby
La forma en que lo interpreto SkipBerne afirma que para cada algoritmo de compresión hay una cadena que no se puede comprimir. Cual es verdad. Esa cadena no comprimible será diferente para diferentes algoritmos, por supuesto.
Jose Antonio Restablece a Mónica el
@DavidRicherby Estás extraviando los cuantificadores: está razonablemente claro que SkipBerne escribió que (para cualquier método de compresión, hay un punto después del cual no hay compresión), no eso (hay un punto después del cual para cualquier método de compresión, hay sin compresión). Esta respuesta es objetivamente correcta, pero no agrega nada a las respuestas antiguas y mejor escritas.
Gilles 'SO- deja de ser malvado'