Snappy (anteriormente conocido como Zippy ) es una biblioteca rápida de compresión y descompresión de datos escrita en C++ por Google basada en ideas de LZ77 y de código abierto en 2011. [3] [4] No apunta a una compresión máxima ni a la compatibilidad con ninguna otra biblioteca de compresión; en cambio, apunta a velocidades muy altas y una compresión razonable. La velocidad de compresión es de 250 MB/s y la velocidad de descompresión es de 500 MB/s utilizando un solo núcleo de un procesador "Westmere" Core i7 de 2,26 GHz de alrededor de 2011 que se ejecuta en modo de 64 bits . La relación de compresión es entre un 20 y un 100 % menor que 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, 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 una secuencia). 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 una variante 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 indicar el final del campo de longitud.
Los bytes restantes del flujo se codifican utilizando uno de los cuatro tipos de elementos. El tipo de elemento se codifica en los dos bits inferiores del primer byte ( byte de etiqueta ) del elemento: [12]
La copia se refiere al diccionario (datos recién descomprimidos). El desplazamiento es el cambio desde la posición actual hasta el flujo ya descomprimido. La longitud es la cantidad de bytes que se copiarán del diccionario. El tamaño del diccionario fue limitado por el compresor Snappy 1.0 a 32.768 bytes, y actualizado a 65.536 en la versión 1.1. [ cita requerida ]
La descripción oficial completa del formato snappy se puede encontrar en el repositorio de GitHub de Google. [11]
El texto
Wikipedia es un proyecto de enciclopedia libre, colaborativo, multilingüe y basado en la web.
Puede comprimirse de esta manera y mostrarse 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 >gratis, basado en web<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 una variante [11] : sección 1 ; por lo tanto, el primer byte, con el bit alto libre, corresponde a una longitud de 51 16 = 81 bytes.
El primer bloque debe ser un literal, y f042 corresponde a él: el primer byte se descompone como f0 16 ⇒ len−1=111100 2 ;type=00 2 ; el tipo 0 significa un literal, y una longitud−1 de 111100 2 =60 significa que la longitud se lee del byte siguiente, en este caso 42 16 =66. A continuación se muestran los primeros 66 bytes del texto (" Wikipedia es una enciclopedia libre, colaborativa, multilingüe y basada en la web "). [11] : 2.1
000040 6e 63 79 63 6c 6f 09 3f 1c 70 72 6f 6a 65 63 74 >proyecto ncyclo.?<000050 2e >.<
El encabezado del siguiente bloque consta de 093f , desglosado como 09 16 ⇒ off h =000 2 ,len−4=010 2 ;type=01 2 : el tipo 1 indica una "copia con un desplazamiento de 1 byte": la longitud a copiar es 010 2 +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 16 }=00000111111 2 =63. [11] : 2.2,2.2.1
Esto significa copiar 6 bytes, comenzando 63 bytes atrás – 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 16 ⇒ len−1=000111 2 ;type=00 2 , es decir, un literal de longitud 000111 2 +1=8. [11] : 2.1 Sigue la parte final del texto (" proyecto ").
En este ejemplo, el proceso de compresión eliminó todas las subcadenas comunes con cuatro o más caracteres. Los compresores más comunes pueden comprimir esto mejor. A diferencia de los métodos de compresión como gzip y bzip2, no se utiliza ninguna codificación de entropía para comprimir 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 que están comprimidas de manera insuficiente, además de no ser autoidentificables y no tener un 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 tramado 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
Ambos tipos de fragmentos de datos también contienen una suma de comprobación CRC-32C de los datos sin comprimir.
Los fragmentos de los tipos 2-7F 16 están reservados y deben generar errores. [2] : 4.5 Los de los tipos 80 16 -FE 16 pueden ser ignorados por los descompresores que no los entiendan. [2] : 4.4,4.6
Las distribuciones de Snappy incluyen enlaces 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]
.svg/1280px-Free_and_open-source_software_logo_(2009).svg.png){kind=logo}