Подання інформації в комп’ютерах, Детальна інформація

“Подання інформації

в комп’ютерах” 

Системи числення.

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

В другій половині ХХ-го століття з винайденням та розвитком ЕОМ проблема стискання та кодування привернула до себе увагу, бо з чисто теоретичної перетворилася в прикладну та вкрай необхідну. Стрімко зросли обсяги даних, з’явилась потреба в передачі дискретної інформації на далекі відстані з достатньою надійністю, проблема захисту такої інформації від несанкціанованого доступу і т. д. З розвитком комп’ютерних мереж (зокрема, INTERNET) обсяг інформації, що передається, швидко зростає і вимагає її мінімізації шляхом специфічного кодування для підтримання швидкодії мережі. Можна навести багато інших застосувань кодування інформації.

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

Ідея арифметичного кодування.

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

Перед початком роботи відповідний до тексту інтервал є [0 ; 1). При обробці наступного символу його ширина звужується за рахунок виділення цьому символу частини інтервалу. Наприклад, застосуемо до тексту “еаіі!” алфавіта {а, е, і, о, u, ! } модель з постійними ймовірностями, що задані в таблиці 1.

Таблиця SEQ Таблица \* ARABIC 1 . Приклад постійної моделі для алфавіта {а, е, і, о, u, ! }.

Символ Ймовірність Інтервал

А 0,2 [0,0; 0,2)

Е 0,3 [0,2; 0,5)

І 0,1 [0,5; 0,6)

О 0,2 [0,6; 0,8)

У 0,1 [0,8; 0,9)

! 0,1 [0,9; 1,0)



І кодувальнику, і декодувальнику відомо, що на самому початку інтервал є [0; 1). Після перегляду першого символу “е”, кодувальник звужує інтервал до [0,2; 0,5), який модель виділяє цьомк символу. Другий символ “а” звузить цей новий інтервал до першої його п’ятої частина, оскільки для “а” виділено фіксований інтервал [0,0; 0,2). В результаті отримаємо робочий інтервал [0,2; 0,26), бо попередній інтервал мав ширину в 0,3 одиниці та одна п’ята від нього є 0,06. Наступному символу “і” відповідає фіксований інтервал [0,5; 0,6), що застосовно до робочого інтервалу [0,2; 0,26) звужує його до інтервалу [0,23; 0,236). Продовжуючи таким саме способом маємо:

На початку [0.0; 1.0 )

Після перегляду “е” [0.2; 0.5 )

Після перегляду “а” [0.2; 0.26 )

Після перегляду “і” [0.23; 0.236 )

Після перегляду “і” [0.233; 0.2336 )

Після перегляду “!” [0.23354; 0.2336 )

Припустимо, що все те, що декодувальник знає про текст, це кінцевий інтервал [0,23354; 0,2336). Він відразу ж зрозуміє, що перший закодований символ – це “е”, тому що підсумковий інтервал цілком лежить в інтервалі, що був виділений цьому символу відповідно до Таблиці 1. Тепер повторимо дії кодувальника:

Спочатку [0.0; 1.0 )

Після перегляду “е” [0.2; 0.5 )



Звідси зрозуміло, що другий символ – це “а”, оскільки це призведе до інтервалу [0,2; 0,26), який цілком містить в собі підсумковий інтервал [0,23354; 0,2336). Працюючи в такий спосіб, декодувальник витягує весь текст.