Ім'я файлу: Referat_Archivation.docx
Розширення: docx
Розмір: 125кб.
Дата: 20.10.2021
скачати

ДЕРЖАВНИЙ УНІВЕРСИТЕТ ТЕЛЕКОМУНІКАЦІЙ

Навчально-науковий інститут Заочного та Дистанційного навчання
Кафедра Інформаційної та кібернетичної безпеки

Спеціальність 125 – «Кібербезпека»

заочна форма навчання

Курс, академгрупа

РЕФЕРАТ

з дисципліни «Теорія інформації та кодування»

на тему:

«ІНФОРМАЦІЯ. СТИСНЕННЯ ДАНИХ. ПРОГРАМИ-АРХІВАТОРИ»
студента


Київ – 2019

Зміст





Вступ 3

1. Поняття інформації та даних. Поняття носія інформації 4

2. Стиснення (архівування) інформації 6

3. Алгоритми стиснення без втрати інформації 10

3.1. Алгоритм RLE 10

3.2. Алгоритми групи KWE 10

3.3. Алгоритм Хафмана 12

4. Програми-архіватори 13

Висновки 14

Список використаної літератури 15

Вступ



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

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

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

1. Поняття інформації та даних. Поняття носія інформації



Для початку треба визначити що ж таке «інформація», її види та способи передачі. Почнемо з визначення науки, що вивчає інформацію – інформатики.

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

До базових понять, які використовуються в інформатиці, відносяться: данні та інформація. Ці поняття часто використовуються як синоніми, однак між ними є суттєві відмінності. Термін «данні» походить від слова data – факт, а поняття «інформація» (від латинського information – відомості, роз’яснення, виклад) багатозначне.

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

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

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

  • вірогідність;

  • повнота;

  • актуальність;

  • корисність;

  • зрозумілість.

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

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

Розрізняють такі носії інформації:

  • рукописні й типографські;

  • машинні: запам’ятовуючі пристрої комп’ютера (диски, дискети, флешки);

  • спеціальні: кіно, відео, фотографія тощо.

Носії інформації – матеріальний об’єкт для зберігання інформації. Носієм інформації може бути:

  • Будь-який матеріальний предмет (папір, камінь, дерево, класна дошка, зоряний пил тощо);

  • Хвилі різної природи: акустична (звук), електромагнітна (світло, радіохвиля), гравітаційна (тиск, тяжіння) тощо;

  • Речовина в різному стані: концентрація молекул у рідкому розчині, температура і тиск газу тощо.

2. Стиснення (архівування) інформації



Характерною особливістю більшості типів даних є їх надлишковість (ентропія).

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

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

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

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

  • Стиснення (архівування) файлів: використовується для зменшення розмірів файлів при підготовці їх до передавання каналами зв’язку або до транспортування на зовнішніх носіях малої ємності;

  • Стиснення (архівування) папок: використовується як засіб зменшення обсягу папок перед довготерміновим зберіганням, наприклад, при резервному копіюванні;

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

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

  • зміна вмісту даних;

  • зміна структури даних;

  • комбінація змін структури та вмісту даних.

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

  • JPEG – для графічних даних;

  • MPG – для відеоданих;

  • MP3 – для аудіоданих.

Розглянемо приклад стиснення зі зміною вмісту на Рисунку 1. В результаті стиснення графічного зображення з 11,2 КБ до 1,5 КБ (на 86 %) таким методом, відбувається незворотна втрата частини інформації.


