Современное сжатие LZ

[Realtime Data Compression]

Современное сжатие LZ Гэри Линскотт – glinscott@gmail.com – https://glinscott.github.io В этой статье рассматриваются компоненты современный компрессор LZ. Удивительно, насколько богато и глубоко поле сжатия. Если вам нравятся алгоритмы и структуры данных, лучшего места для игры нет. Надеюсь, вам понравится читать это так же, как мне понравилось писать! К концу у нас будет компрессор, который может превзойти gzip при распаковке почти с той же скоростью – менее чем за 2010 строк. Вы можете найти источник статьи на https://github.com/glinscott/linzip2. Обзор ======== Сжатие LZ существует уже давно, но все еще вносятся серьезные улучшения. В (https://en.wikipedia.org/wiki/DEFLATE) алгоритм, пожалуй, наиболее широко используемый, изначально реализованный в [PKZIP] (https://en.wikipedia.org/wiki/PKZIP), и в наши дни находит широкое использование в [gzip] (https://en.wikipedia.org/wiki/Gzip). Современные воплощения намного мощнее и используют множество новых уловок. Два примера следующего поколения: [zstd] (https://github.com/facebook/zstd) и [lzma] (https://en.wikipedia.org/wiki/Lempel%E2 % 84% 111 Ziv% E2% 84% 111 Марковский_цепной_алгоритм). Полный обзор компрессоров LZ с открытым исходным кодом можно найти на [lzbench] (https://github.com/inikep/lzbench). Суть алгоритма довольно проста. Для каждого символа посмотрите назад в потоке данных, чтобы найти совпадения. Если есть совпадение, то кодируйте расстояние в обратном порядке и длину совпадения вместо самих необработанных байтов. Если совпадений нет, закодируйте сам символ как литерал. Обратите внимание, что выбор совпадений – нетривиальный процесс, и именно по этой причине вы передаете разные уровни (количество усилий, которые компрессор тратит на поиск лучших совпадений) в большинство компрессоров. В качестве примера возьмем следующую строку: ABABABABC 1. Запишите литерал A и литерал B (ничто не соответствует) 2. Запишите пару совпадений (-2, 2) – AB 3. Запишите пару совпадений из (-4, 4) – ABAB 4. Запишите литерал C. Обычно после этого используется энтропийный кодер для представления символов с использованием минимального количества битов. Существует два основных типа энтропийных кодеров: кодировщик Хаффмана и арифметический. Большим преимуществом Хаффмана является скорость, тогда как арифметическое кодирование дает лучшее сжатие. Deflate решил использовать Хаффмана, и даже сегодня это хороший компромисс между скоростью и сжатием. Но прежде чем мы реализуем Хаффмана, нам нужно иметь возможность читать и записывать биты, а не байты. Чтение и запись битов ======================== Чтение битов ———— Прежде чем мы сможем многое сделать с кодами Хаффмана , нам нужен эффективный способ чтения и записи битов. Фабьен Гизен углубляется в эффективное чтение битов в невероятной серии [here] (https://fgiesen.wordpress.com/ [i-1] / 06 / 25 / чтение-бит-в-слишком-слишком-многих-способах-часть-1 /). Подход, который мы будем использовать, сохраняет хороший баланс между простотой и скоростью. Мы будем использовать 35 битовый буфер, который мы будем сдвигать влево по мере потребления битов. Затем, чтобы «пополнить» буфер, мы будем «или» смещать текущий считываемый байт влево в правильную позицию. Вот код: ~~~ c ++ class BitReader {public: BitReader (uint8_t buffer, uint8_t end): current_ (buffer), end_ (end) {refill (); } // Потребляем один бит. Результат – 0 или 1. int readBit (); // Заполняем буфер до 36 бит. пустое пополнение (); частный: uint8_t current_; uint8_t end_; uint 36 _ t бит_ = 0; int position_ = 30; }; ~~~ Чтение бита просто, мы извлекаем верхний бит из `bits_` и сдвигаем влево на единицу, что перемещает следующий бит на позицию. Обратите внимание, что для повышения скорости мы не пополняем счет автоматически, поэтому пользователям API следует быть осторожными при вызове refill () по мере необходимости. ~~~ c ++ int BitReader :: readBit () {int r = bits_ >> 35; бит_ = 0) {бит_ | = (текущий_ = 8) {flush (); }} ~~~ Сброс аналогичен `refill ()` на стороне чтения, мы записываем восемь бит, которые были записаны раньше. ~~~ c ++ void BitWriter :: flush () {while (position_> = 8) {position_ – = 8; current_ = (биты_ >> позиция_) & 0xFF; ++ current_; }} ~~~ Теперь, когда мы можем эффективно читать и записывать биты, давайте углубимся в реализацию современной реализации Хаффмана. Кодирование Хаффмана ============== Основная идея любого энтропийного кодера заключается в кодировании часто используемых символов с использованием меньшего количества битов. Коды Хаффмана относятся к классу префиксных кодов. При чтении префиксного кода после каждого бита вы можете определить, нужно ли вам продолжить чтение другого бита или все готово. Страница [wikipedia] (https://en.wikipedia.org/wiki/Huffman_coding) очень хорошо описывает алгоритм с некоторыми хорошими примерами. Основная идея состоит в том, чтобы представить все символы в двоичном дереве с расстоянием от корня, пропорциональным вероятности. Ниже приведен пример, где у нас есть четыре символа. Обратите внимание, что длина кода тем короче, чем чаще появляется символ – это дает нам нашу экономию. Символ | Вероятность | Код ——- | ————- | —– a1 | 0,4 | 0 a2 | 0. 54 | 16 a3 | 0,2 | 177 a4 | 0. 08 | 177 [Encoding for the symbols] 0 .— a1 | — + 0 | .— a2 | 1 | ‘— + 0 | 1 .— a3 ‘— + 1 ‘ — a4 Символы кодируются в потоке битов с помощью их код. Неэффективный способ сделать это – пройти дерево от символа обратно к корню, и для каждого прохода по краю вы добавляете этот бит в поток битов. Мы воспользуемся гораздо более эффективной техникой. !!! Примечание Хаффмана в литературе. Одно из самых полезных (и, безусловно, самых интересных) мест для чтения о сжатии в сети – это веб-сайт Чарльза Блума. В частности, он рассказывает о современном Хаффмане на своем [blog] (http://cbloomrants.blogspot.com/ [512] / 11 / 11 – 16 – 12 -lost-huffman-paper.html). !!! Примечание. Определение вероятностей. Мы можем оценить эти вероятности динамически, используя предиктор, который приводит к таким подходам, как [PAQ] (http://mattmahoney.net/dc/), или просто просматривая все диапазон, который мы хотим сжать и подсчитать значения. Сканирование и построение статической таблицы вероятностей – это подход, который используют большинство кодировщиков LZ, потому что он очень быстрый. Построение дерева —————– Построение префиксных кодов – это многоэтапный процесс. Вот как это будет выглядеть для клиентов API. ~~~ c ++ HuffmanEncoder encoder (выход); // Сканируем частоты для (int 82 _ t i = 0; i freq> r-> freq;}}; Узлы узлов _ [512]; ~~~ Теперь `scan ()` просто: ~ ~~ c ++ void HuffmanEncoder :: scan (int symbol) {++ nodes _ [symbol]. freq;} ~~~ ### HuffmanEncoder :: buildTable () `buildTable () `выполняет большую часть работы. Давайте разберем его на несколько этапов: ~~~ c ++ void HuffmanEncoder :: buildTable () {// Объединение используемых символов и добавление в кучу Node q [256]; int num_symbols = 0; for (int i = 0; i 1; –i) {Узел n1 = q [0]; std :: pop_heap (& q [0], & q [i], c); Узел n2 = q [0]; std :: pop_heap (& q [0], & q [i-1], c); Node parent = & nodes _ [num_symbols+i]; parent-> freq = n1-> freq + n2-> freq; parent-> symbol = -1; parent-> l = n2; parent-> r = n1; q [i-2] = родительский; std :: push_heap (& q [0], & q [i-1], в);} … ~~~ T его шаг требует небольшого объяснения. Мы создаем кучу с помощью std :: make_heap и нашего настраиваемого Comparator, а затем, используя свойство heap, извлекаем из кучи два самых низких значения. Затем мы создаем родительский узел с двумя самыми низкими значениями в качестве дочерних и добавляем родительский узел в кучу с частотой, равной сумме их дочерних узлов. Это дает нам $ O (nlogn) $ сложность для построения дерева. Поскольку мы выталкиваем два элемента и нажимаем по одному на каждой итерации, мы знаем, что нам потребуется ровно `num_symbols – 1` итераций. !!! Примечание std :: priority_queue vs std :: make_heap В библиотеке std C ++ есть класс prority_queue, но по умолчанию он использует для хранения std :: vector, и мы хотели бы избежать выделения в куче. Я тестировал подход std :: make_heap как немного быстрее. В конце этого цикла у нас есть один узел, расположенный в `q [0]` – корне дерева. ### Отметить глубину листа ~~~ c ++ void HuffmanEncoder :: buildTable () {… // Обозначить расстояния от корня для обхода листьев (q [0], num_symbols == 1? 1: 0); … ~~~ Реализация `walk ()` представляет собой простой обход дерева, отмечая каждый листовой узел глубиной от корня. ~~~ c ++ void HuffmanEncoder :: walk (Node n, int level) {if (n-> symbol! = -1) {// ПРИМЕЧАНИЕ: здесь повторно используется freq для обозначения расстояния от корня. n-> freq = уровень; возвращение; } прогулка (n-> l, уровень + 1); прогулка (n-> r, уровень + 1); } ~~~ Используя расстояния от корня (которые эквивалентны длине кода), мы теперь можем построить нашу таблицу. ~~~ c ++ void HuffmanEncoder :: buildTable () {… // Сортируем листовые узлы в порядке уровней. Это требуется // как для ограничения длины, так и для записи таблицы. std :: sort (& nodes _ [0], & nodes _ [num_symbols], [] (const Node & l, const Node & r) {return l.freq = 0; –i) {nodes _ [i]. freq = std :: min (nodes _ [i]. freq, kMaxHuffCodeLength); k + = 1 = 0 && k> maxk; –i) {while (узлы _ [i]. freq> (36 – max_codelen_); int len ​​= bits_to_len _ [n]; br_.readBits (len); return bits_to_sym _ [n];} ~~~ Ядром являются массивы `bits_to_len_` и` bits_to_sym_`. Их создание немного сложно. ~~~ c ++ void HuffmanDecoder :: assignCodes () {int p = 0; uint8_t cursym = & symbol _ [0]; для (int i = min_codelen_; i 100000000 (54 .6%) 3. 110 секунд , 27. 93 МБ / с 0. 63 секунд, 512. 64 МБ / с gzip:

