Участник:Facmad - История изменений

Facmad в 19:39, 6 декабря 2016

2016-12-06T19:39:25Z

Facmad в 18:55, 6 декабря 2016

2016-12-06T18:55:44Z

Facmad в 20:24, 5 декабря 2016

2016-12-05T20:24:53Z

Facmad в 19:54, 5 декабря 2016

2016-12-05T19:54:49Z

Facmad в 19:02, 5 декабря 2016

2016-12-05T19:02:48Z

Facmad в 19:00, 5 декабря 2016

2016-12-05T19:00:39Z

Facmad: Новая страница: «LZMA (англ. Lempel-Ziv-Markov chain-Algorithm) — это алгоритм, используемый для выполнения сжатия без поте...»

2016-12-05T18:59:05Z

Новая страница: «LZMA (англ. Lempel-Ziv-Markov chain-Algorithm) — это алгоритм, используемый для выполнения сжатия без поте...»

Новая страница

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

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

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

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

==Схема кодирования==
В дополнении к алгоритмам, используемым в LZ77, LZMA использует Дельта-фильтр и интервальное кодирование.
[[Файл:Lzma.jpg]]

← Предыдущая		Версия 19:39, 6 декабря 2016
Строка 14:		Строка 14:
	В дополнении к алгоритмам, используемым в LZ77, LZMA использует Дельта-фильтр и интервальное кодирование.		В дополнении к алгоритмам, используемым в LZ77, LZMA использует Дельта-фильтр и интервальное кодирование.
	[[Файл:Lzma3.png]]		[[Файл: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/>
		+	В декодере должны быть такое же распределение вероятностей как и при кодировании.

@@ Строка 13: / Строка 13: @@
 ==Схема кодирования==
 В дополнении к алгоритмам, используемым в LZ77, LZMA использует Дельта-фильтр и интервальное кодирование.
-[[Файл:Lzma2.png]]
+[[Файл:Lzma3.png]]

← Предыдущая		Версия 19:02, 5 декабря 2016
Строка 13:		Строка 13:
	==Схема кодирования==		==Схема кодирования==
	В дополнении к алгоритмам, используемым в LZ77, LZMA использует Дельта-фильтр и интервальное кодирование.		В дополнении к алгоритмам, используемым в LZ77, LZMA использует Дельта-фильтр и интервальное кодирование.
		+	[[Файл:a.jpg]]

← Предыдущая		Версия 19:00, 5 декабря 2016
Строка 13:		Строка 13:
	==Схема кодирования==		==Схема кодирования==
	В дополнении к алгоритмам, используемым в LZ77, LZMA использует Дельта-фильтр и интервальное кодирование.		В дополнении к алгоритмам, используемым в LZ77, LZMA использует Дельта-фильтр и интервальное кодирование.
−	~~[[Файл:Lzma.jpg]]~~