WikiSort.ru - Не сортированное

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

Snappy часто используется в проектах Google, например, таких как BigTable, MapReduce и во внутренней системе RPC. Библиотеку можно использовать в MariaDB ColumnStore,^[7] Cassandra,^[8] Hadoop,^[9] LevelDB^[en],^[10] MongoDB,^[11] RocksDB^[en][12] и Lucene^{[источник не указан 111 дней]}. По большей части, в Snappy не используются ассемблерные вставки, также, библиотека является переносимой.

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

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

Первый байт в потоке определяет размер несжатых данных, хранится в виде little endian «varint», то есть целое число в коде переменной длины^[en]. Первые семь бит каждого байта используются для данных, а восьмой бит — флаг конца поля, описывающего этот размер.

Остальные байты потока закодированы в виде одного из четырёх типов элемента. Тип элемента закодирован в первые два бита первого байта (байт-тега — tag byte) элемента.^[13]

Обозначения: код — ссылка на словарь; сдвиг — сдвиг от текущей позиции назад к уже распакованному потоку; длина — количество байтов кода из словаря.

• 00 — несжатые данные; последующие 6 битов используются для хранения размера данных; если размер занимает более 60 байтов, будет использован код нефиксированной ширины
• 01 — код, хранящий длину (3 бита) и сдвиг (11 битов); один байт после тега используется для невместившейся части сдвига
• 10 — код, хранящий длину (6 бит) тега и сдвиг в виде двух-байтового числа после тега
• 11 — код, хранящий длину (6 бит) тега и сдвиг в виде четырёх-байтового числа после тега

Размер словаря ограничен ${\displaystyle 2^{16}}$ байтами (${\displaystyle 2^{15}}$ для версии 1.0).

Пример потока

Оригинальный текст:

Wikipedia is a free, web-based, collaborative, multilingual encyclopedia project.

Сжатый поток:

0000000: ca02 f042 5769 6b69 7065 6469 6120 6973  ...BWikipedia is

Первые 2 байта 0xCA02 — это длина, выраженная в виде little-endian varint (см. также Protocol Buffers для спецификации varint — записи целого числа переменной длины), таким образом, наиболее значимый байт здесь — это 02. 0x02CA (вид LE) = 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, collaborativ
0000030: 652c 206d 756c 7469 6c69 6e67 7561 6c20  e, multilingual
0000040: 656e 6379 636c 6f09 3ff0 8101 7072 6f6a  encyclo.?...proj

0x09 — это байт-тег типа 01 с длиной 4 бита и сдвигом = 0x3F = 63₁₀ или "pedia "; 0xf08101 — это литерал с длиной 129+1 байт

0000050: 6563 742e 0000 0000 0000 0000 0000 0000  ect.

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

Интерфейсы

Snappy распространяется в виде обёрток над C и C++. Существуют версии для следующих языков:

См. также

• Snappy mailing list

Примечания