Snappy
| Тип | архіватор |
|---|---|
| Автор | Джефф Дін, Sanjay Ghemawat[en], Steinar H. Gunderson |
| Розробник | |
| Стабільний випуск | 1.1.9 (4 травня 2021) |
| Операційна система | крос-платформовий |
| Мова програмування | C++ |
| Ліцензія | модифікована ліцензія BSD |
| Репозиторій | github.com/google/snappy |
| Вебсайт | github.com/google/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 — для детальної специфікації запису цілого числа змінної довжини або преамбулу в формальному описанні формату — для короткої нотатки), не стисненого потоку в байтах — 8310.
Наступний байт, 0xF0, містить інформацію про тип елементу: 0 згідно перших двох бітах — отже це літерал. Так як він більше аніж 60, згідно інформації в решті 6 бітах, то довжина літералу зазначена в наступному байті 0x48 — 7210, а його фактична буде 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 — 4410. Довжина та зсув вказує на попередньо зчитані UTF-8 дані — "педії". Далі літерал 0x00 з довжиною 0 + 1 байт та байтом 0x2E що містить дані літералу — ".".
В прикладі повторення з п'яти UTF-8 символів було вилучено в процесі стискання. Більшість інших бібліотек, наприклад як вже класичні — gzip чи bzip2, можуть стиснути цей приклад краще.
Зноски[ред. | ред. код]
- ↑ README.md # Introduction. Репозиторій бібліотеки від Google на GitHub (англ.). Архів оригіналу за 16 жовтня 2018. Процитовано 1 січня 2022.
- ↑ Avram, Abel (6 квітня 2011). Google Snappy–A Fast Compressing Library. InfoQ (англ.). Архів оригіналу за 10 жовтня 2021. Процитовано 1 січня 2022.
- ↑ Metz, Cade (24 березня 2011). Google open sources MapReduce compression. The Register (англ.). Архів оригіналу за 3 липня 2018. Процитовано 1 січня 2022.
- ↑ format_description.txt. Репозиторій бібліотеки від Google на GitHub (англ.). Архів оригіналу за 20 листопада 2021. Процитовано 1 січня 2022.
| |||||||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||