Декодирование
Пример
Декодировать: (0,A) (0,B) (0,R) (1,C) (1,D) (1,B) (3,A) (7,B) (1,R) (6,A)
Декодер |
Индекс |
Выходные данные |
(0, A) |
1 |
A |
(0, B) |
2 |
B |
(0, R) |
3 |
R |
(1, C) |
4 |
AC |
(1, D) |
5 |
AD |
(1, B) |
6 |
AB |
(3, A) |
7 |
RA |
(7, B) |
8 |
RAB |
(1, R) |
9 |
AR |
(6, A) |
10 |
ABA |
(0, EOF) |
11 |
|
Слово: АBRACADABRARABARABA
11
Какие же существую преимущества и недостатки у алгоритма L78?
Ограничен |
в 1,5 раза |
1,5 раза |
доступной |
||
памятью |
медленнее |
|
|
lZ77 |
|
Объем |
Скорость |
Коэффицие |
словаря |
сжатия |
нт сжатия |
12
Преимущества алгоритма LZ78
1.Универсальный алгоритм сжатия, который не требует каких-либо знаний о входных данных
2.Не использует скользящее окно, он хранит словарь из уже просмотренных фраз
3.Алгоритм сжатия данных без потерь
4.Использует трехуровневую структуру данных, поскольку она более эффективна
5.Длина подстроки, которую можно закодировать, не ограничена размером буфера
6.Возможность кодирования подстрок, отстоящих друг от друга на расстоянии, большем длины словаря;
13
Заключение
Таким образом, алгоритм упаковки и распаковки методом LZ78 весьма прост. Основную проблему при реализации этого метода представляет устройство словаря.
Очевидно, что чем больше словарь, тем (при прочих равных условиях) большую степень сжатия можно достичь. С другой стороны, важным практическим моментом является скорость упаковки, этот параметр тоже зависит от устройства словаря. Основные операции при упаковке: 1) поиск в словаре фрагмента; 2) вставка в словарь новых фрагментов. Необходимо, чтобы эти две операции были максимально быстрыми.
14
Список использованных источников
•http://mf.grsu.by/UchProc/livak/po/comprsite/theory_lzm.html «Алгоритмы сжатия»
•https://habr.com/ru/post/132683/ «Алгоритмы LZW, LZ77 и LZ78»
•http://masters.donntu.org/2005/fvti/kozlenko/library/ mastr_lzw.pdf «Алгоритмы сжатия информации»
автор – Д. Мастрюков
•https://www.compression.ru/book/pdf/ compression_methods_part1_2-4.pdf «Методы сжатия данных»
авторы – Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин.
15