53
правки
Изменения
Нет описания правки
LZMA ('''Lempel-Ziv-Markov chain-Algorithm''') — это алгоритм, используемый для выполнения алгоритма сжатия без потерь. Он разрабатывался с 1996-1998 гг и впервые был использован в формате 7z архиватора 7-Zip.Алгоритм использует словарное сжатие , в чем-то схожее с алгоритмом [[Алгоритмы LZ77 и LZ78|LZ77]].
==Описание==
===Основная идея===LZMA использует алгоритм словарного сжатия, выходные данные которого закодированы интервальным кодированием, использующим сложную модель вычисления вероятности появления каждого бита. Система сжатия находит соответствия, используя словарную структуру данных, и создает поток символов и ссылок фраз, уже находящихся в словаре, который закодирован <tex>1 </tex> битом интервальным кодировщиком.
Главной инновацией LZMA было то, что вместо общей байтовой модели, модель LZMA использовала зависящие от контекста битовые поля в каждом представлении букв или фраз. Эта модель почти также проста как битовая, но дает лучший коэффициент сжатия, потому что избегает смешивания несвязных битов вместе в том же самом контексте.
===Основные преимущества===*Высокий По сравнению с алгоритмом LZ77 алгоритм LZMA имеет следующие преимущества: более высокий коэффициент сжатия.*Изменяемый , изменяемый размер словаря.*Небольшие , небольшие требования по памяти для “распаковки” «распаковки» данных.===Недостатки===Алгоритм LZMA не на всех типах входных данныхработает одинаково эффективно.
===Схема кодирования===
В дополнении к алгоритмам, используемым в LZ77, LZMA использует Дельта-фильтр и интервальное кодирование.
[[Файл:Lzma3.png]]
====Кодер====
1. Функция принимает массив и длину массива как аргументы, если длина не была передана, то массив не обрабатывается.<br>
2. Инициализируем переменные tmp, для сохранения последнего элемента и last для хранения предыдущего числа.
Инициализируем цикл.<br> 3. В цикле: <br>* 3.1 Сохраняем элемент с индексом i.<br/>* 3.2 Вычисляем разницу между элементом под номером i и i-1 и перезаписываем ее в элемент массива с индексом i.<br/>
'''function''' delta_encode(bp: '''char*''', n: '''int''')
'''char''' last=0,''tmp
last=tmp
====Декодер====
1.Инициализируем переменную для хранения последнего символа.<br/> 2.Инициализируем цикл.<br/> 3.В цикле:<br/>
* 3.1 Добавляем к этому элементу значение предыдущего элемента.
* 3.2 Сохраняем значение текущего элемента.
==Интервальное кодирование==
При интервальном кодировании все символы сообщения кодируются как одно число, для того чтобы достичь наилучшего коэффициента сжатия. Это работает эффективно с вероятностями появления символа не являющимися степенями двойки.
Интервальное кодирование работает так:<br>1. #Выделяется достаточно большой диапазон целых чисел и дается оценка вероятности вхождения для символов.<br/>2. #Исходный диапазон чисел делится на поддиапазоны, размер которых пропорционален вероятности вхождения символа, за который они отвечают.<br>3. #Каждый символ сообщения кодируется, после чего диапазон сокращается до размера диапазона только что закодированного символа и вновь делится по вероятностям.<br>
В декодере должны быть такое же распределение вероятностей как и при кодировании.
== Пример ==
Закодируем строку <tex>abehhilopsu</tex>.<br>Для начала пропустим ее через дельта фильтр.<br>Тогда исходная строка <tex>abehhilopsu</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>. Как мы видим, теперь в нашей строке вместо 10 различных символов 5 различных символа.<br>
Далее применим к получившейся строке метод "скользящего" окна:
{| border="1"
|<2,1,<tex>2</tex>>
|}
Получаем код: <tex>00a001003110431212<EOM></tex>, где <tex><EOM></tex>— это символ конца сообщения.<br> Для нашей строки получаем диапазон [<tex>0; 10^9</tex>] и распределение вероятностей: {<tex>0</tex>: 0,37; <tex>1</tex>: 0,26; <tex>2</tex>: 0,11; <tex>3</tex>: 0,11; <tex>4</tex>: 0,05; <tex>a</tex>: 0,05; <tex><EOM></tex>: 0,05}<br>
Таким образом, произведя интервальное кодирование нашей строки, получим диапазон который будет отвечать закодированному сообщению.
