1.Вступ
Ефективна організація обміну інформацією придає все більше значення передусім успішній практичній діяльності людей. Обсяг інформації, необхідної для нормального функціонування сучасного суспільства, росте приблизно пропорціонально квадрату розвитку продуктивних сил. Частка робочої сили, зайнятої питаннями забезпечення інформацією, в розвинених країнах починає перевищувати частку робочої сили, зайнятої безпосередньо в сфері виробництва. Застосування методів і коштів автоматизації на всіх етапах звертання інформації дозволяє істотно підвищити ефективність функціонування економіки країни і вивільнити значні трудові ресурси.
Хоч роль інформації може обмежуватися невизначеним емоційним впливом на людину, в чисто технічних (автоматичних) і людино-машинних (автоматизованих) системах вона частіше за все використовується для вироблення впливу на продуктивність,що здійснюється або коштами інформаційної техніки, або людиною. Якщо процес обробки формалізуємо, він може виконуватися технічними засобами. У сучасних складних системах ці функції покладаються на ЕОМ і мікропроцесори. Якщо процес обробки не піддається формалізації і вимагає творчого підходу, обробка інформації здійснюється людиною. У системах управління найважливішою метою обробки є рішення задачі вибору керуючих впливів (етап прийняття рішення).
Етап відображення інформації повинен передувати етапам, пов'язаним з участю людини, надати людині потрібну йому інформацію за допомогою пристроїв, здатних впливати на його органи почуттів.На етапі такого впливу, інформація використовується для здійснення необхідних змін в системі.
Діяльність людини пов'язана з обробкою матеріалів, енергії та інформації. Відповідно розвиваються науково-технічні дисципліни, що розв'язують питання технології, енергетики, інформатики. Теорія інформації і інформаційна техніка ще порівнянно молоді галузі які отримали поштовх до розвитку з появою електорнно-обчислювальних машин, електорнних систем передачі інформації і систем автоматизованого керування. Тому центральне місце в теорії інформації займає створена Шеноном теорія зв'язку.
З розвитком технологій і суспільства в 20 столітті сталался важлива для інформаційних систем переоцінка цінностей – різко зросла вартість продукту, на який до цього майже не звертали уваги – інформації, інформація стала одним з засобів виробництва. Тому була переглянута і структура інформаційних систем .
Найвразливішим місцем в інформаційній системі є канал зв'язку – на нього впливають непередбачувані природні події і до нього мають доступ сторонні особи. В результаті інформація може бути пошкоджена або до неї отримують доступ люди, що немають на це повноважень. Можливі збитки від подібних ситуацій виправдовують встановлення засобів захисту інформації – систем завадостійкого кодування і шифрування.
В наш час, коли відбувається бурхливий розвиток інформаційних систем, надзвичайно гостро постала проблема передавання інформації по каналам зв'язку, і тепер ця проблема є актуальною не лише з академічної точки зору, адже все більше і більше ПК оснащюються модемами для обміну інформацією на відстані, все більше абонентів підключаються до всесвітньої мережі Internet, і вже не лише державні установи та великі корпорації, але й малі підприємства об'єднують свої комп'ютери в мережі. Відповідно до цього постійно збільшується кількість інформації що передається по каналам зв'язку. Зрозуміло, ростуть вимоги й до інформаційних систем.
Ідеалом такої ІC є :
1. Якнайвища швидкість передачи даних
2. Абсолютна надійність передачі ( гарантія цілісності даних)
3. Гарантія секретності інформації
4. Низька вартість передачі даних
Проблема стискання та кодування інформації з’явилась набагато раніше ніж, власне, термін “інформація”. Згадаємо, що принаймні за часів Римсокої імперії армія використовувала метод шифрування повідомлень з метою її захисту від ворогів. Так званий шифр Цезаря став першим з відомих на сьогодні методів шифрування з таємним ключом. Іншим прикладом кодування є писемність, яка виникла так давно, що точних даних про конкретний час її появи не існує і, мабуть, ніколи не буде знайдено.
В другій половині ХХ-го століття з винайденням та розвитком ЕОМ проблема стискання та кодування привернула до себе увагу, бо з чисто теоретичної перетворилася в прикладну та вкрай необхідну. Стрімко зросли обсяги даних, з’явилась потреба в передачі дискретної інформації на далекі відстані з достатньою надійністю, проблема захисту такої інформації від несанкціанованого доступу і т. д. З розвитком комп’ютерних мереж (зокрема, INTERNET) обсяг інформації, що передається, швидко зростає і вимагає її мінімізації шляхом специфічного кодування для підтримання швидкодії мережі. Можна навести багато інших застосувань кодування інформації.
Арифметичне кодування є одним з перспективних методів стиску інформації, та, в деякому розумінні, її шифрування. Це кодування дозволяє пакувати символи вхідного алфавіту за умови, що розподіл частот цих символів відомий. Концепція методу була розроблена Еліасом в 60-х роках. Після цього метод був суттєво розвинутий та вдосконалений. Арифметичне кодування є оптимальним, досягає теоретичної границі ступеня стиску, - ентропії вхідного потоку.
2.Аналіз методів стиснення інформації
2.1. Кодування Хафмана
Один із класичних алгоритмів, відомих з 60-х років. Зіставляє символам вхідного потоку, що зустрічаються більше число раз, ланцюжок біт меншої довжини. І, навпроти, що зустрічається рідко — ланцюжок більшої довжини. Для збору статистики вимагає двох проходів по зображенню.
Для початку введемо несколько визначень.
Визначення. Нехай завдань алфавіт ? ={a1, ..., ar}, що складається з кінцевого числа букв. Кінцеву послідовність символів з ?
будемо називати словом в алфавіті ? , а число n — довжиною слова A. Довжина слова позначається як l(A).
Нехай завдань алфавіт ? , ? ={b1, ..., bq}. Через B позначимо слово в алфавіті ? і через S(? ) — безліч усіх непорожніх слів в алфавіті ? .
Нехай S=S(? ) — безліч усіх непорожніх слів в алфавіті ? , і S' — деяка підмножина безлічі S. Нехай також задане відображення F, що шкірному слову A, A? S(? ), ставити у відповідність слово
B=F(A), B? S(? ).
Слово В будемо назвати кодом повідомлення A, а перехід від слова A до його коду — кодуванням.
Визначення. Розглянемо відповідність між буквами алфавіту ? і деякими словами алфавіту ? :
a1 — B1, a2 — B2, . . . ar — Br
Цю відповідність називають схемою і позначають через ? . Воно визначає кодування в такий спосіб: шкірному слову из S'(? )=S(? ) ставитися у відповідність слово , називане кодом слова A. Слова B1 ... Br називаються елементарними кодами. Даний вид кодування називають алфавітним кодуванням.
Визначення. Нехай слово В має вид
B=B' B"
Тоді слово B'называется чи початком префіксом слова B, а B" — кінцем слова B. При этом порожнє слово ? і саме слово B вважаються початками і кінцями слова B.
Визначення. Схема ?має властивість префікса, якщо для будь-яких iи j(1?i, j? r, i? j) слово Bi не є префіксом слова Bj.
Теорема 1. Якщо схема ?має властивість префікса, то алфавітне кодування буде взаємно однозначним.
Припустимо, що задано алфавіт ? ={a1,..., ar} (r>1) і набір імовірностей p1, . . . , pr появи символів a1,..., ar. Нехай, далі, завдань алфавіт ? , ? ={b1, ..., bq} (q>1). Тоді можна побудувати цілий ряд схем ? алфавітного кодування
a1 — B1, . . . ar — Br
що володіють властивістю взаємної однозначності.
Для кожної схеми можна ввести середню довжину lср, обумовлену як математичне чекання довжини елементарного коду: — довжини слів.
Довжина lср показує, у скількох разів збільшується середня довжина слова при кодуванні зі схемою ? .
Можна показати, що lср досягає величини свого мінімуму l* на деякої ?і визначена як
Визначення. Коди, обумовлені схемою ? с lср= l*, називаються кодами з мінімальною надмірністю, чи кодами Хаффмана.
Коди з мінімальною надмірністю дають у середньому мінімальне збільшення довжин слів при відповідному кодуванні.
У нашому випадку, алфавіт ? ={a1,..., ar} задає символи вхідного потоку, а алфавіт ? ={0,1}, тобто складається усього з нуля й одиниці.
Алгоритм побудови схеми ? можна представити в такий спосіб:
Крок 1. Упорядковуємо всі букви вхідного алфавіту в порядку убування імовірності. Вважаємо усі відповідні слова Bi з алфавіту ? ={0,1} порожніми.
Крок 2. Поєднуємо два символи air-1 і air з найменшими імовірностями pi r-1 і pi r у псевдосимвол а'{air-1 air} c імовірністю pir-1+pir. Дописываем 0 у початок слова Bir-1 (Bir-1=0Bir-1), і 1 у початок слова Bir (Bir=1Bir).
Крок 3. Удаляем зі списку упорядкованих символів air-1 і air, заносимо туди псевдосимвол а'{air-1air}. Проведено крок 2, додаючи при необхідності 1 чи нуль для всіх слів Bi, що відповідають псевдосимволам, доти, поки в списку не запозбавитися 1 псевдосимвол.
Приклад: Нехай у нас є 4 букви в алфавіті ? ={a1,..., a4} (r=4), p1=0.5, p2=0.24, p3=0.15, p4=0.11. . Тоді процес побудови схеми можна представити так:
Роблячи дії, що відповідають 2-му кроку, мі одержуємо псевдосимвол з імовірністю 0.26 (і приписуємо 0 і 1 відповідним словам). Повторюючи ж ці дії для зміненого списку, мі одержуємо псевдосимвол з імовірністю 0.5. И, нарешті, на останньому етапі мі одержуємо сумарну імовірність 1.
Для того, щоб відновити слова, що кодують, нам треба пройти по від від початкових символів до кінця бінарного дерева, що вийшло. Так, для символу з імовірністю p4, одержиме B4=101, для p3 одержимо B3=100, для p2 одержимо B2=11, для p1 одержимо B1=0. Що означає схему:
a1 — 0, a2 — 11 a3 — 100 a4 — 101
Ця схема являє собою префиксный код, що є кодом Хаффмана. Самий часто зустрічається в потоці символ a1 мі будемо кодувати самим коротким словом 0, а самий рідко зустрічається a4 довгим словом 101.
Для послідовності з 100 символів, у якій символ a1 зустрінеться 50 разів, символ a2 — 24 рази, символ a3 — 15 разів, а символ a4 — 11 разів, даний код дозволити одержати послідовність з 176 біт (). Т.е. у середньому мі витратимо 1.76 бита на символ потока.
2.2.Кодування Шеннона-Фано
Як відмічалося, в більшості випадків знаки повідомлень перетворюються в послідовності двійкових символів. У розглянутих пристроях це перетворення виконувалося без урахування статистичних характеристик поступаючих повідомлень.
Враховуючи статистичні властивості джерела повідомлення, можна мінімізувати середнє число символів, що вимагаються для вираження одного знаку повідомлення, що при відсутності шуму дозволяє зменшити час передачі або об'єм запам'ятовуючого пристрою.
Основна теорема Шеннона про кодування для каналу без перешкод. Ефективне кодування повідомлень для передачі їх по дискретному каналу без перешкод базується на теоремі Шеннона, яку можна сформулювати так:
1. При будь-якій продуктивності джерела повідомлень, меншій пропускній спроможності каналу, існує спосіб кодування, що дозволяє передавати по каналу всі повідомлення, що виробляються джерелом.
2. Не існує способу кодування, що забезпечує передачу повідомлень без їх необмеженого накопичення.
У основі доказу лежить ідея можливості підвищення швидкості передачі інформації по каналу, якщо при кодуванні послідовності символів ставити у відповідність не окремим знакам, а їх послідовностям такої довжини, при якій справедлива теорема об їх асимптотичній ймовірності. Зазначимо, що обмежуючись кодуванням типових. послідовностей, імовірності яких рівні, ми забезпечуємо рівномірне і незалежне надходження символів на вхід каналу, що відповідає повному усуненню надмірності в повідомленні, що передається.
Справедливість другої частини теореми, вказуючої на неможливість здійснення передачі виходить з визначення пропускної спроможності каналу як максимально досяжної швидкості передачі інформації, взятої по всій множині джерел заданого класу. Тому якщо пропускна спроможність каналу менше продуктивності джерела, то неминуче накопичення повідомлень на передаючій стороні.
Теорема Шеннона часто приводиться і в іншому формулюванні:
повідомлення джерела з ентропією завжди можна закодувати послідовностями символів з об'ємом алфавіта т так, що середнє число символів на знак повідомлення буде як бажано близько до величини Н(Z)/logm, але не менше за її.
Дане твердження влаштовується також вказівкою на можливу процедуру кодування, при якій забезпечується рівномірне і незалежне надходження символів на вхід каналу, а отже, і максимальна кількість переносимої кожним з них інформації, рівне log m. Як ми встановили раніше, в загальному випадку це можливе, якщо кодувати повідомлення довгими блоками. Вказаний кордон досягається асимптотично, при безмежному збільшенні довжини блоків, що кодуються.
Теорема не вказує конкретного способу кодування, але з неї слідує, що при виборі кожного символа кодової комбінації необхідно старатися, щоб він ніс максимальну інформацію.Отже, кожний символ повинен приймати значення 0 і 1 по можливості з рівними імовірностями і кожний вибір повинен бути незалежний від значень попередніх символів.Для випадку відсутності статистичного взаємозв'язку між знаками конструктивні методи побудови ефективних кодів були дані уперше американськими вченими Шенноном і Фано. Їх методики істотно розрізнюються і тому відповідний код отримав звання коду Шеннона Фано.
Код будують таким чином: знаки алфавіта спілкування виписують в таблицю в порядку убування імовірностей. Потім їх розділяють на дві групи так, Щоб суми імовірностей в кожній з груп були можливості однакові. Всім знакам верхньої половини як перший символ приписують 0, а всім нижнім 1. Кожну з отриманих груп, в свою чергу, розбивають на дві підгрупи з однаковими сумарними імовірностями і т. д. Процесс повторюється доти, поки в кожній підгрупі залишиться по одному знаку. З теореми Шеннона слідує, що цю надмірність також можна усунути, якщо перейти до кодування досить великими блоками.
Потрібно підкреслити, що збільшення ефективності кодування при укрупненні блоків не пов'язане з урахуванням все більш далеких статистичних зв'язків, оскільки нами розглядалися алфавіти з некоррельованими знаками. Підвищення ефективності визначається лише тим, що набір імовірностей, що виходять при укрупненні блоків, можна ділити на більш близькі по сумарних імовірностях підгрупи.
Розглянута методика Шеннона - Фано не завжди приводить до однозначної побудови коду. Адже при разбитті на підгрупи можна зробити більшою по імовірності як верхню, так і нижню підгрупи. Від вказаного недоліку вільна методика Хаф-фмена. Вона гарантує однозначну побудову коду з найменшим для даного розподілу імовірностей середнім числом символів на букву.
Розглянувши методики побудови ефективних кодів,
неважко пересвідчитися в тому, що ефект досягається завдяки привласненню більш коротких кодових комбинацій більш вірогідним знакам і більш довгих менш вірогідним знакам. Таким чином, ефект пов'язаний з відмінністю в числі символів кодових комбінацій.
А це приводить до труднощів при декодування. Звичайно але, для розрізнення кодових комбінацій можна ставити спеціальний розділовий символ, але при цьому , значно знижується ефект, якого ми домагалися, оскільки середня довжина кодової комбінації по суті збільшується на символ.
I більш доцільно забезпечити однозначне декодування без введення додаткових символів. Для цього ефективний код необхідно будувати так, щоб ні I одна комбінація коду не співпадала з початком більш довгої комбінації. Коди, що задовольняють цю умову, називають префіксними кодами.
Як ми вже бачимо в більшості випадках повідомлення – це послідовності двійкових символів. В побудованій інформаційній системі перетворення відбувається без врахування статистичних характеристик вхідних повідомлень.
Враховуючі статистичні властивості джерела сигналу, можливо мінімізувати середню кількість двійкових символів необхідних для зображення дного символа з вхідного алфавіту, що при відсутності завад дозволяє зменшити час передачі або об’єм запам’ятовуючого пристрою.
Таке оптимальне кодування базується на на основній теоремі Шенона для каналів без завад.
Шенон довів, що повідомлення, складене з символів деякого алфавіту, можна закодувати так, що середня кількість двійкових символів на букву буде як завгодно близька до ентропії джерела повідомлення, але не менша за неї.
Основна проблема в тому, що теорема не описує конкретний спосіб кодування, але з неї випливає, що при виборі кожного символа кодової комбінації необхідно старатисящоб він ніс максимальну інформацію. Тому кожний символ повинен приймати значення 0 і 1 по можливості з рівними імовірностями і кожен вибір по можливості повинен бути незалежним від значення попередніх символів.
Для випадку відсутності статистичного зв’язку між буквами конструктивні методи побудови ефективних кодів вперше були запропоновані Шенноном і Фано. Їх методики майже не відрізняються і тому відповідний код отримав назву Кода Шеннона-Фано.
Код будується наступним чином: букви алфавіта повідомлення записуються в таблицю в порядку зменшення імовірності . Далі вони розділяються на дві групи так, щоб суми імовірностей кожної групи були по можливості однакові. Всім буквам верхньої половини в якості першого символа приписується 0, а всім нижнім – 1.Кожна з отриманих груп в свою чергу розбивається на дві підгрупи з однаковими сумарними імовірностями і т.д. Процес продовжується доти, поки в кожній підгрупі не залишиться по одному символу.
Розглянута методика не завжди призводить до однозначної побудови коду. Адже при розбитті на підгрупи можна зробити більшою за імовірністю як верхню, так і нижню підгрупи. Від цього недоліка вільна методика Хаффмена. Вона гарантує однозначну побудову коду з найменшим можливим для данного розподілу імовірностей середнім числом символів на букву.
Для двійкового коду методика зводиться до наступного : букви повідомлення виписуються в основний стовбець в порядку зменшення імовірності. Дві останні букви об’єднують в одну допоміжну, якій приписують сумарну імовірність. Імовірності букв що не брали участь в об’єднанні і отримана сумарна імовірність розміщаються в порядку зменшення імовірності в додатковому стовпці, а дві останні об’єднуються. Так продовжується до тих пір, доки не отримуємо єдину допоміжну букву з імовірністю рівною одиниці.
Для побудови кодової комбінації необхідно прослідкувати шлях переходу повідомлення по стовпцям таблиці. Для наглядності будується кодове дерево. З точки, що відповідає імовірності в 1, направляються дві гілки, причому гілці з більшою імовірністю присваюється символ 1. Таке послідовне розгалуження продовжується поки не дійдемо до імовірностей окремих букв. Далі рухаючись по кодовому дереву зверху вниз можно записати для кожної букви відповідний код.
Розглянувши методику побудови ефективних кодів неважко побачити, що ефект досягається за рахунок присвоєння більш коротких кодових комбінацій символам з більшою імовірністю. Це призводить до проблем при декодуванні, звичайно можна ставити спеціальни символ розділювач, але це знижує ефект через зростання довжини комбінації.
Більш доцільно забезпечити забезпечити однозначне декодування без введення додаткових символів. Для цього ефективний код треба будувати так, щоб жодна комбінація кода не співпала з початком довшої комбінації. Коди які задовільняють цій умові називаються префіксними кодами.Наприклад:
01 101 100
Z1 Z2 Z3
буде декодуватися однозначно. Неважко переконатися, що коди отримані за методиками Шеннона-Фано і Хаффмана є префіксними.
2.3.Кодування LZW
Відомі методи оптимального кодування різнозначними кодами (кодами різної довжини), які базуються на врахуванні різної частоти символів в тексті. Найбільш відомі з них: метод Шеннона-Фано та метод Хаффмана. Ці методи забезпечують достатньо ефективне стиснення без втрат. Для підвищення рівня стиснення даних доцільно перейти від оптимального кодування окремих символів до кодування буквосполучень. Саме таке кодування забезпечує метод LZW.
Метод базується на побудові таблиці фраз (словника), яка відображає стрічки символів повідомлення, що стискається, в коди фіксованої довжини (12 біт). Таблиця має властивість попередництва, тобто для кожної фрази словника, яка складається з деякої фрази w і символа K, фраза w теж міститься в словнику і представляється відповідним номером n.
Словником в даному алгоритмі є потенційно нескінчений список фраз. І кодер, і декодер починають роботу з майже пустого словника, що містить тільки один закодований рядок – NULL-рядок. Коли кодер прочитує черговий сиавол повідомлення, символ додається до поточного рядка. Процес продовжується доти, поки поточний рядок відповідає якій-небудь фразі з словника. Але рано чи піздно поточний рядок перестає відповідати якій-небудь фрзі словника. У цей момент, коли поточний рядок являє собою останній збіг з словником плюс щойно прочитаний символ повідомлення, кодер видає код, що складається з індексу збігу і наступного за ним символа, що порушив збіг рядків. Крім того, нова фраза, що складається з індексу збігу і наступного за ним символа, додається у словник. У наступний раз, коли ця фраза з‘явиться у повідомленні, вона може бути використана для побудови більш довгої фрази, що підвищує міру стиснення інформації. LZW побудований навколо таблиці фраз (словника), яка відображає рядки символів стиснуваного повідомлення в коди фіксованої довжини. Таблиця володіє так званою властивістю передування, тобто для кожної фрази словника, що складається з деякої фрази w і символа К фраза w також міститься в словнику. Якщо всі частинки словника повністю заповнені, кодування перестає бути адаптивним (кодування відбувається виходячи з вже існуючих у словнику фраз).
Кодер LZW ніколи не видає самі символи повідомлення, що стискається – тільки коди фраз.
Алгоритми групи LZ (які послужили основою для алгоритму LZW) мають істотний недолік. Оскільки вони використовують в якості словника тільки невеликий фрагмент повідомлення, тобто немає можливості кодувати підстрічки, що повторюються, відстань між якими в повідомленні більша, ніж розміп словника. Крім того, алгоритми обмежують розмір підстрічки, яку можна закодувати. Очевидно, що вказані чинники знижують ефективність кодування.
Чисто механічний підхід до поліпшення характеристик кодера LZ за рахунок збільшення розмірів словника звичайно дає зворотні бажані результати і теоретично більш потужний кодер стає практично неможливо використати.
Алгоритм кодера LZW можна описати таким чином:
Проініціалізувати словник односимвольними фразами, відповідними символам вхідного алфавіта (256 ASCII символів). Прочитати перший символ повідомлення в поточну фразу W.
Крок алгоритму;
Прочитати черговий символ повідомлення К;
Якщо КІНЕЦЬ_ПОВІДОМЛЕННЯ;
Видати код W;
Вихід;
Кінець Якщо;
Якщо фраза WК вже є в словнику
Замінити W на код фрази WК;
Повторити Крок алгоритму
Інакше
Видати код W;
Додати WК у словник;
Повторити Крок алгоритму;
Кінець Якщо;
Роботу кодера LZW продемонструємо на прикладі такої послідовності символів: мамамиларамурамамиламаму. Результат роботи приведений в таблиці.
Код
Фраза
Символ, що порушив збіг
Словник

