Snappy (сжатие)

Библиотека быстрого сжатия и распаковки данных, написанная на C ++ от Google

Snappy

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

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

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

• 1 Формат потока
• 2 Пример сжатого потока
• 3 Интерфейсы
• 4 См. Также
• 5 Ссылки
• 6 Внешние ссылки

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

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

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

• 00 - Literal - несжатые данные; старшие 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 байт.

Текст

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

может быть сжат до этого, показанного в шестнадцатеричном формате данные с пояснениями:

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

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

0000010: 2061 2066 7265 652c 2077 6562 2d62 6173 a free, web-bas 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 encyclo.?..proje

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

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

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

• Портал бесплатного программного обеспечения с открытым исходным кодом

• Zstandard

• Быстрый список рассылки