Алгоритм LZMA — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 1: Строка 1:
LZMA (англ. Lempel-Ziv-Markov chain-Algorithm) — алгоритм сжатия данных без потерь. Он разрабатывался с 1996-1998 гг и впервые был использован в формате 7z архиватора 7-Zip. Алгоритм использует схему сжатия данных по словарю, сходную с алгоритмом LZ77, опубликованным Авраамом Лемпелем (Abraham Lempel) и Якобом Зивом (Jacob Ziv) в 1977 году, и отличается высокой степенью сжатия, произвольным размером словаря, тогда как скорость распаковки сходна с другими алгоритмами сжатия.
+
LZMA (англ. Lempel-Ziv-Markov chain-Algorithm) — это алгоритм, используемый для выполнения сжатия без потерь. Он разрабатывался с 1996-1998 гг и впервые был использован в формате 7z архиватора 7-Zip.Алгоритм использует словарное сжатие , в чем-то схожее с алгоритмом LZ77.
  
 
==Описание==
 
==Описание==
LZMA использует алгоритм сжатия данных по словарю, чей результат закодирован интервальным кодированием, используя сложную модель вычисления вероятности появления каждого бита. Система сжатия ищет совпадения, используя словарь структур данных, и создает поток символов и ссылок на фразы, который закодирован 1 битом интервальным кодировщиком, в то же время динамическое программирование используется, чтобы выбрать оптимальный код под некоторой аппроксимацией.
+
LZMA использует алгоритм словарного сжатия, выходные данные которого закодированы интервальным кодированием, использующим сложную модель вычисления вероятности появления каждого бита. Система сжатия находит соответствия, используя словарную структуру данных, и создает поток символов и ссылок фраз, уже находящихся в словаре, который закодирован 1 битом интервальным кодировщиком.
 +
 
 +
Главной инновацией LZMA было то, что вместо общей байтовой модели, модель LZMA использовала зависящие от контекста битовые поля в каждом представлении букв или фраз. Эта модель почти также проста как битовая, но дает лучший коэффициент сжатия, потому что избегает смешивания несвязных битов вместе в том же самом контексте.
 +
 
 +
==Основные преимущества==
 +
*Высокий коэффициент сжатия.
 +
*Изменяемый размер словаря.
 +
*Небольшие требования по памяти для “распаковки” данных.
 +
 
 +
==Схема кодирования==
 +
В дополнении к алгоритмам, используемым в 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/>
 +
В декодере должны быть такое же распределение вероятностей как и при кодировании.

Версия 15:59, 11 декабря 2016

LZMA (англ. Lempel-Ziv-Markov chain-Algorithm) — это алгоритм, используемый для выполнения сжатия без потерь. Он разрабатывался с 1996-1998 гг и впервые был использован в формате 7z архиватора 7-Zip.Алгоритм использует словарное сжатие , в чем-то схожее с алгоритмом LZ77.

Описание

LZMA использует алгоритм словарного сжатия, выходные данные которого закодированы интервальным кодированием, использующим сложную модель вычисления вероятности появления каждого бита. Система сжатия находит соответствия, используя словарную структуру данных, и создает поток символов и ссылок фраз, уже находящихся в словаре, который закодирован 1 битом интервальным кодировщиком.

Главной инновацией LZMA было то, что вместо общей байтовой модели, модель LZMA использовала зависящие от контекста битовые поля в каждом представлении букв или фраз. Эта модель почти также проста как битовая, но дает лучший коэффициент сжатия, потому что избегает смешивания несвязных битов вместе в том же самом контексте.

Основные преимущества

  • Высокий коэффициент сжатия.
  • Изменяемый размер словаря.
  • Небольшие требования по памяти для “распаковки” данных.

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

В дополнении к алгоритмам, используемым в 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. функция принимает массив и длину массива как аргументы, если длина не была передана, то массив не обрабатывается.
2. инициализируются переменные tmp, для сохранения последнего элемента и last для хранения предыдущего числа. инициализация цикла, где i это счетчик.
3. В цикле:

  • 3.1 сохранение символа под номером i в массиве
  • 3.2 вычисление разницы между элементом под номером i и i-1, первый элемент не меняется, и присвоение разницы этому элементу.
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.инициализация переменной для хранения последнего символа.
2.инициализация цикла, где i это счетчик.
3.В цикле:

  • 3.1добавление к этому элементу значение предыдущего элемента.
  • 3.2сохранение значение этого элемента.
  function delta_encode(bp:char*, n:int)
    char last=0
    fori=0 to n-1 
        bp[i]+=last
        last=bp[i]

Модель "скользящего" окна

Модель скользящего окна идентичен алгоритму LZ77

Интервальное кодирование

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