Коротка історія розвитку теорії стиснення інформації

У сорокових роках учені, що працюють в області інформаційних технологій, ясно зрозуміли, що можна розробити такий спосіб збереження даних, при якому простір буде витрачатися більш ощадливо. Клод Шеннон, вивчаючи нюанси розходжень між семантикою (semantics) (що деяка сутність значить) і синтаксисом (syntax) (як деяка сутність виражається), розробив більшість базових понять цієї теорії. Розуміння того, що те саме значення (семантика) може бути реалізовано різними способами (синтаксис), приводить до закономірного питання: "Який спосіб вираження чого-небудь є найбільш економічним?" Пошук відповіді на це питання привів Шеннона до думки про ентропію, що, простіше говорячи, співвідноситься з кількістю, що міститься у файлі корисної інформації. Методи стиску намагаються збільшувати ентропію файлу, тобто зменшувати довжину файлу, зберігаючи при цьому всю інформацію.

Однак, Шеннон не був першим, хто задумувався про сутність інформації і визначенні її кількості. Перший крок на цьому шляху зробив у 1928 р. Хартлі. Основний отриманий їм результат можна сформулювати приблизно так: якщо в заданій безлічі, що містить N елементів, виділений деякий елемент x, про яке відомо лише, що він належить цій безлічі, то, щоб знайти x, необхідно одержати кількість інформації, рівне log2 N. Цю формулу звичайно називають формулою Хартлі.

Формула Хартлі є часткою случаємо більш загальної формули Шенона, що дозволяє знайти кількість інформації у випадковому повідомленні фіксованого алфавіту. Нехай X1, ..., Xn - символи цього алфавіту, P1, ..., Pn - імовірності їхньої появи в тексті повідомлення, тоді формула Шеннона приймає вид:

H = P1*log2(1/ P1) + ... + Pn*log2(1/ Pn),

де H - кількість біт інформації в одному символі повідомлення, чи ентропія символу повідомлення. Це число показує мінімальне середнє число біт, необхідних для представлення одного символу алфавіту даного повідомлення.

У деяких випадках алфавіт повідомлення може бути невідомий, тоді висуваються гіпотези про алфавіт повідомлення. Маючи різні алфавіти, можна досягти різних коефіцієнтів стиску. Наприклад, текстовий файл, якщо його розглядати як послідовність бітів, має ентропію порядку 0.7 - 0.9, якщо як послідовність байтів, - 0.5 - 0.7, хоча популярні програми стиску зменшують розміри текстових файлів до 0.3 - 0.4 від вихідного розміру.

Доказ Шенона не було конструктивним, тобто не містило способу побудови цих оптимальних кодів, а лише показувало їхнє існування. До появи роботи Шенона, кодування символів алфавіту при передачі повідомлення по каналах зв'язку здійснювалося однаковою кількістю біт, одержуваним по формулі Хартлі. З появою цієї роботи почали з'являтися способи, що кодують символи різним числом біт у залежності від імовірності появи їхній у тексті. Наприклад, часто у файлах деякі значення байта зустрічаються частіше інших. Таким чином, за рахунок використання для кожного значення байта коду різної довжини можна значно зменшити загальний розмір даних. Ця базова ідея лежить в основі алгоритмів стиску Шенона-Фано (Shannon-Fano) і Хафмана (Huffman). Подібні алгоритми вибирають більш короткі коди для часто зустрічаються і більш довгі для рідко зустрічаються значень байта. Звичайно текстові файли (у який одні значення байтів повторюються набагато частіше інших) вони стискають досить добре.

Більш тридцяти років алгоритм стиску Хафмана і його варіанти залишалися найбільш популярними методами. Однак у 1977 два дослідників з Ізраїлю запропонували зовсім інший підхід до цієї проблеми. Абрахам Лемпел і Якоб Зів висунули ідею формування "словника" загальних послідовностей даних. При цьому стиск даних здійснюється за рахунок заміни записів відповідними кодами зі словника.

2. Архіватори MS DOS

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

Однак у роботі з цією інформацією іноді небажано розкривати повний архів, щоб взяти один чи два необхідних чи файли ж просто подивитися, що в архіві за інформація.

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

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

Найбільш відомі программи-архіватори для MS-DOS: ARJ (розроблювач -- Robert K. Jung), pkzip

(компанія PKWARE Inc.), lha (Haruyasu Yoshizaki), zoo (Rahul Dhesi). Безумовним лідером в усьому світі за останні 5 років став архіватор RAR. В даний час RAR активно витісняє ZIP як основну утиліту стиску FTP архівів у мережі INTERNET. RAR я є єдиною всесвітньо використовуваною програмою, створеної російським програмістом (за винятком TETRIS). Всі архіватори відрізняються використовуваними алгоритмами стиску, форматами архівних файлів, швидкістю роботи і т.д.

Терміни, використовувані в архівації

Add file Додавання (копировние) файлу в архів. Якщо архів не існує, то він створюється.

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

Exclude selected files При архівації НЕ додавати в архів визначені файли.

Extract files Витяг файлів з архіву без збереження структури підкаталогів.

Extract files with pathnames Витяг файлів з архіву зі збереженням структури підкаталогів.

Fresh files Додавання в архів нових версій уже наявних там файлів.

Garble (чи scramble) files with password Архівація файлів з паролем. Витягти файли з такого архіву можна, лише