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

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

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

Формат потока [ править ]

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

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

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

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

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

Полное официальное описание формата snappy можно найти в репозитории google github [10] .

Пример сжатого потока [ править ]

Текст

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

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

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

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

0000010: 2061 2066 7265 652c 2077 6562 2d62 6173 бесплатный веб-сайт0000020: 6564 2c20 636f 6c6c 6162 6f72 6174 6976 ed, коллаборатив0000030: 652c 206d 756c 7469 6c69 6e67 7561 6c20 e, многоязычный0000040: 656e 6379 636c 6f 09 3ff0 81 70 726f 6a65 энциклопедия .?..proje

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

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

Интерфейсы [ править ]

Распределения Snappy включают привязки C ++ и C. Сторонние привязки и порты включают [11] C # , Common Lisp , Erlang , Go , Haskell , Lua , Java , Node.js , Perl , PHP , Python , R , Ruby , Rust , Smalltalk и OpenCL . [12] [13]

См. Также [ править ]

  • Zстандарт

Ссылки [ править ]

  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. ^ a b «Буферы протокола - Кодирование: Объяснение кодирования буферов протокола» .
  9. ^ "GitHub - google / snappy: быстрый компрессор / декомпрессор" . 11 ноября 2019 г. - через GitHub.
  10. ^ https://github.com/google/snappy/blob/master/format_description.txt
  11. ^ "резкий" . резкий .
  12. ^ "Xilinx" . Xilinx .
  13. ^ "InAccel" . InAccel .

Внешние ссылки [ править ]

  • Список рассылки Snappy