Алгоритм LZMA — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показана 41 промежуточная версия 4 участников)
Строка 1: Строка 1:
LZMA (''Lempel-Ziv-Markov chain-Algorithm'') — это алгоритм, используемый для выполнения сжатия без потерь. Он разрабатывался с 1996-1998 гг и впервые был использован в формате 7z архиватора 7-Zip.Алгоритм использует словарное сжатие , в чем-то схожее с алгоритмом LZ77.
+
'''LZMA''' (Lempel-Ziv-Markov chain Algorithm) — алгоритма сжатия без потерь. Он разрабатывался с 1996-1998 гг и впервые был использован в формате 7z архиватора 7-Zip<ref>[https://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Markov_chain_algorithm LZMA]</ref>. Алгоритм использует словарное сжатие , в чем-то схожее с алгоритмом [[Алгоритмы LZ77 и LZ78|LZ77]]. На сегодняшний день алгоритм LZMA используется в основном в LZMA SDK<ref>[http://www.7-zip.org/sdk.html 7-Zip — LZMA SDK]</ref> архиватора 7-Zip.  
  
 
==Описание==
 
==Описание==
LZMA использует алгоритм словарного сжатия, выходные данные которого закодированы интервальным кодированием, использующим сложную модель вычисления вероятности появления каждого бита. Система сжатия находит соответствия, используя словарную структуру данных, и создает поток символов и ссылок фраз, уже находящихся в словаре, который закодирован 1 битом интервальным кодировщиком.
+
===Основная идея===
 +
LZMA использует алгоритм словарного сжатия, выходные данные которого закодированы интервальным кодированием, использующим сложную модель вычисления вероятности появления каждого бита. Система сжатия находит соответствия, используя словарную структуру данных, и создает поток символов и ссылок фраз, уже находящихся в словаре, который закодирован <tex>1</tex> битом интервальным кодировщиком.
  
 
Главной инновацией LZMA было то, что вместо общей байтовой модели, модель LZMA использовала зависящие от контекста битовые поля в каждом представлении букв или фраз. Эта модель почти также проста как битовая, но дает лучший коэффициент сжатия, потому что избегает смешивания несвязных битов вместе в том же самом контексте.
 
Главной инновацией LZMA было то, что вместо общей байтовой модели, модель LZMA использовала зависящие от контекста битовые поля в каждом представлении букв или фраз. Эта модель почти также проста как битовая, но дает лучший коэффициент сжатия, потому что избегает смешивания несвязных битов вместе в том же самом контексте.
  
==Основные преимущества==
+
===Сравнение с другими алгоритмами===
*Высокий коэффициент сжатия.
+
====Основные преимущества====
*Изменяемый размер словаря.
+
По сравнению с алгоритмом LZ77 алгоритм LZMA имеет следующие преимущества: более высокий коэффициент сжатия, изменяемый размер словаря, небольшие требования по памяти для «распаковки» данных.
*Небольшие требования по памяти для “распаковки” данных.
+
====Недостатки====
 +
Алгоритм LZMA не на всех типах входных данных работает одинаково эффективно.
  
==Схема кодирования==
+
===Схема кодирования===
 
В дополнении к алгоритмам, используемым в LZ77, LZMA использует Дельта-фильтр и интервальное кодирование.
 
В дополнении к алгоритмам, используемым в LZ77, LZMA использует Дельта-фильтр и интервальное кодирование.
 +
 +
Поступив на вход, данные пропускаются через дельта фильтр, где они преобразуются, для дальнейшего кодирования. После полученная последовательность подвергается словарному сжатию, алгоритм которого идентичен, алгоритму используемому в [[Алгоритмы LZ77 и LZ78|LZ77]].
 +
Пропустив данные через алгоритм «скользящего» окна, получаем код, который для достижения лучшего сжатия подвергнем интервальному кодированию. На выходе получаем интервал целых чисел который и будет отвечать исходной последовательности.
 +
 
 
[[Файл:Lzma3.png]]
 
[[Файл:Lzma3.png]]
 +
  
 
==Дельта-кодирование и декодирование==
 
==Дельта-кодирование и декодирование==
Строка 19: Строка 26:
  
 
===Пример===
 
===Пример===
  Входная последовательность: <tex>2,3,4,6,7,9,8,7,5,3,4</tex>
+
{| class="wikitable"
  Закодированная последовательность: <tex>2,1,1,2,1,2,-1,-1,-2,-2,1</tex>
+
|-
  Количество различных символов в входных данных: <tex>8</tex>
+
|style="background-color:#FFF;padding:2px 40px"|Входная последовательность:
  Количество различных символов после кодирования:<tex>4</tex>
+
|style="background-color:#FFF"| <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,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>
 +
|}
  
 
===Кодер и декодер===
 
===Кодер и декодер===
 
====Кодер====  
 
====Кодер====  
  
1. функция принимает массив и длину массива как аргументы, если длина не была передана, то массив не обрабатывается.<br/>
+
#Функция принимает массив и длину массива как аргументы, если длина не была передана, то массив не обрабатывается.
2. инициализируются переменные tmp, для сохранения последнего элемента и last для хранения предыдущего числа.
+
#Инициализируем переменные <tex>tmp</tex>, для сохранения последнего элемента и <tex>last</tex> для хранения предыдущего числа.Инициализируем цикл.
инициализация цикла, где i это счетчик.<br/> 
+
#В цикле:
3. В цикле: <br/>
+
#:3.1 Сохраняем элемент с индексом <tex>i</tex>.
* 3.1 сохранение символа под номером i в массиве <br/>
+
#:3.2 Вычисляем разницу между элементом под номером <tex>i</tex> и <tex>i-1</tex> и перезаписываем ее в элемент массива с индексом <tex>i</tex>.
* 3.2 вычисление разницы между элементом под номером i и i-1, первый элемент не меняется, и присвоение разницы    этому элементу.<br/>  
+
 
  '''function''' delta_encode(bp: '''char*''', n: '''int''')
+
  '''function''' deltaEncode(bp: '''list<char>''', n: '''int'''):
     '''char''' last=0,''tmp
+
     '''char''' last = 0
     '''for''' i=0 '''to''' n - 1
+
     '''for''' i = 0 '''to''' n - 1
         tmp=bp[i]
+
         '''char''' tmp = bp[i]
         bp[i]-=last
+
         bp[i] -= last
         last=tmp
+
         last = tmp
 
====Декодер====
 
====Декодер====
1.инициализация переменной для хранения последнего символа.<br/>
+
#Инициализируем переменную для хранения последнего символа.
2.инициализация цикла, где i это счетчик.<br/>
+
#Инициализируем цикл.
3.В цикле:<br/>
+
#В цикле:
*3.1 добавление к этому элементу значение предыдущего элемента.
+
#:3.1 Добавляем к этому элементу значение предыдущего элемента.
*3.2 сохранение значение этого элемента.
+
#:3.2 Сохраняем значение текущего элемента.
   '''function''' delta_encode(bp:'''char*''', n:'''int''')
+
   '''function''' deltaDecode(bp:'''list<char>''', n:'''int'''):
     '''char''' last=0
+
     '''char''' last = 0
     '''for'''i=0 '''to''' n - 1  
+
     '''for''' i = 0 '''to''' n - 1  
         bp[i]+=last
+
         bp[i] += last
         last=bp[i]
+
         last = bp[i]
==Модель "скользящего" окна==
 
Модель скользящего окна идентичен алгоритму LZ77
 
 
==Интервальное кодирование==
 
==Интервальное кодирование==
 
При интервальном кодировании все символы сообщения кодируются как одно число, для того чтобы достичь наилучшего коэффициента сжатия. Это работает эффективно с вероятностями появления символа не являющимися степенями двойки.
 
При интервальном кодировании все символы сообщения кодируются как одно число, для того чтобы достичь наилучшего коэффициента сжатия. Это работает эффективно с вероятностями появления символа не являющимися степенями двойки.
Интервальное кодирование работает так:<br/>
+
Интервальное кодирование работает так:
1. Выделяется достаточно большой диапазон целых чисел и дается оценка вероятности вхождения для символов.<br/>
+
 
2. Исходный диапазон чисел делится на поддиапазоны, размер которых пропорционален вероятности вхождения символа, за который они отвечают.<br/>
+
#Выделяется достаточно большой диапазон целых чисел и дается оценка вероятности вхождения для символов.
3. Каждый символ сообщения кодируется, после чего диапазон сокращается до размера диапазона только что закодированного символа и вновь делится по вероятностям.<br/>
+
#Исходный диапазон чисел делится на поддиапазоны, размер которых пропорционален вероятности вхождения символа, за который они отвечают.
 +
#Каждый символ сообщения кодируется, после чего диапазон сокращается до размера диапазона только что закодированного символа и вновь делится по вероятностям.
 +
 
 
В декодере должны быть такое же распределение вероятностей как и при кодировании.
 
В декодере должны быть такое же распределение вероятностей как и при кодировании.
 
== Пример ==
 
== Пример ==
Закодируем строку <tex>abehhilopsu</tex>.<br/>
+
Закодируем строку <tex>abehhilopsu</tex>.
Для начала пропустим ее через дельта фильтр.<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/>
+
Тогда исходная строка <tex>abehhilopsu</tex> примет вид:
Далее применим к получившейся строке метод "скользящего окна":
+
 
{| border="1"  
+
<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> различных символа.
 +
Далее применим к получившейся строке метод «скользящего» окна:
 +
{| class="wikitable" style="text-align:center"
 
  !Сообщение
 
  !Сообщение
 
  !Подстрока
 
  !Подстрока
Строка 71: Строка 92:
 
  |<tex>\fbox{a1330}133132 </tex>
 
  |<tex>\fbox{a1330}133132 </tex>
 
  |
 
  |
  |<0,0,<tex>a</tex>>
+
  |<tex>\langle0,0,a\rangle</tex>
 
  |-
 
  |-
 
  |<tex>a\fbox{13301}33132</tex>
 
  |<tex>a\fbox{13301}33132</tex>
 
  |
 
  |
  |<0,0,<tex>1</tex>>
+
  |<tex>\langle0,0,1\rangle</tex>
 
  |-
 
  |-
 
  |<tex>a1\fbox{33013}3132</tex>
 
  |<tex>a1\fbox{33013}3132</tex>
 
  |
 
  |
  |<0,0,<tex>3</tex>>
+
  |<tex>\langle0,0,3\rangle</tex>
 
  |-
 
  |-
 
  |<tex>a13\fbox{30133}132</tex>
 
  |<tex>a13\fbox{30133}132</tex>
 
  |<tex>3</tex>
 
  |<tex>3</tex>
  |<1,1,<tex>0</tex>>
+
  |<tex>\langle1,1,0\rangle</tex>
 
  |-
 
  |-
 
  |<tex>a1330\fbox{13313}2</tex>
 
  |<tex>a1330\fbox{13313}2</tex>
 
  |<tex>133</tex>
 
  |<tex>133</tex>
  |<4,3,<tex>1</tex>>
+
  |<tex>\langle4,3,1\rangle</tex>
 
  |-
 
  |-
 
  |<tex>a13301331\fbox{32}</tex>
 
  |<tex>a13301331\fbox{32}</tex>
 
  |<tex>3</tex>
 
  |<tex>3</tex>
  |<2,1,<tex>2</tex>>
+
  |<tex>\langle2,1,2\rangle</tex>
 
  |}
 
  |}
 +
Получаем код: <tex>00a001003110431212\$</tex>, где <tex>\$</tex> — это символ конца сообщения.
 +
 +
Для нашей строки получаем диапазон <tex>[0; 10^9]</tex> и распределение вероятностей: <tex>\{0: 0,37; 1: 0,26; 2: 0,11; 3: 0,11; 4: 0,05; a: 0,05; \$: 0,05\}</tex>
 +
 +
Таким образом, произведя интервальное кодирование  нашей строки, получим диапазон который будет отвечать закодированному сообщению.
 +
 
== См.также ==
 
== См.также ==
 
* [[Алгоритмы LZ77 и LZ78]]
 
* [[Алгоритмы LZ77 и LZ78]]
 +
* [[Алгоритм LZW]]
 +
* [[Алгоритм LZSS]]
 +
 +
==Примечания==
 +
<references/>
  
== Ссылки ==
+
== Источники информации ==
* [https://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Markov_chain_algorithm Соответствующая статья в википедии(Алгоритм описан немного по-другому)]
+
* [https://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Markov_chain_algorithm Wikipedia — алгоритма LZMA]
* [http://research.ijais.org/volume5/number4/ijais12-450900.pdf Статья подробно описывающая работу алгоритма LZMA и его аппаратную реализацию ]
+
* [http://research.ijais.org/volume5/number4/ijais12-450900.pdf E.Jebamalar Leavline — Статья подробно описывающая работу алгоритма LZMA и его аппаратную реализацию ]
* [https://ru.wikipedia.org/wiki/%D0%94%D0%B5%D0%BB%D1%8C%D1%82%D0%B0%D0%BA%D0%BE%D0%B4%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5 Дельта-кодирование ]
+
* [https://ru.wikipedia.org/wiki/%D0%94%D0%B5%D0%BB%D1%8C%D1%82%D0%B0-%D0%BA%D0%BE%D0%B4%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5 Wikipedia — Дельта кодирование ]
*[https://ru.wikipedia.org/wiki/%D0%98%D0%BD%D1%82%D0%B5%D1%80%D0%B2%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B5_%D0%BA%D0%BE%D0%B4%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5 Интервальное кодирование ]
+
*[https://ru.wikipedia.org/wiki/%D0%98%D0%BD%D1%82%D0%B5%D1%80%D0%B2%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B5_%D0%BA%D0%BE%D0%B4%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5 Wikipedia — Интервальное кодирование ]
* [http://www.7-zip.org/sdk.html Описание преимуществ алгоритма LZMA, LZMA SDK]
+
* [http://www.7-zip.org/sdk.html 7-zip — Описание преимуществ алгоритма LZMA, LZMA SDK]
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
  
 
[[Категория: Алгоритмы сжатия ]]
 
[[Категория: Алгоритмы сжатия ]]

Текущая версия на 19:31, 4 сентября 2022

LZMA (Lempel-Ziv-Markov chain Algorithm) — алгоритма сжатия без потерь. Он разрабатывался с 1996-1998 гг и впервые был использован в формате 7z архиватора 7-Zip[1]. Алгоритм использует словарное сжатие , в чем-то схожее с алгоритмом LZ77. На сегодняшний день алгоритм LZMA используется в основном в LZMA SDK[2] архиватора 7-Zip.

Описание

Основная идея

LZMA использует алгоритм словарного сжатия, выходные данные которого закодированы интервальным кодированием, использующим сложную модель вычисления вероятности появления каждого бита. Система сжатия находит соответствия, используя словарную структуру данных, и создает поток символов и ссылок фраз, уже находящихся в словаре, который закодирован [math]1[/math] битом интервальным кодировщиком.

Главной инновацией LZMA было то, что вместо общей байтовой модели, модель LZMA использовала зависящие от контекста битовые поля в каждом представлении букв или фраз. Эта модель почти также проста как битовая, но дает лучший коэффициент сжатия, потому что избегает смешивания несвязных битов вместе в том же самом контексте.

Сравнение с другими алгоритмами

Основные преимущества

По сравнению с алгоритмом LZ77 алгоритм LZMA имеет следующие преимущества: более высокий коэффициент сжатия, изменяемый размер словаря, небольшие требования по памяти для «распаковки» данных.

Недостатки

Алгоритм LZMA не на всех типах входных данных работает одинаково эффективно.

Схема кодирования

В дополнении к алгоритмам, используемым в LZ77, LZMA использует Дельта-фильтр и интервальное кодирование.

Поступив на вход, данные пропускаются через дельта фильтр, где они преобразуются, для дальнейшего кодирования. После полученная последовательность подвергается словарному сжатию, алгоритм которого идентичен, алгоритму используемому в LZ77. Пропустив данные через алгоритм «скользящего» окна, получаем код, который для достижения лучшего сжатия подвергнем интервальному кодированию. На выходе получаем интервал целых чисел который и будет отвечать исходной последовательности.

Lzma3.png


Дельта-кодирование и декодирование

Дельта фильтр перестраивает входные данные для эффективного сжатия скользящим окном. Первый байт на выходе совпадает с первым байтом на входе, последующие же байты представлены как разность между текущим и предыдущим байтом. Для постоянно меняющихся данных, дельта-кодирование делает работу скользящего окна более эффективной.

Пример

Входная последовательность: [math]2,3,4,6,7,9,8,7,5,3,4[/math]
Закодированная последовательность: [math]2,1,1,2,1,2,-1,-1,-2,-2,1[/math]
Количество различных символов в входных данных: [math]8[/math]
Количество различных символов после кодирования: [math]4[/math]

Кодер и декодер

Кодер

  1. Функция принимает массив и длину массива как аргументы, если длина не была передана, то массив не обрабатывается.
  2. Инициализируем переменные [math]tmp[/math], для сохранения последнего элемента и [math]last[/math] для хранения предыдущего числа.Инициализируем цикл.
  3. В цикле:
    3.1 Сохраняем элемент с индексом [math]i[/math].
    3.2 Вычисляем разницу между элементом под номером [math]i[/math] и [math]i-1[/math] и перезаписываем ее в элемент массива с индексом [math]i[/math].
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

Декодер

  1. Инициализируем переменную для хранения последнего символа.
  2. Инициализируем цикл.
  3. В цикле:
    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]

Интервальное кодирование

При интервальном кодировании все символы сообщения кодируются как одно число, для того чтобы достичь наилучшего коэффициента сжатия. Это работает эффективно с вероятностями появления символа не являющимися степенями двойки. Интервальное кодирование работает так:

  1. Выделяется достаточно большой диапазон целых чисел и дается оценка вероятности вхождения для символов.
  2. Исходный диапазон чисел делится на поддиапазоны, размер которых пропорционален вероятности вхождения символа, за который они отвечают.
  3. Каждый символ сообщения кодируется, после чего диапазон сокращается до размера диапазона только что закодированного символа и вновь делится по вероятностям.

В декодере должны быть такое же распределение вероятностей как и при кодировании.

Пример

Закодируем строку [math]abehhilopsu[/math]. Для начала пропустим ее через дельта фильтр. Тогда исходная строка [math]abehhilopsu[/math] примет вид:

[math]a[/math] [math]1[/math] [math]3[/math] [math]3[/math] [math]0[/math] [math]1[/math] [math]3[/math] [math]3[/math] [math]1[/math] [math]3[/math] [math]2[/math].

Как мы видим, теперь в нашей строке вместо [math]10[/math] различных символов [math]5[/math] различных символа. Далее применим к получившейся строке метод «скользящего» окна:

Сообщение Подстрока Код
[math]\fbox{a1330}133132 [/math] [math]\langle0,0,a\rangle[/math]
[math]a\fbox{13301}33132[/math] [math]\langle0,0,1\rangle[/math]
[math]a1\fbox{33013}3132[/math] [math]\langle0,0,3\rangle[/math]
[math]a13\fbox{30133}132[/math] [math]3[/math] [math]\langle1,1,0\rangle[/math]
[math]a1330\fbox{13313}2[/math] [math]133[/math] [math]\langle4,3,1\rangle[/math]
[math]a13301331\fbox{32}[/math] [math]3[/math] [math]\langle2,1,2\rangle[/math]

Получаем код: [math]00a001003110431212\$[/math], где [math]\$[/math] — это символ конца сообщения.

Для нашей строки получаем диапазон [math][0; 10^9][/math] и распределение вероятностей: [math]\{0: 0,37; 1: 0,26; 2: 0,11; 3: 0,11; 4: 0,05; a: 0,05; \$: 0,05\}[/math]

Таким образом, произведя интервальное кодирование нашей строки, получим диапазон который будет отвечать закодированному сообщению.

См.также

Примечания

Источники информации