3622
правки
Изменения
м
Нет описания правки
'''LZMA''' (Lempel-Ziv-Markov chain Algorithm) — алгоритма сжатия без потерь. Он разрабатывался с 1996-1998 гг и впервые был использован в формате 7z архиватора 7-Zip<ref>[httphttps://wwwen.7-zipwikipedia.org/7z.html 7-Zip Formatwiki/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 было то, что вместо общей байтовой модели, модель LZMA использовала зависящие от контекста битовые поля в каждом представлении букв или фраз. Эта модель почти также проста как битовая, но дает лучший коэффициент сжатия, потому что избегает смешивания несвязных битов вместе в том же самом контексте.
===Сравнение с другими алгоритмами=======Основные преимущества====
По сравнению с алгоритмом LZ77 алгоритм LZMA имеет следующие преимущества: более высокий коэффициент сжатия, изменяемый размер словаря, небольшие требования по памяти для «распаковки» данных.
====Недостатки====
Алгоритм LZMA не на всех типах входных данных работает одинаково эффективно.
[[Файл:Lzma3.png]]
==Дельта-кодирование и декодирование==
===Пример===
{| class="wikitable"
|-
|style="background-color:#FFF;padding:2px 40px"|Входная последовательность: |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>2,1,1,2,1,2,-1,-1,-2,-2,18</tex>
|-
|style="background-color:#FFF;padding:2px 40px"|Количество различных символов в входных данныхпосле кодирования: <tex>8</tex> |style="background- color:#FFF"|Количество различных символов после кодирования:<tex>4</tex>
|}
#В цикле:
#:3.1 Сохраняем элемент с индексом <tex>i</tex>.
#:3.2 Вычисляем разницу между элементом под номером <tex>i</tex> и <tex>i-1</tex> и перезаписываем ее в элемент массива с индексом <tex>i</tex> .
'''function''' deltaEncode(bp: '''list<char>''', n: '''int'''):
'''char''' last = 0
'''for''' i = 0 '''to''' n - 1
'''char''' tmp = bp[i]
bp[i] -= last
<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> различных символа.
Далее применим к получившейся строке метод «скользящего» окна:
Таким образом, произведя интервальное кодирование нашей строки, получим диапазон который будет отвечать закодированному сообщению.
== См.также ==
* [[Алгоритмы LZ77 и LZ78]]
* [[Алгоритм LZW]]
* [[Алгоритм LZSS]]
==Примечания==
* [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 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 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 Wikipedia — Интервальное кодирование ]
* [http://www.7-zip.org/sdk.html 7-zip — Описание преимуществ алгоритма LZMA, LZMA SDK]
