Snappy (software)
| Original author(s) | Zeev Tarantov,[1] Steinar H. Gunderson |
|---|---|
| Developer(s) | |
| Initial release | March 18, 2011 |
| Stable release | 1.1.0 / January 18, 2013 |
| Development status | Active |
| Written in | C++ |
| Platform | Portable |
| Size | 2 MB |
| Type | data compression |
| License | Apache 2 (up to 1.0.1)/New BSD |
| Website | http://code.google.com/p/snappy/ |
Snappy (previously known as Zippy) is a fast data compression and decompression library developed by Google based on ideas from LZ77 and open-sourced in 2011.[2][3] It was designed to be very fast and stable, but not to achieve a high compression ratio. Compression speed is 250 MB/s and decompression speed is 500 MB/s using a single threaded, 64-bit Core i7 processor. The compression ratio is 20–100% lower than gzip.[4]
Snappy is widely used in Google projects like BigTable, MapReduce, and in compression data in Google's internal RPC systems. It can be used in open-source projects like Cassandra, Hadoop, LevelDB, Lucene[5] Decompression is tested to detect any errors in the compressed stream. Snappy does not use inline assembler and is portable. It is optimized for 64-bit, little-endian architectures, primary x86_64.[6]
Stream format
Snappy encoding is not bit-oriented, but byte-oriented (only whole bytes are emitted or consumed from a stream). The format uses no entropy encoder, like Huffman tree or arithmetic encoder.
The first bytes of the stream are the length of uncompressed data, stored as a little-endian varint, which allows for variable-length encoding. The lower seven bits of each byte are used for data and the first bit is a flag which tells if the next byte is used for the same integer.
The remaining bytes in the stream are encoded using one of four element types. The element type is encoded in the first byte (tag byte) of the element. The two lower bits of this byte is the type code:[7]
- 00 – Literal – uncompressed data; upper 6 bits are used to store length of data; if the length of data is more 60 bytes, additional variable-length encoding is added
- 01 – Copy with length stored as 3 bits and offset stored as 11 bits; one byte after tag byte is used for part of offset;
- 10 – Copy with length stored as 6 bits of tag byte and offset stored as two-byte integer after the tag byte;
- 11 – Copy with length stored as 6 bits of tag byte and offset stored as four-byte little-endian integer after the tag byte;
The copy refers to the dictionary (just-decompressed data). The offset is the shift from the current position back to the already decompressed stream. The length is the number of bytes to copy from the dictionary. The size of the dictionary was limited by the 1.0 Snappy compressor to 32768 bytes, and updated to 65536 in version 1.1.
Example of a compressed stream
The text
Wikipedia is a free, web-based, collaborative, multilingual encyclopedia project.
may be compressed to (showed as hex data, every compressed subpart is descripted):
0000000: ca02 f042 5769 6b69 7065 6469 6120 6973 ...BWikipedia is
Length of data is 0x02ca(varint) = 0x014a = 330 bytes; 0xf042 = literal of 66+1 bytes follows
0000010: 2061 2066 7265 652c 2077 6562 2d62 6173 a free, web-bas 0000020: 6564 2c20 636f 6c6c 6162 6f72 6174 6976 ed, collaborativ 0000030: 652c 206d 756c 7469 6c69 6e67 7561 6c20 e, multilingual 0000040: 656e 6379 636c 6f09 3ff0 8170 726f 6a65 encyclo.?..proje
0x09 is tag-byte of type 01 with length of 0b10= 2 +4 = 6 and offset = 0x03f = 63 or "pedia ";
0xf081 is a literal with length of 129+1 bytes
0000050: 6374 2e00 0000 0000 0000 0000 0000 0000 ct.
In this example all common substrings with four or more characters were eliminated by the compression process. More common compressors can compress this better. Unlike compression methods such as gzip and bzip2, there is no entropy encoding used to pack alphabet into the bit stream.
Interfaces
Snappy distributions include C++ and C bindings. Third party-provided bindings and ports include:[8]
References
- ↑ http://comments.gmane.org/gmane.linux.drivers.driver-project.devel/15159
- ↑ "Google Snappy–A Fast Compressing Library". InfoQ. Retrieved August 1, 2011.
- ↑ Google open sources MapReduce compression. In the name of speed // The Register, 2011-03-24
- ↑ "Snappy: A fast compressor/decompressor: Readme". Google Code. Retrieved August 1, 2011."Snappy vs lzo vs zlib".
- ↑ snappy. A fast compressor/decompressor - Project page at Google Code
- ↑ http://www.opennet.ru/opennews/art.shtml?num=30003 (Russian)
- ↑ http://code.google.com/p/snappy/source/browse/trunk/format_description.txt
- ↑ http://code.google.com/p/snappy/
Links
| ||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||