1
м

м

2
а

а

3
и

и

4
л

л

5
р

р

6
у

у

7
ма
а
1а

8
ам
м
2м

9
мам
м
7м

10
ми
и
1и

11
ил
л
3л

12
ла
а
4а

13
ар
р
2р

14
ра
а
5а

15
аму
у
8у

16
ур
р
6р

17
рам
м
14м

18
мами
и
9и

19
ила
а
11а

20
ама
а
8а


В результаті код заданої стрічки має вигляд:
1 2 7 1 3 4 2 5 8 6 14 9 11 8 15.
Описаний алгоритм не намагається оптимально вибирати фрази для додавання в словник або розбирати повідомлення. Однак в силу його простоти він може бути ефективно реалізований.
Очевидно, що декодер LZW використовує той же словник, що і кодер, будуючи його за аналогічними правилами при відновленні стиснутого повідомлення. Кожний код, що зчитується розбивається за допомогою словника на попередню фразу W і символ К. Потім рекурсія продовжується для попередньої фрази доти, поки вона не стане кодом одного символа, що і завершує декомпресію цього коду. Оновлення словника відбувається для кожного коду, що декодується, крім першого. Після завершення декодування коду його останній символ, сполучений з попередньою фразою, додається у словник. Нова фраза набуває того ж значення коду, що привласнив її кодер. Так крок за кроком декодер відновлює той словник, який побудував кодер.
Алгоритм декодування LZW може бути описаний наступним чином:
КОД = Прочитати перший код повідомлення ();
Попередній КОД = КОД;
Видати символ К, у якого код (К) = КОД;
Наступний код:
КОД = Прочитати черговий код повідомлення ();
Вхідний Код = КОД;
Якщо КІНЕЦЬ_ПОВІДОМЛЕННЯ
ВИХІД:
Кінець Якщо;
Наступний символ;
Якщо КОД = код (WК)
Видати К;
КОД = код(W);
Повторити наступний символ
Інакше якщо КОД = код(К)
Видати К;
Додати у словник (Попередній КОД, К);
Попередній КОД = Вхідний Код;
Повторити наступний код;
Кінець Якщо.
У цьому алгоритмі є два істотних недоліки. По-перше, він видає символи в зворотньому порядку, по-друге, він не буде працювати у вийнятковій ситуації.
Змінити порядок видачі розкодованих символів нескладно, для цього досить використати стандартний LIFO стек.
Обробка вийняткової ситуації дещо складніша. Виняткова ситуація виникає тоді, коли кодер намагається закодувати повідомлення КWКWК, де фраза КW вже присутня в словнику. Кодур виділить КW, видасть код КW і внесе КW в словник. Потім він виділить КWК і пошле щойно створений код КWК. Декодер при отриманні коду КWК ще не додав цей код до словника, тому що не знає символ розширення попередньої фрази. Проте, коли декодер зустрічає невідомий йому код, він може визначити, який символ видавати першим. Це символ розширення попередньої фрази; він був останнім розкодованим символом і буде останнім символом поточної фрази.
Модифікований алгоритм декодування виглядає наступним чином:
Код = прочитати перший код повідомлення();
Попердній код = код;
Видати символ К, у якого код(К) = код;
останнійСимвол = К;
наступний Код:
код = Прочитати черговий код повідомлення();
вхідний код = код;
якщо кінець повідомлення
вихід:
кінець якщо;
якщо невідомий(код) // обробка помилкової ситуації
видати (останній символ);
код = попередній код;
вхідний код = код (попередній код, останній символ);
кінець якщо;
наступний символ:
якщо код = код(КW)
у_стек(К);
код = код(W);
повторити наступний символ;
інакше якщо код = код (К);
видати К;
останній символ = К;
поки стек не пустий
видати (із_стека( ) );
кінець поки;
додати в словник (попередній код, К);
попердній код = вхідний код;
повторити наступний код;
кінець.
Метод LZW являється методом арифметичного кодування і приклад розробки та реалізації стиснення даних методом LZW наведено у додатку 1.
3. Ідея арифметичного кодування.
При арифметичному кодуванні текст представляється числами з плаваючою комою в інтервалі від 0 до 1. В процесі кодування тексту інтервал, що його відображає – зменшується, а кількість бітів для його представлення збільшується. Наступні символи тексту зменшують величину інтервала, виходячи з значень їх ймовірностей, які визначаються моделлю. Більш ймовірні символи роблять це в меншій мірі ніж менш ймовірні та, таким чином, додають менше бітів до результату.
Перед початком роботи відповідний до тексту інтервал є [0 ; 1). При обробці наступного символу його ширина звужується за рахунок виділення цьому символу частини інтервалу. Наприклад, застосуемо до тексту “еаіі!” алфавіта {а, е, і, о, u, ! } модель з постійними ймовірностями, що задані в таблиці 1.
Таблиця 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). Працюючи в такий спосіб, декодувальник витягує весь текст.
Декодувальник не має потреби знати значення обох меж підсумкового інтервалу, який був одержаний від кодувальника. Навіть одного значення, що лежить всередині нього, наприклад, 0,23355 вже достатньо. (Інші числа – 0,23354, 0,23357 та навіть 0,23354321 – цілком придатні). Однак, щоб завершити процес, декодувальнику потрібно своєчасно розпізнати кінець тексту. Крім того, одне й те саме число 0,0 можна представити і як “а”, і як “аа”, і як “ааа” і т. д. Для усунення непорозуміння ми повинні позначати завершення кожного тексту спеціальним символом EOF, що відомий і кодувальнику, і декодувальнику. Для алфавіту з таблиці 1 з цією метою, і тільки з нею, буде використовуватися символ “!”. Коли декодувальник зустрічає цей символ, то він завершує свій процес.
Для фіксованої моделі, яка задається моделлю таблиці 1, ентропія 5-ти символьного тексту “еаіі!” буде –log 0,3 – log 0,2 – log 0,1 – log 0,1 – log 0,1 = – log 0,00006 ( 4,22. (Тут застосовуємо логариф з основою 10, бо вищенаведене кодування виконувалося для десяткових чисел). Це пояснює, чому потрібно 5 десяткових цифр для кодування цього тексту. Таким чином, ширина підсумкового інтервалу є 0,2336 – 0, 23354 = 0,00006, а ентропія – від’ємний десятковий логарифм цього числа. Звичайно ми працюємо з двійковою арифметикою, передаємо двійкові числа та вимірюємо ентропію в бітах.
П’яти десяткових цифр здається забагато для кодування тексту з чотирьох голосних! Мабуть не зовсім вдало бу закінчувати приклад розгортанням, а не зтисканням. Однак зрозуміло, що різні моделі дають різну ентропію. Краща модель, побудована на аналізі окремих символів тексту “еаіі!”, є така множина частот символів: {“е” (0,2), “а” (0,2), “і” (0,4), “!” (0,2) }. Вона дає ентропію, що дорівнює 2,89 в десятковій системі відліку, тобто кодує вихідний текст числом з трьох цифр. Однак, більш складні моделі, як відмічалося раніше, дають в загальному випадку набагато кращій результат.

4. Ефективність стискання.
Взагалі, при кодуванні тексту аріфметичним методом, кількість бітів в закодованому рядку дорівнює ентропії цього тексту відносно використаної для кодування моделі. Три чинника викликають погіршення цієї характеристики: видатки на завершення тексту; використання арифметики з кінцевою точністю; таке масштабування лічильників, що їх сума не перевищує Max_frequency.
Як було показано, жоден з них не є значним. В порядку виділення результатів арифметичного кодування, модель буде розглядатися як сувора (в визначеному вище сенсі).
Арифметичне кодування повинне досилати додаткові біти в кінець кожного тексту, здійснюючи таким чином додаткові зусилля на завершення тексту. Для ліквідації непорозуміння з останнім символом процедура done_encoding () посилає два біти. В випадку, коли перед кодуванням поток бітів має блокуватися в 8-бітові символи, буде необхідно завершувати до кінця блоку. Таке комбінування може додатково потрібувати 9 бітів.
Видатки при використанні арифметики з обмеженою точністю проявляються в зменшені залишків при діленні. Це видно при порівнянні з теоретичною ентропією, яка виводить частоти із лічильників, які таким саме чином масштабуються при кодуванні. Тут видатки незначні – порядку 10^-4 бітів / символ. Додаткові видатки на масштабування лічильників дещо більші, але все одно досить малі. Для коротких текстів (менших 2^14 байт) їх немає. Але навіть з текстами в 10^5 – 10^6 байтів накладні видатки, підраховані експериментально, складають менше 0,25% від рядка, шо кодується.
Адаптивна модель в програмі, при загрозі перевищення загальною сумою накопичених частот значення Max_frequency, зменшує всі лічильники. Це призводить до того, що зважувати останні події важче, ніж більш ранні. Таким чином, показники мають тенденцію прослідковувати зміни у вхідній послідовності, які модуть бути дуже корисними (відомі випадки, коли обмеження лічильників до 6-7 бітів давало кращі результати, ніж підвищення точності арифметики). Звичайно, це залежить від джерела, до якого застосовується модель.
5. Застосування арифметичного кодування.
5.1 Кодування чорно – білих зображень.
Застосування з цією метою арифметичного кодування розглядалося Лангдоном та Риссаненом, що отримали при цьому чудові результати за допомогою моделі, що використовує оцінку ймовірності колбору точки відносно деякого шаблону, що її оточує. Він являє собою сукупність з 10 точок, що лежать зверху та спереду від поточної, тому при скануванні растру вони їй передують. Це дає 1024 можливих контексту, відносно яких, ймовірність чорного коліру в даній точці оцінюється адаптивно по мірі перегляду зображення. Після чого кожна полярність точки кодувалася арифметичним методом відповідно з цією ймовірністю. Такий підхід покращив стискання на 20 – 30% порівняно з більш ранніми методами. Для збільшення швидкості кодування Лангдон та Риссанен застосували приблизний метод арифметичного кодування, який обійшов операції множення шляхом представлення ймовірностей в вигляді цілих ступенів дробу 1/2/. Кодування Хаффмана для цього випадку не може бути використано напряму, оскільки воно ніколи не виконує стиснення двохсимвольного алфавіту. Іншу можливість для арифметичного кодування, що застосовується для такого алфавіту, дає популярний метод кодування довжин тиражів (run-length method). Модель тут приводить дані до послідовності довжин серій однакових символів (наприклад, зображення представляється довжинами послідовностей чорних точок, які йдуть за білими, які слідують за чорними, яким передують білим і т. д.). в результаті повинна бути передана послідовність довжин. Стандарт факсимільних апаратів ССІТТ будує код Хаффмана на основі частот, з якими чорні і білі послідовності різних довжин з’являються в зразках документів. Фіксоване арифметичне кодування, яке буде використовувати ті ж самі частоти, буде мати кращі характеристики, а адаптація таких частот для кожного окремого документу буде працювати ще краще.
5.2 Кодування довільно розподілених цілих чисел.
Воно часто розглядається на основі застосування більш складних моделей текстів, зображеняь або інших даних. Розглянемо, наприклад, локально адаптовану схему стискання Бентлі та ін., де кодування та декодування працює з N останніми різними словами. Слово, що знаходиться в кеш-буфері, визначається по цілочисельному індексу буфера. Слово, яке в ньому не знаходиться, передається в кеш-буфер через пересилання його маркера, який йде наступним за самими символами цього слова. Це чудова модель для тексту, в якому слова часто використовуються на протязі деякого короткого часу, а потім вже довго не використовуються. Їх стаття обговорює декілька кодувань змінної довжени вже для цілочисельних індексів кеш-буфера. В якості основи для кодів змінної довжини аріфметичний метод дозволяє використовувати будь-яке розподілення ймовірностей, в тому числі серед багатьох інших й ті, які навадені тут. Крім того, він допускає для індексів кеш-буфера застосування адаптивної моделі, що є бажаним у випадку, коли розподілення доступів до кеш-буферу важкопередбачуване.
Додаток 1
#include <stdio.h>
#include <string.h>
typedef struct dic
{
int c;
int dc;
char ch;
} dic;
int is_sym_in_dic(char ch, dic *d,int n);
int c_code(dic *d,int code,char ch,int n);
void decode(dic *d,int code,char *buff,int *i);
int main(int arg,char ** argv)
{
FILE *fin,*fdic,*fc,*fdc;
char file_name[100];
int n=0,i,code,z;
char b[10000];
char temp;
dic d[10000];
if(arg>1)
{
strcpy(file_name,argv[1]);
printf("Input file:%s",file_name);
}
else
{
printf("\nVvedit filename to code:");
scanf("%s",file_name);
}
fin=fopen(file_name,"r");
fdic=fopen("dic.txt","w");
fc=fopen("code.txt","wb");
fdc=fopen("decode.txt","w");
fscanf(fin,"%c",&temp);
d[0].ch=temp;
d[0].c=n+1;
d[0].dc=0;
while(!feof(fin))
{
fscanf(fin,"%c",&temp);
if (is_sym_in_dic(temp,d,n))
{
n++;
d[n].ch=temp;
d[n].c=n+1;
d[n].dc=0;
}
}
fclose(fin);
fin=fopen(file_name,"r");
unsigned int k;
fscanf(fin,"%c",&temp);
while(!feof(fin))
{
code=c_code(d,0,temp,n);
fscanf(fin,"%c",&temp);
while((code=c_code(d,k=code,temp,n)) && !feof(fin))
fscanf(fin,"%c",&temp);
if(!code)
{
n++;
d[n].ch=temp;
d[n].c=n+1;
d[n].dc=k;
if(!feof(fin))
fwrite(&k,sizeof(unsigned int),1,fc);
else
fwrite(&k,sizeof(unsigned int),1,fc);
}
}
for(i=0;i<n;i++)
fprintf(fdic,"%d - %d:%c\n",d[i].c,d[i].dc,d[i].ch);
fclose(fc);
fc=fopen("code.txt","rb");
while(!feof(fc))
{
z=0;
fread(&code,sizeof(unsigned int),1,fc);
decode(d,code,b,&z);
b[z]='\0';
fprintf(fdc,"%s",b);
}
printf("Dictionary in [dic.txt]\nCode in [code.txt]\nDecode text in [dec.txt]\n");
fclose(fin);
fclose(fdc);
fclose(fc);
fclose(fdic);
return 0;
}
int is_sym_in_dic(char ch, dic *d,int n)
{
for(int i=0;i<=n;i++)
if (ch==d[i].ch)
return 0;
return 1;
}
int c_code(dic *d,int code,char ch,int n)
{
for(int i=0;i<=n;i++)
if((d[i].ch==ch) && (d[i].dc==code))
return d[i].c;
return 0;
}
void decode(dic *d,int code,char *buff,int *i)
{
if (d[code-1].dc!=0)
{
*i=*i+1;
decode(d,d[code-1].dc,buff,i);
}
else
*i=0;
buff[*i]=d[code-1].ch;
*i=*i+1;
return;
}