1632
правки
Изменения
м
1. #Функция принимает массив и длину массива как аргументы, если длина не была передана, то массив не обрабатывается. 2. #Инициализируем переменные <tex>tmp</tex>, для сохранения последнего элемента и <tex>last</tex> для хранения предыдущего числа.Инициализируем цикл.#В цикле:#:3.1 Сохраняем элемент с индексом <tex>i</tex>.#:3.2 Вычисляем разницу между элементом под номером <tex>i</tex> и <tex>i-1</tex> и перезаписываем ее в элемент массива с индексом <tex>i</tex>.
3. В цикле:
* 3.1 Сохраняем элемент с индексом <tex>i</tex>.
* 3.2 Вычисляем разницу между элементом под номером <tex>i</tex> и <tex>i-1</tex> и перезаписываем ее в элемент массива с индексом <tex>i</tex>
1.#Инициализируем переменную для хранения последнего символа. 2.#Инициализируем цикл. 3.#В цикле:* #:3.1 Добавляем к этому элементу значение предыдущего элемента.* #:3.2 Сохраняем значение текущего элемента.
rollbackEdits.php mass rollback
'''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 было то, что вместо общей байтовой модели, модель LZMA использовала зависящие от контекста битовые поля в каждом представлении букв или фраз. Эта модель почти также проста как битовая, но дает лучший коэффициент сжатия, потому что избегает смешивания несвязных битов вместе в том же самом контексте.
===Сравнение с другими алгоритмами=======Основные преимущества====
По сравнению с алгоритмом LZ77 алгоритм LZMA имеет следующие преимущества: более высокий коэффициент сжатия, изменяемый размер словаря, небольшие требования по памяти для «распаковки» данных.
====Недостатки====
Алгоритм LZMA не на всех типах входных данных работает одинаково эффективно.
Поступив на вход, данные пропускаются через дельта фильтр, где они преобразуются, для дальнейшего кодирования. После полученная последовательность подвергается словарному сжатию, алгоритм которого идентичен, алгоритму используемому в [[Алгоритмы LZ77 и LZ78|LZ77]].
Пропустив данные через алгоритм «скользящего» окна, получаем код, который для достижения лучшего сжатия подвергнем интервальному кодированию. На выходе получаем интервал целых чисел который и будет отвечать исходной последовательности.
[[Файл: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"|Закодированная последовательность: <tex>2,1,1,2,1,2,-1,-1,-2,-2,1</tex> |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>
|}
====Кодер====
'''function''' deltaEncode(bp: '''list<char>''', n: '''int'''):
'''char''' last = 0
'''for''' i=0 '''to''' n - 1 '''char''' tmp tmp = bp[i]
bp[i] -= last
last = tmp
====Декодер====
'''function''' deltaDecode(bp:'''list<char>''', n:'''int'''):
'''char''' last = 0
'''for'''i = 0 '''to''' n - 1
bp[i] += last
last = bp[i]
<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"
!Сообщение
|<tex>\fbox{a1330}133132 </tex>
|
|<<tex>0\langle0,0,a\rangle</tex>>
|-
|<tex>a\fbox{13301}33132</tex>
|
|<<tex>0\langle0,0,1\rangle</tex>>
|-
|<tex>a1\fbox{33013}3132</tex>
|
|<<tex>0\langle0,0,3\rangle</tex>>
|-
|<tex>a13\fbox{30133}132</tex>
|<tex>3</tex>
|<<tex>1\langle1,1,0\rangle</tex>>
|-
|<tex>a1330\fbox{13313}2</tex>
|<tex>133</tex>
|<<tex>4\langle4,3,1\rangle</tex>>
|-
|<tex>a13301331\fbox{32}</tex>
|<tex>3</tex>
|<<tex>2\langle2,1,2\rangle</tex>>
|}
Получаем код: <tex>00a001003110431212\$</tex>, где <tex>\$</tex> — это символ конца сообщения.
Для нашей строки получаем диапазон [<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>\$</tex>: 0,05\}</tex>
Таким образом, произведя интервальное кодирование нашей строки, получим диапазон который будет отвечать закодированному сообщению.
== См.также ==
* [[Алгоритмы LZ77 и LZ78]]
* [[Алгоритм LZW]]
* [[Алгоритм LZSS]]
==Примечания==
<references/>
== Ссылки Источники информации ==
* [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]
