Алгоритм LZMA
| НЕТ ВОЙНЕ |
|
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России |
| Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению. |
| meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки. |
LZMA (Lempel-Ziv-Markov chain Algorithm) — алгоритма сжатия без потерь. Он разрабатывался с 1996-1998 гг и впервые был использован в формате 7z архиватора 7-Zip[1]. Алгоритм использует словарное сжатие , в чем-то схожее с алгоритмом LZ77. На сегодняшний день алгоритм LZMA используется в основном в LZMA SDK[2] архиватора 7-Zip.
Описание
Основная идея
LZMA использует алгоритм словарного сжатия, выходные данные которого закодированы интервальным кодированием, использующим сложную модель вычисления вероятности появления каждого бита. Система сжатия находит соответствия, используя словарную структуру данных, и создает поток символов и ссылок фраз, уже находящихся в словаре, который закодирован битом интервальным кодировщиком.
Главной инновацией LZMA было то, что вместо общей байтовой модели, модель LZMA использовала зависящие от контекста битовые поля в каждом представлении букв или фраз. Эта модель почти также проста как битовая, но дает лучший коэффициент сжатия, потому что избегает смешивания несвязных битов вместе в том же самом контексте.
Сравнение с другими алгоритмами
Основные преимущества
По сравнению с алгоритмом LZ77 алгоритм LZMA имеет следующие преимущества: более высокий коэффициент сжатия, изменяемый размер словаря, небольшие требования по памяти для «распаковки» данных.
Недостатки
Алгоритм LZMA не на всех типах входных данных работает одинаково эффективно.
Схема кодирования
В дополнении к алгоритмам, используемым в LZ77, LZMA использует Дельта-фильтр и интервальное кодирование.
Поступив на вход, данные пропускаются через дельта фильтр, где они преобразуются, для дальнейшего кодирования. После полученная последовательность подвергается словарному сжатию, алгоритм которого идентичен, алгоритму используемому в LZ77. Пропустив данные через алгоритм «скользящего» окна, получаем код, который для достижения лучшего сжатия подвергнем интервальному кодированию. На выходе получаем интервал целых чисел который и будет отвечать исходной последовательности.
Дельта-кодирование и декодирование
Дельта фильтр перестраивает входные данные для эффективного сжатия скользящим окном. Первый байт на выходе совпадает с первым байтом на входе, последующие же байты представлены как разность между текущим и предыдущим байтом. Для постоянно меняющихся данных, дельта-кодирование делает работу скользящего окна более эффективной.
Пример
| Входная последовательность: | |
| Закодированная последовательность: | |
| Количество различных символов в входных данных: | |
| Количество различных символов после кодирования: |
Кодер и декодер
Кодер
- Функция принимает массив и длину массива как аргументы, если длина не была передана, то массив не обрабатывается.
- Инициализируем переменные , для сохранения последнего элемента и для хранения предыдущего числа.Инициализируем цикл.
- В цикле:
- 3.1 Сохраняем элемент с индексом .
- 3.2 Вычисляем разницу между элементом под номером и и перезаписываем ее в элемент массива с индексом .
function deltaEncode(bp: list<char>, n: int):
char last = 0
for i = 0 to n - 1
char tmp = bp[i]
bp[i] -= last
last = tmp
Декодер
- Инициализируем переменную для хранения последнего символа.
- Инициализируем цикл.
- В цикле:
- 3.1 Добавляем к этому элементу значение предыдущего элемента.
- 3.2 Сохраняем значение текущего элемента.
function deltaDecode(bp:list<char>, n:int):
char last = 0
for i = 0 to n - 1
bp[i] += last
last = bp[i]
Интервальное кодирование
При интервальном кодировании все символы сообщения кодируются как одно число, для того чтобы достичь наилучшего коэффициента сжатия. Это работает эффективно с вероятностями появления символа не являющимися степенями двойки. Интервальное кодирование работает так:
- Выделяется достаточно большой диапазон целых чисел и дается оценка вероятности вхождения для символов.
- Исходный диапазон чисел делится на поддиапазоны, размер которых пропорционален вероятности вхождения символа, за который они отвечают.
- Каждый символ сообщения кодируется, после чего диапазон сокращается до размера диапазона только что закодированного символа и вновь делится по вероятностям.
В декодере должны быть такое же распределение вероятностей как и при кодировании.
Пример
Закодируем строку . Для начала пропустим ее через дельта фильтр. Тогда исходная строка примет вид:
.
Как мы видим, теперь в нашей строке вместо различных символов различных символа. Далее применим к получившейся строке метод «скользящего» окна:
| Сообщение | Подстрока | Код |
|---|---|---|
Получаем код: , где — это символ конца сообщения.
Для нашей строки получаем диапазон и распределение вероятностей:
Таким образом, произведя интервальное кодирование нашей строки, получим диапазон который будет отвечать закодированному сообщению.
