Відмінності між версіями «'''Методи стиснення з втратою даних'''»

Поточна версія на 08:17, 21 березня 2017

Методи стиснення з втратою даних I Шевченко Є. В.

Вступ Характерною особливістю більшості типів даних є їхній розмір. Для людини надлишковість даних часто пов'язана з якістю інформації, оскільки надлишковість, як правило, покращує зрозумілість та сприйняття інформації. Однак, коли мова йде про зберігання та передачу інформації засобами комп'ютерної техніки, то надлишковість відіграє негативну роль, оскільки вона приводить до зростання вартості зберігання та передачі інформації. Особливо актуальною є ця проблема у випадку необхідності обробки величезних обсягів інформації при незначних об'ємах носіїв даних. У зв'язку з цим постійно виникає проблема позбавлення надлишковості або стиснення даних. Основний принцип, на якому базується стиснення даних, полягає в економічному описі повідомлення, згідно якому можливе відновлення початкового його значення з похибкою, яка контролюється. Метою даної роботи є знаходження такого способу архівації, який дозволить досягти ефективного стиснення даних і мінімізувати втрату інформації при відновленні. Існує багато практичних алгоритмів стиснення даних. Однак, в основі цих методів лежать чотири теоретичних алгоритми: алгоритм RLE (Run Length Encoding); алгоритми групи KWE (KeyWord Encoding); алгоритм Хафмана, сімейство алгоритмів LZ78 (LZW, MW, AP, Y) В основі алгоритму RLE лежить ідея виявлення послідовностей даних, що повторюються, та замфіни цих послідовностей більш простою структурою, в якій вказується код даних та коефіцієнт повторення. В основі алгоритму KWE покладено принцип кодування лексичних одиниць групами байт фіксованої довжини. Результат кодування зводиться в таблицю, утворюючи так званий словник. В основі алгоритму Хафмана лежить ідея кодування бітовими групами. Після частотного аналізу вхідної послідовності символи сортуються за спаданням частоти входження. Чим частіше зустрічається символ, тим меншою кількістю біт він кодується. Результат кодування зводиться в словник, що необхідний для декодування. Пошуку нових шляхів стиснення даних на основі ефективного кодування та теоретико-числових перетворень (ТЧП) присвячено багато наукових робіт. Зокрема необхідно відзначити значний внесок відомих вчених: Харкевича О.О., Вошні О.Г., Макса Ж., Хартлі Р., Рабінера Л., Рейдера У., Голда Б., Акушського І. Я., Николайчука Я.М., Ольховського Ю.Б.

Історія розвитку теорії стиснення інформації У сорокових роках учені, що працюють в області інформаційних технологій, ясно зрозуміли, що можна розробити такий спосіб збереження даних, при якому простір буде витрачатися більш ощадливо. Клод Шеннон, вивчаючи нюанси розходжень між семантикою (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 від вихідного розміру. Доведення Шенона не було конструктивним, тобто не містило способу побудови цих оптимальних кодів, а лише показувало їхнє існування. До появи роботи Шенона, кодування символів алфавіту при передачі повідомлення по каналах зв'язку здійснювалося однаковою кількістю біт, одержуваним по формулі Хартлі. З появою цієї роботи почали з'являтися способи, що кодують символи різним числом біт у залежності від імовірності їх появи у тексті.

Стиснення з втратами та стиснення без втрат Стиснення з втратами (англ. Lossy compression) — метод стиснення даних, при якому розпакований файл відрізняється від оригінлау, проте може бути корисним для використання. Стиснення із втратами найчастіше використовується для мультимедіа даних (аудіо, відео, зображення), особливо для потокової передачі даних та і телефонії. В цьому контексті такі методи часто називаються кодеками. Існують дві основних схеми стиску із втратами: 1)У трансформуючих кодеках стиснення (англ. lossy transform codecs) беруться фрейми зображень або звуку, розрізуються на невеликі сегменти, трансформуються в новий базисний простір і здійснюється квантування. Результат потім стискується ентропійними методами. 2)У предиктивних кодеках стиснення (англ. 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

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

Архіватори При збереженні, резервному копіюванні інформації тощо, якої б місткості не були ваші диски, завжди бажано стиснути файли так, щоб вони займали якомога менше місця. Найпростіше це робиться за допомогою програм, які звуться архіваторами. Зауважимо, що ці програми не тільки стискають інформацію в окремому файлі, але й можуть поміщувати в один архів групу (звичайно, споріднених за якоюсь ознакою) файлів. Існує багато архіваторів. Серед них найбільш відомі: ARJ, DIET, ICE, LHA, LHARC, LZH, LZEXE, NARC, PAK, PKARC, PKLITE, PKXARC, PKPAK, PKZIP, PKUNZIP, RAR, ZOO. Далі ми розглянемо лише ті з них, які зарекомендували себе з найкращого боку і, отже, найчастіше використовуються на практиці. Зауважимо, що сучасні програмні продукти відомих фірм розповсюджуються в архівованому вигляді (за допомогою власних засобів) і розархівовуються при встановленні відповідної системи на вінчестер (програмами Setup або Install).