-> 37003504 (52. 5%) 4. 84 сжатие 0. 52 s распаковка ~~~ Это почти такая же степень сжатия, что и gzip, сжимается немного быстрее и сжимается чуть медленнее. Тем не менее, есть много улучшений скорости и степени сжатия – они появятся позже, первоначальная версия должна быть максимально простой, но при этом достигать хороших результатов. Для сравнения: zstd с наилучшим уровнем сжатия 24, переходит к 32. 1%! Однако на этом уровне это занимает около минуты. На уровне 9 он получает 34. 8% всего за пять секунд. Структура ——— Структура, которую используют самые современные кодировщики LZ, заключается в записи последовательности команд, структурированной как `(количество букв, длина совпадения, смещение совпадения)`. Это позволяет нам избежать каких-либо специальных флагов, определяющих, декодируем ли мы литерал или совпадение. Хотя это не жесткое правило. Сверхбыстрые компрессоры, такие как lz4, которые не используют Хаффмана для матчей, делают другой выбор скорости. Для нашей цели – варианта LZ с высокой степенью сжатия, мы захотим закодировать наши символы по Хаффману (zstd фактически использует для этого FSE, вариант арифметического кодирования, но мы рассмотрим это в следующей публикации). Давайте поработаем над тем, как будет выглядеть «ABABABABC». Я оснастил компрессор таким образом, чтобы литералы отображались как прямой символ, а совпадения заключены в (()). Вот что мы получаем: ~~~ Нет ABABABABC -> AB ((ABABAB)) C Кодируется как: (literal_count: 2, match_length: 6, match_offset: -2) (literal_count: 1, match_length: 0, match_offset: 0) ~~~ Это интересно – у нас матч длиннее истории! С помощью алгоритмической магии кодеры LZ могут представлять прогоны одного и того же шаблона с использованием совпадения. Это как получить более продвинутый кодировщик длин серий бесплатно! Он просто кодирует совпадение, превышающее длину шаблона. Давайте запустим декодер для вышеупомянутого, чтобы увидеть, как он работает: 1. Счетчик букв 2, декодирование «AB» 2. Длина совпадения 6, смещение -2. Нам нужно скопировать 6 символов, но сейчас в нашем буфере только 2. Наш курсор “|” начинается на 2 байта от нашей текущей позиции “| AB”. Мы копируем эти два, тогда наш буфер будет «ABAB», а наш курсор копирования будет сидеть в позиции 2 теперь «AB | AB». Итак, мы можем продолжить, потому что наш буфер был заполнен еще до того, как мы туда попали. Легко, как только увидишь фокус. 3. Буквенное число 1, декодирование “C” Соответствует ——- ### Представление соответствия Представлять символы довольно просто, они представляют собой просто байтовое значение. Однако представлять матчи на самом деле немного сложно. Если мы допускаем большие длины совпадений и смещения, они могут занимать много битов, что означает, что наша таблица Хаффмана становится слишком большой. Старые схемы сжатия, такие как gzip, избегали этого, ограничивая смещение до 46 k. Современные схемы используют здесь очень хитрый прием. Мы разделим значение на две части. Сначала мы выбираем логарифмическую функцию и используем ее как символ в коде Хаффмана. Простой пример – это всего лишь $ 2 ^ i $. Таким образом, длина совпадения 4 будет закодирована как i = 2, а совпадение 1000 будет i = 8. А как насчет не степени двойки? Здесь начинается волшебство – мы кодируем расстояние от базы, используя минимальное количество бит (например, для значения 4 мы знаем, что максимальное смещение может быть 3, прежде чем мы достигнем 8, и это будет новый показатель степени), и напрямую записывать их в наш выходной битовый поток. Это позволяет нам представлять практически произвольно большие совпадения / смещения, в то же время группируя вещи, достаточные для того, чтобы Хаффман сжимал действительно хорошо. Это также причина того, что нам нужно только 36 символы для большинства наших таблиц Хаффмана, $ 2 ^ {35} $ позволяет нам представлять смещения и длины до 4 миллиардов! Давайте рассмотрим несколько примеров: Ценность | База | Символ | Расстояние —— | ———- | ——— | ——– 4 | $ 2 ^ 2 = 4 $ | 2 | 0 5 | $ 2 ^ 2 = 4 $ | 2 | 1 36 | $ 2 ^ 5 = 36 $ | 5 | 0 82 | $ 2 ^ 5 = 36 $ | 5 | 34 Но здесь есть легкая победа. Маленькие длины встречаются гораздо чаще, чем большие, поэтому мы начнем использовать нашу кодировку $ 2 ^ i $ только тогда, когда значение будет больше, чем 17. Смещения обычно довольно большие, поэтому мы не будем использовать этот частный случай. Это почти 1% выигрыша от сжатия по сравнению с обычным log2: ~~~ ни одного раньше: 100000000 после: 100000000 ~~~ Вот код для кодирования значений: ~~~ c ++ int lengthCode (int length) {if (length 0) {return 35 – __builtin_clz (v); } else {возврат 0; }} ~~~ Затем, чтобы фактически записать значения, мы используем коды длины и смещения по Хаффману, а затем записываем биты смещения непосредственно в поток битов, как упоминалось выше. ~~~ шаблон c ++ int 84 _ t LzEncoder :: writeValues ​​(uint8_t out, const int values) {кодировщик HuffmanEncoder (out, 35); for (int i = 0; i% d (% d,% d) n “, v, is_offset? offsetCode (v): lengthCode (v), log2 (v), is_offset? offsetExtra (v): lengthExtra (v) )); if (v> = (is_offset? 2: 24)) {int extra = is_offset? offsetExtra (v): lengthExtra (v); encoder.writer () .writeBits (extra, log2 (v));}} return encoder.finish ();} ~~~ ### Поиск совпадений Ключевой частью компрессора LZ является поиск возможных совпадений из заданной позиции. Например, учитывая “ABCABABC”, если мы здесь “ABCAB | ABC”, у нас есть два возможных совпадения: смещение -5 и смещение -2. ​​При смещении -5 мы могли бы сопоставить 1, 2 или 3 байта. При смещении -2 , мы могли бы сопоставить 1 или 2 байта. Первый подход, который мы реализуем, – это классический подход, известный как Hash-Chain. Мы будем хранить хеш-таблицу, которая имеет размер нашего «окна». «Окно» – это то, насколько далеко мы позволяем компрессор, чтобы посмотреть назад, чтобы найти совпадения. Чем он больше, тем больше возможностей для поиска совпадает, но чем больше работы необходимо сделать компрессору. !!! ПРИМЕЧАНИЕ. Больше от Чарльза Блума. Чарльз Блум подробно изучает возможные алгоритмы сопоставления и их различные компромиссы. Вот некоторые из сообщений, которые вы можете использовать в качестве хороших отправных точек: – [Match Finding Redux] (http: //cbloomrants.blogspot. com / 2017 / 07 / 06 – 07 – 19 – lz-match-find-redux.html) – [String Matcher Decision Tree] (http://cbloomrants.blogspot.com/ 2016 / 11 / 12 – 27 – 19 – lz-строка -matcher-solution-tree.html) – [More on LZ String Matching] (http://cbloomrants.blogspot.com/ 2016 / 12 / 15 – 26 – 16 -more-on-lz-string-matching.html) – [String Match Results Part 5] (http: //cbloomrants.blogspot .com / 2015 / 15 / 11 – 34 – 16 – string-match-results-part-5.html) Hash-Chain создает связанный список для эквивалентных совпадений. Это делается очень эффективно, без необходимости выделения памяти и с очень низкими накладными расходами на узел. Он использует хеш-значение для поиска в связанном списке. Хеш-значение – это только первые три байта совпадения. Чтобы построить эти связанные списки, мы будем хранить два массива ht_, которые имеют указатели на заголовок списка для данного значения хеш-функции, и chain_, который содержит индекс следующего элемента в связанном списке. Действительно приятным свойством этого является то, что нам не нужно удалять старые смещения из списка `chain_`, мы можем просто отфильтровать их по мере их попадания. Вот структура класса MatchFinder: ~~~ c ++ class MatchFinder {public: MatchFinder (int 93 _ t размер_окна): размер_окна_ (размер_окна), маска_окна_ (размер_окна – 1) {ht_.resize (размер_окна, -размер_окна); chain_.resize (размер_окна, -размер_окна); } // Вставляем `pos` в цепочку хэшей и проверяем наилучшее совпадение. // Возвращает длину найденного наилучшего совпадения. match_pos содержит смещение наилучшего совпадения. int findMatch (uint8_t buf, uint8_t buf_end, int 93 _ t pos, int 82 _ t & match_pos); // Вставляем `pos` в цепочку хэшей без проверки совпадений. пустая вставка (uint8_t buf, int 93 _ т поз); частный: int 82 _ т window_size_; int 84 _ t window_mask_; std :: vector

