Snappy (сжатие) - Snappy (compression)

Не путать с Snappii.
Мгновенно
Оригинальный автор (ы)Джефф Дин, Санджай Гемават, Стейнар Х. Гандерсон
Разработчики)Google
изначальный выпуск18 марта 2011 г. (2011-03-18)
Стабильный выпуск
1.1.8 / 14 января 2020 г.; 10 месяцев назад (2020-01-14)[1]
Репозиторий
Отредактируйте это в Викиданных
Написано вC ++
Операционная системаКроссплатформенность
ПлатформаПортативный
Размер2 МБ
ТипСжатие данных
ЛицензияApache 2 (до 1.0.1) /Новый BSD
Интернет сайтGoogle.github.io/ snappy/

Мгновенно (ранее известный как Zippy) быстрый Сжатие данных и декомпрессия библиотека написана в C ++ от Google на основе идей LZ77 и с открытым исходным кодом в 2011 году.[2][3] Он не нацелен на максимальное сжатие или совместимость с любой другой библиотекой сжатия; вместо этого он нацелен на очень высокие скорости и разумное сжатие. Скорость сжатия 250 МБ / с а скорость распаковки составляет 500 МБ / с при использовании одного ядра примерно 2011 г. "Westmere" 2,26 ГГц Core i7 процессор работает в 64-битный режим. В коэффициент сжатия на 20–100% ниже, чем gzip.[4]

Snappy широко используется в таких проектах Google, как Большой стол, Уменьшение карты и при сжатии данных для внутренних RPC системы. Его можно использовать в проектах с открытым исходным кодом, таких как MariaDB ColumnStore,[5] Кассандра, Диван, Hadoop, LevelDB, MongoDB, RocksDB, Lucene, Искра, и InfluxDB.[6] Декомпрессия проверяется на наличие ошибок в сжатом потоке. Snappy не использует встроенный ассемблер (кроме некоторых оптимизаций[7]) и является портативным.

Формат потока

Быстрое кодирование не является побитовым, а побайтно-ориентированным (из потока отправляются или потребляются только целые байты). Формат не использует энтропийный кодировщик, подобно Дерево Хаффмана или же арифметический кодировщик.

Первые байты потока - это длина несжатых данных, хранящихся как прямой порядок байтов варинт[8], что позволяет кодирование с переменной длиной. Младшие семь битов каждого байта используются для данных, а старший бит является флагом, указывающим конец поля длины.

Остальные байты в потоке кодируются с использованием одного из четырех типов элементов. Тип элемента кодируется в младших двух битах первого байта (байт тега) элемента:[9]

  • 00 – Буквальный - несжатые данные; старшие 6 бит используются для хранения длины данных. Длины, превышающие 60, сохраняются в виде целого числа размером 1–4 байта, обозначаемого длиной 6 бит от 60 (1 байт) до 63 (4 байта).
  • 01 - Копирование с длиной, сохраненной как 3 бита, и смещением, сохраненным как 11 бит; один байт после байта тега используется для части смещения;
  • 10 - Копия с длиной, сохраненной как 6 бит байта тега, и смещением, сохраненным как двухбайтовое целое число после байта тега;
  • 11 - Копия с длиной, сохраненной как 6 бит байта тега, и смещением, сохраненным как четырехбайтовое целое число с прямым порядком байтов после байта тега;

Копия относится к словарю (только что распакованные данные). Смещение - это сдвиг от текущей позиции обратно к уже распакованному потоку. Длина - это количество байтов, которое нужно скопировать из словаря. Размер словаря был ограничен компрессором 1.0 Snappy до 32 768 байт, а в версии 1.1 был обновлен до 65 536 байт.

Пример сжатого потока

Текст

Википедия - это бесплатный многоязычный проект-энциклопедия на основе Интернета, поддерживаемый некоммерческим фондом Викимедиа. Его 19 миллионов статей (более 3,6 миллиона на английском языке) были написаны совместно добровольцами со всего мира, и почти все его статьи могут редактироваться любым, у кого есть доступ к сайту.

могут быть сжаты до этого в виде шестнадцатеричных данных с пояснениями:

0000000: ca02 f042 5769 6b69 7065 6469 6120 6973 ... BВикипедия - это

Первые 2 байта, ca02 - длина, как вариант с прямым порядком байтов (см. Буферы протокола для спецификации varint)[8]. Таким образом, самый старший байт - «02». 0x02ca (varint) = 0x014a = 330 байт. Следующие два байта, 0xf042, указывают, что следует литерал из 66 + 1 байт.

0000010: 2061 2066 7265 652c 2077 6562 2d62 6173 a бесплатно, web-bas0000020: 6564 2c20 636f 6c6c 6162 6f72 6174 6976 ed, коллаборатив 0000030: 652c 206d 756c 7469 6c69 6e67 7561 6c20 e, многоязычный 67940: 636794009 3ff0 8170 726f 6a65 encyclo.?..proje

0x09 - байт тега типа 01 длиной - 4 = 0102 = 210 и смещение = 0x03f = 63 или "pedia";
0xf081 - это литерал длиной 129 + 1 байт

В этом примере все общие подстроки с четырьмя и более символами были удалены в процессе сжатия. Более распространенные компрессоры могут сжимать это лучше. В отличие от таких методов сжатия, как gzip и bzip2, здесь нет энтропийное кодирование используется для упаковки алфавита в битовый поток.

Интерфейсы

Распределения Snappy включают привязки C ++ и C. Сторонние привязки и порты включают[10] C #, Common Lisp, Erlang, Идти, Haskell, Lua, Ява, Node.js, Perl, PHP, Python, р, Рубин, Ржавчина, Болтовня, и OpenCL[11][12].

Смотрите также

Рекомендации

  1. ^ "Релизы - google / snappy". Получено 21 августа 2020 - через GitHub.
  2. ^ "Google Snappy - библиотека быстрого сжатия". InfoQ. Получено 1 августа, 2011.
  3. ^ Сжатие MapReduce с открытыми исходными кодами Google. Во имя скорости // Реестр, 24.03.2011
  4. ^ «Snappy: быстрый компрессор / декомпрессор: Readme». Код Google. Архивировано из оригинал 8 сентября 2015 г.. Получено 1 августа, 2011."Snappy vs lzo vs zlib".
  5. ^ "Архитектура хранилища ColumnStore". База знаний MariaDB.
  6. ^ резкий. Быстрый компрессор / декомпрессор - Страница проекта в Google Code
  7. ^ «Добавьте директиву выравнивания цикла, чтобы обойти снижение производительности. · Google / snappy @ 824e671». GitHub.
  8. ^ а б «Буферы протокола - кодирование: объяснение кодирования буферов протокола».
  9. ^ "GitHub - google / snappy: быстрый компрессор / декомпрессор". 11 ноября 2019 г. - через GitHub.
  10. ^ "энергичный". резкий.
  11. ^ "Xilinx". Xilinx.
  12. ^ "InAccel". InAccel.

внешняя ссылка