Snappy (knihovna)

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 16. srpna 2020; ověření vyžaduje 1 úpravu .
Elegantní
Typ knihovna funkcí a program ke kombinaci [d]
Vývojář Google
Zapsáno v C++
Operační systém multiplatformní
První vydání 18. března 2011 [1] [2]
Nejnovější verze
Čitelné formáty souborů elegantní
Vygenerované formáty souborů elegantní
Licence upravená licence BSD [d] [4]
webová stránka github.com/google/snappy

Snappy (dříve Zippy ) [5]  je knihovna pro rychlou kompresi a dekompresi dat napsaná v C++ u Google založená na LZ77 ; otevřena v roce 2011 [6] [7] [8] . Hlavním cílem bylo dosáhnout vysoké rychlosti komprese, přičemž nebyla nastavena nejvyšší komprese ani kompatibilita s jinými knihovnami. V roce 2011 dosáhla kompresní rychlost na jednom jádru Core i7 (2,26 GHz, 64 bitů) 250 MB/s a 500 MB/s pro dekompresi [8] , ale kompresní poměr se ukázal být 20 - 100 % nižší než gzip [9] .

Používá se v projektech Google, jako je BigTable , MapReduce a interní systém RPC , používaný ve sloupcovém enginu pro MariaDB [10] , Cassandra [11] , formáty souborů pro ekosystém Hadoop [12] , LevelDB [13] . MongoDB [14] , RocksDB [15] . Je vysoce přenosný, nepoužívá vložky assembleru .

Distribuováno jako obaly přes C a C++ ; rozhraní existují pro řadu dalších jazyků, včetně C# , Lisp , Erlang , Go , Haskell , Haxe , Java , Lua , Node.js , Perl , PHP , Python , R , Ruby , Rust , Smalltalk .

Formát streamu

Kódování ve Snappy je bajt po bajtu, ve streamu mohou být pouze bajty. Formát se vyhýbá entropickému kódování pomocí Huffmanova algoritmu nebo aritmetického kódování podle potřeby.

První bajt v proudu definuje velikost nekomprimovaných dat uložených jako little endian "varint", tj. celé číslo v kódu s proměnnou délkou . Prvních sedm bitů každého bajtu se používá pro data a osmý bit je koncový příznak pro pole popisující tuto velikost.

Zbývající bajty proudu jsou zakódovány jako jeden ze čtyř typů prvků. Typ prvku je zakódován v prvních dvou bitech prvního bajtu (bajtu značky) prvku. [16]

Zápis: kód  - odkaz na slovník; shift  - posun z aktuální pozice zpět na již rozbalený stream; délka  - počet bajtů kódu ze slovníku.

Velikost slovníku je omezena na bajty ( pro verzi 1.0).

Příklad toku

Původní text:

Wikipedie je bezplatný, webový, spolupracující, vícejazyčný encyklopedický projekt.

Komprimovaný stream:

0000000: ca02 f042 5769 6b69 7065 6469 6120 6973 ...BWikipedie je

První 2 bajty 0xCA02 jsou délka vyjádřená jako little-endian varint (viz také Protokolové vyrovnávací paměti pro specifikaci varint - celočíselná notace s proměnnou délkou), takže nejvýznamnější byte je zde 02. 0x02CA(pohled LE) = 0x014A= 330 bajtů. Další dva bajty 0xF042označují, že stejný literál bude následovat na pozici 66+1

0000010: 2061 2066 7265 652c 2077 6562 2d62 6173 bezplatný web-bas 0000020: 6564 2c20 636f 6c6c 6162 6f72 6174 6976ed, spolupracující 0000030: 652c 206d 756c 7469 6c69 6e67 7561 6c20 e, vícejazyčný 0000040: 656e 6379 636c 6f 09 3f f0 14 70 726f 6a65 encyklopedie.?.proje

0x09 je bajt značky typu 01s délkou 4 bitů a offsetem 0x3F== 63 10 nebo "pedia"; 0xf014 je literál o délce 20+1 bajtů

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

V tomto příkladu byla všechna opakování podřetězce čtyř nebo více znaků eliminována procesem komprese. Většina ostatních knihoven dokáže tento příklad komprimovat lépe. Na rozdíl od klasických archivátorů gzip nebo bzip2 nepoužívá Snappy entropické kódování (jako je Huffmanův kód ) a nepřebaluje abecední znaky do kompaktnějších bitových sekvencí podle frekvence jejich výskytu.

Poznámky

  1. ↑ https://www.theregister.co.uk/2011/03/24/google_open_sources_snappy/
  2. ↑ http://www.infoq.com/news/2011/04/Snappy
  3. ↑ Vydání 1.1.9 – 2021.
  4. ↑ https://github.com/google/snappy/blob/master/NEWS
  5. ↑ README.md  #Úvod . Úložiště Google na GitHubu . Získáno 16. října 2018. Archivováno z originálu 16. října 2018.
  6. ↑ Avram, Abel . Google Snappy-A Fast Compressing Library  (anglicky) , InfoQ  (6. dubna 2011). Archivováno z originálu 4. července 2018. Staženo 16. října 2018.
  7. ↑ Metz, Cade . Google open source komprese MapReduce  (anglicky) , The Register  (24. března 2011). Archivováno z originálu 3. července 2018. Staženo 16. října 2018.
  8. ↑ 12 Ximen . _ Knihovna pro kompresi dat od společnosti Google , linux.org.ru  (23. dubna 2011). Archivováno z originálu 3. července 2015. Staženo 16. října 2018.
  9. ↑ Erdem Agaoglu. LZO vs Snappy vs LZF vs ZLIB, Srovnání kompresních algoritmů pro tukové buňky v  HBase . Blog (14. dubna 2011). Získáno 16. října 2018. Archivováno z originálu 3. července 2018.
  10. ↑ Architektura úložiště ColumnStore # Komprese s dekompresí v reálném čase  . Znalostní báze MariaDB . Získáno 16. října 2018. Archivováno z originálu 16. října 2017.
  11. ↑ Storage Engine #CommitLog  . Dokumentace Apache Cassandra . Získáno 16. října 2018. Archivováno z originálu 17. března 2018.
  12. ↑ Nativní knihovny Guide # Components  . Dokumentace Apache Hadoop . Získáno 16. října 2018. Archivováno z originálu 5. dubna 2018.
  13. ↑ README.md  #Features . Úložiště Google na GitHubu . Získáno 16. října 2018. Archivováno z originálu 18. října 2017.
  14. ↑ Slovník - Dokumentace MongoDB  . Dokumentace MongoDB . Získáno 16. října 2018. Archivováno z originálu 9. září 2018.
  15. ↑ Komprese #Konfigurace  . Úložiště Facebooku na GitHubu . Získáno 16. října 2018. Archivováno z originálu 28. prosince 2017.
  16. ↑ format_description.txt  . _ Úložiště Google na GitHubu . Získáno 16. října 2018. Archivováno z originálu 30. dubna 2017.