Snappy (bibliotek)

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 16 augusti 2020; verifiering kräver 1 redigering .
Snappy
Sorts funktionsbibliotek och program för att kombinera [d]
Utvecklaren Google
Skrivet i C++
Operativ system plattformsoberoende
Första upplagan 18 mars 2011 [1] [2]
senaste versionen
Läsbara filformat pigg
Genererade filformat pigg
Licens modifierad BSD-licens [d] [4]
Hemsida github.com/google/snappy

Snappy (tidigare Zippy ) [5]  är ett snabbt datakomprimerings- och dekompressionsbibliotek skrivet i C++ hos Google baserat på LZ77 ; öppnade 2011 [6] [7] [8] . Huvudmålet var att uppnå en hög komprimeringshastighet, medan den högsta komprimeringen eller kompatibiliteten med andra bibliotek inte var inställd. 2011 nådde komprimeringshastigheten på en enda Core i7-kärna (2,26 GHz, 64 bitar) 250 MB/s och 500 MB/s för dekompression [8] , men kompressionsförhållandet visade sig vara 20 - 100 % lägre än gzip [9] .

Används i Google-projekt som BigTable , MapReduce och internt RPC- system , används i kolumnmotor för MariaDB [10] , Cassandra [11] , filformat för Hadoop -ekosystem [12] , LevelDB [13] . MongoDB [14] , RocksDB [15] . Är mycket bärbar, använder inte assembler-insatser .

Distribueras som omslag över C och C++ ; gränssnitt finns för ett antal andra språk, inklusive C# , Lisp , Erlang , Go , Haskell , Haxe , Java , Lua , Node.js , Perl , PHP , Python , R , Ruby , Rust , Smalltalk .

Strömformat

Kodning i Snappy sker byte för byte, det kan bara finnas byte i strömmen. Formatet undviker entropikodning , med hjälp av Huffman-algoritmen eller aritmetisk kodning som är lämpligt.

Den första byten i strömmen definierar storleken på okomprimerad data, lagrad som en liten endian "varint", dvs ett heltal i kod med variabel längd . De första sju bitarna av varje byte används för data, och den åttonde biten är slutflaggan för fältet som beskriver den storleken.

De återstående byten i strömmen är kodade som en av fyra elementtyper. Elementtypen kodas i de två första bitarna av elementets första byte (taggbyte). [16]

Notation: kod  - länk till ordboken; shift  - skift från den aktuella positionen tillbaka till den redan uppackade strömmen; längd  - antalet byte kod från ordboken.

Ordbokens storlek är begränsad till byte ( för version 1.0).

Flödesexempel

Original text:

Wikipedia är ett gratis, webbaserat, samarbetande, flerspråkigt uppslagsverk.

Komprimerad ström:

0000000: ca02 f042 5769 6b69 7065 6469 6120 6973 ...BWikipedia är

De första 2 byten 0xCA02 är längden, uttryckt som en liten endian varint (se även Protocol Buffers för specifikationen av varint - variabel längd heltalsnotation), så den mest signifikanta byten här är 02. 0x02CA(LE-vy) = 0x014A= 330 byte. De kommande två byten 0xF042indikerar att samma bokstav kommer att följa vid position 66+1

0000010: 2061 2066 7265 652c 2077 6562 2d62 6173 en gratis, webbaserad 0000020: 6564 2c20 636f 6c6c 6162 6f72 6174 6976ed, collaborativ 0000030: 652c 206d 756c 7469 6c69 6e67 7561 6c20 e, flerspråkig 0000040: 656e 6379 636c 6f 09 3f f0 14 70 726f 6a65 encyclo.?.proje

0x09 är en typtaggbyte 01med en längd på 4 bitar och offset 0x3F== 63 10 eller "pedia "; 0xf014 är en bokstavlig med en längd på 20+1 byte

0000050: 6374 2e00 0000 0000 0000 0000 0000 0000 ct.

I exemplet har alla upprepningar av en delsträng med fyra eller fler tecken eliminerats av komprimeringsprocessen. De flesta andra bibliotek kan komprimera detta exempel bättre. Till skillnad från klassiska gzip- eller bzip2-arkiverare använder Snappy inte entropikodning (som Huffman-kod ) och packar inte om alfabetiska tecken till mer kompakta bitsekvenser enligt deras frekvens.

Anteckningar

  1. ↑ https://www.theregister.co.uk/2011/03/24/google_open_sources_snappy/
  2. ↑ http://www.infoq.com/news/2011/04/Snappy
  3. ↑ Release 1.1.9 - 2021.
  4. ↑ https://github.com/google/snappy/blob/master/NEWS
  5. ↑ README.md  #Introduktion . Googles repository på GitHub . Hämtad 16 oktober 2018. Arkiverad från originalet 16 oktober 2018.
  6. ↑ Avram, Abel . Google Snappy-A Fast Compressing Library  (engelska) , InfoQ  (6 april 2011). Arkiverad från originalet den 4 juli 2018. Hämtad 16 oktober 2018.
  7. ↑ Metz, Cade . Googles öppna källor MapReduce compression  (engelska) , The Register  (24 mars 2011). Arkiverad från originalet den 3 juli 2018. Hämtad 16 oktober 2018.
  8. ↑ 12 Ximen . _ Datakomprimeringsbibliotek från Google , linux.org.ru  (23 april 2011). Arkiverad från originalet den 3 juli 2015. Hämtad 16 oktober 2018.
  9. ↑ Erdem Agaoglu. LZO vs Snappy vs LZF vs ZLIB, En jämförelse av kompressionsalgoritmer för fettceller i  HBase . Blogg (14 april 2011). Hämtad 16 oktober 2018. Arkiverad från originalet 3 juli 2018.
  10. ↑ ColumnStore Storage Architecture # Kompression med realtidsdekompression  . MariaDB Kunskapsbas . Hämtad 16 oktober 2018. Arkiverad från originalet 16 oktober 2017.
  11. ↑ Storage Engine #CommitLog  . Apache Cassandra dokumentation . Hämtad 16 oktober 2018. Arkiverad från originalet 17 mars 2018.
  12. ↑ Infödda bibliotek vägleder # Komponenter  . Apache Hadoop-dokumentation . Hämtad 16 oktober 2018. Arkiverad från originalet 5 april 2018.
  13. ↑ README.md  #Features . Googles repository på GitHub . Hämtad 16 oktober 2018. Arkiverad från originalet 18 oktober 2017.
  14. ↑ Ordlista - MongoDB-dokumentation  . MongoDB-dokumentation . Hämtad 16 oktober 2018. Arkiverad från originalet 9 september 2018.
  15. ↑ Kompression #Configuration  . Facebook-förråd på GitHub . Hämtad 16 oktober 2018. Arkiverad från originalet 28 december 2017.
  16. ↑ format_description.txt  . _ Googles repository på GitHub . Hämtad 16 oktober 2018. Arkiverad från originalet 30 april 2017.