1632
правки
Изменения
м
{| 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>8</tex> |- |style="background-color:#FFF;padding:2px 40px"| Количество различных символов после кодирования: |style="background-color:#FFF"| <tex>4</tex> |}
1. #Функция принимает массив и длину массива как аргументы, если длина не была передана, то массив не обрабатывается.#Инициализируем переменные <tex>tmp</tex>, для сохранения последнего элемента и <tex>last</tex> для хранения предыдущего числа.Инициализируем цикл.#В цикле:#:3.1 Сохраняем элемент с индексом <tex>i</tex>.#:3.2 Вычисляем разницу между элементом под номером <tex>i</tex> и <tex>i-1</tex> и перезаписываем ее в элемент массива с индексом <tex>i</tex>.
2. Инициализируем переменные <tex>tmp</tex>, для сохранения последнего элемента и <tex>last</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 Сохраняем значение текущего элемента.
==Модель "скользящего" окна==
Модель скользящего окна идентичен алгоритму LZ77
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, LZMA использует Дельта-фильтр и интервальное кодирование.
Поступив на вход, данные пропускаются через дельта фильтр, где они преобразуются, для дальнейшего кодирования. После полученная последовательность подвергается словарному сжатию, алгоритм которого идентичен, алгоритму используемому в [[Алгоритмы LZ77 и LZ78|LZ77]].
Пропустив данные через алгоритм «скользящего» окна, получаем код, который для достижения лучшего сжатия подвергнем интервальному кодированию. На выходе получаем интервал целых чисел который и будет отвечать исходной последовательности.
[[Файл:Lzma3.png]]
==Дельта-кодирование и декодирование==
===Пример===
===Кодер и декодер===
====Кодер====
'''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]