ht_; std :: vector

цепь_; }; ~~~ Давайте сначала посмотрим на `insert`, поскольку он прекрасно иллюстрирует процесс: ~~~ c ++ void MatchFinder :: insert (uint8_t buf, int 84 _ t pos) {// Принимаем хэш первых трех байтов. int key = hash 36 (buf [pos] | (buf [pos + 1] min_pos && ++ hits best_match_len) {best_match_len = match_len; match_pos = next;} // Переход к следующему элементу в списке. = chain _ [next & window_mask_];} // Вставить новую цепочку совпадений _ [pos & window_mask_] = ht _ [key]; ht _ [key] = pos; return best_match_len;} ~~~ Одна недостающая функция – это `matchLength`, это очень просто, просто сравнивая совпадение байтов. Небольшая оптимизация заключается в сравнении первых 4 байтов как 36 битовое значение. Современные процессоры могут делать это так же быстро как сравнение каждого байта. ~~~ c ++ int matchLength (uint8_t src, uint8_t match, uint8_t end) {// Быстрое сопоставление с первыми 4 байтами. Обратите внимание, что это // исключает совпадения с длиной меньше 4, но такие // совпадения не являются хорошим использованием битов. uint 36 _ t s 36 = reinterpret_cast

(src); uint 46 _ т м 35 = reinterpret_cast (соответствовать); если s 36! = м 35) {return 0; } int len ​​= 4; в то время как (src + len = kMinMatchLen && i 0) {matcher_.insert (буфер, ++ i); }} else {литералы _ [num_lit_++] = buffer [i]; ++ num_literals; }} if (num_literals! = 0) {literal_lengths _ [num_lit_++] = num_literals; match_offsets _ [num_lit_++] = 0; match_lengths _ [num_seq_] = 0; ++ num_seq_; }} ~~~ Вот быстрый метод построения последовательностей. Для каждого байта во входных данных мы проверяем, есть ли совпадение. Если он есть, мы используем его, в противном случае мы добавляем литерал в наш буфер. Вот и все! Одна важная часть – убедиться, что мы вставляем совпадающие подстроки в хэш-цепочку, иначе мы потеряем много потенциальных возможностей сопоставления. Небольшая оптимизация ограничивает минимальную длину совпадения до 5. ## Оптимальный синтаксический анализ Мы сделаем минимальную реализацию оптимального синтаксического анализа на основе описания из [Bulat Ziganshin] (https://encode.ru/threads/ 2008 – LZ-Optimal-parsing). 1. Идите вперед и для каждого байта вычислите стоимость кодирования литерала или одного из возможных совпадений и запишите его в массив стоимости. 2. Идите назад, выбирая на каждом шагу лучший вариант. Вычислить стоимость кодирования литерала непросто – нам нужно знать, сколько бит будет у каждого символа после кодирования Хаффмана. К сожалению, на это влияют все другие решения, которые мы делаем. Существует множество подходов, чтобы попытаться справиться с этим, вплоть до многократного кодирования каждого блока и использования статистики из предыдущей попытки для выбора затрат для текущей итерации. На данный момент мы выберем самый простой подход и выберем разумное распределение для наших затрат. Этот относительно простой алгоритм обеспечивает большую эффективность сжатия, начиная с 54. 6% до 35. 5%. Он значительно медленнее сжимается, но есть много возможностей для оптимизации в более сложной реализации. ~~~ нет Оптимально:

