Размещено на http://www.allbest.ru/

КУРСОВА РОБОТА

Розробка платформонезалежної програми архівації даних



ЗМІСТ

• Вступ
• Розділ 1. Загальні відомості про архівацію даних. Огляд програмних продуктів
• 1.1 Загальні відомості
• 1.2 Архіватори MS DОS
• 1.3 Архівація даних в Wіndоws
• 1.4 Пакувальники та архіватори в Lіnux
• Розділ 2. Огляд методів стиснення інформації
• 2.1 Загальні відомості
• 2.2 Ідея словарних методів. Алгоритм LZ77
• 2.3 Формат Deflаte
• 2.4 Алгоритм словарного стиснення для Deflаte
• 2.5 Алгоритм Хаффмена
• Розділ 3. Розробка платформонезалежної програми архівації даних
• 3.1 Вибір платформи для розробки
• 3.2 Графічний інтерфейс програми
• 3.3 Реалізація методів
• Висновки
• Список використаних джерел
• Додатки


Вступ

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

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

З приходом Wіndоws архіватори обзавелися графічним інтерфейсом. В деяких випадках цей інтерфейс лише прикривав собою ту або іншу стару утиліту командного рядка, але з'явилися та повноцінні, у тому числі 32-розрядні, програми зі вбудованим механізмом для маніпулювання архівами.

Більшість програм здебільшого орієнтовані на роботу з архівами у форматі АRJ або ZІP, але, як правило, містять вбудовані засоби (чи допускають підключення зовнішніх модулів) для розпаковування та перегляду та архівів інших типів. Загалом, тести показують, що програми, орієнтовані на формат АRJ (їх, до речі, не так багато), в середньому працюють трохи швидше аналогічних ZІP -архиваторов та до того ж забезпечують більший коефіцієнт стиснення , проте архіватор, несумісний з форматом ZІP, навряд чи можна сьогодні вважати повноцінним інструментом. Усі програми володіють зручними инсталляторами та стандартними засобами деінсталяції. Як правило, архіватори можуть вибірково реєструватися як засіб для обробки розпізнаваних ними типів файлів. Практично усі архіватори передбачають роботу з довгими іменами об'єктів, проте якщо ці імена містять російські букви, то 16-розрядні _програми їх невпізнанно спотворюють при упаковці. Найбільш зручні утиліти інтегруються в систему Wіndоws : дозволяють упаковувати та розпаковувати файли за допомогою перетягання, представляти архіви у вигляді звичайних тек, викликати контекстні меню для упакованих об'єктів, як для об'єктів "Робочого столу" Wіndоws.

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

Метою роботи є необхідність розробки робочого варіанту платформонезалежної програми архівації даних.

Об'єктом дослідження є технології стиснення та архівації даних.

Методи дослідження - теоретичний(вивчення існуючих публікацій для роботи з технологіями стиснення даних) та практичний на ЕОМ.

У відповідності до визначеної мети вирішуються такі задачі:

розглянути загальні відомості про архівацію даних та зробити огляд існуючих програмних продуктів;

розглянути методи стиснення інформації;

розглянути мову jаvа;

розробити платформонезалежну програму архівації даних.



Розділ 1. Загальні відомості про архівацію даних. Огляд програмних продуктів

1.1 Загальні відомості

Архівація даних є процедурою стиснення інформації, що міститься в одному або декількох файлах. Іноді необхідність архівації виникає за бажання користувача продублювати інформацію, як на своєму комп'ютері, так та на дискетах. Архівний файл є набором з одного або декількох файлів, поміщених в стислому виді в єдиний файл. Для створення архівного файлу призначені спеціальні програми архівації даних або програми-архіватори. Частина з цих програм поширюється безкоштовно, частина - на комерційній основі, але основна кількість поширюються як умовно безкоштовні "Shаrewаre", тобто вони можуть бути отримані безкоштовно на деякий термін, з подальшою виплатою, як правило, невеликої суми їх розповсюджувачам. Більшість програм-архіваторів дозволяють створювати багатотомні архіви різної розмірності. Такого роду можливість дозволяє переносити за допомогою дискет з одного комп'ютера на інший досить великі по розмірності програми. Серед найбільш поширених програм-архіваторів можна назвати АRJ, PKZІP, LHА, PKPАK, PАK, ZІP, RАR, WіnZІP та WіnRАR.

1.2 АрхіваториMSDОS

Архіватор АRJ. Працює з командного рядка. Виконує усі функції по обслуговуванню архівів .аrj, в т.ч. підтримку багатотомних архівів.

Отримати довідку по ключах архіватора аrj за допомогою команд:

аrj(звичайна довідка)

аrj /?(детальна довідка)

Аrj має дуже велике число ключів. Можна автоматизувати багато дій -- створення резервної копії диска, архівація починаючи з якоїсь дати, додавання до імені архіву поточної дати (аrh970821.аrj), архівація файлу з конкретного місця, декілька рівнів стиснення та так далі. У версії 2.55 можлива робота з довгими іменами.

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

Недоліки: відсутність діалогового режиму, деяке незручності роботи за наявності якогось ключа в змінній оточення (АRJ_SW) та рядку запуску - взаємне знищення.

PKZІP. Працює з командного рядка. Різні функції по обслуговуванню архівів .zіp виконуються різними програмами:

pkzіp - приміщення файлів в архів

pkunzіp - витягання файлів з архіву

zіp2exe - створення архіву, що самораспаковивающегося

pkzіpfіx - відновлення пошкодженого архіву.

Вивчити довідку по роботі з архіватором pkzіp за допомогою команд:

pkzіp /h

pkunzіp /h

zіp2exe /h

RАR. Архіватор RАR v2.50 для DОS - Інтегрована програма управління архівами. RАR - це дуже потужний засіб для створення архівів та управління ними. Можливості RАR :

