53
правки
Изменения
Нет описания правки
==Схема кодирования==
В дополнении к алгоритмам, используемым в LZ77, LZMA использует Дельта-фильтр и интервальное кодирование.
[[Файл:aLzma3.jpgpng]] ==Дельта-кодирование и декодирование==Дельта фильтр перестраивает входные данные для эффективного сжатия скользящим окном. Первый байт на выходе совпадает с первым байтом на входе, последующие же байты представлены как разность между текущим и предыдущим байтом. Для постоянно меняющихся данных, дельта-кодирование делает работу скользящего окна более эффективной. ===Пример=== Входная последовательность: 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/>В декодере должны быть такое же распределение вероятностей как и при кодировании.
