LZ77 і LZ78: відмінності між версіями
| [неперевірена версія] | [перевірена версія] |
Вилучено вміст Додано вміст
CHINGO (обговорення | внесок) Немає опису редагування |
CHINGO (обговорення | внесок) Немає опису редагування |
||
Рядок 2:
== Історія виникнення ==
Більше тридцяти років [[Алгоритм Хафмана|алгоритм стиснення Хаффмана]] і його варіанти залишалися найпопулярнішими методами. Проте 1977 року ізраїльскі дослідники Авраам Лемпель і
При цьому стиснення даних здійснюється за рахунок заміни записів відповідними кодами із словника. Існують два алгоритми стиснення даних — LZ77 і LZ78. Вони вже не вимагають включення словника даних в архів, оскільки якщо ви формуєте ваш словник визначеним способом, програма декодування може його відновлювати безпосередньо з ваших даних. На жаль, LZ77 і LZ78 витрачають багато часу на створення ефективного словника. Лемпель був запрошений фірмою Sperry для допомоги в розробці способу найефективнішої упаковки даних на комп'ютерних стрічках. У цій же фірмі Тері Велч розширив алгоритм LZ78, створивши новий варіант, широко відомий як LZW.
Рядок 28:
Текст стискувався на 4 символи, але і, як мінімум, 4 символи опинилися у словнику. Крім того, побудова словника зажадає введення роздільників і ін.
Але і це ще не все. А якщо в тексті вже є символи 1 ? Як зрозуміти, що це саме 1, а не посилання на словник? Як же поступити найбільш грамотно? Ось тут відповідь далеко неоднозначна. Вона і не може бути однозначна, тому що стиснення — це не таблиця множення. Один текст краще стискається одним методом інший — абсолютно іншим способом. Спершу ми розглянемо дуже спрощений варіант, щоб мати від чого
Для визначеності вважатимемо, що кожен символ в тексті — це впорядкований набір з 8 бітів, тобто байт, або, що те ж саме ціле число від 0 до 255.
Рядок 71:
== Варіанти вдосконалення ==
Приведені вище деталі алгоритму і значення параметрів не можуть бути виведені якими-небудь раціональними строгими методами. У якійсь мірі в них відбиті особливості сучасного програмування і людської мови. Але автори кожного архіватора знаходять свій оптимум, і що краще — може підказати тільки практика (критерій загальний, але
Могутні архіватори зазвичай роблять попередню оцінку початкового файлу і до кожного файлу (або до великих частин одного файлу) здійснюють індивідуальний підхід. Наприклад, перед кожним великим фрагментом стислої коди вказується його обсяг і тип стискування для цього досить 3 байти, які не псують загальної якості компресії.
| |||