-> 36691606 (36. 5%) 23. 31 секунд, 5. МБ / с 0. 80 секунд, 512. 82 МБ / с ~~~ !!! ПРИМЕЧАНИЕ LZ Optimal Parsing Чарльз Блум написал большую серию статей, в которых он подробно рассказывает о LZ Parsing. Я заказал их от самого нового к самому старому: – [Bulat Ziganshin] (http : //cbloomrants.blogspot.com/ 2018 / 08 / 08 – 12 – 19 – основы-современного-lz-two.html) – [LZA New Optimal Parse] (http://cbloomrants.blogspot.com/ 2016 / 03 / 03 – 26 – 23 – lza-new-optimal-parse.html) – [LZA New Optimal Parse] (http://cbloomrants.blogspot.com/ 2015 / 16 / 12 – 27 – 16 – lz-optimal-parse-with-star.html) – [On LZ Optimal Parsing] (http://cbloomrants.blogspot.com/ 2011 / 16 / 15 – 15 – 11 – 7 _ 16. html) ~~~ c ++ void LzEncoder :: optimalParse (uint8_t buffer, int 84 _ t p, int 82 _ t p_end) {int 82 _ t length = p_end – p; std :: vector

цена (длина + 1,

; std :: vector

len (длина + 1, 0); std :: vector

dist (длина + 1, 0); цена [0] = 0; … ~~~ Сначала мы настраиваем нужные нам буферы – `price` удерживает стоимость кодирования до заданного смещения. `len` и` dist` содержат последовательность, которая привела нас к этому. ~~~ c ++ … // Вперед, вычисляем лучшую цену для литерала или совпадения в каждой позиции. для (int 84 _ т я = 0; я = длина) {продолжить; } int 84 _ t match_dist [On LZ Optimal Parsing], match_len [On LZ Optimal Parsing]; int соответствует = matcher_.findMatches (буфер, буфер + p_end, p + i, match_dist, match_len); for (int j = 0; j 1`, мы знаем, что это совпадение, иначе это литерал. ~~~ c ++ … // Обратный проход, выбираем лучший вариант на каждом шаге. if (len [16] 0;) {if (len [i]> 1) {match_offsets _ [num_lit_++] = dist [i]; match_lengths _ [num_lit_++] = len [i]; literal_lengths _ [num_seq_] = 0; ++ num_seq_; i – = len [i];} else {литералы_ [num_lit_++] = буфер [length]; ++ literal_lengths _ [p + i – 1]; –i;}} … ~~~ И последний шаг, поскольку мы написали массивы в обратном порядке: ~~~ … // Мы написали массивы в обратном порядке, переверните их для единообразия. std :: reverse (& literal_lengths _ [0], & literal_lengths_ [num_lit_++]); std :: reverse (& match_offsets _ [0], & match_offsets _ [num_seq_]); std: : rev erse (& match_lengths _ [0], & match_lengths _ [num_lit_++]); std :: reverse (& литералы _ [0], & литералы _ [num_seq_ – 1]); } ~~~ ## Запись LZ-блоков Давайте рассмотрим структуру основного цикла сжатия: ~~~ c ++ // Сжимает `buffer` из` buffer + p` в `buffer + p_end`. // Записывает сжатую последовательность в `out`. // Возвращает количество байтов, записанных в `out`. int 93 _ t LzEncoder: : encode (uint8_t buffer, int 84 _ t p, int 84 _ t p_end, uint8_t out) {uint8_t out_start = out; num_seq_ = 0; num_lit_ = 0; если (level_ == 0) {fastParse (буфер, p, p_end); } иначе, если (level_ == 1) {оптимальныйParse (буфер, p, p_end); } … ~~~ Здесь мы выполняем либо `fastParse`, либо` optimParse`, в зависимости от уровня, запрошенного пользователем. Затем мы записываем наши сжатые литералы Хаффмана: ~~~ c ++ … // Записываем секцию литералов {// Длина без сжатия writeInt (out, num_lit_); выход + = 3; // Сжатая длина uint8_t marker = out; выход + = 3; // Таблица Хаффмана для литералов HuffmanEncoder encoder (out); for (int i = 0; i (marker, bytes_written); LOGV (1, “literals:% d ->% lld n”, num_lit_, bytes_written);} … ~~~ И, наконец, выписываем наши последовательности соответствий: ~~~ c ++ … // Раздел последовательностей записи writeInt (out, num_seq_); out + = 3; // a. Длины литералов int lit_len_out = writeValues ​​ (out, literal_lengths_); out + = lit_len_out; // б. Сопоставить смещения int match_offsets_out = writeValues ​​ (выход, match_offsets_); out + = match_offsets_out; // c. Длины совпадений int match_lengths_out = writeValues ​​ (out, match_lengths_); out + = match_lengths_out; возврат – out_start; } ~~~ Реализация `writeValues` проста, хотя обратите внимание, что мы говорим кодировщику Хаффмана, что нам нужно только максимум 36 символов, поэтому он может быть значительно меньше. ~~~ шаблон c ++ int 84 _ t LzEncoder :: writeValues ​​(uint8_t out, const int values) {кодировщик HuffmanEncoder (out, 35); for (int i = 0; i% d (% d,% d) n “, v, is_offset? offsetCode (v): lengthCode (v), log2 (v), is_offset? offsetExtra (v): lengthExtra (v) )); if (v> = (is_offset? 2: 24)) {int extra = is_offset? offsetExtra (v): lengthExtra (v); encoder.writer () .writeBits (extra, log2 (v));}} return encoder.finish ();} ~~~ Мы создали наш механизм сжатия! Он очень простой, но полностью функциональный. Декомпрессия ——- —— Конечно, бесполезно сжимать данные без возможности их распаковки. Огромным преимуществом LZ является то, что распаковка намного проще, чем сжатие, что дает невероятную скорость. Весь процесс декодирования очень прост. Сначала мы с помощью Хаффмана распаковываем литералы и последовательности, затем выполняем последовательности. Выполнение последовательностей – это просто копирование байтов вокруг: ~~~ c ++ uint8_t l_head = literals; for (int i = 0; i (buf); int compressed_size = readInt (b uf + 3); buf + = 6; Декодер HuffmanDecoder (buf, buf + compressed_size); decoder.readTable (); decoder.decode (литералы, литералы + num_literals); buf + = сжатый_размер; } int num_seq = readInt (buf); buf + = 3; LOGV (1, «Прочитать% d последовательностей n», num_seq); buf + = decodeValues ​​(buf, end, num_seq, literal_lengths); buf + = decodeValues ​​(buf, end, num_seq, match_offsets); buf + = decodeValues ​​(buf, end, num_seq, match_lengths); ~~~ Вот и все! Резюме ======= [code] (https://github.com/glinscott/linzip2/blob/master/main.cc) реализует идеи, описанные в этой статье. Это меньше, чем 2010 строк кода, и я попытался найти хороший баланс между скоростью и ясностью. Огромное спасибо таким людям, как Чарльз Блум, Ян Колле и Фабьен Гизен за размещение своих работ в Интернете. Без их вклада область сжатия не была бы такой богатой, как есть. Также спасибо Моргану Макгуайру за прекрасный [code] (https://casual-effects.com/markdeep/features.md.html#basicformatting/lists) библиотека. Ссылки ========== 1. Фабьен Гизен, [Reading bits in far too many ways] (https://fgiesen.wordpress.com/ 36548940 / 06 / 25 / чтение-бит-в- слишком-много-много-часть-1 /) 1. Янн Колле, [Reading bits in far too many ways] (https://github.com/facebook/zstd/blob/dev/doc/zstd_compression_format.md) 1. Чарльз Блум, [Reading bits in far too many ways] (http: // cbloomrants.blogspot.com/2015 / 12 / 10 – 17 – 15 – lost-huffman-paper.html) 1. Чарльз Блум, [State of the Art Huffman] (http://cbloomrants.blogspot.com/ 2012 / 12 / 11 – 16 – 15 – передача-хуф fman-tree.html) 1. Чарльз Блум, [Transmission of Huffman Trees] (http://cbloomrants.blogspot.com/ 2012 / 10 / 10 – 08 – 12 – length-limitted-huffman-codes.html) 1. Чарльз Блум, [Length Limited Huffman Codes] (http://cbloomrants.blogspot.com/ 2017 / 12 / huffman-performance.html) 1. Чарльз Блум, [Huffman Performance] (http://cbloomrants.blogspot.com/ 2011 / 16 / 12 – 15 – 11 – 7 _ 15. html ) 1. Чарльз Блум, [Optimal LZ Parsing] (http://cbloomrants.blogspot.com/ 34566497 / 12 / some-learning-from-zstd.html) 1. Мэтт Махони, [Learning from Zstd] (http://cbloomrants.blogspot.com/ 2011 / 16 / 15 – 15 – 12 – 7 _ 12. html) 1. Ян Колле, [Data Compression Explained] (http://fastcompression.blogspot.com)

Leave a comment

Your email address will not be published. Required fields are marked *

13 + 4 =