Теорія операційної системи

:: Меню ::

Головна
Представлення даних в обчислювальних системах
Машинні мови
Завантаження програм
Управління оперативною пам'яттю
Сегментна і сторінкова віртуальна пам'ять
Комп'ютер і зовнішні події
Паралелізм з точки зору програміста
Реалізація багатозадачності на однопроцесорних комп'ютерах  
Зовнішні пристрої
Драйвери зовнішніх пристроїв
Файлові системи
Безпека
Огляд архітектури сучасних ОС

:: Друзі ::

Карта сайту
 

:: Статистика ::

 

 

 

 

 

 

Упаковка даних

Дані багатьох форматів мають значний об'єм, тому їх зберігання і передача частенько вимагають значних ресурсів. Одним із способів вирішення цієї проблеми є підвищення ємкості пристроїв, що запам'ятовують, і пропускної спроможності каналів зв'язку. Проте у багатьох випадках застосовна і дешевша альтернатива цим методам — упаковка даних.
Науковою основою всіх методів упаковки є теорія інформації: дані, в яких є статистичні автокореляції, називаються надлишковими або такими, що мають низьку ентропію. Усунувши ці автокореляції, тобто підвищивши ентропію, об'єм даних можна зменшити без втрати сенсу, а частенько і з можливістю однозначно відновити вихідні дані. Методи підвищення ентропії, які не дозволяють по упакованому потоку відновити початковий, називаються необоротними, приблизними або що стискують з втратами (losing compression). Відповідно, методи, які дозволяють це сделать, називаються оборотними, точними, або що стискують без втрат (losless compression).
Один з перших методів упаковки був запропонований задовго до розробки сучасної теорії інформації; у 1844 році Семюел Морзе побудував першу лінію дротяного телеграфу. Система кодування букв, відома як Азбука Морзе (таблиця. 1.4), використовувала для представлення різних букв алфавіту посилки різної довжини, при цьому довжина посилки залежала від частоти використання відповідного символу в англійській мові. Символи, що часто зустрічаються, кодувалися коротшими послідовностями.

Таблиця 1.4. Російська азбука Морзе

Буква

Символи Морзе

Слово

Буква

Символи Морзе

Слово

А

.-

а-том

Р

.-.

ра-ду-га

Би

-...

бес-са-раб-ка

З

 

са-ма-ра

У

.--

ва-ви-лон

Т

-

Струм

Г

--.

го-ло-ва

В

..-

 

Д

-..

до-бав-ка

ф

..-.

фа-на-тіч-ка

Е

   

X

 

ха-на-ан-ка

Же

...-

жат-ва-зла-ков

ц

-.-.

ци-га-ноч-ка

3

--..

звон-бу-ла-та

ч

 

че-ре-му-ха

І

   

ш

— -

ше-ре-ме-тев

До

-.-

конс-тан-тин

Щ

--.-

щу-ро-гла-зий

Л

.-..

ла-до-жан-ка

ю

..--

 

М-код

--

мі-іїн

я

.-.-

 

Н

-.

но- га

и

-.--

и-ка-ні-е

0

о-ло-во

ь-'

-..-

 

П

.--.

па-ні-хи-да

     

Примітка
У допоміжних словах для запам'ятовування склади, що містять букву "а", позначають крапкою, що не містять - тире.

