http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&feedformat=atom&user=178.70.46.27&*Викиконспекты - Вклад участника [ru]2026-08-02T21:44:14ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_LZMA&diff=57793Алгоритм LZMA2016-12-13T10:51:55Z<p>178.70.46.27: </p>
<hr />
<div>LZMA (англ. Lempel-Ziv-Markov chain-Algorithm) — это алгоритм, используемый для выполнения сжатия без потерь. Он разрабатывался с 1996-1998 гг и впервые был использован в формате 7z архиватора 7-Zip.Алгоритм использует словарное сжатие , в чем-то схожее с алгоритмом LZ77.<br />
<br />
==Описание==<br />
LZMA использует алгоритм словарного сжатия, выходные данные которого закодированы интервальным кодированием, использующим сложную модель вычисления вероятности появления каждого бита. Система сжатия находит соответствия, используя словарную структуру данных, и создает поток символов и ссылок фраз, уже находящихся в словаре, который закодирован 1 битом интервальным кодировщиком.<br />
<br />
Главной инновацией LZMA было то, что вместо общей байтовой модели, модель LZMA использовала зависящие от контекста битовые поля в каждом представлении букв или фраз. Эта модель почти также проста как битовая, но дает лучший коэффициент сжатия, потому что избегает смешивания несвязных битов вместе в том же самом контексте.<br />
<br />
==Основные преимущества==<br />
*Высокий коэффициент сжатия.<br />
*Изменяемый размер словаря.<br />
*Небольшие требования по памяти для “распаковки” данных.<br />
<br />
==Схема кодирования==<br />
В дополнении к алгоритмам, используемым в LZ77, LZMA использует Дельта-фильтр и интервальное кодирование.<br />
[[Файл:Lzma3.png]]<br />
<br />
==Дельта-кодирование и декодирование==<br />
Дельта фильтр перестраивает входные данные для эффективного сжатия скользящим окном. Первый байт на выходе совпадает с первым байтом на входе, последующие же байты представлены как разность между текущим и предыдущим байтом. Для постоянно меняющихся данных, дельта-кодирование делает работу скользящего окна более эффективной.<br />
<br />
===Пример===<br />
Входная последовательность: 2,3,4,6,7,9,8,7,5,3,4<br />
Закодированная последовательность: 2,1,1,2,1,2,-1,-1,-2,-2,1<br />
Количество различных символов в входных данных: 8<br />
Количество различных символов после кодирования:4<br />
<br />
===Кодер и декодер===<br />
====Кодер==== <br />
<br />
1. функция принимает массив и длину массива как аргументы, если длина не была передана, то массив не обрабатывается.<br/><br />
2. инициализируются переменные tmp, для сохранения последнего элемента и last для хранения предыдущего числа.<br />
инициализация цикла, где i это счетчик.<br/> <br />
3. В цикле: <br/><br />
* 3.1 сохранение символа под номером i в массиве <br/><br />
* 3.2 вычисление разницы между элементом под номером i и i-1, первый элемент не меняется, и присвоение разницы этому элементу.<br/> <br />
'''function''' delta_encode(bp: '''char*''', n: '''int''')<br />
'''char''' last=0,''tmp<br />
'''for''' i=0 '''to''' n-1<br />
tmp=bp[i]<br />
bp[i]-=last<br />
last=tmp<br />
====Декодер====<br />
1.инициализация переменной для хранения последнего символа.<br/><br />
2.инициализация цикла, где i это счетчик.<br/><br />
3.В цикле:<br/><br />
*3.1добавление к этому элементу значение предыдущего элемента.<br />
*3.2сохранение значение этого элемента.<br />
'''function''' delta_encode(bp:'''char*''', n:'''int''')<br />
'''char''' last=0<br />
'''for'''i=0 '''to''' n-1 <br />
bp[i]+=last<br />
last=bp[i]<br />
==Модель "скользящего" окна==<br />
Модель скользящего окна идентичен алгоритму LZ77<br />
==Интервальное кодирование==<br />
При интервальном кодировании все символы сообщения кодируются как одно число, для того чтобы достичь наилучшего коэффициента сжатия. Это работает эффективно с вероятностями появления символа не являющимися степенями двойки.<br />
Интервальное кодирование работает так:<br/><br />
1. Выделяется достаточно большой диапазон целых чисел и дается оценка вероятности вхождения для символов.<br/><br />
2. Исходный диапазон чисел делится на поддиапазоны, размер которых пропорционален вероятности вхождения символа, за который они отвечают.<br/><br />
3. Каждый символ сообщения кодируется, после чего диапазон сокращается до размера диапазона только что закодированного символа и вновь делится по вероятностям.<br/><br />
В декодере должны быть такое же распределение вероятностей как и при кодировании.<br />
== Пример ==<br />
Закодируем строку <tex>abehhilopsu</tex>.<br/><br />
Для начала пропустим ее через дельта фильтр.<br/><br />
Тогда исходная строка <tex>abehhilopsu</tex> примет вид: <tex>97</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/><br />
Далее применим к получившейся строке метод "скользящего окна":<br />
{| border="1" <br />
!Сообщение<br />
!Подстрока<br />
!Код<br />
|-<br />
|<tex>\fbox{971330}133132 </tex><br />
|<br />
|<0,0,<tex>97</tex>><br />
|-<br />
|<tex>97\fbox{13301}33132</tex><br />
|<br />
|<0,0,<tex>1</tex>><br />
|-<br />
|<tex>971\fbox{33013}3132</tex><br />
|<br />
|<0,0,<tex>3</tex>><br />
|-<br />
|<tex>9713\fbox{30133}132</tex><br />
|<tex>3</tex><br />
|<1,1,<tex>0</tex>><br />
|-<br />
|<tex>971330\fbox{13313}2</tex><br />
|<tex>133</tex><br />
|<4,3,<tex>1</tex>><br />
|-<br />
|<tex>9713301331\fbox{32}</tex><br />
|<tex>3</tex><br />
|<2,1,<tex>2</tex>><br />
|}</div>178.70.46.27