Изменения

'''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 использует алгоритм словарного сжатия, выходные данные которого закодированы интервальным кодированием, использующим сложную модель вычисления вероятности появления каждого бита. Система сжатия находит соответствия, используя словарную структуру данных, и создает поток символов и ссылок фраз, уже находящихся в словаре, который закодирован <tex>1 </tex> битом интервальным кодировщиком.

===Сравнение с другими алгоритмами=======Основные преимущества====*Высокий По сравнению с алгоритмом LZ77 алгоритм LZMA имеет следующие преимущества: более высокий коэффициент сжатия.*Изменяемый , изменяемый размер словаря.*Небольшие , небольшие требования по памяти для “распаковки” «распаковки» данных.====Недостатки====Алгоритм LZMA не на всех типах входных данныхработает одинаково эффективно.

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

{| 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. #Функция принимает массив и длину массива как аргументы, если длина не была передана, то массив не обрабатывается.<br>2. #Инициализируем переменные <tex>tmp</tex>, для сохранения последнего элемента и <tex>last </tex> для хранения предыдущего числа.Инициализируем цикл.<br> 3. #В цикле: <br>* #:3.1 Сохраняем элемент с индексом <tex>i.<br/tex>.* #:3.2 Вычисляем разницу между элементом под номером <tex>i </tex> и <tex>i-1 </tex> и перезаписываем ее в элемент массива с индексом <tex>i.<br/tex> .   '''function''' delta_encodedeltaEncode(bp: '''list<char*>''', n: '''int'''): '''char''' last=0,''tmp '''for''' i=0 '''to''' n - 1 '''char''' tmp=bp[i] bp[i]-=last last=tmp

1.#Инициализируем переменную для хранения последнего символа.<br/>2.#Инициализируем цикл.<br/>3.#В цикле:<br/>* #:3.1 Добавляем к этому элементу значение предыдущего элемента.* #:3.2 Сохраняем значение текущего элемента. '''function''' delta_encodedeltaDecode(bp:'''list<char*>''', n:'''int'''): '''char''' last=0 '''for'''i=0 '''to''' n - 1 bp[i]+=last last=bp[i]==Модель "скользящего" окна==Модель скользящего окна идентичен алгоритму LZ77

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

Закодируем строку <tex>abehhilopsu</tex>.<br>Для начала пропустим ее через дельта фильтр.<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>. Как мы видим, теперь в нашей строке вместо <tex>10 </tex> различных символов <tex>5 </tex> различных символа.<br>Далее применим к получившейся строке метод "скользящего" «скользящего» окна:{| borderclass="1wikitable" style="text-align:center"

|<0tex>\langle0,0,<tex>a\rangle</tex>>

|<0tex>\langle0,0,<tex>1\rangle</tex>>

|<0tex>\langle0,0,<tex>3\rangle</tex>>

|<1tex>\langle1,1,<tex>0\rangle</tex>>

|<4tex>\langle4,3,<tex>1\rangle</tex>>

|<2tex>\langle2,1,<tex>2\rangle</tex>>

Получаем код: <tex>00a001003110431212<EOM>\$</tex>, где <tex><EOM>\$</tex>— это символ конца сообщения.<br>  Для нашей строки получаем диапазон [<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><EOM></tex>\$: 0,05\}<br/tex> 

== Ссылки Источники информации ==* [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]