АЛГОРИТМЫ СЖАТИЯ

ТеорияПрактикаКонтроль знанийДемонстрация
Содержание
Введение
Классификация
-Критерии оценки
-Надёжность и сложность
-Методы сжатия
-Методы кодирования
Сжатие без потерь
-RLE
-Семейство LZ
-LZ77
-LZSS
-LZ78
-LZW
-LZM
-LZB
-LZH
-LZC
-LZT
-LZMV
-LZJ
-LZFG
-Унарное кодирование
-Метод Хаффмана
-Арифметическое кодирование
-Вероятностное сжатие
-BWT
Сжатие с потерями
-Звук и видео
-Изображения
Алгоритмы сжатия с потерями
-JPEG
-JPEG2000
-Wavelet
-Фрактальный
Предметный указатель

Обзор алгоритмов сжатия без потерь

Алгоритмы семейства LZ

Алгоритм LZ лежит в основе таких известных программ-архиваторов, как PKZIP, LHA, ARJ, Stacker, Dblspace и многих других. Своим появлением он обязан двум исследователям из Израиля: Якобу Зиву и Абрахаму Лемпелу (Jacob Ziv & Abraham Lempel). В 1977 году они опубликовали работу. Ее появление ознаменовало начало новой эры в сжатии информации. Практически все современные компьютерные программы-архиваторы используют ту или иную модификацию алгоритма LZ. Одной из причин широкого распространения алгоритма LZ стала его исключительная простота.

Основная идея алгоритма
Вспомним первое четверостишье бессмертного “Евгения Онегина”:

Мой дядя, самых честных правил,
Когда не в шутку занемог,
Он уважать себя заставил
И лучше выдумать не мог.
Его пример...

Обратите внимание на то, что Пушкин избегает повторного использования подстроки “Мой дядя”. Сначала вместо нее используется местоимение “он”, затем — “его”. При этом информативность всего сообщения нисколько не снижается, а его объем уменьшается. Очевидно, что нет смысла полностью повторять однажды сказанную в разговоре фразу несколько раз. То же самое относится и к компьютерной информации.

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


НазадК cодержаниюВперёд
2006 All Rights Reserved