Snappy (komprese) - Snappy (compression)

Nesmí být zaměňována s Snappii.
Elegantní
Původní autořiJeff Dean, Sanjay Ghemawat, Steinar H. Gunderson
VývojářiGoogle
První vydání18. března 2011 (2011-03-18)
Stabilní uvolnění
1.1.8 / 14. ledna 2020; Před 10 měsíci (2020-01-14)[1]
Úložiště
Upravte to na Wikidata
NapsánoC ++
Operační systémCross-platform
PlošinaPřenosný
Velikost2 MB
Typkomprese dat
LicenceApache 2 (až 1.0.1) /Nová BSD
webová stránkaGoogle.github.io/elegantní/

Elegantní (dříve známé jako Zipy) je rychlý komprese dat a dekomprese knihovna napsaná v C ++ Google na základě nápadů od LZ77 a open-source v roce 2011.[2][3] Jeho cílem není maximální komprese ani kompatibilita s jakoukoli jinou knihovnou komprese; místo toho usiluje o velmi vysoké rychlosti a rozumnou kompresi. Rychlost komprese je 250 MB / s a rychlost dekomprese je 500 MB / s při použití jediného jádra kolem roku 2011 „Westmere“ 2,26 GHz Core i7 běžící procesor 64bitový režim. The kompresní poměr je o 20–100% nižší než gzip.[4]

Snappy je široce používán v projektech Google, jako je Bigtable, MapReduce a při kompresi dat pro interní Google RPC systémy. Může být použit v open-source projektech, jako je MariaDB ColumnStore,[5] Cassandra, Couchbase, Hadoop, LevelDB, MongoDB, RocksDB, Lucene, Jiskra, a InfluxDB.[6] Dekomprese se testuje, aby se zjistily chyby v komprimovaném streamu. Snappy nepoužívá inline assembler (kromě některých optimalizací[7]) a je přenosný.

Formát streamu

Snappy kódování není bitově orientované, ale bajtově orientované (ze streamu jsou emitovány nebo spotřebovány pouze celé bajty). Formát používá číslo kodér entropie, jako Huffmanův strom nebo aritmetický kodér.

První bajty datového proudu jsou délka nekomprimovaných dat uložených jako a malý Endian varint[8], což umožňuje kódování s proměnnou délkou. Dolních sedm bitů každého bajtu se používá pro data a horní bit je příznak označující konec pole délky.

Zbývající bajty v proudu jsou kódovány pomocí jednoho ze čtyř typů prvků. Typ prvku je zakódován do spodních dvou bitů prvního bajtu (bajt značky) prvku:[9]

  • 00 – Doslovný - nekomprimovaná data; horních 6 bitů se používá k ukládání délky dat. Délky větší než 60 jsou uloženy v 1-4 bajtovém čísle označeném 6bitovou délkou 60 (1 bajt) až 63 (4 bajty).
  • 01 - Kopie s délkou uloženou jako 3 bity a offset uloženou jako 11 bitů; jeden bajt za bajtem značky se použije pro část ofsetu;
  • 10 - Kopie s délkou uloženou jako 6 bitů bajtu značky a offset uložený jako dvoubajtové celé číslo po bajtu značky;
  • 11 - Kopie s délkou uloženou jako 6 bitů bajtu tagu a offsetem uloženým jako čtyřbajtové malé endianské celé číslo po bajtu tagu;

Kopie odkazuje na slovník (právě dekomprimovaná data). Posun je posun z aktuální polohy zpět do již dekomprimovaného proudu. Délka je počet bajtů, které se mají zkopírovat ze slovníku. Velikost slovníku byla omezena kompresorem 1.0 Snappy na 32 768 bajtů a ve verzi 1.1 aktualizována na 65 536.

Příklad komprimovaného streamu

Text

Wikipedia je bezplatný webový víceúčelový encyklopedický projekt založený na spolupráci podporovaný neziskovou nadací Wikimedia Foundation. Jeho 19 milionů článků (více než 3,6 milionu v angličtině) bylo napsáno ve spolupráci dobrovolníků z celého světa a téměř všechny jeho články může upravovat kdokoli s přístupem na stránky.

může být na toto komprimováno, zobrazeno jako hexadecimální data s vysvětlením:

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

První 2 bajty, ca02 jsou délka jako variace na malý endian (viz Vyrovnávací paměti protokolu pro specifikaci varintu)[8]. Nejvýznamnějším bajtem je tedy „02“. 0x02ca (varint) = 0x014a = 330 bajtů. Další dva bajty, 0xf042, označují, že následuje doslovný počet 66 + 1 bajtů

0000010: 2061 2066 7265 652c 2077 6562 2d62 6173 a zdarma, web-bas0000020: 6564 2c20 636f 6c6c 6162 6f72 6174 6976 ed, spolupracovativ0000030: 652c 206d 756c 7469 6c69 6e67 7561 6c20 e, vícejazyčný 0000040 6 6509 3ff0 8170 726f 6a65 encyklopedie.? Projekt

0x09 je tag-byte typu 01 s délkou - 4 = 0102 = 210 a offset = 0x03f = 63 nebo „pedia“;
0xf081 je literál o délce 129 + 1 bajtů

V tomto příkladu byly všechny běžné podřetězce se čtyřmi nebo více znaky odstraněny procesem komprese. Běžnější kompresory to mohou lépe komprimovat. Na rozdíl od kompresních metod, jako jsou gzip a bzip2, neexistuje kódování entropie slouží k zabalení abecedy do bitového proudu.

Rozhraní

Snappy distribuce zahrnují vazby C ++ a C. Vazby a porty poskytované třetí stranou zahrnují[10] C#, Společný Lisp, Erlang, Jít, Haskell, Lua, Jáva, Node.js, Perl, PHP, Krajta, R, Rubín, Rez, Pokec, a OpenCL[11][12].

Viz také

Reference

  1. ^ „Vydání - google / snappy“. Citováno 21. srpna 2020 - přes GitHub.
  2. ^ „Google Snappy - knihovna s rychlou kompresí“. InfoQ. Citováno 1. srpna 2011.
  3. ^ Otevřené zdroje Google MapReduce komprese. Ve jménu rychlosti // Registr, 2011-03-24
  4. ^ "Snappy: Rychlý kompresor / dekompresor: Readme". Google Code. Archivovány od originál 8. září 2015. Citováno 1. srpna 2011.„Snappy vs lzo vs zlib“.
  5. ^ „Architektura úložiště ColumnStore“. MariaDB KnowledgeBase.
  6. ^ elegantní. Rychlý kompresor / dekompresor - Stránka projektu v Google Code
  7. ^ „Přidejte směrnici pro zarovnání smyčky a obejdete regresi výkonu. · Google / snappy @ 824e671“. GitHub.
  8. ^ A b "Vyrovnávací paměti protokolu - kódování: Vysvětlení kódovacích vyrovnávacích pamětí protokolu".
  9. ^ „GitHub - google / snappy: rychlý kompresor / dekompresor“. 11. listopadu 2019 - prostřednictvím GitHub.
  10. ^ "elegantní". elegantní.
  11. ^ "Xilinx". Xilinx.
  12. ^ „InAccel“. InAccel.

externí odkazy