Рис. 1. Результат стиснення графічних даних методом зміни вмісту даних (виконано за допомогою ресурсу https://compressimage.toolur.com/)
Якщо при стисненні даних відбувається тільки зміна структури даних, то метод стиснення є зворотнім. У цьому випадкові з архіву можна відновити інформацію повністю. Зворотні методи стиснення можна застосовувати до будь-яких типів даних, але вони дають менший ступінь стиснення у порівнянні з незворотними методами стиснення. Приклади форматів стиснення без втрати інформації:

  • GIF, TIFF – для графічних даних;

  • AVI – для відеоданих;

  • ZIP, ARJ, RAR, CAB, LH – для довільних типів даних.

Отже, обирати оптимальний алгоритм стиснення необхідно з урахуванням багатьох факторів, бо кожен з них має свої недоліки та переваги. Для прикладу ефективності архівування в залежності від типу даних розглянемо Таблицю 1, де наведені приклади результатів архівування даних різного формату.
Таблиця 1. Результат архівування різних типів даних»

Файл

Тип даних

Початковий обсяг даних

Відсоток стиснення

Обсяг даних після архівування

Колобок.gif

Малюнок gif

53430

14 %

46117

Animation.gif

Малюнок gif

1015

1 %

1004

Машина.bmp

Точковий малюнок

1399958

99 %

5650

Пісня.doc

Документ MS Word

638976

88 %

78640

Car.jpg

Малюнок jpeg

59209

1 %

58635

Кіно.mpeg

Кінострічка

860418

4 %

824239

Ch.psp

Paint shop pro image

520580

23 %

401031

Mspaint.exe

Додаток

344064

57 %

146306

slipmenu

Макрос

2813

60 %

1123

Index.dat

Файл dat

16 384

98 %

316

Edit.hlp

Файл довідки

11016

63 %

4102

Car.wmf

Малюнок wmf

7222

71 %

2092

Jscript.htm

Документ html

77

9 %

70


3. Алгоритми стиснення без втрати інформації



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

  • Алгоритм RLE (Run Length Encoding);

  • Алгоритми групи KWE (KeyWord Encoding);

  • Алгоритм Хафмана.



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


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

Існує досить багато реалізацій цього алгоритму, серед яких найбільш поширеними є алгоритм Лемпеля-Зіва (алгоритм LZ) та його модифікація алгоритм Лемпеля-Зіва-Велча (алгоритм LZW). Словником в даному алгоритмі є потенційно нескінченний список фраз. Алгоритм починає роботу з майже пустого словника, що містить тільки один закодований рядок, так званий NULL-рядок. Коли зчитується черговий символ вхідної послідовності даних, він додається до поточного рядка. Процес продовжується доти, поки поточний рядок відповідає якій-небудь фразі з словника. Але рано чи пізно поточний рядок перестає відповідати якій-небудь фразі словника. У цей момент, коли поточний рядок являє собою останній збіг зі словником плюс щойно прочитаний символ повідомлення, кодер видає код, що складається з індексу збігу і наступного за ним символу, що порушив збіг рядків. Крім того, нова фраза, що складається з індексу збігу і наступного за ним символу, додається в словник. У наступний раз, коли ця фраза з’явиться в повідомленні, вона може бути використана для побудови більш довгої фрази, що підвищує міру стиснення інформації.

Алгоритм LZW побудований навколо таблиці фраз (словника), яка відображає рядки символів стискуваного повідомлення в коди фіксованої довжини. Таблиця володіє так званою властивістю передування, тобто для кожної фрази словника, що складається з деякої фрази (W) і символу (К) фраза W також міститься в словнику. Якщо всі частинки словника повністю заповнені кодування перестає бути адаптивним (кодування відбувається виходячи з вже існуючих в словнику фраз).

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

3.3. Алгоритм Хафмана


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

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

Розглянемо простий приклад, що ілюструє роботу алгоритму Хафмана. Нехай задано текст, в якому літера «А» міститься 10 разів, літера «B» – 8 разів, «C» – 6 разів , «D» – 5 разів, «E» та «F» – по 4 рази. Тоді один з можливих варіантів кодування за алгоритмом Хафмана наведений у Таблиці 2.
Таблиця 2. «Кодування символів за алгоритмом Хафмана»

Символ

Частота входження

Бітовий код

A

10

00

B

8

01

C

6

100

D

5

101

E

4

110

F

4

111


Як видно з Таблиці 2, розмір вхідного тексту до стиснення рівний 37 байт, тоді як після стиснення – 93 біт, тобто майже 12 байт (без врахування довжини словника). Коефіцієнт стиснення рівний 32 %. Алгоритм Хафмана універсальний, тобто його можна застосовувати для стиснення даних будь-яких типів, але він малоефективний для файлів малих розмірів (за рахунок необхідності зберігання словника).

4. Програми-архіватори



Архіватори – це програми (комплекс програм), які використовують для стискання і відновлення стиснених файлів у первинний вигляд. Процес стискання файлів називається архівацією. Процес відновлення стислих файлів – розархівуванням.

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

Найбільш поширеними програмами-архіваторами є: PKZIP (з розархіватором PKUNZIP), LHARC, RAR, ARJ, ICE, WinZip, WinRar, 7z. Ці програми відрізняються форматами архівних файлів, швидкістю роботи, мірою стиснення записів в архіві, інтерфейсом користувача, операційною системою, під управлінням якої вони працюють.

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

  • наявності на дисках великих обсягів інформації, яка буде необхідною для використання в майбутньому;

  • збереження та передавання інформації за допомогою дискет чи комп’ютерної мережі;

  • створення резервних копій в стислому вигляді.

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

Висновки



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

Список використаної літератури




  1. Інформатика: Комп’ютерна техніка. Комп’ютерні технології / За ред. О.І. Пушкаря – К.: Видавничий центр «Академія», 2001. – 696 с.

  2. Саєнко Г. В., Волобуєва Т. Б. Курс користувачів персональним комп’ютером. – 2006. – 278 с.

  3. Рудненко В. Д., Макарчук О. М., Патланжоглу М. О. Практичний курс інформатики / За ред. Мадзігона В.М. - К.: Фенікс, 2007. – 304 с.

скачати

© Усі права захищені
написати до нас