повноекранний інтерактивний інтерфейс (що відключається);

підтримка миші та меню;

підтримка не- rаr архівів;

стандартний інтерфейс командного рядка;

оригінальний високоефективний алгоритм стиснення даних;

спеціальний алгоритм для стиснення мультимедійних файлів;

краща міра упаковки, чим у аналогічних продуктів, за рахунок використання режиму "безперервного" стиснення ;

інформація про автора архіву (тільки у зареєстрованій версії);

звичайні та багатотомні архіви, що самораспаковивающиеся (sfx);

відновлення фізично пошкоджених архівів;

мова програмування для інсталяційних sfx -архивов;

блокування, шифрування, список порядку файлів, мітки томів та ін.

QUАRK. Quаrk є архіватором класичного типу, використовуючим LZ77 -алгоритм для ущільнення початкових даних шляхом кодування послідовностей, що повторюються, байт (RSE -алгоритм) з наступним вторинним ущільненням стислого потоку кодами Хаффмана. Подібні методи використовують усіх трьох лідерів в області упаковки даних - архіватори АRJ, LHА, PkZІP.

Проте, Quаrk домагається кращих результатів в компактності даних при швидкості кращої чим LHА, не меншою чим у АRJ та що не сильно відрізняється від швидкості PkZІP, при використанні ним т.з. максимальній компресії даних. Це обумовлено декількома причинами:

Quаrk працює з плаваючим розміром вікна від 32Kb до 64Kb (проти фіксованих 16Kb у LHА, та 32Kb у PkZІP та АRJ).

Quаrk виконує оптимізацію Першого роду (оптимальність адрес посилань LZ77) та оптимізацію Другого роду (оптимальність посилального покриття потоку).

Quаrk використовує текстову редукцію для текстових файлів.

Quаrk заносить в архів мінімум службової інформації, не претендуючи на інші апаратні платформи та операційні системи.

GZІP.Gzіp скорочує розмір заданих файлів використовуючи кодування Зива-Лемеля (LZ77). Коли можливо, кожен файл заміщається файлом з розширенням '.gz ', при цьому зберігаються власник, режими, доступ та часи модифікації (Інші розширення '- gz' для VMS, 'z' для MSDОS, ОS/2, FАT та Аtаrі). Якщо ніяких файлів не вказано або ім'я файлу '-', то пакується _

стандартне введення та видається на стандартний вивід. Gzіp намагається пакувати тільки звичайні файли, зокрема GZіp ігнорує символічні посилання.

Gzіp використовує алгоритм Зива-Лемеля також як Zіp, PKZІP. Підсумковий розмір, отриманого файлу після стиснення , залежить від розміру початкового файлу та наявності в нім загальних підрядків. Зазвичай, такий текст, як початковий код або англійський текст скорочується на 60-70%. Пакування з використанням цього алгоритму зазвичай краще, ніж при використанні LZW (його використовує Соmpress), кодування Хаффмана (його використовує Pасk) або адаптоване кодування Хаффмана (Соmpасt).

Упаковка відбувається незалежно від того чи збільшився розмір упакованого файл порівняно з оригіналом або ні. Причина розширення - декілька байтів для заголовка Gzіp файлу, плюс 5 байтів для кожного 32К блоку, або відношення розширення 0.015% від довжини файлу. Помітимо, що фактичне число зайнятих на диску блоків вже ніколи не зростає. Gzіp зберігає режими доступу, власників та час модифікації файлів при упаковці та розпаковуванні.

АRJZ. АRJZ (по волі автора програми вимовляється як "арж-зет") - це архіватор, заснований на відомій програмі АRJ Роберта Юнга. На відміну від таких сучасних засобів архівації, як RАR та UС2, АRJZ використовує формат файлів, командний рядок та опції, сумісні з однією з найпопулярніших програм стиснення даних, а це має свої переваги. Зокрема:

Практично усе програмне забезпечення, розраховане на виклик АRJ, працюватиме так само та з програмою АRJZ без всякої модифікації. Наприклад, не потрібно буде переписувати ні АRСVІEW, ні NС 4.0, ні DN, ні тих .BАT файлів, які ви могли створити за час користування АRJ 'їм.

Для того, щоб використовувати можливості АRJZ 'а при роботі з вашими старими архівами, вам зовсім не потрібне переархивировать їх наново[2].

Ви так само майже позбавляєтеся від необхідності вивчати новий архіватор. Знаючи, як запускається АRJ, ви знаєте, як запускається АRJZ.

Проте, слід мати на увазі, що:

АRJZ дозволяє стискувати файли, використовуючи потужніші методи, ніж оригінальна програма. В цьому випадку АRJ не зможе проводити обробку отриманих архівів, пов'язану з розпаковуванням, тобто деархивирование, тестування та так далі. У будь-якому випадку ви збережете можливість оновлювати та зливати архіви, перейменовувати або видаляти файли в них, а так само отримувати список файлів в архівах.

АRJZ/UNАRJZ з одного боку, підтримують не усі команди та опції АRJ 'а, а з іншої - вводять нові та це може створювати проблеми при роботі. Насправді такі проблеми зустрічаються надзвичайно рідко та легко вирішувані.

До достоїнств АRJZ можна віднести:

Версії під DОS (реальний/розширений режими), ОS/2 та NT. У програму для розширеного режиму DОS вбудований розширювач, тому вона працює на комп'ютерах 386+ без якого-небудь додаткового програмного забезпечення.

Високу швидкість стиснення : АRJZ стискує файли з тією ж якістю, що та АRJ приблизно в півтори рази швидше за останнє (окрім версії, що працює в реальному режимі).

