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

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

Нехай на вхід кодера надходить послідовність символів виду / WED / WE / WEE / WEB, при цьому розмір алфавіту вхідних символів dim A = 255.

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

Вхідні символи Вихідний код Нові символи словника W 256 = W

E W 257 = WE

D E 258 = ED

D 259 = D

WE 256, 260 = WE

E 261 = E

WEE 260 262 = WEE

W 261 263 = E, W

EB 257 264 = WEB

<END> B

У результаті отримаємо вихідний код

/ WED <256> E <260> <261> <257> B.

Як при цьому змінилася довжина вихідного коду в порівнянні з вхідним.

Якщо для двійкового кодування рядка / WED / WE / WEE / WEB довжиною в 15 літер і розміром алфавіту dim A = 255 нам знадобилося б 15 * log ₂ 255 = 15х8 = 120 біт, то для двійкового кодування вихідний рядка кодера / WED <256> E <260> <261> <257> З довжиною в 10 нових символів з ​​алфавітом в 264 літери - 10 • 9 = 90 біт.

144, 144 +3, 147 +3, 150-4, 146-5, 141 +1, 142-4, 138 +5, 143 +2, 145-3
ß ß ß ß ß ß ß ß ß ß
144, 147, 150, 146, 141, 142, 138, 143, 145, 142.
Для кодування першого числа з отриманої послідовності різниць відліків, як і раніше, знадобиться 8 біт, всі інші числа можна закодувати 4-бітовими словами (один знаковий біт і 3 біти на кодування модуля числа).
Таким чином, в результаті кодування отримаємо кодове слово довжиною 8 + 9 * 4 = 44 біта або майже вдвічі коротший, ніж при індивідуальному кодуванні відліків.
Метод диференціального кодування дуже широко використовується в тих випадках, коли природа даних така, що їх сусідні значення незначно відрізняються один від одного, при тому, що самі значення можуть бути як завгодно великими.
Це відноситься до звукових сигналів, особливо до мови, зображень, сусідні пікселі яких мають практично однакові яскравості і колір і т.п. У той же час цей метод абсолютно не підходить для кодування текстів, креслень або будь-яких цифрових даних з незалежними сусідніми значеннями.

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