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