Алгоритмы сжатия данных с потерями и без потерь

1.

Выполнили:
Студенты: Голованова Татьяна
Кочуев Андрей

2.

Алгоритмы сжатия данных
С потерями
Без потерь

3.

Семейство алгоритмов LZ*
Авраам Лемпель
Яаков Зив

4.

Семейство алгоритмов LZ*

5.

LZ77
1977 – год публикации статьи с алгоритмом.
Идея:
Повторные
вхождения
группы
элементов заменяются ссылкой на
их
первое вхождение

6.

LZ77
Скользящее окно:
α = abbdcabdcaabdaa
0
0
W=5
М=3
0
Код:
1. Смещение;
2. Длина подстроки;
3. Символ расхождения.
W – длина словаря
М – длина буфера
W >> M

7.

LZ77
Общая длина кода:
N – число шагов

8.

LZ77
Недостатки:
• невозможность кодирования подстрок, отстоящих
друг от друга на расстоянии, большем длины
словаря;
• длина подстроки, которую можно закодировать,
ограничена размером буфера;
• малая эффективность при кодировании
незначительного объёма данных

9.

Спасибо
за
внимание!!!