Стиснення інформації
Зміст
1. Вступ
2. Коротка історія розвитку теорії стиснення інформації
3. Алгоритми стиснення даних
3.1. Алгоритм RLE.
3.2. Алгоритми групи KWE
3.3. Алгоритм Хафмана
3.4. Сімейство алгоритмів LZ78 (LZW, MW, AP, Y)
4. Стиснення інформації.
4.1. Стиснення із втратами та стиснення без втрат
4.2. Архіватори
4.2.1. Програма ARJ
4.2.2. Програма PKZIP
4.2.3. Програма PKUNZIP
4.2.4. Програма LHA
4.2.5. Програма PKLITE
4.2.6. Програма LZEXE
5. Висновки
6. Список використаної літератури
1. Вступ
Характерною особливістю більшості типів даних є їх надлишковість. Для людини надлишковість даних часто пов'язана з якістю інформації, оскільки надлишковість, як правило, покращує зрозумілість та сприйняття інформації. Однак, коли мова йде про зберігання та передачу інформації засобами комп'ютерної техніки, то надлишковість відіграє негативну роль, оскільки вона приводить до зростання вартості зберігання та передачі інформації. Особливо актуальною є ця проблема у випадку необхідності обробки величезних обсягів інформації при незначних об'ємах носіїв даних. У зв'язку з цим постійно виникає проблема позбавлення надлишковості або стиснення даних.
Основний принцип, на якому базується стиснення даних, полягає в економічному описі повідомлення, згідно якому можливе відновлення початкового його значення з похибкою, яка контролюється.
Метою даної роботи є знаходження такого способу архівації, який дозволить досягти ефективного стиснення даних і мінімізувати втрату інформації при відновленні.
Існує багато практичних алгоритмів стиснення даних . Однак, в основі цих методів лежать чотири теоретичних алгоритми: алгоритм RLE (Run Length Encoding); алгоритми групи KWE (KeyWord Encoding); алгоритм Хафмана, сімейство алгоритмів LZ78 (LZW, MW, AP, Y)
В основі алгоритму RLE лежить ідея виявлення послідовностей даних, що повторюються, та замфіни цих послідовностей більш простою структурою, в якій вказується код даних та коефіцієнт повторення. В основі алгоритму KWE покладено принцип кодування лексичних одиниць групами байт фіксованої довжини. Результат кодування зводиться в таблицю, утворюючи так званий словник. В основі алгоритму Хафмана лежить ідея кодування бітовими групами. Після частотного аналізу вхідної послідовності символи сортуються за спаданням частоти входження. Чим частіше зустрічається символ, тим меншою кількістю біт він кодується. Результат кодування зводиться в словник, що необхідний для декодування.
Пошуку нових шляхів стиснення даних на основі ефективного кодування та теоретико-числових перетворень (ТЧП) присвячено багато наукових робіт. Зокрема необхідно відзначити значний внесок відомих вчених: Харкевича О.О., Вошні О.Г., Макса Ж., Хартлі Р., Рабінера Л., Рейдера У., Голда Б., Акушського І. Я., Николайчука Я.М., Ольховського Ю.Б.
2. Коротка історія розвитку теорії стиснення інформації
У сорокових роках учені, що працюють в області інформаційних технологій, ясно зрозуміли, що можна розробити такий спосіб збереження даних, при якому простір буде витрачатися більш ощадливо. Клод Шеннон, вивчаючи нюанси розходжень між семантикою (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). Подібні алгоритми вибирають більш короткі коди для значень байта, що зустрічаються частіше, і більш довгі для тих, що зустрічаються рідше. Звичайно текстові файли (у який одні значення байтів повторюються набагато частіше інших) вони стискають досить добре.
3. Алгоритми стиснення даних
3.1. Алгоритм RLE.
В основі алгоритму RLE лежить ідея виявлення послідовностей даних, що повторюються, та заміни цих послідовностей більш простою структурою, в якій вказується код даних та коефіцієнт повторення. Наприклад, нехай задана така послідовність даних, що підлягає стисненню:
1 1 1 1 2 2 3 4 4 4
В алгоритмі RLE пропонується замінити її наступною структурою:
1 4 2 2 3 1 4 3,
де перше число кожної пари чисел -це код даних, а друге - коефіцієнт повторення. Якщо для зберігання кожного елементу даних вхідної послідовності відводиться 1 байт, то вся послідовність займатиме 10 байт пам'яті, тоді як вихідна послідовність (стиснений варіант) займатиме 8 байт пам'яті.
Чим менше значення коефіцієнта стиснення, тим ефективніший метод стиснення. Зрозуміло, що алгоритм RLE буде давати кращий ефект стиснення при більшій довжині послідовності даних, що повторюється. У випадкові розглянутого вище прикладу, якщо вхідна послідовність матиме такий вигляд:
1 1 1 1 1 1 3 4 4 4,
то коефіцієнт стиснення буде рівний 60%. У зв'язку з цим найбільша ефективність алгоритму RLE досягається при стисненні графічних даних (особливо для однотонових фонових зображень).
3.2. Алгоритми групи KWE
В основі алгоритму стиснення за ключовими словами покладено принцип кодування лексичних одиниць групами байт фіксованої довжини. Прикладом лексичної одиниці може бути звичайне слово. На практиці, в ролі лексичних одиниць вибираються послідовності символів, що повторюються, які кодуються ланцюжком символів (кодом) меншої довжини. Результат кодування зводиться в таблицю, утворюючи так званий словник.
Існує досить багато реалізацій цього алгоритму, серед яких найбільш поширеними є алгоритм Лемпеля-Зіва (алгоритм LZ) та його модифікація алгоритм Лемпеля-Зіва-Велча (алгоритм LZW). Словником в даному алгоритмі є потенційно нескінченний список фраз. Алгоритм починає роботу з майже пустого словника, що містить тільки один закодований рядок, так званий NULL-рядок. Коли зчитується черговий символ вхідної послідовності даних, він додається до поточного рядка. Процес продовжується доти, поки поточний рядок відповідає якій-небудь фразі з словника. Але рано або пізно поточний рядок перестає відповідати якій-небудь фразі словника. У цей момент, коли поточний рядок являє собою останній збіг зі словником плюс щойно прочитаний символ повідомлення, кодер видає код, що складається з індексу збігу і наступного за ним символу, що порушив збіг рядків. Крім того, нова фраза, що складається з індексу збігу і наступного за ним символу, додається в словник. У наступний раз, коли ця фраза з'явиться в повідомленні, вона може бути використана для побудови більш довгої фрази, що підвищує міру стиснення інформації.
Алгоритм LZW побудований навколо таблиці фраз (словника), яка відображає рядки символів стискуваного повідомлення в коди фіксованої довжини. Таблиця володіє так званою властивістю передування, тобто для кожної фрази словника, що складається з деякої фрази w і символу К фраза w також міститься в словнику. Якщо всі частинки словника повністю заповнені кодування перестає бути адаптивним (кодування відбувається виходячи з вже існуючих в словнику фраз).
Алгоритми стиснення цієї групи найефективніші для текстових даних великих обсягів і малоефективні для файлів малих розмірів (за рахунок необхідності зберігання словника).
3.3. Алгоритм Хафмана
В основі алгоритму Хафмана лежить ідея кодування бітовими групами. Спочатку проводиться частотний аналіз вхідної послідовності даних, тобто встановлюється частота входження кожного символу, що зустрічається у ній. Після цього символи сортуються по спаданню частоти входження.
Основна ідея полягає в наступному: чим частіше зустрічається символ, тим меншою кількістю біт він кодується. Результат кодування зводиться в словник, що необхідний для декодування.
Розглянемо простий приклад, що ілюструє роботу алгоритму Хафмана. Нехай задано текст, в якому літера 'А' входить 10 разів, літера 'B' - 8 раз, 'C'- 6 разів , 'D' - 5 разів, 'E' і 'F' - по 4 рази. Тоді один з можливих варіантів кодування за алгоритмом Хафмана наведений у таблиці 1.
Символ Частота входження Бітовий код
A 10 00
B 8 01
C 6 100
D 5 101
E 4 110
F 4 111
Таблиця 1. Кодування за алгоритмом Хафмана.
Як видно з таблиці 1, розмір вхідного тексту до стиснення рівний 37 байт, тоді як після стиснення - 93 біт, тобто майже 12 байт (без врахування довжини словника). Коефіцієнт стиснення рівний 32%. Алгоритм Хафмана універсальний, тобто його можна застосовувати для стиснення даних будь-яких типів, але він малоефективний для файлів малих розмірів (за рахунок необхідності зберігання словника).
На практиці програмні засоби стиснення даних синтезують ці три "чистих" алгоритми, оскільки їх ефективність залежить від типу та обсягу даних.
3.4. Сімейство алгоритмів LZ78 (LZW, MW, AP, Y)
Не можна не відзначити широко відмий алгоритм Лемпеля-Зіва-Велча (Lempel-Ziv-Welch compression, LZW, LZ78). Алгоритм відрізняється високою швидкістю роботи при кодуванні та декодуванні, невибагливістю до пам’яті та проста апаратна реалізація. Недолік – менший коефіцієнт компресії порівняно зі схемою двоступеневого кодування. Наведемо принципи роботи цього алгоритму.
Створимо словник, що зберігає рядки тексту і містить близько 2-3-8 тисяч пронумерованих комірок. Запишемо до перших 256 комірок рядки, що складаються з одного символа, номер якого дорівнює номеру комірки. Алгоритм проглядає вхідний потік, розбиваючи його на підрядки і додаючи нові комірки в кінець словника.
Будемо зчитувати із вхідного потоку по одному символу, кожного разу перевіряючи, чи є вже зчитаний ланцюжок у словнику. Таким чином ми отримаємо рядок S – найдовший префікс вхідного тексту (якщо його розглядати як рядок In), який вже є у словнику. Нехай його знайдено в комірці з номером n. Виведемо число n у вихідний потік, змістимо вказівник вхідного потоку на length(S) символів наперед та додамо до словника нову комірку, що містить рядок Sc, де с – черговий символ на вході (відразу після S). За побудовою ланцюжка S ланцюжка Sc у словнику немає. Алгоритм перетворює потік символів на вході на потік індексів комірок словника на виході. При розмірі словника в 4096 комірок можна передавати 12 біт на індекс кожного ланцюжка, що знайдено.
Реалізовуючи цей алгоритм, треба враховувати, що будь-яка комірка словника, за винятком найперших, які містять односимвольні ланцюжки, зберігає копію деякої іншої комірки, до кінця якої приписано один символ: використовується літерно-інкрементний словник.Таким чином, алгоритм LZW має важливу властивість префіксності: якщо деякий ланцюжок S міститься в словнику, то всі його префікси – також.
Далі, кодер використовує дві операції зі словником: пошук рядка Sc, за умови, що рядок S є в словнику (та відома його позиція в ньому), а с – це наступний прочитаний символ, та додавання нової комірки, що містить цей рядок. Внаслідок цього можна обійтися структурою даних, що називається trie – деревом послідовного політерного пошуку.
Час роботи цього алгоритма лінійний за довжиною вхідного потоку та не залежить від розміру словника (для кожного символа, що зчитується, відбувається або один пошук у словнику, або додавання однієї нової комірки). Саме тому він є досить популярним в апаратних реалізаціях (приклад –протокол v42bis).
Кодер LZW додає до словника одну комірку для кожного розпізнаного ланцюжка (тому його можна назвати методом із фразо-розширюваним словником). Коли словник переповнюється, кодер може або припинити його заповнення (“заморозити” словник, як класичний LZW), або очистити (повністю – compress, частково – PKZIP shrinking). Розглянемо тепер три інших методи цього сімейства.
Алгоритм MW (Miller and Wegman), на відміну від LZW, утворює нові комірки словника шляхом склеювання двох рядків (тобто використовує фразо-інкрементний словник): розпізнавши за аналогією з LZW ланцюжок S на вході, він додає до словника нову комірку PS – конкатенацію ланцюжків Р (попереднього розпізнаного ланцюжка) та S (нового). Завдяки цьому він, як правило, швидше адаптується до тексту, але може пропустити деякі ланцюжки. Тому він стискає не набагато краще за LZW, а деколи навіть і гірше.
Алгоритм MW не є префіксним. Тому реалізація словника для нього є складним завданням: звичайно, ми можемо використовувати trie для політерного пошуку (для цього ми запам’ятаємо всі префікси всіх ланцюжків із словника), однак маємо додати до кожного вузла прапорець, що вказує, чи міститься поданий рядок у словнику. До того ж пошук по словнику може вимагати повернення: якщо словник містить рядки abc та abcde, але не містить рядка abcdef (який тільки-но прочитано зі входу), то нам доведеться спочатку зчитати його весь, щоб пересвідчитися,що в словнику його немає, а потім “прокрутити” вхідний потік назад на три символи.
Властивість префіксності можна повернути, не втративши адаптивності алгоритму MW, якщо під час розпізнавання чергового ланцюжка S після ланцюжка P додавати до словника не тільки сам ланцюжок PS (як алгоритм MW), а множину АР(P,S) – всі префікси PS, що довші за S. Маємо кодування АР (all prefixes), відкрите Сторером у 1988 р.
Алгоритм АР нарощує словник значно швидше, ніж MW. У той самий час, він зазвичай стискає краще, ніж MW.
Стосовно Y-кодування, відкритого Деніелом Бернстейном, то цей метод додає до словника один рядок на кожний прочитаний символ (подібно до АР), до того ж має властивість префіксності (подібно до LZW), тобто це – літерно-інкрементний метод з літерно-розширюваним словником.
4. Стиснення інформації.
4.1. Стиснення з втратами та стиснення без втрат
Стиснення з втратами (англ. Lossy compression) — метод стиснення даних, при якому розпакований файл відрізняється від оригінлау, проте може бути корисним для використання. Стиснення із втратами найчастіше використовується для мультимедіа даних (аудіо, відео, зображення), особливо для потокової передачі даних та і телефонії. В цьому контексті такі методи часто називаються кодеками .
Існують дві основних схеми стиску із втратами:
У трансформуючих кодеках стиснення (англ. lossy transform codecs) беруться фрейми зображень або звуку, розрізуються на невеликі сегменти, трансформуються в новий базисний простір і здійснюється квантування. Результат потім стискується ентропійними методами.
У предиктивних кодеках стиснення (англ. lossy predictive codecs) попередні і/або наступні дані використаються для того, щоб пророчити поточний фрейм зображення або звуку. Помилка між передбаченими даними і реальними разом з додатковою інформацією, необхідною для здійснення предикту, потім квантизується і кодується.
У деяких системах ці дві техніки комбінуються шляхом використання трансформуючих кодеків для стиску помилкових сигналів, згенерованих на стадії пророкування.
Стиснення без втрат (англ. Lossless) — метод стиснення даних, при використанні якого закодована інформація може бути відновлена з точністю до біта. Для кожного з типів цифрової інформації, як правило, існують свої алгоритми стиску без втрат.
Перелік форматів стиснення без втрат
1. універсальні:
1.1. Zip,
1.2. 7-Zip,
1.3. RAR,
1.4. GZip,
1.5. PAQ та ін.
2. аудіо
2.1. FLAC (Free Lossless Audio Codec),
2.2. Monkey's Audio (APE),
2.3. TTA (True Audio),
2.4. TTE,
2.5. LA (LosslessAudio),
2.6. RealAudio Lossless,
2.7. WavPack та ін.
3. зображення -
3.1. BMP,
3.2. GIF,
3.3. PNG
3.4. TIFF
3.5. JPEG 2000
4. відео
4.1. CorePNG
4.2. FFV1
4.3. H.264/MPEG-4 AVC
4.4. Huffyuv
4.5. Lagarith
Перевага методів стиснення із втратами над методами стиску без втрат полягає в тому, що перші істотно перевершують по ступені стиску, продовжуючи задовольняти поставленим вимогам. Методи стиску із втратами часто використаються для стиску звуку або зображень. У таких випадках розпакований файл може дуже сильно відрізнятися від оригіналу на рівні порівняння «біт у біт», але практично не відрізняється для людського вуха або ока в більшості практичних застосувань.
Багато методів фокусуються на особливостях будови органів почуттів людини. Психоакустична модель визначає те, наскільки сильно звук може бути стиснений без погіршення сприйманої якості звуку. Помітні для людського вуха або ока недоліки, що виникли через стиснення із втратами, відомі як артефакти стиску.
4.2. Архіватори
При збереженні, резервному копіюванні інформації тощо, якої б місткості не були ваші диски, завжди бажано стиснути файли так, щоб вони займали якомога менше місця. Найпростіше це робиться за допомогою програм, які звуться архіваторами. Зауважимо, що ці програми не тільки стискають інформацію в окремому файлі, але й можуть поміщувати в один архів групу (звичайно, споріднених за якоюсь ознакою) файлів.
Існує багато архіваторів. Серед них найбільш відомі: ARJ, DIET, ICE, LHA, LHARC, LZH, LZEXE, NARC, PAK, PKARC, PKLITE, PKXARC, PKPAK, PKZIP, PKUNZIP, RAR, ZOO. Далі ми розглянемо лише ті з них, які зарекомендували себе з найкращого боку і, отже, найчастіше використовуються на практиці. Зауважимо, що сучасні програмні продукти відомих фірм розповсюджуються в архівованому вигляді (за допомогою власних засобів) і розархівовуються при встановленні відповідної системи на вінчестер (програмами Setup або Install).
Комп'ютер не «розуміє» ніяких інших кодувань символів крім ASCII-кодування (чи споріднених кодувань). Тому перед використанням архівований файл повинен бути розархівованим.
Останнім часом з'явилися програми, які, знаходячись у пам'яті комп'ютера резидентно, архівують та розархівують «на льоту» всі файли, з якими ви працюєте, що дозволяє суттєвим чином заощаджувати простір на жорсткому диску. Такі можливості надають, наприклад, утиліта DBLSPACE операційної системи MS-DOS та програма DIET (T.Matsumoto, Японія).
4.2.1. Програма ARJ
Програма ARJ (R.Jung, США) дозволяє архівувати та розархівувати файли. Формат команди, за яким викликається програма:
ARJ команда [-кл [-кл...]] ім'я_архіву [імена_файлів...]
ім'я_архіву — задає архівний файл, який обробляється. Якщо ви додаєте файли до неіснуючого архівного файлу, то він утворюється з указаним іменем. Якщо розширення в імені архіву не задане, то мається на увазі, що воно — .ARJ.
імена_файлів — задає файли, що додаються до архіву, видаляються з архіву і т.д. Можна використовувати символи шаблонів (масок) DOS * та ?. Якщо імена файлів не задані, то маються на увазі всі файли у поточному каталозі або всі файли в архіві.
Далі наводиться список команд та ключів, які вживаються найчастіше. Його можна отримати після виконання команди ARJ без параметрів. Виконайте команду ARJ-? для одержання додаткової інформації.
Команди:
a Додати (Add) файли до архіву. Якщо в архіві вже існують указані файли, то вони заміщуються тими, що є на диску! Якщо вказаний архівний файл не існує, то він утворюється. Якщо файли, що додаються до архіву, не вказані, то архівуються всі файли поточного каталогу.
d Видалити (Delete) файли з архіву. При видаленні файлів з архіву треба обов'язково вказувати їх імена.
e Видобути (Extract) файли з архіву. Команда розархівовує вказані файли у вказаний каталог (за умовчанням — у поточний). Якщо у каталозі призначення вже існує файл з іменем файлу, що розархівовується, буде даний підказ-запит про перезапис або перейменування.
f Освіжити (Freshen) файли в архіві. До архіву додаються тільки нові (із більш пізньою датою утворення) версії файлів, які вже є в архіві.
l Видати список (List) файлів в архіві. Команда виводить на екран інформацію про імена файлів, їхні розміри у нестиснутому та стиснутому вигляді, відношення компресування, дати та час, контрольні суми, методи архівування.
m Перемістити (Move) файли до архіву. Цей режим повністю аналогічний режиму a, але при успішному архівуванні вказані файли знищуються на диску. Команда може використовуватися разом із ключами f та u.
t Тестувати (Test) цілісність файлів в архіві. Перевіряє внутрішню структуру архівного файлу і можливість його розархівування. Не виправляє помилок архіву, якщо вони є.
u Поновити (Update) файли в архіві. На відміну від режиму f до архіву додаються не тільки нові версії існуючих там файлів, а і файли, які відсутні в архіві.
v Видати багатослівний (Verbosely) список файлів в архіві. Додатково до інформації, що виводиться командою l, даються ще послідовні номери, шляхи, коментарі всіх файлів в архіві та деякі інші відомості.
x Видобути (eXtract) файли з архіву з повним шляхом. Відрізняється від команди e тим, що файли, поміщені до архіву із збереженням імен каталогів (ключ r), розархівовуються разом із структурою каталогів.
Ключі:
e Виключити (Exclude) шляхи з імен файлів. При розархівуванні файлів, які збережені з повними шляхами (ключ r), ці шляхи не беруться до уваги, тобто вказані файли відновлюються у поточний каталог без відтворення структури каталогів.
f Освіжити (Freshen) існуючі файли. Діє аналогічно до такої ж команди. Використовується разом із командами m, e, x.
g Архівувати (Garble — спотворювати) із паролем. Установлює пароль при архівуванні та розархівуванні. Зауважимо, що великі та малі літери розрізняються! При видаленні файлів з архіву (команда d) та при його прогляданні (команди l та v) задавати пароль не обов'язково. Будьте обережні при використанні цього ключа! Якщо ви забудете пароль, то інформація в архіві буде недоступною!
i Не виводити індикатор (Indicator) процесу (роз)архівування. Під час роботи програми виводяться поточні відсотки виконаної роботи. Ви можете відключити цей індикатор.
je Утворити архів, що саморозархівовується. Використовується разом із командою a. Створений архів має розширення .EXE і після запуску цього (виконуваного) файлу відбувається його самостійне розархівування без програми ARJ.
m Із застосуванням методу (Method) 0, 1, 2, 3, 4. Задає різні види стискання інформації при архівуванні:
0 Без стискання інформації, файли просто поміщаються до архіву. Найшвидший метод.
1 Максимальне стискання, працює повільно.
2 Менше стискання, більша швидкість.
3 Ще менше стискання, велика швидкість.
4 Найменше стискання, найбільша швидкість.
n Тільки нові (New) файли (не існуючі). При виконанні команди a до архіву додаються тільки ті файли, імена яких відсутні в архіві. При виконанні команд e або x з архіву видобуваються тільки ті файли, імена яких відсутні на диску призначення.
r Рекурсивне (Recurse) архівування підкаталогів. При використанні цього ключа разом із командами архівування до архіву заносяться також файли з підкаталогів каталогу, що архівується. Імена файлів із підкаталогів заносяться разом із шляхами.
u Поновити (Update) файли (нові та більш нові). Діє аналогічно до такої ж команди. Використовується разом із командами m, e, x.
v Дозволити багатотомний (multiple Volumes) архів. При архівуванні великих об'ємів інформації часто виникає ситуація, коли архів не може бути повністю поміщений на гнучкий диск. У цьому випадку використовується ключ v, який дозволяє записувати архів у багато томів (на декілька дискет). Перший том має розширення .ARJ, другий — .A01, третій — .A02 і т.д. Ключ звичайно використовується у комбінаціях: v360, v720, v1200, v1440, що задають розміри томів (збігаються зі стандартними форматами дискет), та va, що означає автоматичне визначення розмірів томів.
w Призначити робочий (Work) каталог. У процесі роботи програма ARJ утворює проміжні (тимчасові) файли на диску. Якщо ви архівуєте файли на дискеті, вам може не вистачити вільного простору. У цьому разі за допомогою ключа, що розглядається, ви можете задати робочий каталог на вінчестері, де, як правило, завжди є досить місця.
x Виключити (eXclude) указані файли з процесу обробки програмою ARJ. Застосовується як у режимі архівування, так і в режимі розархівування. Допускається використання символів * та ?.
y Передбачає відповідь «так» (Yes) на всі запитання. Цей ключ зручно використовувати в пакетних (batch) файлах. На будь-яке запитання (утворити каталог, перезаписати файл та ін.) дається позитивна відповідь.
Приклади використання програми ARJ:
1. Додати всі файли без структури каталогу: ARJ a -e archive *.*
2. Додати два файли до архіву: ARJ a archive name1 name2
3. Освіжити файли в архіві: ARJ f archive *.doc
4. Видалити файли з архіву: ARJ d archive *.txt
5. Видобути файли з архіву: ARJ e archive
6. Видобути файли з архіву із структурою каталогів: ARJ x archive
7. Видати список файлів в архіві: ARJ l archive
8. Перемістити файли до архіву: ARJ m archive *.doc
9. Те ж саме з паролем «TopSecr»: ARJ m -gTopSecr archive *.doc
10. Тестувати цілісність файлів в архіві: ARJ t archive
11. Додати файли до багатотомного архіву: ARJ a -va a:archive *.*
12. Видобути файли з багатотомного архіву: ARJ x -v a:archive
13. Перетворити архів на саморозгортаємий: ARJ a -je archive
4.2.2. Програма PKZIP
Програма PKZIP (фірма PKWARE, Inc., США) архівує файли. Формат команди, за яким викликається програма:
PKZIP [опції] ім'я_архіву [@файл_список] [імена_файлів...]
ім'я_архіву — задає архівний файл, який обробляється. Якщо ви додаєте файли до неіснуючого архівного файлу, то він утворюється з указаним іменем. Якщо розширення в імені архіву не задане, то мається на увазі, що воно — .ZIP.
імена_файлів — задає файли, що додаються до архіву, видаляються з архіву і т.д. Можна використовувати символи шаблонів (масок) DOS * та ?. Якщо імена файлів не задані, то маються на увазі всі файли у поточному каталозі або всі файли в архіві.
@файл_список — задає текстовий файл, у якому містяться імена файлів, що обробляються.
Далі наводиться список опцій, які вживаються найчастіше. Його можна отримати після виконання команди PKZIP /h[1|2|3|4]. Оскільки ці опції багато в чому аналогічні командам та ключам програми ARJ, наведемо лише їх короткий опис.
-a Додати (Add) файли до архіву.
-b[drive] Утворити тимчасовий архів на альтернативному диску.
-d Видалити (Delete) файли з архіву.
-e[x,n,f,s,0] Використати методи архівування: [eXtra — екстра | Normal — нормальний (умовчання) | Fast — швидкий | Super fast — надшвидкий | NO compression - без компресування].
-f Освіжити (Freshen) файли в архіві.
-l Вивести на екран ліцензійну (License) угоду.
-m[f,u] Перемістити (Move) файли до архіву [з опціями f або u].
-u Поновити (Update) файли в архіві.
-p|P Зберегти імена каталогів разом з іменами файлів, які архівуються (p — від заданого каталогу | P — від поточного).
-r Рекурсивне (Recurse) архівування підкаталогів.
-s[pwd] Архівувати (Scramble) із паролем (password) [якщо пароль не заданий, буде даний підказ для його введення].
-v[b][r][m][t][c] Продивитись (View) файли в архіві [Brief — коротко] [Reverse — в оберненому порядку] [More — поекранно] [Technical — із докладною технічною інформацією] [Comment — із коментарями], відсортовані за [d,e,n,o,p,s] [Date — датою | Extension — розширенням | Name — іменем | natural Order — у звичайному порядку (умовчання) | Percentage — відсотком стискання | Size — розміром].
-a+ Очистити атрибут «архівний» (archive Attribute) після архівування.
-c Утворити/редагувати коментарі (Comments) для всіх файлів.
-C Додати коментарі (Comments) тільки для нових файлів.
-i[-] Додати файли до архіву з існуючим установленням атрибуту «архівний» (archive Attribute) [не виключати атрибут].
-j|J<h,r,s> Маскувати або не маскувати файли з атрибутами (Hidden — прихований | System — системний | Read-only — тільки для читання) (умовчання — jhrs).
-o Встановити дату архіву за датою найпізнішого файлу у ньому.
-w|W<h,s> Включити або виключити (Hidden — прихований | System — системний) файли з процесу архівування (умовчання — Whs).
-x<file> Виключити (eXclude) указаний файл із процесу архівування.
-x@listfile Виключити (eXclude) указані у списку файли з процесу архівування.
-z Утворити або редагувати коментар архіву.
-@listfile Використати список імен файлів, які знаходяться у вказаному файлі
Приклади використання програми PKZIP
1. Додати всі файли поточного каталогу до архіву: PKZIP -a myzip
2. Додати всі файли типу .DOC диска A: до архіву: PKZIP -a mydoc a:*.doc
3. Видалити всі файли типу .DOC з архіву: PKZIP -d mydoc *.doc
4. Продивитись зміст архіву, що відсортований за іменем: PKZIP -vn myzip
5. Поновити файли поточного каталогу і його підкаталогів: PKZIP -ur mydoc
4.2.3. Програма PKUNZIP
Програма PKUNZIP (фірма PKWARE, Inc., США) розархівовує файли з архівів, утворених програмою PKZIP. Формат команди, за яким викликається програма:
PKUNZIP [опції] ім'я_архіву [@файл_список] [імена_файлів...]
ім'я_архіву — задає архівний файл, який обробляється. Якщо розширення в імені архіву не задане, то мається на увазі, що воно — .ZIP.
імена_файлів — задає файли, що обробляються програмою. Можна використовувати символи шаблонів (масок) DOS * та ?. Якщо імена файлів не задані, то маються на увазі всі файли у поточному каталозі або всі файли в архіві.
@файл_список — задає текстовий файл, у якому містяться імена файлів, що обробляються.
Далі наводиться список опцій, які вживаються найчастіше. Його можна отримати після виконання команди PKUNZIP /h[1|2|3|4]. Оскільки ці опції багато в чому аналогічні командам та ключам програми ARJ, наведемо лише їх короткий опис.
-c[m] Вивести файли на консоль — екран (Console) [у режимі More — поекранно].
-d Відновити/утворити структуру каталогів (Directory structure), збережену в архіві.
-e[c|d|e|n|p|r|s] Видобути (Extract) файли з архіву. Сортувати за [CRC — контрольною сумою | Date — датою | Extension — розширенням | Name — іменем | Percentage — відсотком стискання | Reverse — в оберненому порядку | Size — розміром].
-f Освіжити (Freshen) файли у каталозі призначення.
-j|J<h,r,s> Маскувати або не маскувати файли з атрибутами (Hidden — прихований | System — системний | Read-only — тільки для читання) (умовчання — jhrs).
-n Видобути тільки більш нові (Newer) файли з архіву.
-o Перезаписати (Overwrite) попередньо існуючі файли.
-p[a/b][c][#] Вивести файли на принтер (Printer) [Ascii-режим, Bin-режим, Com-порт] [порт №].
-s[pwd] Розархівувати (Scramble) із паролем (password) [якщо пароль не заданий, буде даний підказ для його введення].
-t Тестувати (Test) цілісність файлів в архіві.
-v[b][r][m][t][c] Продивитись (View) файли в архіві [Brief — коротко] [Reverse — в оберненому порядку] [More — поекранно] [Technical — із докладною технічною інформацією], відсортовані за [d,e,n,o,p,s] [Date — датою | Extension — розширенням | Name — іменем | natural Order — у звичайному порядку (умовчання) | Percentage — відсотком стискання | Size — розміром].
-x<filespec> Виключити (eXclude) указані файли з процесу розархівування.
-@listfile Використати список імен файлів, які знаходяться у вказаному файлі.
Приклади використання програми PKUNZIP
1. Перевірити цілісність файлів в архівах на диску A:: PKUNZIP -t a:*
2. Продивитись зміст архіву, що відсортований за іменем: PKUNZIP -vn myzip
3. Видобути файли з архіву: PKUNZIP myzip
4.2.4. Програма LHA
Програма LHA (H.Yoshizaki, Японія) дозволяє архівувати та розархівувати файли. Формат команди, за яким викликається програма:
LHA команда [/опції[-+012|WDIR]] ім'я_архіву [імена_файлів...]
ім'я_архіву — задає архівний файл, який обробляється. Якщо ви додаєте файли до неіснуючого архівного файлу, то він утворюється з указаним іменем. Якщо розширення в імені архіву не задане, то мається на увазі, що воно — .LZH.
імена_файлів — задає файли, що додаються до архіву, видаляються з архіву і т.д. Можна використовувати символи шаблонів (масок) DOS * та ?. Якщо імена файлів не задані, то маються на увазі всі файли у поточному каталозі або всі файли в архіві.
[/опції[-+012|WDIR]] — кожна з опцій може мати три значення (0, 1, 2), або два символи (+ — опція діє, - — опція не діє). Ці значення та символи ставляться праворуч від опції. Параметр WDIR задає робочий каталог (див. опцію w).
Далі наводиться список команд та опцій, які вживаються найчастіше. Його можна отримати після виконання команди LHA без параметрів.
Команди
a Додати (Add) файли до архіву. Якщо в архіві вже існують вказані файли, то вони заміщуються тими, що є на диску! Якщо вказаний архівний файл не існує, то він утворюється. Якщо файли, що додаються до архіву, не вказані, то архівуються всі файли поточного каталога.
d Видалити (Delete) файли з архіву. При видаленні файлів з архіву треба обов'язково вказувати їх імена. Можна використовувати символи шаблонів (масок) DOS * та ?.
e Видобути (Extract) файли з архіву. Команда розархівовує вказані файли у вказаний каталог (за умовчанням — у поточний). Можна використовувати символи шаблонів (масок) DOS * та ? як в іменах архівів, так і в іменах файлів. Якщо у каталозі призначення вже існує файл з іменем файлу, що розархівовується, то архівований файл не буде видобуватися.
f Освіжити (Freshen) файли в архіві. До архіву додаються тільки нові (з більш пізньою датою утворення) версії файлів, які вже є в архіві.
l Видати список (List) файлів у архіві. Команда виводить на екран інформацію про імена файлів, їх розміри у нестиснутому та стиснутому вигляді, відношення компресування, дати та час, контрольні суми, методи архівування. Якщо повне ім’я файла містить також каталог, то поруч із таким файлом ставиться знак «+».
m Перемістити (Move) файли до архіву. Цей режим повністю аналогічний режиму a, але при успішному архівуванні вказані файли знищуються на диску.
p Вивести на екран (disPlay) вміст файлів. Має сенс виводити вміст текстових файлів.
t Тестувати (Test) цілісність файлів у архіві. Перевіряє внутрішню структуру архівного файлу і можливість його розархівування. Не виправляє помилок архіву, якщо вони є.
u Поновити (Update) файли в архіві. На відміну від режиму f до архіву додаються не тільки нові версії існуючих там файлів, а і файли, які відсутні в архіві.
v Продивитись (View) список файлів у архіві. Додатково до інформації, що виводиться командою l, даються ще шляхи всіх файлів у архіві.
x Видобути (eXtract) файли з архіву з повним шляхом. Відрізняється від команди e тим, що файли, поміщені до архіву із збереженням імен каталогів (опція r), розархівовуються разом із структурою каталогів.
s Утворити архів, що саморозархівовується. Створений архів має розширення .EXE і після запуску цього (виконуваного) файлу відбувається його самостійне розархівування без програми LHA.
Опції
a Дозволити архівування файлів із будь-якими атрибутами (Attributes) — архівний (Archive), тільки для читання (Read Only), прихований (Hidden), системний (System). Якщо ця опція не вказана, то до архіву не заносяться приховані та системні файли.
c Пропустити перевірку (Check) дати та часу утворення файлів. При використанні цієї опції з командами розархівування (e та x) та при наявності у каталозі призначення файла з іменем файлу, що розархівовується, буде даний запит про розархівування та перезапис існуючого файла.
h Вибрати рівень заголовку (Header) (умовчання = 1).
i Не ігнорувати (Ignore) нижній регістр (малі літери). Якщо ви працюєте тільки з операційною системою MS-DOS, то ця опція не потрібна.
l Виводити на екран під час роботи архіватора разом із індикатором «довгі» (Long) імена файлів. Це означає, що разом із іменем виводиться також повідомлення вигляду [m/n], де n — загальна кількість файлів, що обробляються, m — порядковий номер файла, що обробляється у поточний момент часу.
m Не виводити на екран повідомлення (Message) про запит на розархівування, який задається при використанні опції «c».
n Не (No) виводити на екран індикатор процесу роботи архіватора та/або повні шляхи. Індикатор процесу роботи архіватора відображається символами «ooooooooooooooo...........».
o Використовувати старий (Old) метод компресування для забезпечення сумісності з попередніми версіями програми.
p Розрізняти повні — із шляхом (Path) — імена файлів. Використовується разом із командами розархівування (e та x). При цьому у поточний каталог розархівовуються лише ті файли, імена яких не містять підкаталогів. Якщо дана опція не використовується, то розархівовуються всі файли.
r Рекурсивне (Recurse) архівування підкаталогів. При використанні цього ключа разом з командами архівування (a, f, m, u) до архіву заносяться також файли із підкаталогів каталога, що архівується. Імена файлів з підкаталогів заносяться разом із шляхами.
t Зберігати час утворення архіву (archive's Time-stamp). Без цієї опції дата утворення архіву встановлюється за поточним системним часом, при її використанні — за самою новою датою файла із архіву.
w Призначити робочий (Work) каталог. В процесі роботи програма LHA утворює проміжні (тимчасові) файли на диску. Якщо ви архівуєте файли на дискеті, вам може не вистачити вільного простору. В цьому разі за допомогою ключа, що розглядається, ви можете задати робочий каталог на вінчестері, де, як правило, завжди є досить місця.
x Дозволити розширені (eXtended) імена файлів, тобто імена, в яких вказуються також і підкаталоги. Може використовуватись разом із опцією «r».
z Не виконувати компресування файлів (Zero compression — нульове компресування). Тільки помістити їх до архіву.
– Дозволити використання символів «–» або «@» як перших літер у іменах файлів.
Приклади використання програми LHA
1. Додати два файли до архіву: LHA a archive name1 name2
2. Освіжити файли в архіві: LHA f archive *.doc
3. Видалити файли з архіву: LHA d archive *.txt
4. Видобути файли з усіх lha-архівів: LHA e ?.lha
5. Видобути файли з архіву із структурою каталогів: LHA x archive
4.2.5. Програма PKLITE
Програма PKLITE (фірма PKWARE, Inc., США) використовується для компресування виконуваних файлів (з розширеннями .COM та .EXE). При цьому компресовані файли при їх запуску розархівовуються у пам'яті комп'ютера автоматично. Стискає виконувані файли приблизно в два рази. Формат команди, за яким викликається програма:
PKLITE [опції] вхід_файл [вихід_файл]
вхід_файл — задає ім'я вхідного виконуваного файлу, який компресується. Можна використовувати символи шаблонів (масок) DOS * та ?.
вихід_файл — задає ім'я вихідного виконуваного компресованого файлу. За умовчанням приймає значення імені вхідного файлу.
Далі наводиться список опцій. Його можна отримати після виконання команди PKLITE.
-a Завжди (Always) компресувати файли з оверлеями та оптимізувати таблицю переміщень. З цією опцією у вас можуть виникнути проблеми, тому краще не використовувати її.
-b Утворити копію (з розширенням .BAK) оригінального файлу.
-e Зробити компресований файл таким, що не розгортається надалі з використанням опції -x (Extra compression — екстракомпресування). З цією опцією компресований файл зменшується у розмірі незначним чином (на декілька десятків байтів), тому її використання навряд чи доцільне.
-l Вивести на екран ліцензійну (License) угоду про умови розповсюдження та використання програми.
-n Ніколи (Never) не компресувати файли з оверлеями або оптимізувати таблицю переміщень. Якщо ви компресуєте групу файлів, селектованих за допомогою шаблонів DOS, і серед цих файлів є оверлейні, краще скористатися цією опцією.
-o Перезаписати вихідний файл, якщо він існує на диску.
-r Видалити (Remove) оверлейні дані. З цією опцією у вас можуть виникнути проблеми, тому краще не використовувати її.
-u Поновити (Update) час та дату утворення файлу, що компресується, змінивши їх на поточні.
-x Розгорнути (eXpand) компресований файл (на диску), тобто перевести його до первісного стану, декомпресувати. Опція не діє, якщо ви компресували файл з опцією -e.
Приклади використання програми PKLITE
1. Компресувати всі виконувані файли в поточному каталозі: PKLITE *.*
2. Розгорнути компресований файл: PKLITE -x myfile.exe
4.2.6. Програма LZEXE
Програма LZEXE (F.Bellard, Франція), як і PKLITE, використовується для компресування виконуваних файлів (тільки з розширеннями .EXE). При цьому компресовані файли при їх запуску розархівовуються у пам'яті комп'ютера автоматично. Стискає виконувані файли приблизно у два рази. Оригінальні (некомпресовані) файли зберігаються під тим саме іменем, але з розширенням .OLD. Формат команди, за яким викликається програма:
LZEXE імена_файлів
імена_файлів — задає імена EXE-файлів, які компресуються. Задавати розширення (.EXE) — не обов'язково. Можна використовувати символи шаблонів (масок) DOS * та ?.
Приклад використання програми LZEXE:
1. Компресувати всі EXE-файли в поточному каталозі: LZEXE *.*
5. Висновки
Серед великої кількості алгоритмів стиснення інформації у даній роботі було розглянуто ті які використовуються найчастіше, а отже мають найбільше практичне застосування. В основі усіх цих методів лежать чотири теоретичних алгоритми: алгоритм RLE (Run Length Encoding); алгоритми групи KWE (KeyWord Encoding); алгоритм Хафмана та сімейство алгоритмів LZ78 (LZW, MW, AP, Y).
Пошуку нових шляхів стиснення даних на основі ефективного кодування та теоретико-числових перетворень (ТЧП) присвячено багато наукових робіт. Великий внесок у розвиток цієї теорії зробили Шеннон та Хартлі.
Кожен з розглянутих вище архіваторів має свої недоліки і переваги, в залежності від того, ким вони використовуються і яку інформацію обробляють. Однак всі вони зарекомендували себе з кращого боку, адже найчастіше використовуються на практиці.
6. Використана література
1. Кричевский Р.Е. Сжатие и поиск информации. – М., Радио и связь, 1989
2. Кох Яцків Н.Г., Николайчук Я.М. Методи стиснення даних в багатоканальних системах на основі кодів Галуа // Вісник національного університету «Львівська політехніка» Радіоелектроніка та телекомунікації. – 2002.- №443. – С.135-138манюк Д. “Сжатие информации: как это делается”, Index PRO, 1993 К., №№ 1-2
3. Рябко Б.Я. Сжатие информации с помощью стопки книг. // Проблемы передачи информации.- 1980, т.16, №4. С.16-21
4. Кохманюк Д. Сжатие данных: как это делается // Компьютеры+программы,1995.
5. Новосельский А. Алгоритмы шифрования // Компьютеры + программы 1996-№5.- С.70-77
6. Хоффман Л. Современные методы защиты информации: Пер. с англ. -М.: Сов. радио, 1980, 264с.
7. Калабин С.И., Голик Л.В.,Пустовит А.В., Козакова Е.В. Справочник пользователя IBM PC. -К: КП "Техинком" МИП "Арфа", ' 1991.-112 с
8. Зкслер А. Б. Архиваторы (Проґраммы для хранения й обработки информации в сжатом виде). - М: Малое предприятие "Алекс", 1992. - 150 с. 12. Компьютер Пресе. -М: 1994; N 1-5
