Поцедури декодування

LZW-декодер, обробляючи вхідний потік закодованих даних, відновлює з нього вихідні дані. Так само, як і алгоритм стиснення, декодер додає нові рядки в словник щоразу, коли знаходить у вхідному потоці новий код. Все, що йому залишається зробити, - це перетворити вхідний код у вихідну рядок символів і віддати її на вихід кодера.

Схема роботи LZW-декодера виглядає наступним чином:

рядок на вході кодера - / WED <256> E <260> <261> <257> B.

Вхідні символи Вихідна рядок Нові символи словника

/ /

W W 256 = / W

E E 257 = WE

D D 258 = ED

256 / W 259 = D /

E E 260 = / WE

260 / WE 261 = E /

261 E / 262 = / WEE

257 WE 263 = E / W

B B 264 = WEB

Самою чудовою якістю цього способу стиснення є те, що весь словник нових символів передається декодеру без власне передачі.

В кінці процесудекодування декодер має точно такий же словник нових символів, який у процесі кодування був накопичений кодером, при цьому його створення було частиною процесу декодування. Робота кодера -декодера сімейства LZ77 - першій опублікованій версії LZ-методу - виглядає дещо інакше.
В алгоритмі LZ77 покажчики позначають фрази у вікні постійного діаметра, попередні позиції коду. Максимальна довжина замінних покажчиками підрядків визначається параметром F (зазвичай це від 10 до 20). Ці обмеження дозволяють LZ77 використовувати "ковзне вікно" з N символів.

З них перші NF були вже закодовані, а останні F складають попереджуючий буфер.
При кодуванні символу в перших NF символах вікна шукають найдовшу, збігається з цим буфером рядок. Вона може частково перекривати буфер, але не може бути самим буфером.
Знайдене найбільшу відповідність потім кодується тріадою [i, j, a] де i є його зсув від початку буфера,

j - довжина відповідності,

a - перший символ, що не відповідає підрядку вікна.
Потім вікно зсувається вправо на j +1 символ і готове до нового кроку алгоритму.
Прив'язка певного символу до кожного вказівником гарантує, що кодування буде виконуватися навіть в тому випадку, якщо для першого символу попереджуючого буфера не буде знайдено відповідність.
Обсяг пам'яті, необхідний кодеру і декодеру, обмежується розміром вікна. Кількість біт, необхідне для подання зсуву (i) у тріаді, становить [log(NF)].

Кількість символів (j), замінних тріадою, може бути закодовано [logF] бітами.
Декодування здійснюється дуже просто і швидко. При цьому підтримується той самий порядок роботи з вікном, що і при кодуванні, але на відміну від пошуку однакових рядків він, навпаки, копіює їх з вікна відповідно до чергової тріади.

Диференціальне кодування

Робота диференціального кодера заснована на тому факті, що для багатьох типів даних різниця між сусідніми відліками відносно невелика, навіть якщо самі дані мають великі значення. Наприклад, не можна очікувати великої різниці між сусідніми пікселями цифрового зображення.
Наступний простий приклад показує, яку перевагу може дати диференційне кодування (кодування різниці між сусідніми відліками) у порівнянні з простим кодуванням без пам'яті (кодуванням відліків незалежно один від одного).
Проскануйте 8-бітове (256-рівневе) цифрове зображення, при цьому десять послідовних пікселів мають рівні:
144, 147, 150, 146, 141, 142, 138, 143, 145, 142.
Якщо закодувати ці рівні піксель за пикселами яким-небудь кодом без пам'яті, що використовує 8 біт на піксел зображення, отримаємо кодове слово, що містить 80 біт.
Припустимо тепер, що перш ніж піддавати відліки зображення кодуванню, ми обчислимо різниці між сусідніми пікселями. Ця процедура дає нам послідовність такого вигляду:
144, 147, 150, 146, 141, 142, 138, 143, 145, 142.
ß ß ß ß ß ß ß ß ß ß
144, 3, 3, - 4, -5, 1, -4, 5, 2, -3.
Вихідна послідовність може бути легко відновлена ​​з різницевої простим підсумовуванням (дискретним інтегруванням):

---

Дата добавления: 2015-07-11