¿Cuál es el mejor algoritmo de compresión para pequeños archivos de 4 KB?

Question

Estoy tratando de comprimir paquetes TCP cada uno de aproximadamente 4   KB de tamaño. Los paquetes pueden contener cualquier byte (de 0 a 255). Todos los puntos de referencia sobre los algoritmos de compresión que encontré se basaban en archivos más grandes. No encontré nada que compare la relación de compresión de diferentes algoritmos en archivos pequeños, que es lo que necesito. Necesito que sea de código abierto para que pueda implementarse en C++, por lo que no hay RAR, por ejemplo. ¿Qué algoritmo puede recomendarse para archivos pequeños de aproximadamente 4 kilobytes de tamaño? LZMA? HACC? ZIP? gzip? bzip2?

Answer 1

Elija el algoritmo que sea más rápido, ya que probablemente le interese hacerlo en tiempo real. En general, para bloques de datos más pequeños, los algoritmos comprimen casi lo mismo (dan o toman unos pocos bytes) principalmente porque los algoritmos necesitan transmitir el diccionario o árboles Huffman además de la carga útil.

Recomiendo Deflate (usado por zlib y Zip) por varias razones. El algoritmo es bastante rápido, bien probado, con licencia BSD, y es la única compresión requerida para ser compatible con Zip (según Appzote infozip). Además de los conceptos básicos, cuando determina que la compresión es mayor que el tamaño descomprimido, hay un modo STORE que solo agrega 5 bytes por cada bloque de datos (el bloque máximo es de 64k bytes). Además del modo STORE, Deflate admite dos tipos diferentes de tablas Huffman (o diccionarios): dinámico y fijo. Una tabla dinámica significa que el árbol Huffman se transmite como parte de los datos comprimidos y es el más flexible (para diferentes tipos de datos no aleatorios). La ventaja de una tabla fija es que la tabla es conocida por todos los decodificadores y, por lo tanto, no necesita estar contenida en la secuencia comprimida. El código de descompresión (o inflar) es relativamente fácil. He escrito versiones de Java y Javascript basadas directamente en zlib y funcionan bastante bien.

Los otros algoritmos de compresión mencionados tienen sus ventajas. Prefiero desinflar debido a su rendimiento en tiempo de ejecución tanto en el paso de compresión como en particular en el paso de descompresión.

Un punto de aclaración: Zip no es un tipo de compresión, es un contenedor. Para hacer la compresión de paquetes, omitiría Zip y simplemente usaría las API desinflar/inflar proporcionadas por zlib.

Answer 2

Todos estos algoritmos son razonables de probar. Como dices, no están optimizados para archivos pequeños, pero tu siguiente paso es simplemente probarlos. Es probable que tome solo 10 minutos comprimir algunos paquetes típicos y ver qué tamaños resultan. (Pruebe diferentes banderas de compresión también). A partir de los archivos resultantes, es probable que pueda elegir qué herramienta funciona mejor.

Los candidatos que enumeró son todos buenos intentos. También puedes probar bzip2.

A veces, el simple "probarlos todos" es una buena solución cuando las pruebas son fáciles de hacer. Pensar demasiado a veces lo hace más lento.

Answer 3

No creo que el tamaño del archivo importe, si no recuerdo mal, el LZW en GIF restablece su diccionario cada 4K.

Answer 4

ZLIB debería estar bien. Se usa en MCCP.

Sin embargo, si realmente necesita una buena compresión, haría un análisis de patrones comunes e incluiría un diccionario de ellos en el cliente, lo que puede producir incluso mayores niveles de compresión.

Answer 5

Hice lo que Arno Setagaya sugirió en su respuesta: realizó algunas pruebas de muestra y comparó los resultados.

Las pruebas de compresión se realizaron utilizando 5 archivos, cada uno de ellos de 4096 bytes de tamaño. Cada byte dentro de estos 5 archivos se generó al azar.

IMPORTANTE: En la vida real, los datos probablemente no serían todos aleatorios, pero tenderían a tener un poco de bytes repetitivos. Por lo tanto, en la aplicación de la vida real, la compresión tenderá a ser un poco mejor que los siguientes resultados.

NOTA: Cada uno de los 5 archivos se comprimió solo (es decir, no junto con los otros 4 archivos, lo que daría lugar a una mejor compresión). En los siguientes resultados solo uso la suma del tamaño de los 5 archivos juntos por simplicidad.

Incluí RAR solo por razones de comparación, aunque no es de código abierto.

Resultados: (de mejor a peor)

lzop: 20775/20480 * 100 = 101,44% del tamaño original

RAR: 20825/20480 * 100 = 101,68% del tamaño original

LZMA: 20827/20480 * 100 = 101,69% del tamaño original

postal: 21020/20480 * 100 = 102,64% del tamaño original

BZIP: 22899/20480 * 100 = 111.81% del tamaño original

Conclusión: Para mi sorpresa TODOS los algoritmos probados produjeron un tamaño mayor que los originales !!! Supongo que solo sirven para comprimir archivos más grandes o archivos que tienen muchos bytes repetidos (no datos aleatorios como el anterior). Por lo tanto, no utilizaré ningún tipo de compresión en mis paquetes TCP. Tal vez esta información sea útil para otros que consideren la compresión de pequeños datos.

EDIT: Olvidé mencionar que utilicé las opciones predeterminadas (indicadores) para cada uno de los algoritmos.

Answer 6

He tenido suerte al usar librerías de compresión zlib directamente y no usar ningún contenedor de archivos. ZIP, RAR, tienen sobrecarga para almacenar cosas como nombres de archivo. He visto la compresión de esta manera dar resultados positivos (compresión menor que el tamaño original) para paquetes de hasta 200 bytes.

Answer 7

Puede intentar delta compression. La compresión dependerá de tus datos. Si tiene alguna encapsulación en la carga útil, puede comprimir los encabezados.

Answer 8

Si desea "comprimir paquetes TCP", puede considerar el uso de una técnica estándar de RFC.

• RFC1978 PPP Compresión Predictor Protocolo
• RFC2394 carga útil IP compresión utilizando DESINFLAR
• RFC2395 carga útil IP compresión utilizando LZS
• RFC3173 Protocolo de compresión de carga útil IP (IPComp)
• RFC3051 carga útil IP ITU-compresión utilizando TELEVISIÓN.44 paquetes Método
• Negociación RFC5172 para IPv6 datagramas de compresión mediante el Protocolo de Control IPv6
diccionario estático
• RFC5112 La Presencia-específico para la señalización de compresión (SIGCOMP) Formato
• RFC3284 El VCDIFF Genérico Diferenciación y compresión de datos
• RFC2118 Microsoft Point Protocolo de compresión punto a punto (MPPC)

Probablemente haya otros RFC relevantes que he pasado por alto.

Answer 9

Puede probar bicom. Este algoritmo está prohibido para uso comercial. Si lo desea para uso profesional o comercial, mire el "algoritmo de codificación de rango".