В кінці сорокових років XX століття засновником сучасної теорії інформації Шеноном, і незалежно від нього, Фано був розроблений універсальний алгоритм побудови оптимальних код. Більш ізвестий аналог цього алгоритму був запропонований декілька пізніше Девідом Хаффманом [Huffman 1952]. Принцип побудови цих код в цілому відповідає логіці, якою керувався Морзе, — кодувати значення, які часто повторюються в потоці, коротшими послідовностями бітів.
Коди Хаффмана і Шеннона-фано усувають автокореляції, відповідні нерівномірності тієї, що зустрічається символів, але зберігають без змін послідовності символів, що часто зустрічаються, а вони відповідальні за значну частину надмірності текстів на природних і синтетичних мовах. Для упаковки даних такого роду в кінці 70-х Лемпелем і Зіффом було запропоновано сімейство алгоритмів, найбільш відомі з яких - Lz77 і LZW [Lempel-ziv 1978].
Всі ці алгоритми зводяться до пошуку в потоці послідовностей, що повторюються, і заміни цих послідовностей на їх номер в динамічно формованому словнику. Відмінність полягає в способах кодування номера і формування словника. Номер послідовності в словнику повинен містити більше бітів, чим символи вихідного потоку, хоч би вже для того, щоб його можна було відрізнити від символу, тому алгоритми Лемпеля-зіффа передбачають те, що подальше перекодувало перетвореного потоку кодом Хаффмана. Більшість сучасних архіваторів, такі, як Pkzip, GNU Zip, RAR, засновані на варіаціях і аналогах алгоритмів Лем-пеля-зіффа.
При упаковці нетекстових даних можуть застосовуватися і інші способи видалення повторень. Наприклад, при упаковці растрових зображень широко використовується метод RLE (Run-length Encoding), коли піксели, що повторюються, замінюються лічильником повторень і значенням піксела.
Найбільш універсальні так звані арифметичні алгоритми, які знаходять і усувають всі автокореляції, присутні у вхідних даних. Математичне обгрунтування і принципи роботи цих алгоритмів заслуговують на окрему книгу і відвели б нас далеко убік від теми. На жаль, із-за великих обчислювальних витрат ці алгоритми і програми, що реалізовують їх, не набувають широкого поширення.
Всі перераховані алгоритми здатні лише усувати автокореляції, що вже існують у вхідному потоці. Зрозуміло, що якщо автокореляцій не було, то упаковки не станеться, тому гарантувати рівень упаковки ці алгоритми не можуть.
Для упаковки даних, отриманих оцифруванням реальних сигналів, перш за все зображень і звуку, точні алгоритми не личать абсолютно. Річ у тому, що реальний сигнал завжди супроводиться тепловим, так званим білим (що рівномірно містить всі частоти) шумом. Цей шум спотворює наявні в сигналі автокореляції, сам же автокореляцій не має, тому оборотні алгоритми із зашумленним сигналом впоратися не можуть.
Щоб переконатися в цьому, можна спробувати упакувати будь-яким, або навіть декількома з поширених архіваторів трек аудіо-cd або цифрову фотографію втім, щоб з цифровою фотографією фокус вийшов, необхідно, щоб кадр був знятий без обробки вбудованим пакувальником камери.
Ідея обширного сімейства алгоритмів, придатних для стискування зашумлен-них сигналів, була позаїмствована з принципу роботи цифрових фільт-ров-"щумодавов". Шумодав працює таким чином: він здійснює над сигналом перетворення Фур'є і видаляє з отриманого спектрального образу найслабкіші частоти, які нижче за поріг придушення.
Сигнал при цьому, звичайно, спотворюється, але найсильніше при цьому страждає рівномірно розподілений по спектру шум, що і потрібне (мал. 1.8).

Мал. 1.8. Зашумленний сигнал і його спектральний образ (результат перетворення Фур'є), цит. по [Smith 1997]

Алгоритми JFIF (лежачий в основі поширеного формату зберігання растрових зображень JPG), MPEG, Mp3 [www.jpeg.org] теж починаються з виконання над вхідним потоком перетворення Фур'є. Але, на відміну від шумодава, JFIF видаляє з отриманого спектру не частоти, які нижче заданого порогу, а фіксовану кількість частот — звичайно ж, прагнучи відібрати найслабкіші. Кількість частот, які треба викинути, визначається параметром налаштування пакувальника. В JFIF цей параметр так і називається — коефіцієнтом упаковки, в МРЗ — бітрейтом.
Профільтрований сигнал свідомо містить автокореляції — навіть якщо початковий, незашумленний, сигнал їх і не містив, така фільтрація їх створить — і тому легко піддається упаковці. Завдяки цьому, всі перераховані алгоритми забезпечують гарантований рівень упаковки. Вони здатні стискувати в задане число раз навіть чистий білий шум. Зрозуміло, що точно відновити по підданому такому перетворенню потоку вихідний сигнал неможливо, але такій меті і не ставиться, тому всі перераховані методи відносяться до розряду необоротних.
При розумно вибраному рівні упаковки результат — фотореалістичне зображення або музичний твір — на погляд (або, відповідно, на слух) практично невідмітний від оригінала. Відмінність може показати лише спектральний аналіз даних. Але якщо розпакувати стисле з втратами зображення, піддати його редагуванню (наприклад, отмасштабіровать або примальовувати який-небудь логотип), а потім упакувати знову, результат буде гнітючим: редагування привнесе в зображення нові частоти, тому велика небезпека, що повторна упаковка навіть з нижчим коефіцієнтом стискування відкусить якісь з "корисних" частот зображення. Після декількох таких перепаковувань від зображення залишається лише сюжет, а від музики — лише основний ритм. Тому серйозно пропонується використовувати приблизні алгоритми упаковки як механізм зашиті авторських прав: у спірній ситуації лише справжній автор твору може пред'явити його вихідний, неупакований варіант.
Експериментальні варіанти приблизних алгоритмів замість класичного розкладання по зваженій сумі синусів і косинусів використовують розкладання по спеціальних функціях, так званим вейвлетам (wavelet). Затверджується, що вейвлетная фільтрація при тому ж рівні стискування (зрозуміло, що порівнювати по рівню стискування алгоритми, які стискують що завгодно в задане число разів, абсолютно безглуздо) дає менший рівень суб'єктивно виявлених спотворень. Але суб'єктивне сприйняття, як відомо, сильно схильне до ефекту плацебо (людина схильна бачити поліпшення або взагалі зміну там, де його немає, якщо має підстави передбачати, що зміна повинна статися), зате вейвлетниє алгоритми сильно поступаються звичайним варіаціям JFIF по продуктивності, тому до цих пір вони не вийшли з експериментального достатку.


:: Реклама ::

 

:: Посилання ::


 

 

 


Copyright © Kivik, 2017