LZ77 і LZ78: відмінності між версіями
[перевірена версія] | [неперевірена версія] |
Вилучено вміст Додано вміст
м оформлення, вікіфікація |
|||
Рядок 33:
Текст стискувався на 4 символи, але і, як мінімум, 4 символи опинилися у словнику. Крім того, побудова словника зажадає введення роздільників і ін.
Але і це ще не все. А якщо в тексті вже є символи 1 ? Як зрозуміти, що це саме 1, а не посилання на словник? Як же поступити найбільш грамотно? Ось тут відповідь далеко неоднозначна. Вона і не може бути однозначна, тому що стиснення — це не таблиця множення. Один текст краще стискається одним методом, інший — абсолютно іншим способом. Спершу ми розглянемо дуже спрощений варіант, щоб мати від чого відштовхуватися надалі.
Для визначеності вважатимемо, що кожен символ в тексті — це впорядкований набір з 8 бітів, тобто байт, або, що те ж саме ціле число від 0 до 255.
Послідовно читаємо початковий текст і одночасно формуємо вихідний файл. Якщо чергова буква зустрілася вперше, або вона виявилася останньою в тексті, то на вихід посилаємо біт 1 і 8 бітів від самої цієї букви. Так само треба
Якщо черговий символ в парі з наступним за ним вже зустрічався то в принципі від цієї пари можна вивести два біта 01 і вказівку на існуючу аналогічну пару. Тоді декодувальник, побачивши 01, по цій вказівці подивиться на вже розшифровану частину тексту, візьме потрібну пару і припише таку саму в кінець розшифрованої частини.
|