Snappy (biblioteca)

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 16 august 2020; verificarea necesită 1 editare .
Vioi
Tip de bibliotecă de funcții și program de combinat [d]
Dezvoltator Google
Scris in C++
Sistem de operare multiplatformă
Prima editie 18 martie 2011 [1] [2]
ultima versiune
Formate de fișiere care pot fi citite rapid
Formate de fișiere generate rapid
Licență licență BSD modificată [d] [4]
Site-ul web github.com/google/snappy

Snappy (fost Zippy ) [5]  este o bibliotecă rapidă de compresie și decompresie a datelor scrisă în C++ la Google bazată pe LZ77 ; deschis în 2011 [6] [7] [8] . Scopul principal a fost de a obține o viteză mare de compresie, în timp ce cea mai mare compresie sau compatibilitate cu alte biblioteci nu a fost stabilită. În 2011, rata de compresie pe un singur nucleu Core i7 (2,26 GHz, 64 biți) a ajuns la 250 MB/s și 500 MB/s pentru decompresie [8] , dar raportul de compresie s-a dovedit a fi 20 - 100% mai jos decât gzip [9] .

Folosit în proiecte Google precum BigTable , MapReduce și sistemul intern RPC , folosit în motorul de coloane pentru MariaDB [10] , Cassandra [11] , formate de fișiere pentru ecosistemul Hadoop [12] , LevelDB [13] . MongoDB [14] , RocksDB [15] . Este foarte portabil, nu folosește inserții de asamblare .

Distribuit ca wrapper-uri peste C și C++ ; Există interfețe pentru o serie de alte limbi, inclusiv C# , Lisp , Erlang , Go , Haskell , Haxe , Java , Lua , Node.js , Perl , PHP , Python , R , Ruby , Rust , Smalltalk .

Formatul fluxului

Codificarea în Snappy este octet cu octet, pot exista doar octeți în flux. Formatul evită codarea entropică , folosind algoritmul Huffman sau codarea aritmetică , după caz.

Primul octet din flux definește dimensiunea datelor necomprimate, stocate ca un little endian „varint”, adică un întreg în cod de lungime variabilă . Primii șapte biți ai fiecărui octet sunt utilizați pentru date, iar al optulea bit este indicatorul de sfârșit pentru câmpul care descrie acea dimensiune.

Octeții rămași ai fluxului sunt codificați ca unul dintre cele patru tipuri de elemente. Tipul elementului este codificat în primii doi biți ai primului octet (byte de etichetă) al elementului. [16]

Notație: cod  - link către dicționar; shift  - treceți de la poziția curentă înapoi la fluxul deja dezambalat; lungime  - numărul de octeți de cod din dicționar.

Dimensiunea dicționarului este limitată la octeți ( pentru versiunea 1.0).

Exemplu de flux

Text original:

Wikipedia este un proiect de enciclopedie gratuit, bazat pe web, colaborativ, multilingv.

Flux comprimat:

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

Primii 2 octeți 0xCA02 sunt lungimea, exprimată ca o variantă little-endian (vezi și Protocol Buffers pentru specificarea Varint - notație întreg cu lungime variabilă), deci cel mai semnificativ octet aici este 02. 0x02CA(vizualizare LE) = 0x014A= 330 de octeți. Următorii doi octeți 0xF042indică faptul că același literal va urma la poziția 66+1

0000010: 2061 2066 7265 652c 2077 6562 2d62 6173 a gratuit, web-bas 0000020: 6564 2c20 636f 6c6c 6162 6f72 6174 6976ed, colaborativ 0000030: 652c 206d 756c 7469 6c69 6e67 7561 6c20 e, multilingv 0000040: 656e 6379 636c 6f 09 3f f0 14 70 726f 6a65 encyclo.?.proje

0x09 este un octet de etichetă de tip 01cu o lungime de 4 biți și offset 0x3F== 63 10 sau „pedia”; 0xf014 este un literal cu o lungime de 20+1 octeți

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

În exemplu, toate repetițiile unui subșir de patru sau mai multe caractere au fost eliminate prin procesul de comprimare. Majoritatea celorlalte biblioteci pot comprima mai bine acest exemplu. Spre deosebire de arhivele clasice gzip sau bzip2, Snappy nu folosește codificarea entropică (cum ar fi codul Huffman ) și nu reambalează caracterele alfabetice în secvențe de biți mai compacte în funcție de frecvența lor de apariție.

Note

  1. ↑ https://www.theregister.co.uk/2011/03/24/google_open_sources_snappy/
  2. ↑ http://www.infoq.com/news/2011/04/Snappy
  3. ↑ Versiunea 1.1.9 - 2021.
  4. ↑ https://github.com/google/snappy/blob/master/NEWS
  5. ↑ README.md  #Introducere . Depozitul Google pe GitHub . Consultat la 16 octombrie 2018. Arhivat din original la 16 octombrie 2018.
  6. ↑ Avram, Abel . Google Snappy-A Fast Compressing Library  (engleză) , InfoQ  (6 aprilie 2011). Arhivat din original pe 4 iulie 2018. Preluat la 16 octombrie 2018.
  7. ↑ Metz, Cade . Surse deschise Google MapReduce compresie  (engleză) , The Register  (24 martie 2011). Arhivat din original pe 3 iulie 2018. Preluat la 16 octombrie 2018.
  8. ↑ 12 Ximen . _ Biblioteca de compresie a datelor de la Google , linux.org.ru  (23 aprilie 2011). Arhivat din original pe 3 iulie 2015. Preluat la 16 octombrie 2018.
  9. ↑ Erdem Agaoglu. LZO vs Snappy vs LZF vs ZLIB, O comparație a algoritmilor de compresie pentru celulele adipoase din  HBază . Blog (14 aprilie 2011). Consultat la 16 octombrie 2018. Arhivat din original la 3 iulie 2018.
  10. ↑ Arhitectura de stocare ColumnStore # Compresie cu  decompresie în timp real . Baza de cunoștințe MariaDB . Consultat la 16 octombrie 2018. Arhivat din original la 16 octombrie 2017.
  11. ↑ Motor de stocare #CommitLog  . Documentație Apache Cassandra . Preluat la 16 octombrie 2018. Arhivat din original la 17 martie 2018.
  12. ↑ Native Libraries Guide # Components  . Documentație Apache Hadoop . Consultat la 16 octombrie 2018. Arhivat din original la 5 aprilie 2018.
  13. ↑ README.md  #Features . Depozitul Google pe GitHub . Consultat la 16 octombrie 2018. Arhivat din original la 18 octombrie 2017.
  14. ↑ Glosar - Documentație MongoDB  . Documentația MongoDB . Consultat la 16 octombrie 2018. Arhivat din original la 9 septembrie 2018.
  15. ↑ Compresie #Configurare  . Depozitul Facebook pe GitHub . Preluat la 16 octombrie 2018. Arhivat din original la 28 decembrie 2017.
  16. ↑ format_description.txt  . _ Depozitul Google pe GitHub . Consultat la 16 octombrie 2018. Arhivat din original la 30 aprilie 2017.