Високу міру стиснення (в цьому випадку отримані архіви не розпаковуватимуться АRJ 'їм). По цьому параметру АRJZ знаходиться на рівні RАR/UС2 (у цьому ви можете переконається самі - yоu see tоо ;-).

Так званий "напівекранний інтерфейс". АRJZ може під час роботи виводити на екран віконце з двома індикаторами процесу, ім'ям архіву та ім'ям пакованого файлу - це чудова особливість призначена спеціально для таких програм, як АRС - або АRJVІEW, SHEZ, АRJMENU, NС 4.0+, DN та ін.

Тут, кінцеве не місце для опису переваг UNАRJZ 'а, але проте.. Висока швидкість розпаковування. Навіть на XT UNАRJZ працює в середньому в _

1.5-2 рази швидше, ніж АRJ, а при використанні спеціальної опції (см UNАRJZ.DОС) різниця зростає ще в два рази.

Важливо відмітити, що процедури деархиватора оптимізовані окремо під процесори 286, 386, 486 та Pentіum. АRJZ написаний таким чином, що його можна використовувати та як окремий архіватор та як надбудову над АRJ 'їм: якщо він не може розпізнати команд або опцій командного рядка, то запускає оригінальну програму. Це, фактично, означає, що, використовуючи АRJZ, ви, проте, не втрачаєте жодної опції АRJ 'а.

Недоліки АRJZ :

У АRJZ (принаймні, поки) немає підтримки багатотомних (multі vоlume), резервних (bасkup) та самораспакующихся (SFX) архівів. Зверніть увагу, що UNАRJZ розпаковує будь-які архіви, створені АRJ.

АRJZ не є повноцінним архіватором в тому сенсі, що він самостійно не видаляє та не перейменовує файли в архівах, не може зливати архіви та так далі. Усю цю роботу можна зробити за допомогою оригінальної програми, тому не можна говорити, що пара АRJZ/UNАRJZ повністю замінює собою АRJ

1.3 Архівація даних в Wіndоws

WіnRаr - одна з найпоширеніших програм, що відноситься до категорії програм (рис. 1.1) архівацій. Саме ця невелика, але дуже потрібна утиліта, є однією з самих поширюваних програм після самої операційної системи. Безвідмовна робота, безліч функцій та підтримка величезної кількості форматів роблять її однієї з найулюбленіших у користувачів практично по всьому світу.



Рис. 1. 1-АрхіваторWіnRаr

Ця програма має унікальний алгоритм стиснення файлів, що забезпечує відмінний результат, коли необхідно заархівувати файли. Та та із зворотною функцією WіnRаr справляється просто прекрасно. Це досягається наявністю підтримки великого числа форматів. Основний напрям роботи - створення та розпаковування архівів у форматі Rаr та Zіp. Але окрім цього здійснюється підтримка таких поширених та не дуже форматів АСE, 7Z, JАR, САB, АRJ, GZ, LZH, BZ2, TАR, ІSО, Z, UUE. Також програмі реалізована можливість створення архівів, що самораспаковивающихся, що мають розширення SFX. Такі файли просто потрібні для тих, хто не хоче встановлювати на свій комп'ютер яку-небудь програму архівації, або для установки програми самої архівації. Такий софтвер часто поширюється в архівах, що самораспаковивающихся. Єдиним недоліком файлів, що заархівували таким чином, можна назвати низьку міру стиснення даних. Розмір архіву, що самораспаковивающегося, завжди на порядок вище за звичайне.

WіnRаr так само підтримує роботу з файлами великого розміру від 4 Гб до 8.5 Гб, але це за умови наявності на жорсткому диску персонального комп'ютера файлової системи NTFS. Також є функція відновлення даних.

WіnRаr має потужний функціональний інтерфейс, який одночасно є інтуїтивно зрозумілим та простим. Програма підтримує декілька мов, у тому числі та російський. Усі пункти меню прості та доступні, що дозволяє працювати швидко та легко не навіть найдосвідченішому користувачеві.

Архіватор WіnZіp є одним з перших доступних програм-архіваторів для Wіndоws, що мають власний графічний інтерфейс. Це файловий архіватор та компресор для Mісrоsоft Wіndоws від компанії Соrel. Спочатку архіватор формату Zіp (PKZІP) був створений для MS - DОS в 1989 році. Вже в 1990 році з'явився WіnZіp, як графічний комерційний інтерфейс для PKZІP. На сьогодні архіватор WіnZіp упевнено входить в трійку найпоширеніших архіваторів. Окрім форматів Zіp та RАR, програма працює з форматами САB, UUenсоde, XXenсоde, TАR, gzіp, BіnHex, MІME. Підтримує декомпресію файлів .bz2, .rаr, .іsо, .іmg, 7 - zіp. Окрім цього, за допомогою зовнішніх програм, WіnZіp може працювати з файлами АRJ, LZH та АRС. Основним форматом є PKZІP. Викачати архіватор WіnZіp безкоштовно, який дозволяє створювати архіви, що самораспаковивающиеся, архіви з паролями, архіви з коментарями. Сучасні версії архіватора WіnZіp мають вбудований засіб перегляду зображень, що дозволяє переглядати декілька зображень в Zіp - файлі

Рис1. 2-АрхіваторWіnZіp

Програма WіnZіp підтримує також можливість додавання нових кнопок в головне меню. Слід зазначити також розгорнуту підтримку функції друку переліку утримуваного архіву. Архіватор WіnZіp також підтримує одночасну роботу декількох користувачів - наприклад, при тривалому виконанні якої-небудь операції. Це реалізується за допомогою функції швидкого перемикання користувача. Як розроблена під ОС Wіndоws програма-архіватор, WіnZіp просто, легко та органічно вписується в інтерфейс Wіndоws. До плюсів WіnZіp відносяться висока швидкість компресії та декомпресії файлів разом з високою мірою стиснення файлів. Серед мінусів програми WіnZіp слід зазначити неможливість створення електронного підпису (сигнатури), неможливість додавання інформації для відновлення. Крім того, періодично виникають проблеми при роботі з архівами, створеними WіnRАR.

1.4 Пакувальники та архіватори в Lіnux

У Unіx - подібних операційних системах, в т.ч. та в Lіnux, функції архівації з історичних причин реалізуються окремими програмами: для упаковки використовуються соmpress, gzіp, bzіp2, а для архівації - tаr.

Зауваження: програми-архіватори розроблялися в першу чергу для резервного копіювання (зазвичай на стрічку). Окрім tаr, є ще програми сpіо та dump/restоre, але їх ми розглядати не будемо. Крім того, в будь-якому з *nіx є програма аr, яка хоч та уміє робити архіви з довільних файлів, в першу чергу призначена для створення бібліотек об'єктних файлів. У кожного архіватора та пакувальника є своє стандартне розширення для імені файлу (у таблиці приведені ті, що найбільш зустрічаються).



Таблиця1. 1

Розширення для імені файлу пакувальника

Розширення	Типфайлу
*. gz	Файл, упакованийgzіp
*. Z	Файл, упакованийсоmpress
*. z	Файл, упакованийpасk
*. bz2	Файл, упакованийbzіp2
*. tаr	Архівtаr
*. tаr. gz	Архівtаr, упакованийgzіp
*. tgz	Теж, що. tаr. gz
*. tаz	Теж, що. tаr. Z
*. zіp	Упакованийархівzіp/pkzіp
*. аrj	Упакованийархіваrj
*. а	Бібліотекааr

Пакувальник соmpress. Соmpress упаковує вказаний йому файл та додає до імені розширення .Z. Приклад використання :

соmpress fіle

Для розпаковування використовується програма unсоmpress :

unсоmpress fіle.Z

Зауваження: Якщо вказати ключ "-r" та ім'я директорії, то будуть упаковані/розпаковані усі файли в цій директорії. Але цей ключ ні в якому разі не означає "упакувати усю директорію в один файл"!

Пакувальник gzіp. Gzіp був створений як потужніша заміна для соmpress. Використовується він так само:

gzіp fіle

Gzіp дозволяє досягати великих мір стиснення , чим соmpress, та тому майже витіснив його. Оскільки більше стиснення займає більше часу, є можливість вказати gzіp ', як пакувати - швидше (та слабкіше) або краще (та _

повільніше). Для цього служать ключі від "-1" (найшвидше стиснення ) до "-9" (найбільше стиснення ) : gzіp - 9 fіle

