Стиснення без втрат

Стиснення без втрат — метод стиснення даних, при використанні якого закодована інформація може бути повністю відновлена зі стиснутих даних. Навпроти, стиснення з втратами дозволяє лише відновлення даних, які є тільки наближенням до початкових даних. Для кожного з типів цифрової інформації, як правило, існують свої оптимальні алгоритми стиснення без втрат.

Стиснення даних без втрат використовується в багатьох програмах. Наприклад, воно використовується в усіх файлових архіваторах. Воно також використовується як компонент в стисненні з втратами.

Стиснення без втрат використовується, коли важливо, щоб відновленні дані були ідентичні оригіналу. Типовий приклад — виконуваний файл або джерельний код, текстовий файл. Деякі графічні файлові формати, наприклад, PNG та GIF використовують тільки стиснення без втрат, тоді як формати TIFF та MNG можуть використовувати стиснення як з втратами, так й без втрат. Формати стиснення звуку без втрат використовується для архівування або виробничих цілей, в той час, як менші формати стиснення аудіо з втратами використовуються в аудіопрогравачах та в ситуаціях коли простір для зберігання інформації обмежений або нема потреби в точному відтворенні інформації.

У загальних рисах значення стиснення без втрат полягає в пошуку закономірності в початкових даних і з її урахуванням генерації іншої послідовності, яка повністю описує початкову. Наприклад, для кодування бінарних послідовностей, в яких багато нулів та мало одиниць, ми можемо використати таку заміну:

• 00 > 0
• 01 > 10
• 10 > 110
• 11 > 111

В такому випадку шістнадцять бітів:

00 01 00 00 11 10 00 00.

будуть перетворені у 13 бітів:

0 10 0 0 111 110 0 0.

Така заміна є видом префіксного коду, тобто має таку особливість: якщо ми запишемо стиснений рядок без пропусків, ми все одно зможемо розставити в ній пропуски — а тому, і відновити початкову послідовність. Найбільш відомим префіксним кодом є код Хаффмана.

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

Статистичні моделі алгоритмів для тексту (чи текстових бінарних даних, таких як виконувальні файли) містять:

• · Перетворення Берроуза — Вілера
• · LZ77 і LZ78
• · LZW[4]