53
правки
Изменения
Нет описания правки
В дополнении к алгоритмам, используемым в LZ77, LZMA использует Дельта-фильтр и интервальное кодирование.
[[Файл:Lzma3.png]]
==Дельта-кодирование и декодирование==
Дельта фильтр перестраивает входные данные для эффективного сжатия скользящим окном. Первый байт на выходе совпадает с первым байтом на входе, последующие же байты представлены как разность между текущим и предыдущим байтом. Для постоянно меняющихся данных, дельта-кодирование делает работу скользящего окна более эффективной.
===Пример===
Входная последовательность: 2,3,4,6,7,9,8,7,5,3,4
Закодированная последовательность: 2,1,1,2,1,2,-1,-1,-2,-2,1
Количество различных символов в входных данных: 8
Количество различных символов после кодирования:4
===Кодер и декодер===
====Кодер:====
1. функция принимает массив и длину массива как аргументы, если длина не была передана, то массив не обрабатывается.<br/>
2. инициализируются переменные tmp, для сохранения последнего элемента и last для хранения предыдущего числа.
инициализация цикла, где i это счетчик.<br/>
3. В цикле: <br/>
* 3.1 сохранение символа под номером i в массиве <br/>
* 3.2 вычисление разницы между элементом под номером i и i-1, первый элемент не меняется, и присвоение разницы этому элементу.<br/>
'''function''' delta_encode(bp: '''char*''', n: '''int''')
'''char''' last=0,''tmp
'''for''' i=0 '''to''' n-1
tmp=bp[i]
bp[i]-=last
last=tmp
====Декодер:====
1.инициализация переменной для хранения последнего символа.<br/>
2.инициализация цикла, где i это счетчик.<br/>
3.В цикле:<br/>
*3.1добавление к этому элементу значение предыдущего элемента.
*3.2сохранение значение этого элемента.
'''function''' delta_encode(bp:'''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/>
В декодере должны быть такое же распределение вероятностей как и при кодировании.