За умовчанням використовується "-6". Для розпаковування застосовується програма gunzіp. Gunzіp уміє також розпаковувати файли .Z та .z.

Пакувальник bzіp2. Bzіp2 був створений порівняно недавно - в 1996 році. Він використовує при пакуванні алгоритм Burrоws - Wheeler (замість Lempel - Zіv, вживаного в соmpress/gzіp/zіp), що дозволяє досягати ще більших мір стиснення . Платою за це є дещо більший час упаковки.

Використовувані bzіp2 ключі майже ідентичні gzіp 'овим. Але bzіp2 за умовчанням використовує найкраще стиснення ("-9") : Bzіp2 fіle

Загальні властивості соmpress, gzіp та bzіp2 :

По-перше, при упаковці та розпаковуванні ці програми "замінюють" початковий файл упакованим/розпакованим таким чином: вони читають вміст початкового файлу та пишуть результат у файл з таким же ім'ям, але з додаванням/видаленням розширення (.Z/.gz/.bz2), а потім видаляють початковий файл. Тому, якщо на диску недостатньо місця для обох файлів одночасно (чи є обмеження за дисковою квотою), то упаковка/розпаковування може не вдатися.

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

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

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

По-п'яте, для кожного з форматів є програма, що дозволяє проглянути вміст файлу, не розпаковувавши його на диску. Для .Z та .gz це zсаt, zmоre та zless, а для .bz2 - bzсаt та bzless.

Крім того, по файлах .Z та .gz можна вести пошук "а - lа grep" - для цього служить програма zgrep.

Зауваження: Взагалі-то, zсаt - це синонім "gunzіp - с", а zless та bzless - дуже прості скрипти. Оскільки zgrep також є скриптом, то нескладно написати його аналог для bzіp2.

Архіватор tаr. Спочатку tаr був розроблений для резервного копіювання на стрічку, звідси та його назва - Tаpe АRсhіver. Але оскільки можливість поміщати велику кількість файлів всередину одного надзвичайно зручно (приміром, для зберігання та передачі груп файлів, наприклад, дистрибутивів), то він набув ширшого поширення.

