После просмотра драмы HBO «Силиконовая долина» я всегда интересовался алгоритмами сжатия. Ричард Хендрикс и его алгоритм среднего сжатия, конечно, фальшивые, но после серьёзного поиска в Google я понял, что в реальной жизни существует настоящий гений алгоритма сжатия.
Ян Колле изобрёл алгоритм сжатия LZ4 в 2011 году. Конечно, алгоритм LZ4 не так хорош, как middle out, но он известен своей непобедимой скоростью сжатия и более высокой скоростью декомпрессии, когда можно гарантировать определённую скорость сжатия.
Я не буду подробно описывать оценку скорости сжатия, если интересно, можете прочитать эту сравнительную статью:Вход по гиперссылке виден.
Также прилагается адрес github LZ4:Вход по гиперссылке виден.
В данной статье сосредоточена на объяснении принципа алгоритма сжатия LZ4. Великий бог ранее написал объяснение алгоритма LZ4:Вход по гиперссылке виден.Но когда я учился раньше, мне показалось, что эта статья не очень дружелюбна для новичков, поэтому я начал новую статью для новичков, таких как я.
Если подытожить в одном предложении, LZ4 — это LZ77, который хранит словарь с хэш-таблицей размера 16k и упрощает поиск.
LZ4 — это алгоритм сжатия без потерь, который обеспечивает скорость сжатия > 500 МБ/с на ядро, который можно масштабировать с помощью многоядерных процессоров. Он оснащен чрезвычайно быстрыми декодерами со скоростью несколько ГБ/с на ядро, часто достигая ограничений скорости оперативной памяти на многоядерных системах.
Скорость можно динамически регулировать, выбирая коэффициент «ускорения», который заменяет степень сжатия на более высокую скорость. С другой стороны, также предоставляется производный LZ4_HC с высоким сжатием для увеличения сжатия за счёт времени процессора. Все версии имеют одинаковую скорость декомпрессии.
Так что же такое LZ77?
Сжатие LZ77 и принцип
LZ77 — это алгоритм, который применяет словарь для сжатия. Простыми словами, это позволяет программе наблюдать (посмотрите словарь), дублируются ли текущие данные с предыдущими, и если да, то сохраняем расстояние (смещение) и длину дублирующихся полей, чтобы заменить дублирующиеся поля и сжать данные.
ссылкаВход по гиперссылке виден.
Для строки из букв A A B C B при чтении второго A программа сохраняет (1,1) (1 цифра от предыдущей, длина 1), и аналогично, при чтении второго B программа сохраняет (2,1) (расстояние 2, длина 1).
Но если строка длиннее и программа постоянно записывает данные в словарь, поиск дублирующих полей становится крайне трудоёмким, потому что в худшем случае программа просматривает весь словарь с каждой новой буквой. LZ77 использует метод скользящего окна для решения этой задачи.
Аналогично начальной точке TCP с использованием скользящего окна, скользящее окно может уменьшить область кэша, чтобы избежать одновременной обработки слишком большого количества кэшированных данных. В LZ77 словарь не увеличивается постоянно, а удаляет первые символы, добавленные в словарь, когда он превышает максимальный размер, указанный словаром, чтобы гарантировать, что размер словаря всегда сохраняется на заданном максимальном размере.
Предположим, что длина словаря равна 3
| Словарь |
| A | А Б В Б Б А Б В
Выход (0,0,A)
| A A | Б В Б Б А Б В
Выпуск(1,1)
| А А Б | C B B A B C
Выход (0,0,B)
A | A B C | Б Б А Б В В
Выход (0,0,C)
A A | B C B | Б А Б В
Выпуск(2,1)
Другая часть скользящего окна — это кэш для поиска (буфер для просмотра не имеет официального перевода). Кэш, который нужно искать, — это несжатая часть длины, ближайшая к словару. Алгоритм LZ77 будет совпадать с самой длинной строкой в этой части символа, которая совпадает с словарём. Предыдущий пример можно рассматривать как буфер вперёд 1.
Предположим, что длина словаря равна 5, а размер кэша для поиска — 3
| Словарь | Буфер «Смотри вперёд» |
A | A B C B B | A B C |
Выход(5,3)
Самая длинная совпадающая строка — ABC
Полный процесс сжатия:
Предположим, что длина словаря равна 5, а размер кэша для поиска — 3
| Словарь | Буфер «Смотри вперёд» |
| А А Б | C B B A B C
Выход (0,0,A)
| A | A B C | Б Б А Б В В
Выпуск(1,1)
| A A | B C B | Б А Б В
Выход (0,0,B)
| А А Б | C B B | А Б В
Выход (0,0,C)
| A A B C | B B A | B C
Выпуск(2,1)
| A A B C B | B A B | C
Выпуск(1,1)
A | A B C B B | A B C |
Выход(5,3)
A A B C | B B A B C | 。。。 |
Нет необходимости сохранять словарь в выходном файле компрессора, так как программа декомпрессии восстанавливает словарь, сопоставив выходные единицы.
Процесс декомпрессии
Одно из главных преимуществ алгоритма LZ77 — его очень быстрое декомпрессия.
Если первая единица сопоставления равна (0,0,A), то выходом является A.
Второй блок сопоставления — (1,1), который копирует предыдущий бит в выходной строке и выводит A, если длина копирования равна 1.
。。。
Если последний совпадающий блок равен (5,3), то посмотрите назад на 5 бит в строке копирования, а если длина копирования равна 3, то выводите A, B, C.
Самая трудоёмкая часть сжатия алгоритма LZ77 — найти самый длинный совпадающий символ в кэше для поиска в словаре. Если словарь и кэш для поиска слишком короткие, шансы найти совпадение малы. Поэтому LZ4 изменил алгоритм сопоставления для LZ77.
Во-первых, словарь алгоритма LZ4 представляет собой хеш-таблицу. Ключ в словаре — это строка из 4 байтов, каждая клавиша соответствует только одному слоту, а значение в слоте — это положение этой строки.
Вместо поиска в кэше LZ4 считывает по четыре байта за раз из входного файла, а затем ищет слот, соответствующий строке в хеш-таблице, которая далее называется текущей строкой.
Если вы достигли последних 12 символов, введите их напрямую в выходной файл.
Если в слоте не назначено значение, это означает, что четыре байта появляются впервые, добавьте эти четыре байта и позиции в хеш-таблицу и продолжайте поиск.
Если в слоте есть присваивание, это значит, что мы нашли совпадающее значение.
Если значение в слоте плюс размер окна ползунка < положение текущего символа, то позиция совпадения превышает размер блока, и программа обновляет значение в хеш-слоте до позиции текущей строки.
LZ4 проверит, был ли конфликт хеша. Если 4 байта в слоте не совпадают с текущей строкой, должен возникать конфликт хеша. Собственный xxhash автора также известен своей эффективностью, но конфликты неизбежны. В случае конфликта программа также обновляет значение в хеш-слоте до текущей позиции строки
Наконец, мы можем подтвердить, что совпадение валидно, и программа продолжит проверять, совпадают ли последующие символы в строке сопоставления. Наконец, скопируйте все символы с конца предыдущего действительного совпадения в начало этого действительного совпадения в сжатый файл и добавьте последовательность совпадения этого действительного совпадения.
Колле называет соответствующие единицы, выводящиеся последовательностями LZ4, и они составляют сжатый файл LZ4. Детали следующие:
Токен имеет длину 1 байт: первые 4 слова — это буквальная длина, а последние 4 слова — длина матча. Как уже упоминалось, все символы с конца предыдущего действительного совпадения до начала этого действительного совпадения будут скопированы в сжатый файл, эти несжатые файлы являются литеральными, а их длина — буквальная длина.
За этим буквально следует отклонение. Как и в LZ77, отклонение и длина совпадения относятся к длине текущей строки от её совпадения, а длина совпадения — к длине совпадения текущей строки с той же строкой в словаре. В декомпрессии нужно пройтись по ней, чтобы найти струну, которую нужно скопировать, и длину для копирования. Величина отклонения фиксирована.
На рисунке литеральная длина+ и длина матча + — если литерал или длина матча — 4 слова в жетоне недостаточно, они будут продолжать расти на соответствующих позициях. 4 слова могут представлять от 0 до 15, а если их больше, добавляйте один байт, то есть добавляйте 255 к размеру, пока байт не станет меньше 255. В длине сопоставления 0 обозначает 4 байта.
Последние 12 байт заканчиваются буквально потому, что они были скопированы напрямую.
Давайте посмотрим на код (python более абстрактен)
Краткое содержание Сказав всё это, я до сих пор не объяснил, почему LZ4 такой быстрый. Давайте сначала сравним поиск в словаре между LZ77 и LZ4. Родной LZ77 ищет словари, находя наибольшее совпадение в кэше и в словаре. Это задача поиска самой большой идентичной строки в двух строках. Если мы не используем динамическое программирование, то в худшем случае придётся рассматривать все подстроки одной строки и затем сопоставлять их в другой. Если ×мы используем динамическое программирование, то используем таблицу для хранения самого длинного совпадения в динамике, что позволит завершить совпадение только в случае O(m*n). И это только для пары поисковых тайников и словарей. В худшем случае, если совпадений нет, LZ77 придётся считать (длину всего файла — длину кэша для поиска) столько же таких задач с сопоставлением. LZ4 фактически использует более широкий уровень динамического программирования: он хранит 4 байта и их позиции в хеш-таблице, а затем каждый раз сопоставляет новые 4 байта данных, чтобы проверить, корректны ли значения в хеш-таблице. После нахождения действительного совпадения, если посмотреть на последующие данные двух наборов совпадающих значений, можно также найти их самое длинное совпадение. Поскольку каждый ключ хеш-таблицы LZ4 соответствует только одному слоту, поиск, добавление и модификация хеш-таблицы требует только O(1). Если после сопоставления найдётся больше совпадений, потребуется больше групповых сравнений, но в общем времени эти сравнения заменят больше времени на поиск хеш-таблицы, так что общее время алгоритма LZ4 составляет только O(n). Я должен восхищаться красотой алгоритма Колле! Чтобы сделать алгоритм ещё более быстрым, Collet устанавливает размер хеш-таблицы по умолчанию 16k, что рекомендуется не превышать 32k, чтобы его можно было поместить в кэш L1 почти всех процессоров (Intel). Все знают, что скорость и отношение памяти в кэше L1 CPU сильно отличаются, поэтому неудивительно, что LZ4 летит быстро, не говоря уже о том, что хеш-уравнение, используемое в хеш-таблице LZ4, по-прежнему является самым быстрым xxhash. Конечно, у такого дизайна есть свои недостатки. Чем меньше хеш-таблица, тем меньше в ней ключей. Это означает, что возникнут новые хеш-конфликты, что неизбежно. А больше столкновений хешей — меньше совпадений. Меньшая хеш-таблица также означает меньшее скользящее окно, а значит, больше совпадений будет отбрасировано, потому что они слишком далеко. Меньшее количество совпадений означает меньший степень сжатия, поэтому у LZ4 менее выраженное сжатие. Смотря в будущее, LZ4 предлагает широкий спектр сценариев применения. Точно так же, как middle-out применялся в VR в Кремниевой долине, LZ4 может увеличить использование пропускной способности, добавляя меньше ввода-выводов за счёт очень низкой задержки благодаря высокой скорости сжатия. Есть ещё небольшое предположение: если процессор с большим кэшем на первом уровне, может ли LZ4 увеличить степень сжатия без ущерба для скорости?
Исходный текст:Вход по гиперссылке виден. |
Опубликовано 03.01.2022 13:54:23
|
|
|
|
