Snappy (compresión)

Snappy (anteriormente conocido como Zippy ) es una biblioteca de compresión y descompresión de datos rápida escrita en C++ por Google basada en ideas de LZ77 y de código abierto desde 2011. ^{[ 3 ] [ 4 ]} No busca la máxima compresión ni la compatibilidad con ninguna otra biblioteca de compresión; en cambio, busca velocidades muy altas y una compresión razonable. La velocidad de compresión es de 250 MB/s y la de descompresión es de 500 MB/s utilizando un solo núcleo de un procesador Core i7 "Westmere" de 2,26 GHz de alrededor de 2011 que funciona en modo de 64 bits . La relación de compresión es entre un 20 % y un 100 % menor que la de gzip . ^{[ 5 ]}

Snappy se usa ampliamente en proyectos de Google como Bigtable , MapReduce y en la compresión de datos para los sistemas RPC internos de Google . Se puede usar en proyectos de código abierto como MariaDB ColumnStore , ^{[ 6 ]} Cassandra , Couchbase , Hadoop , LevelDB , MongoDB , RocksDB , Lucene , Spark , Parquet , InfluxDB , ^{[ 7 ]} y Ceph . ^{[ 8 ]} Firefox usa Snappy para comprimir datos en localStorage . ^{[ 9 ]} La descompresión se prueba para detectar cualquier error en el flujo comprimido. Snappy no usa ensamblador en línea (excepto algunas optimizaciones ^{[ 10 ]} ) y es portable.

La codificación Snappy no está orientada a bits, sino a bytes (solo se emiten o consumen bytes completos de un flujo). El formato no utiliza ningún codificador de entropía , como la codificación Huffman o la codificación aritmética .

Los primeros bytes del flujo son la longitud de los datos sin comprimir, almacenados como un varint little-endian , ^{[ 11 ] : sección 1} que permite el uso de un código de longitud variable . Los siete bits inferiores de cada byte se utilizan para los datos y el bit superior es un indicador para señalar el final del campo de longitud.

Los bytes restantes en el flujo se codifican utilizando uno de cuatro tipos de elementos. El tipo de elemento se codifica en los dos bits inferiores del primer byte ( byte de etiqueta ) del elemento: ^{[ 12 ]}

• 00 – Literal – datos sin comprimir; los 6 bits superiores se utilizan para almacenar la longitud (len-1) de los datos. Las longitudes mayores de 60 se almacenan en un entero de 1 a 4 bytes, indicado por una longitud de 6 bits de 60 (1 byte) a 63 (4 bytes).
• 01 – Copia con longitud almacenada como 3 bits y desplazamiento almacenado como 11 bits; un byte después del byte de etiqueta se utiliza para parte del desplazamiento;
• 10 – Copiar con la longitud almacenada como 6 bits del byte de etiqueta y el desplazamiento almacenado como un entero de dos bytes después del byte de etiqueta;
• 11 – Copiar con la longitud almacenada como 6 bits del byte de etiqueta y el desplazamiento almacenado como un entero little-endian de cuatro bytes después del byte de etiqueta;

La copia se refiere al diccionario (datos recién descomprimidos). El desplazamiento indica la posición desde la actual hasta el flujo ya descomprimido. La longitud indica la cantidad de bytes que se copiarán del diccionario. El compresor Snappy 1.0 limitó el tamaño del diccionario a 32 768 bytes, y la versión 1.1 lo actualizó a 65 536 bytes.

La descripción oficial completa del formato snappy se puede encontrar en el repositorio de Google GitHub. ^{[ 11 ]}

El texto

Wikipedia es un proyecto de enciclopedia gratuito, basado en la web, colaborativo y multilingüe.

puede comprimirse a esto, mostrado como datos hexadecimales con explicaciones:

000000 51 f0 42 57 69 6b 69 70 65 64 69 61 20 69 73 20 >Q.BWikipedia es < 000010 61 20 66 72 65 65 2c 20 77 65 62 2d 62 61 73 65 >una plataforma web gratuita< 000020 64 2c 20 63 6f 6c 6c 61 62 6f 72 61 74 69 76 65 >d, colaborativo< 000030 2c 20 6d 75 6c 74 69 6c 69 6e 67 75 61 6c 20 65 >, multilingüe e<

El flujo comienza con la longitud de los datos sin comprimir como un varint , por lo que el primer byte, con el bit más significativo desactivado, corresponde a una longitud de 51 ₁₆ = 81 bytes. ^{[ 11 ] : sección 1}