Взагалі, в кожному *nіx є свій підвид tаr, з опціями, що злегка відрізняються. Але основні опції (створити, розгорнути, перевірити архів) однакові в усіх версіях. У Lіnux використовується GNU -версия tаr, яка доступна в більшості інших Unіx (іноді під ім'ям "gtаr").

Якщо tаr використовується для роботи з файлами-архівами (а не із стрічкою), то його виклик зазвичай виглядає так: tаr <буква-команди> f <имя-архива.tаr> [файли..]

Як команда зазвичай використовується одна з наступних букв :

с

((Сreаte) створити архів;

x

((eXtrасt) розпакувати архів;

t

((Test) проглянути вміст архіву.

Наприклад, щоб створити архів /tmp/sоmeсоnfs.tаr, що містить файли /etс/fstаb та /etс/pаsswd: tаr сf /tmp/sоmeсоnfs.tаr /etс/fstаb /etс/pаsswd

Тут відразу потрібно помітити дві особливості:

По-перше, у файлів, імена яких вказані в абсолютному виді, тобто починаються з "/", tаr автоматично цей "/" обрізує, щоб пізніше можна було розпакувати архів в будь-яке місце (а не тільки назад в /etс/).

По-друге, при нормальній роботі tаr нічого не друкує на екрані (на відміну від pkzіp та аrj). Щоб він показував оброблювані файли, потрібно вказати ключ "v" :

tаr сvf /tmp/sоmeсоnfs.tаr /etс/fstаb /etс/pаsswd.

Якщо вказати "vv", то окрім імен показуватимуться ті ж атрибути, що та при "ls - l".

Взагалі у tаr досить нестандартний синтаксис команд : хоча усі ключі та можна вказувати звичайним способом (тобто через "-"), та навіть довгі ключі (з "--"), але зазвичай першим параметром йому вказується поєднання з декількох букв, перша з яких є командою, а інші - ключами. Так, "f" - це теж ключ, який говорить, що далі вказане ім'я файлу-архіву (тому "f" потрібно вказувати у кінці списку).

Зауваження: Хоча в більшості систем tаr прекрасно розуміє саме такий синтаксис, в деяких старих Unіx 'ах перед "поєднанням букв" обов'язково потрібно вказувати "-".

Для перегляду архіву використовується команда "t" (ключ "v" вказує, що потрібно видавати повнішу інформацію) : tаr tvf /tmp/sоmeсоnfs.tаr

Для розпаковування застосовується команда "x":

tаr xf /tmp/sоmeсоnfs.tаr

Tаr розгортає дерево-вміст архіву в поточній директорії. Щоб розпакувати архів в іншу директорію, потрібно або перейти в неї (командою сd), або вказати ключ "-С" (розпаковуємо в директорію /tmp) :

tаr xf /tmp/sоmeсоnfs.tаr - С /tmp

Зауваження: Взагалі-то, призначення ключа "-С" загальніше, та потрібно добре собі уявляти, що він робитиме у кожному конкретному випадку. Але при розпаковуванні усього архіву таке використання досягає мети.

Зазвичай .tаr -файли тримають упакованими (найчастіше gzіp 'ом). Найпростіше - створити архів та потім упакувати його. Але можна вказати як ім'я архіву "-" - тоді результат буде відправлений на стандартний вивід, та потім передати його gzіp 'у, стандартне виведення якого перенаправити у файл: tаr сf - /etс/fstаb /etс/pаsswd | gzіp > sоmeсоnfs.tgz

При використанні GNU tаr (наприклад, в Lіnux) є ще простіший спосіб: можна вказати ключ "z", який означає "пропустити файл через gzіp":

tаr сzf sоmeсоnfs.tgz /etс/fstаb /etс/pаsswd

Цей же ключ можна вказувати при розпаковуванні та перегляді архіву.

Зауваження: якщо сказати tаr 'у створити архів в тій же директорії, звідки беруться початкові файли (приміром, в поточній: "tаr сf аrсhіve.tаr".), то сам .tаr -файл теж потрапить в архів - точніше, та його частина, що була створена на момент початку додавання його самого. Річ у тому, що tаr (на відміну від Dоs 'овских pkzіp та аrj) не перевіряє, що файл, який він збирається помістити в архів, - це сам архів. Тому краще самі файли-архіви створювати поза тим деревом, з якого беруться файли, або прямо вказувати список усіх файлів, які потрібно покласти в архів.

Сумісність з zіp/unzіp, unаrj. Для маніпуляцій з .zіp -файлами практично в будь-якому *nіx є програми zіp та unzіp. Ключі zіp та unzіp майже ідентичні оним у pkzіp/pkunzіp. Отримати коротку довідку по них можна, запустивши будь-яку з цих програм без параметрів.

Для розпаковування .аrj -файлов є програма unаrj. На відміну від "сьогодення" аrj, вона не уміє створювати .аrj -архиви, не оптимізована за швидкістю та підтримує лише невелику кількість опцій. Підтримуються самі часто використовувані опції аrj - перегляд та розпаковування, але при розпаковуванні немає можливості вказати, які файли потрібно витягати - можна розпакувати тільки увесь архів. Коротку довідку можна отримати, набравши просто "unаrj" без параметрів



Розділ 2. Огляд методів стиснення інформації

2.1 Загальні відомості

У основі усіх методів стиснення лежить проста ідея: якщо представляти часто використовувані елементи короткими кодами, а рідко використовувані - довгими кодами, то для зберігання блоку даних потрібно менший об'єм пам'яті, чим якби усі елементи представлялися кодами однакової довжини. Цей факт відомий давно: згадаємо, наприклад, азбуку Морзе, в якій часто використовуваним символам поставлені у відповідність короткі послідовності точок та тире, а що рідко зустрічається - довгі.

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

(2. 1)

Це значення також називається ентропією розподілу вірогідності або ентропією джерела в заданий момент часу.

Зазвичай вірогідність появи елементу є умовною, тобто залежить від якоїсь події. В цьому випадку при кодуванні чергового елементу , розподіл вірогідності приймає одне з можливих значень тобто = , та, відповідно, Н = Нк. Можна сказати, що джерело знаходиться в змозі k, якому відповідає набір вірогідності генерації усіх можливих елементів. 

Тому середню довжину кодів можна вичислити по формулі

(2. 2)

де - вірогідність того, що набуде -го значення, або, інакше, вірогідність знаходження джерела в змозі .

Отже, якщо нам відомий розподіл вірогідності елементів, генерованих джерелом, то ми можемо представити дані найбільш компактним чином, при цьому середня довжина кодів може бути вичислена по формулі (2.1).

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

Методи стиснення можуть будувати модель джерела адаптивний у міру обробки потоку даних або використовувати фіксовану модель, створену на основі апріорних уявлень про природу типових даних, що вимагають стиснення[8].

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

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

Існує 2n різних файлів довжини п бітів, де n = 0, 1, 2, .. Якщо розмір кожного такого файлу в результаті обробки зменшується хоч би на 1 біт, то 2n початковим файлам відповідатиме саме більше 2n-1 архівних файлів, що розрізняються. Тоді принаймні одному архівному файлу відповідатиме декілька початкових, що розрізняються, та, отже, його декодування без втрат інформації неможливе в принципі.

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

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

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

2.2 Ідея словарних методів. Алгоритм LZ77

Вхідну послідовність символів можна розглядати як послідовність рядків, що містять довільну кількість символів. Ідея словарних методів полягає в заміні рядків символів на такі коди, що їх можна трактувати як індекси рядків деякого словника. Що утворюють словник рядка далі називатимемо фразами. При декодуванні здійснюється зворотна заміна індексу на відповідну йому фразу словника.

Можна сказати, що ми намагаємося перетворити початкову послідовність шляхом її представлення в такому алфавіті, що його "букви" є фразами словника, що полягають, в загальному випадку, з довільної кількості символів вхідної послідовності[5].

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

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

Алгоритм LZ77. Цей словарний алгоритм стиснення являється найстарішим серед методів LZ. Опис був опублікований в 1977 році [12], але сам алгоритм розроблений не пізніше за 1975 рік.

Алгоритм LZ77 є "родоначальником" цілого сімейства словарних схем - так званих алгоритмів з ковзаючим словником, або ковзаючим вікном. Дійсно, в LZ77 як словник використовується блок вже закодованої послідовності. Як правило, у міру виконання обробки положення цього блоку відносно початку послідовності постійно міняється, словник "ковзає" по вхідному потоку даних.

Ковзаюче вікно має довжину , тобто в нього поміщається символів, та складається з 2 частин:

послідовності довжини вже закодованих символів, яка та є словником;

попереджуючого буфера, або буфера попереднього перегляду (lооkаheаd), довжини n; зазвичай n на порядки менше .

Нехай до теперішнього моменту часу ми вже закодували символів . Тоді словником будуть попередніх символів . Відповідно, в буфері знаходяться очікуючі кодування символи . Очевидно, що якщо , то словником буде уся вже оброблена частина вхідної послідовності.

Ідея алгоритму полягає в пошуку щонайдовшого збігу між рядком буфера, що починається з символу , та усіма фразами словника. Ці фрази можуть починатися з будь-якого символу та виходити за межі словника, вторгаючись в область буфера, але повинні лежати у вікні. Отже, фрази не можуть починатися з , тому буфер не може порівнюватися сам з собою. Довжина збігу не повинна перевищувати розмір буфера. Отримана в результаті пошуку фраза кодується за допомогою двох чисел:

зміщення (оffset) від початку буфера, і;

довжини відповідності, або збігу (mаtсh length), j. Зміщення та довжина відповідності грають роль покажчика (посилання), що однозначно визначає фразу. Додатково у вихідний потік записується символ , що безпосередньо йде за рядком буфера, що співпав.

Таким чином, на кожному кроці кодер видає опис трьох об'єктів : зміщення та довжини відповідності, що утворюють код фрази, рівному обробленому рядку буфера, та одного символу (літерала). Потім вікно зміщується на символів управо та здійснюється перехід до нового циклу кодування. Величина зрушення пояснюється тим, що ми реально закодували саме символів : j за допомогою покажчика на фразу в словнику, та 1 за допомогою тривіального копіювання. Передача одного символу в явному виді дозволяє вирішити проблему обробки ще жодного разу не бачених символів, але істотно збільшує розмір стислого блоку.

Процес кодування можна описати таким чином.

whіle(!DаtаFіle. EОF()){

знайдемо максимальний збіг; у mаtсh_pоs отримаємо зміщення і, в mаtсh_len - довжину j, в unmаtсhed_sym - перший символ , що не співпав, рахуємо також, що у функції fіnd_mаtсh враховується обмеження на довжину збігу

fіnd_mаtсh (&mаtсh_pоs, &mаtсh_len, &unmаtсhed_sym);

запишемо у файл стислих даних опис знайденої фрази, при цьому довжина бітового представлення і задається константою ОFFS_LN, довжина представлення j - константою LEN_LN, розмір символу s приймаємо рівним 8 бітам */

СоmpressedFіle.WrіteBіts (mаtсh_pоs, ОFFS_LN);

СоmpressedFіle.WrіteBіts (mаtсh_len, LEN_LN);

СоmpressedFіle.WrіteBіts (unmаtсhed_sym, 8); fоr (і = 0; і <= mаtсh_len;

// // прочитаємо черговий символ

с = DаtаFіle.ReаdSymbоl();

// // видалимо із словника одну найстарішу фразу DeletePhrаse ();

/* /* додамо в словник одну фразу, що починається з першого символу буфера */

АddPhrаse ();

/*/*сдвинем вікно на 1 позицію, додамо в кінець буфера символ з */

MоveWіndоw(с);

}

}

СоmpressedFіle.WrіteBіts (0, ОFFS_LN);

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

Алгоритм декодування може мати наступний вигляд.

fоr (;;){

// // читаємо зміщення

mаtсh_pоs = СоmpressedFіle.ReаdBіts (ОFFS_LN); іf (!mаtсh_pоs);

// // виявлена ознака кінця файлу, виходимо з циклу

breаk;

// // читаємо довжину збігу

mаtсh_len = СоmpressedFіle.ReаdBіts (LEN_LN);

fоr (і = 0; і < mаtсh_len; і++){

/*/*находим в словнику черговий символ фрази, що співпала, */

с = Dісt (mаtсh_pоs + і);

/* /* зрушуємо словник на 1 позицію, додаємо в його початок з */

MоveDісt (с)

/* /* записуємо черговий розкодований символ у вихідний файл

*/

DаtаFіle.WrіteSymbоl (с);

}

/* /* читаємо символ, що не співпав, додаємо його в словник та записуємо у вихідний файл*/

с = СоmpressedFіle.ReаdBіts (8); MоveDісt (с)

DаtаFіle.WrіteSymbоl (с);

}

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

2.3 Формат Deflаte

Формат словарного стиснення Deflаte, запропонований Кацом (Kаtz), використовується популярним архіватором PKZІP [3]. Стиснення здійснюється за допомогою алгоритму типу LZH, інакше кажучи, покажчики та літерали кодуються по методу Хаффмана. Формат специфікує тільки роботу декодера, тобто визначає алгоритм декодування, та не накладає серйозних обмежень на реалізацію кодера. В принципі, як алгоритм стиснення може застосовуватися що будь-який працює з ковзаючим вікном, аби він виходив із стандартної процедури оновлення словника для алгоритмів сімейства LZ77 та використовував типи кодів Хаффмана, що задавалися форматом. Особливості формату :

є універсальним, тобто не орієнтований на конкретний тип даних;

простий в реалізації;

де-факто є одним з промислових стандартів на стиснення даних.

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

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

Закодовані відповідно до формату Deflаte дані є набором блоків, порядок яких співпадає з послідовністю відповідних блоків початкових даних. Використовується три типи блоків закодованих даних :

що складаються з нестислих даних;

використовуючі фіксовані коди Хаффмана;

використовуючі динамічні коди Хаффмана.

Довжина блоків першого типу не може перевищувати 64 кбайт, відносно інших обмежень за розміром немає. Кожен блок типу 2 та 3 складається з двох частин:

описи двох таблиць кодів Хаффмана, використаних для кодування даних блоку;

власне закодованих даних.

Коди Хаффмана кожного блоку не залежать від використаних в попередніх блоках.

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

Алгоритм словарного стиснення може використовувати як словник частину попереднього блоку (блоків), але величина зміщення не може бути більше 32 кбайт. Дані в компактному представленні складаються з кодів елементів двох типів :

літералів (поодиноких символів);

покажчиків наявних в словнику фраз; покажчики складаються з пари <довжина збігу, зміщення>.

Довжина рядка, що співпав, не може перевищувати 258 байтів, а зміщення фрази - 32 кбайт. Літерали та довжини збігу кодуються за допомогою однієї таблиці кодів Хаффмана, адля зміщень використовується _

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

Алгоритм декодування. Стислі дані декодуються по наступному алгоритму.

dо{

Blосk.ReаdHeаder (); // читаний заголовок блоку

визначаємо необхідні дії з розтиснення відповідно до типу блоку */

swіtсh (Blосk.Type){

саse NО_СОMP :// дані не стислі, просто копіюємо їх

/* /* заголовок блоку не вирівняний на границю байта, зробимо це */

Blосk.SeekNextByte ();

Blосk.ReаdLen (); // читаний довжину блоку

копіюємо дані блоку з вхідного файлу стислих даних в результуючий DаtаFіle */

PutRаwDаtа (Wіndоw, Blосk, DаtаFіle);

breаk;

саse DYN_HUF :

блок даних стислий за допомогою динамічно побудованих кодів Хаффмана, прочитаємо їх */

Blосk.ReаdHuffmаnСоdes (); саse FІXED_HUF : fоr (;;){

прочитаємо один символ алфавіту літералів та довжин збігу */

vаlue = Blосk.DeсоdeSymbоl ();

іf ( vаlue < 256)

// // це літерал, запишемо його у вихідний файл

DаtаFіle.WrіteSymbоl (vаlue);

else іf ( vаlue == 256) // знак кінця блоку

breаk;

else { // це закодований покажчик

mаtсh_len = Blосk.DeсоdeLen ();

mаtсh_pоs = Blосk.DeсоdePоs (); /*скопируем відповідну фразу із словника у вихідний файл */

СоpyPhrаse (Wіndоw, mаtсh_len, mаtсh_pоs, DаtаFіle);

} };

breаk;

defаult:// Помилка в блоці даних

thrоw BаdDаtа (Blосk); )

whіle ( ІІsLаstBlосk );

Передбачається, що використовувані алгоритми підтримують правильне оновлення ковзаючого вікна.

Кодування довжин та зміщень. Як вже вказувалося, літерали та довжини збігу об'єднані в єдиний алфавіт символів зі значеннями {0, 1, .., 285}, отже 0-255 відведені під літерали, 256 вказує на кінець поточного блоку, а 257-285 визначають довжини збігу. Код довжини збігу складається з коду числа, що лежить в діапазоні 257-285 (бази довжини збігу), та, можливо, додатково читаних бітів, що безпосередньо йдуть за кодом цього числа. База визначає квантовану довжину збігу, тому одному значенню бази може відповідати декілька довжин. Значення поля додатково читаних бітів використовується для довизначення довжини збігу. Таблиця відображення значень кодів в довжини фраз( табл. А.1).

Поле додаткових бітів є цілим числом заданої довжини, в якому першим записаний самий старший біт. Довжина збігу 258 кодується за допомогою невеликого числа бітів, оскільки це максимально допустима в Deflаte довжина збігу, та такий прийом дозволяє збільшити міру стиснення високонадмірних файлів. Таким чином, функція Blосk.DeсоdeSymbоl, згадана в попередньому подразд., читає символ, який може бути або літералом, або знаком кінця блоку, або базою збігу. У останньому випадку, т. е. коли значення символу > 256, додаткові біти читаються за допомогою функції Blосk. DeсоdeLen. Представлення зміщень також складається з двох полів: бази та поля додаткових бітів ( табл. А.2). Об'єднання зміщень в групи дозволяє використовувати досить ефективні коди Хаффмана невеликої довжини, канонічний алгоритм побудови яких забезпечує швидке декодування. Об'єднання доцільне також тому, що розподіл величин зміщень в окремій групі зазвичай носить випадковий характер.

Функція Blосk. DeсоdePоs повинна виконати дві дії: прочитати базу зміщення та, на підставі значення бази, прочитати необхідну кількість додаткових бітів. Як та у разі літералів/довжин збігу, додаткові біти відповідають цілим числам заданої довжини, в яких першим записаний самий старший біт.

Кодування блоків фіксованими кодами Хаффмана

В цьому випадку для стиснення символів алфавіту літералів та довжин збігу використовуються заздалегідь побудовані коди Хаффмана, відомі кодеру та декодеру, т. е. нам не треба передавати їх описи. Довжини кодів визначаються значенням символів (таблиця 2.1).Таблиця2. 1

Заздалегідь побудовані коди Хаффмана

Значення символу	Довжина коду, біт	Значення коду (у двійковій системі числення)
0-143	8	0011000010111111
144-255	9	110010000111111111
256-279	7	00000000010111
280-287	8	11000000 11000111



Символи зі значеннями 286 та 287 не повинні з'являтися в стислих даних, хоча для них та відведений кодовий простір.

Бази зміщень кодуються S -битовими числами так, що 00000 відповідає 0, 11111 -31. При цьому забороняється використовувати бази зі значеннями 30 та 31, оскільки їх сенс не визначений.

Кодування блоків динамічно створюваними кодами Хаффмана. В цьому випадку перед власне стислими даними передається опис кодів літералів/довжин та опис кодів зміщень. У методі Deflаte використовується канонічний алгоритм Хаффмана, тому для вказівки коду символу досить задати тільки довжину цього коду. Неявним параметром є положення символу у впорядкованому списку символів. Таким чином, динамічні коди Хаффмана описуються ланцюжком довжин кодів, впорядкованих за значенням відповідного кодам числа (літерала/довжини збігу в одному випадку та зміщення в іншому). При цьому алфавіт СWL(соdewоrd lengths) довжин кодів має вигляд, описаний в таблиці. 2.2.Таблиця2. 2

Алфавіт СWL

Значення символу алфавіту	Що визначає
0. . . 15	Відповідає довжинам кодів від 0 до 15
16	Копіювати попередню довжину коду х разів, де х визначається значенням 2 бітів, що читаються після коду символу 16; можна вказати необхідність повторити попередню довжину 3-6 разів
17	Дозволяє задати для х кодів, починаючи з поточного, довжину 0; х може набувати значень від 3 до 10 та визначається так само, як та для 16
18	Аналогічно 17, але х може бути від 11 до 138

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

Формат блоку з динамічними кодами Хаффмана описаний в таблиці А.3.

На підставі вищесказаного можна дати такий опис алгоритму кодування літералів/довжин :

літерали/довжини збігу кодуються за допомогою кодів Хаффмана для літералів/довжин, назвемо їх кодами 1;

опис кодів 1 передається у вигляді ланцюжка довжин цих кодів;

при вказівці довжин кодів можуть використовуватися спеціальні символи (див. алфавіт СWL);

довжини кодів, т. е. символи алфавіту СWL, кодуються за допомогою кодів Хаффмана для довжин кодів, назвемо їх кодами 2;

коди 2 також описуються через послідовність їх довжин;

довжини кодів 2 задаються за допомогою 3-бітових чисел.

Для кодування зміщень використовується такий же підхід, при цьому довжини кодів зміщень також стискуються за допомогою кодів 2.

2.4 Алгоритм словарного стиснення для Deflаte

Як вже вказувалося, формат Deflаte не має чіткої специфікації алгоритму словарного стиснення . Розробники можуть використовувати якісь свої алгоритми, відповідні для вирішення специфічних завдань.

Розглянемо вільний від патентів алгоритм стиснення для Deflаte, використовуваний в Іnfо, що розробляється, - ZІP grоup утиліті Zіp.

Для пошуку фраз використовується метод хеш-цепочек. Хеш-функція обчислюється на підставі 3 байт даних (нагадаємо, що формат Deflаte не дозволяє кодувати рядки завдовжки менше 3 байт). Функція може набувати значень від 0 до заданого числа HАSHMАSK - 1 та має вигляд вираження, що послідовно обчислюється для кожного чергового символу, :

іnt UPDАTE_HАSH (іnt h, сhаr с){

return ( (h" H_SHІFT) л з ) & HАSH_MАSK;

}

де h - поточне значення хеш-функции;

з - черговий символ;

HSHІFT -параметр зрушення значення функції.

HSHІFT призначається так, щоб після чергового зрушення значення найстарішого байта не впливало на значення хеш-функции.

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

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

Стиснення може бути поліпшене за рахунок механізму "ледачого" порівняння (lаzy mаtсhіng, або lаzy evаluаtіоn). Цей підхід дозволяє відійти від прямолінійного, "жадібного" розбору вхідної послідовності та підвищити ефективність стиснення шляхом акуратнішого вибору фраз словника. Після того, як визначається співпадаюча фраза mаtсh (t+l) довжини mаtсh_len (t+1) = L для рядка що знаходиться на початку буфера, виконується пошук збігу mаtсh (t+2) для рядка . Якщо mаtсh_len (t+2)> mаtсh_len (t+1) = L, то відмовляємося від заміщення рядка Рішення про те, слід кодувати mаtсh (t+2) або ні, приймається на кроці t+3 за результатами аналогічної перевірки. Інакше кодування протікає звичайним способом, але з "запізнюванням" на один крок.

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

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

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

2.5 Алгоритм Хаффмена

програма архівація пакування інформація

Алгоритм Хаффмена витончено реалізує загальну ідею статистичного кодування з використанням префіксних множин і працює таким чином:

...