Snappy

Snappy (раніше — Zippy)^[1] — бібліотека для швидкого стиснення і розпакування даних, написана на C++ в Google на основі LZ7; відкрита в 2011 році^[2][3]. Основна мета — досягнення високої швидкості стискання, при цьому не прагнули досягти найбільшого стискання чи сумісності з іншими бібліотеками.

Розповсюджується як C++ бібліотека з обгорткою для С. Існують порти для інших мов програмування, в тому числі для C#, Ліспа, Erlang, Go, Haskell, Haxe, Java, Lua, Node.js, Perl, PHP, Python, R, Ruby, Rust, Smalltalk.

Інформація в Snappy архівах — масив байтів.

Перші байти в потоці визначають розмір даних до стискання. Розмір зберігається у вигляді little endian «varint», тобто ціле число в коді змінної довжини (Variable-length code). Перші сім біт кожного байту використовують для даних, а восьмий біт — ознака кінця даних які описують цей розмір. Максимальний розмір — 2^32 - 1 байт.

Решта байтів потоку закодовані у вигляді одного з чотирьох типів елементу. Тип елементу зазначено в перших двох бітах першого байту (байт тегу — tag byte) елементу.^[4]

Позначення: код — посилання на словник; зсув — зсув від поточної позиції на раніше розпаковані данні з потоку; довжина — кількість байтів коду з словника.

• 00 — не стиснені дані або літерал; решта 6 бітів використовуються для збереження розміру цих даних; якщо розмір більше аніж 60 байтів, наступні 1, 2, 3 або 4 байти використовуються для збереження розміру. Кількість відведених байтів залежить від того наскільки більше від 60 вказано розмір в тег байту — 61, 62, 63 або 64 відповідно. Фактична довжина більша на один байт.
• 01 — код, що зберігає довжину (3 біта) та зсув (11 бітів); один байт після тегу використовують для решти даних бо зсуву. Фактична довжина більша на 4 байти.
• 10 — код, що зберігає довжину (6 біта) та зсув у вигляді двох байтів після. Фактична довжина більша на 1 байт.
• 11 — теж саме що і попередній код, але для зсуву відведено вже 4 байти.

Порядок байтів будь який, проте код не може йти першим позаяк зсуву буде ні на що посилатися, як і зсув не може бути рівним нулю. Розмір в кодах може перевищувати зсув, відповідно як і в RLE кодуванні — інформація при таких обставинах починає братися з початку зсуву і так до моменту коли вся довжина вичерпається.

Текст в UTF-8 кодуванні:

Матеріал з Вікіпедії — вільної енциклопедії.

Один із варіантів архівації потоку:

0000000: 53 F0 48 D0 9C D0 B0 D1 | 82 D0 B5 D1 80 D1 96 D0  SpHMња°т‚еµрЂі–а

Перший байт 0x53 — це довжина, вираз у вигляді little-endian varint (див. також Protocol Buffers — для детальної специфікації запису цілого числа змінної довжини або преамбулу в формальному описанні формату — для короткої нотатки), не стисненого потоку в байтах — 83₁₀. Наступний байт, 0xF0, містить інформацію про тип елементу: 0 згідно перших двох бітах — отже це літерал. Так як він більше аніж 60, згідно інформації в решті 6 бітах, то довжина літералу зазначена в наступному байті 0x48 — 72₁₀, а його фактична буде 72 + 1.

0000010: B0 D0 BB 20 D0 B7 20 D0 | 92 D1 96 D0 BA D1 96 D0  °л» з· В’і–кєі–п
0000020: BF D0 B5 D0 B4 D1 96 D1 | 97 20 E2 80 94 20 D0 B2  їеµдґі–ї— — вІ
0000030: D1 96 D0 BB D1 8C D0 BD | D0 BE D1 97 20 D0 B5 D0  і–л»ьЊнЅоѕї— еµн
0000040: BD D1 86 D0 B8 D0 BA D0 | BB D0 BE D0 15 2C 00 2E  Ѕц†иёкєл»оѕР.,..

0x15 — цей байт тегу вказує на тип 1 з довжиною 5 + 4 байт. Інформація щодо зсуву зазначена в наступному байті 0x2C — 44₁₀. Довжина та зсув вказує на попередньо зчитані UTF-8 дані — "педії". Далі літерал 0x00 з довжиною 0 + 1 байт та байтом 0x2E що містить дані літералу — ".".

В прикладі повторення з п'яти UTF-8 символів було вилучено в процесі стискання. Більшість інших бібліотек, наприклад як вже класичні — gzip чи bzip2, можуть стиснути цей приклад краще.

1. ↑ README.md # Introduction. Репозиторій бібліотеки від Google на GitHub (англ.). Архів оригіналу за 16 жовтня 2018. Процитовано 1 січня 2022.
2. ↑ Avram, Abel (6 квітня 2011). Google Snappy–A Fast Compressing Library. InfoQ (англ.). Архів оригіналу за 10 жовтня 2021. Процитовано 1 січня 2022.
3. ↑ Metz, Cade (24 березня 2011). Google open sources MapReduce compression. The Register (англ.). Архів оригіналу за 3 липня 2018. Процитовано 1 січня 2022.
4. ↑ format_description.txt. Репозиторій бібліотеки від Google на GitHub (англ.). Архів оригіналу за 20 листопада 2021. Процитовано 1 січня 2022.