El primer bloque debe ser un literal, y f042 corresponde a ello: el primer byte se descompone como f0 ₁₆ ⇒ len−1=111100 ₂ ;type=00 ₂ ; type 0 significa un literal, y una longitud−1 de 111100 ₂ =60 significa que la longitud se lee del siguiente byte, en este caso 42 ₁₆ =66. A continuación se muestran los primeros 66 bytes del texto (" Wikipedia es una enciclopedia libre, basada en la web, colaborativa y multilingüe "). ^{[ 11 ] : 2.1}

000040 6e 63 79 63 6c 6f 09 3f 1c 70 72 6f 6a 65 63 74 >ncyclo.?.project< 000050 2e >.<

El encabezado del siguiente bloque consta de 093f , desglosado como 09 ₁₆ ⇒ off _h =000 ₂ ,len−4=010 ₂ ;type=01 ₂ : type 1 indica una "copia con desplazamiento de 1 byte": la longitud a copiar resulta ser 010 ₂ +4=6 bytes, y el desplazamiento es un entero de 11 bits cuyos bits superiores son off _h y cuyos bits inferiores son el siguiente byte: 3f , por lo que {off _h }{3f ₁₆ }=00000111111 ₂ =63. ^{[ 11 ] : 2.2,2.2.1}

Esto significa copiar 6 bytes, comenzando hace 63 bytes; dado que ya se han copiado 67 bytes, esto se evalúa como copiar 6 bytes comenzando en la posición 4 (desde el quinto byte), lo que produce " pedia ".

Este bloque no tiene otro contenido, por lo que el siguiente bloque comienza inmediatamente después: 1c ₁₆ ​​⇒ len−1=000111 ₂ ;type=00 ₂ , es decir, un literal de longitud 000111 ₂ +1=8. ^{[ 11 ] : 2.1} La parte final del texto (" proyecto. ") sigue.

En este ejemplo, el proceso de compresión eliminó todas las subcadenas comunes de cuatro o más caracteres. Los compresores más comunes ofrecen una mejor compresión. A diferencia de métodos de compresión como gzip y bzip2, no se utiliza codificación entrópica para empaquetar el alfabeto en el flujo de bits.

El flujo Snappy admite entradas con un tamaño total de hasta 4 GiB−1, ^{[ 11 ] : sección 1} y puede agregar una sobrecarga significativa a las secciones que no están comprimidas o lo están de manera insuficiente, además de no ser autoidentificable y no tener ningún mecanismo de integridad de datos más allá de una simple verificación del tamaño de salida.

Para combatir estos problemas, se puede utilizar el formato de trama Snappy ^{[ 2 ]} "Snappy framed", que divide la entrada en fragmentos de hasta 64 KiB, ^{[ 2 ] : 4.2,4.3} delimitados por encabezados de bloque de 4 bytes (un identificador de un byte y una longitud de tres bytes): ^{[ 2 ] : sección 1}

• El "Identificador de flujo", de tipo FF ₁₆ , debe iniciar el flujo y debe consistir exclusivamente en "sNaPpY" en ASCII , ^{[ 2 ] : 4.1}
• Los "datos comprimidos", de tipo 0, contienen un flujo Snappy comprimido, ^{[ 2 ] : 4.2}
• Los "datos sin comprimir", de tipo 1, contienen datos que se copiarán textualmente a la salida. ^{[ 2 ] : 4.3}

Ambos tipos de fragmentos de datos también contienen una suma de comprobación CRC-32C de los datos sin comprimir.

Los fragmentos de tipo 2-7F ₁₆ están reservados y deben generar errores. ^{[ 2 ] : 4.5} Los de tipo 80 ₁₆ -FE ₁₆ pueden ser ignorados por los descompresores que no los entienden. ^{[ 2 ] : 4.4,4.6}

Las distribuciones Snappy incluyen enlaces para C++ y C. Los enlaces y puertos proporcionados por terceros incluyen ^{[ 13 ]} C# , Common Lisp , Crystal (lenguaje de programación) , Erlang , Go , Haskell , Lua , Java , Nim , Node.js , Perl , PHP , Python , R , Ruby , Rust , Smalltalk y OpenCL . ^{[ 14 ] [ 15 ]} También está disponible un programa de interfaz de línea de comandos . ^{[ 16 ]}

• Estándar Z

• Lista de correo Snappy