Алгоритм LZMA — различия между версиями
Facmad (обсуждение | вклад) |
м (rollbackEdits.php mass rollback) |
||
(не показано 5 промежуточных версий 3 участников) | |||
Строка 7: | Строка 7: | ||
Главной инновацией LZMA было то, что вместо общей байтовой модели, модель LZMA использовала зависящие от контекста битовые поля в каждом представлении букв или фраз. Эта модель почти также проста как битовая, но дает лучший коэффициент сжатия, потому что избегает смешивания несвязных битов вместе в том же самом контексте. | Главной инновацией LZMA было то, что вместо общей байтовой модели, модель LZMA использовала зависящие от контекста битовые поля в каждом представлении букв или фраз. Эта модель почти также проста как битовая, но дает лучший коэффициент сжатия, потому что избегает смешивания несвязных битов вместе в том же самом контексте. | ||
− | ===Основные преимущества=== | + | ===Сравнение с другими алгоритмами=== |
+ | ====Основные преимущества==== | ||
По сравнению с алгоритмом LZ77 алгоритм LZMA имеет следующие преимущества: более высокий коэффициент сжатия, изменяемый размер словаря, небольшие требования по памяти для «распаковки» данных. | По сравнению с алгоритмом LZ77 алгоритм LZMA имеет следующие преимущества: более высокий коэффициент сжатия, изменяемый размер словаря, небольшие требования по памяти для «распаковки» данных. | ||
− | ===Недостатки=== | + | ====Недостатки==== |
Алгоритм LZMA не на всех типах входных данных работает одинаково эффективно. | Алгоритм LZMA не на всех типах входных данных работает одинаково эффективно. | ||
Строка 19: | Строка 20: | ||
[[Файл:Lzma3.png]] | [[Файл:Lzma3.png]] | ||
+ | |||
==Дельта-кодирование и декодирование== | ==Дельта-кодирование и декодирование== | ||
Строка 26: | Строка 28: | ||
{| class="wikitable" | {| class="wikitable" | ||
|- | |- | ||
− | |Входная последовательность: <tex>2,3,4,6,7,9,8,7,5,3,4</tex> | + | |style="background-color:#FFF;padding:2px 40px"|Входная последовательность: |
+ | |style="background-color:#FFF"| <tex>2,3,4,6,7,9,8,7,5,3,4</tex> | ||
|- | |- | ||
− | |Закодированная последовательность: <tex>2,1,1,2,1,2,-1,-1,-2,-2,1</tex> | + | |style="background-color:#FFF;padding:2px 40px"| Закодированная последовательность: |
+ | |style="background-color:#FFF"| <tex>2,1,1,2,1,2,-1,-1,-2,-2,1</tex> | ||
|- | |- | ||
− | | | + | |style="background-color:#FFF;padding:2px 40px"| Количество различных символов в входных данных: |
+ | |style="background-color:#FFF"| <tex>8</tex> | ||
|- | |- | ||
− | |Количество различных символов | + | |style="background-color:#FFF;padding:2px 40px"| Количество различных символов после кодирования: |
− | |- | + | |style="background-color:#FFF"| <tex>4</tex> |
− | |||
|} | |} | ||
Строка 78: | Строка 82: | ||
<tex>a</tex> <tex>1</tex> <tex>3</tex> <tex>3</tex> <tex>0</tex> <tex>1</tex> <tex>3</tex> <tex>3</tex> <tex>1</tex> <tex>3</tex> <tex>2</tex>. | <tex>a</tex> <tex>1</tex> <tex>3</tex> <tex>3</tex> <tex>0</tex> <tex>1</tex> <tex>3</tex> <tex>3</tex> <tex>1</tex> <tex>3</tex> <tex>2</tex>. | ||
− | + | ||
Как мы видим, теперь в нашей строке вместо <tex>10</tex> различных символов <tex>5</tex> различных символа. | Как мы видим, теперь в нашей строке вместо <tex>10</tex> различных символов <tex>5</tex> различных символа. | ||
Далее применим к получившейся строке метод «скользящего» окна: | Далее применим к получившейся строке метод «скользящего» окна: | ||
Строка 118: | Строка 122: | ||
== См.также == | == См.также == | ||
* [[Алгоритмы LZ77 и LZ78]] | * [[Алгоритмы LZ77 и LZ78]] | ||
+ | * [[Алгоритм LZW]] | ||
+ | * [[Алгоритм LZSS]] | ||
==Примечания== | ==Примечания== |
Текущая версия на 19:31, 4 сентября 2022
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]
Интервальное кодирование
При интервальном кодировании все символы сообщения кодируются как одно число, для того чтобы достичь наилучшего коэффициента сжатия. Это работает эффективно с вероятностями появления символа не являющимися степенями двойки. Интервальное кодирование работает так:
- Выделяется достаточно большой диапазон целых чисел и дается оценка вероятности вхождения для символов.
- Исходный диапазон чисел делится на поддиапазоны, размер которых пропорционален вероятности вхождения символа, за который они отвечают.
- Каждый символ сообщения кодируется, после чего диапазон сокращается до размера диапазона только что закодированного символа и вновь делится по вероятностям.
В декодере должны быть такое же распределение вероятностей как и при кодировании.
Пример
Закодируем строку
. Для начала пропустим ее через дельта фильтр. Тогда исходная строка примет вид:.
Как мы видим, теперь в нашей строке вместо
различных символов различных символа. Далее применим к получившейся строке метод «скользящего» окна:Сообщение | Подстрока | Код |
---|---|---|
Получаем код:
, где — это символ конца сообщения.Для нашей строки получаем диапазон
и распределение вероятностей:Таким образом, произведя интервальное кодирование нашей строки, получим диапазон который будет отвечать закодированному сообщению.