Snappy (сжатие)
| Оригинальный автор(ы) | Джефф Дин , Санджай Гемават , Стейнар Х. Гундерсон |
|---|---|
| Разработчики) | |
| Начальная версия | 18 марта 2011 г. |
| Стабильная версия | 1.1.10
/ 9 марта 2023 г [1] |
| Репозиторий | |
| Написано в | С++ |
| Операционная система | Кросс-платформенный |
| Платформа | Портативный |
| Размер | 1,1 МБ |
| Тип | Сжатие данных |
| Лицензия | Apache 2 (до 1.0.1)/ Новый BSD |
| Веб-сайт | Google |
| Расширение имени файла |
.с |
|---|---|
| Тип интернет-СМИ |
приложение/x-snappy-framed |
| Магическое число | ff 06 00 00 73 4e 61 50 70 59 ( FF 06 00 00 "sNaPpY") |
| Тип формата | Сжатие данных |
| Открытый формат ? | да |
| Свободный формат ? | да |
| Веб-сайт | github |
Snappy (ранее известная как Zippy ) — это библиотека быстрого сжатия и распаковки данных , написанная на C++ компанией Google на основе идей LZ77 и открытая в 2011 году. [3] [4] Он не нацелен на максимальное сжатие или совместимость с какой-либо другой библиотекой сжатия; вместо этого он нацелен на очень высокие скорости и разумное сжатие. Скорость сжатия составляет 250 МБ/с , а скорость распаковки — 500 МБ/с при использовании одного ядра процессора Core i7 «Westmere» 2,26 ГГц примерно 2011 года выпуска , работающего в 64-битном режиме . Степень сжатия на 20–100% ниже, чем у gzip . [5]
Snappy широко используется в таких проектах Google, как Bigtable , MapReduce Google , а также при сжатии данных для внутренних систем RPC . Его можно использовать в проектах с открытым исходным кодом, таких как MariaDB ColumnStore , [6] Кассандра , Couchbase , Hadoop , LevelDB , MongoDB , RocksDB , Lucene , Spark, InfluxDB , [7] и Цеф . [8] Firefox использует Snappy для сжатия данных в localStorage . [9] Распаковка проверяется для обнаружения любых ошибок в сжатом потоке. Snappy не использует встроенный ассемблер (за исключением некоторых оптимизаций). [10] ) и является портативным.
Формат потока [ править ]
Кодирование Snappy является не побитовым, а байтовым (из потока отправляются или потребляются только целые байты). В этом формате не используется энтропийный кодер , такой как кодирование Хаффмана или арифметическое кодирование .
Первые байты потока — это длина несжатых данных, хранящихся как переменная с прямым порядком байтов . [11] : секция 1 что позволяет использовать код переменной длины . Младшие семь бит каждого байта используются для данных, а старший бит является флагом, указывающим конец поля длины.
Остальные байты потока кодируются с использованием одного из четырех типов элементов. Тип элемента кодируется в двух младших битах первого байта ( байта тега ) элемента: [12]
- 00 – Литерал – несжатые данные; Старшие 6 бит используются для хранения длины (len-1) данных. Длины больше 60 сохраняются в виде целых чисел длиной 1–4 байта, обозначенных 6-битной длиной от 60 (1 байт) до 63 (4 байта).
- 01 – Копия с длиной, хранящейся в 3 битах, и смещением, хранящимся в 11 битах; один байт после байта тега используется для части смещения;
- 10 – Копия, длина которой хранится в виде 6 бит байта тега, а смещение хранится в виде двухбайтового целого числа после байта тега;
- 11 – Копия с длиной, хранящейся в виде 6 бит байта тега, и смещением, сохраненным в виде четырехбайтового целого числа с прямым порядком байтов после байта тега;
Копия относится к словарю (только что распакованные данные). Смещение — это сдвиг от текущей позиции обратно к уже распакованному потоку. Длина — это количество байтов, которые нужно скопировать из словаря. Размер словаря был ограничен компрессором Snappy версии 1.0 до 32 768 байт и обновлен до 65 536 в версии 1.1.
Полное официальное описание формата snappy можно найти в репозитории Google GitHub. [11]
Пример сжатого потока [ править ]
Текст
Википедия — это бесплатный сетевой совместный многоязычный энциклопедический проект.
может быть сжато до этого, показано в виде шестнадцатеричных данных с пояснениями:
000000 51 f0 42 57 69 6b 69 70 65 64 69 61 20 69 73 20 >Q.BВикипедия < 000010 61 20 66 72 65 65 2c 20 77 65 62 2d 62 61 73 65 >бесплатная веб-база< 000020 64 2c 20 63 6f 6c 6c 61 62 6f 72 61 74 69 76 65 >d, совместная работа< 000030 2c 20 6d 75 6c 74 69 6c 69 6e 67 75 61 6c 20 65 >, многоязычный e<
Поток начинается с длины несжатых данных в виде варинта. [11] : секция 1 – таким образом, первый байт со свободным старшим битом соответствует длине 51 16 =81 байт.
Первый блок должен быть литералом, и ему соответствует f042 : первый байт разбивается на f0 16 ⇒ len−1=111100 2 ;type=00 2 ; тип 0 означает литерал, а длина-1, равная 111100 2 =60, означает, что длина считывается из следующего байта, в данном случае 42 16 =66. Далее следуют первые 66 байтов текста (« Википедия — бесплатная сетевая совместная многоязычная энциклопедия »). [11] : 2.1
000040 6e 63 79 63 6c 6f 09 3f 1c 70 72 6f 6a 65 63 74 >ncycle.?.project< 000050 2e >.<
Заголовок следующего блока состоит из 093f , разбитого на 09 16 ⇒ off h =000 2 ,len−4=010 2 ;type=01 2 : тип 1 указывает на «копию со смещением в 1 байт»: длина копирования работает. out до 010 2 +4=6 байт, а смещение представляет собой 11-битное целое число, старшие биты которого не совпадают с h , а младшие биты являются следующим байтом: 3f , поэтому {off h }{3f 16 }=00000111111 2 =63 . [11] : 2.2,2.2.1
Это означает копирование 6 байтов, начиная с 63 байтов назад – поскольку уже скопировано 67 байтов, это означает копирование 6 байтов, начиная с позиции 4 (с пятого байта), что создает « педиа ».
Этот блок не имеет другого содержимого, поэтому следующий блок начинается сразу после – 1c 16 ⇒ len−1=000111 2 ;type=00 2 , т.е. литерала длины 000111 2 +1=8. [11] : 2.1 Далее следует заключительная часть текста (« проект. »).
В этом примере все общие подстроки с четырьмя и более символами были удалены в процессе сжатия. Более распространенные компрессоры могут сжать это лучше. не используется энтропийное кодирование В отличие от методов сжатия, таких как gzip и bzip2, для упаковки алфавита в битовый поток .
Формат кадра [ править ]
Поток Snappy поддерживает входы общим размером до 4 ГиБ-1. [11] : секция 1 и может добавить значительные накладные расходы к разделам, которые не сжаты или недостаточно сжаты, а также не имеют самоидентификации и не имеют механизма целостности данных, кроме простой проверки размера выходных данных.
Для решения этих проблем используется формат кадра Snappy. [2] Можно использовать «Snappy Framed», который разбивает входные данные на фрагменты размером до 64 КБ. [2] : 4.2,4.3 разделены 4-байтовыми заголовками блоков (однобайтовый идентификатор и трехбайтовая длина): [2] : секция 1
- «Идентификатор потока» с типом FF 16 должен запускать поток и должен состоять исключительно из «sNaPpY» в ASCII , [2] : 4.1
- «Сжатые данные» с типом 0 содержат сжатый поток Snappy, [2] : 4.2
- «Несжатые данные» типа 1 содержат данные для дословного копирования на выход. [2] : 4.3
Оба типа фрагментов данных также содержат CRC-32C контрольную сумму несжатых данных .
Фрагменты типов 2–7F 16 зарезервированы и должны приводить к ошибкам. [2] : 4.5 Декомпрессоры типов 80 16 -FE 16 могут игнорироваться декомпрессорами, которые их не понимают. [2] : 4.4,4.6
Интерфейсы [ править ]
Дистрибутивы Snappy включают привязки C++ и C. Сторонние привязки и порты включают в себя [13] C# , Common Lisp , Crystal (язык программирования) , Erlang , Go , Haskell , Lua , Java , Nim , Node.js , Perl , PHP , Python , R , Ruby , Rust , Smalltalk и OpenCL . [14] [15] с интерфейсом командной строки . Также доступна программа [16]
См. также [ править ]
Ссылки [ править ]
- ^ «Релизы — google/snappy» . Проверено 4 октября 2023 г. — через GitHub .
- ^ Перейти обратно: а б с д Это ж г час я «Описание формата кадрирования Snappy» . Гитхаб . 26 октября 2021 г.
- ^ «Google Snappy – библиотека быстрого сжатия» . ИнфоQ . Проверено 1 августа 2011 г.
- ^ Сжатие MapReduce с открытым исходным кодом Google. Во имя скорости // The Register, 24 марта 2011 г.
- ^ «Snappy: быстрый компрессор/декомпрессор: Readme» . Гугл-код . Архивировано из оригинала 8 сентября 2015 года . Проверено 1 августа 2011 г. «Snappy против lzo против zlib» .
- ^ «Архитектура хранения данных ColumnStore» . База знаний MariaDB .
- ^ быстро. Быстрый компрессор/декомпрессор — страница проекта в Google Code
- ^ «Сжатие — Документация Ceph» . Проверено 03 января 2024 г.
- ^ «SnappyUtils.cpp — mozsearch» . Проверено 03 января 2024 г.
- ^ «Добавьте директиву выравнивания цикла, чтобы обойти снижение производительности. · google/snappy@824e671» . Гитхаб .
- ^ Перейти обратно: а б с д Это ж г «Описание сжатого формата Snappy» . Гитхаб . 26 октября 2021 г.
- ^ «GitHub — google/snappy: быстрый компрессор/декомпрессор» . 11 ноября 2019 г. – через GitHub.
- ^ «шустрый» . быстрый .
- ^ «Ксилинкс» . Ксилинкс .
- ^ «ИнАксел» . ИнАксел .
- ^ «snappy-tools: snappy(1): мгновенное сжатие и распаковка с кадрированием и без него» . исходная хижина . Проверено 15 февраля 2024 г.
Внешние ссылки [ править ]
сжатия данных Методы |
|---|
