Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Аналіз та реалізація стиснення даних за допомогою алгоритму ADSM
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра систем автоматизованого проектування
Інформація про роботу
Рік:
2008
Тип роботи:
Інші
Предмет:
Методи та засоби комп’ютерних інформаційних технологій
Група:
КН
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра систем автоматизованого проектування
ПОЯСНЮВАЛЬНА ЗАПИСКА
до курсової роботи
з дисципліни “Методи і засоби комп’ютерних інформаційних технологій”
на тему: “Аналіз та реалізація стиснення даних за допомогою алгоритму ADSM”
Допущено до захисту:
Львів 2008
1. Завдання на курсову роботу
Проаналізувати методи стисення даних. Розробити програмну реалізацію методу стиснення даних за допомогою алгоритму ADSM.
2. Анотація
Дана курсова робота складається з 56-х сторінок, містить 6 таблиць та 6 малюнків, один додаток. Для написання курсової роботи були використані матеріали з 4-х літературних джерел.
Метою даної роботи є створення програми стиснення файлів з використанням алгоритму ADSM.
3. Зміст
Завдання на курсову роботу.......................................................................….2
Анотація.........................................................................................................….3
Зміст..............................................................................................................….4
Вступ.............................................................................................................….6
Базова термінологія.....................................................................................….7
Моделювання і ентропія.............................................................................….7
Адаптовані і неадаптовані моделі..............................................................….8
Кодування.....................................................................................................….9
Контекстуальні методи моделювання.......................................................….10
Моделі з фіксованим контекстом........................................................….10
Контекстуально-змішані моделі.........................................................…..11
Ймовірність відходу.............................................................................….12
Виключення...........................................................................................…14
Алфавіти..............................................................................................…...16
Практичні контекстно-обмежені моделі.............................................…16
Реалізація................................................................................................…17
Інші методи статичного моделювання...........................................................18
10.1 Моделі станів............................................................................................18
10.1.1 Динамічне стиснення Маркова………………………………………19
10.2 Граматичні моделі………………………………………………………21
10.3 Моделі новизни…………………………………………………………22
10.4 Моделі для стиснення зображень……………………………………...22
11.Словникові методи…………………………………………………………....22
11.1 Стратегія розбору……………………………………………………….23
11.2 Статичні словникові кодувальники……………………………………24
11.3 Напівадаптоване словникове кодування………………………………24
11.4 Адаптоване словникове кодування: метод Зіва-Лемпела…………….25
11.4.1 LZ77………………………………………………………………...26
11.4.2 LZR……………………………………………………………….…27
11.4.3 LZSS………………………………………………………………...28
11.4.4 LZB………………………………………………………………….28
11.4.5 LZH………………………………………………………………….28
11.4.6 LZ78…………………………………………………………………28
11.4.7 LZW…………………………………………………………………30
11.4.8 LZC………………………………………………………………….30
11.4.9 LZT………………………………………………………………….30
11.4.10 LZMV……………………………………………………………...31
11.4.11 LZJ…………………………………………………………………31
11.4.12 LZFG………………………………………………………….…...31
11.4.13 Структури даних для методу Зіва-Лемпела…………………….32
12.Питання практичної реалізації………………………………………………..32
12.1 Обмеження по пам’яті ..............................................................................32
12.2 Підрахунок...........................................................................................…..33
13.Порівняння..........................................................................................................34
13.1 Характеристики стиснення....................................................................…34
13.2 Вимоги до швидкості і пам’яті..................................................................35
14.Подальші дослідження........................................................................................36
15.Алгоритм стиснення ADSM……………………………………………………40
16.Опис призначення та алгоритму роботи програми…………………………...41
17. Аналіз результатів....................................................................................................42
18. Висновки...................................................................................................................43
19.Список використаної літератури.............................................................................44
20.Додатки......................................................................................................................45
4.Вступ
Стиснення скорочує обсяг простору, необхідного для зберігання файлів в ЕОМ, і кількість часу, необхідного для передачі інформації з каналу встановленої ширини пропущення. Це є форма кодування. Іншими цілями кодування є пошук і виправлення помилок, а також шифрування. Процес пошуку й виправлення помилок протилежний стисненню - він збільшує надмірність даних, коли їх не потрібно представляти в зручній для сприйняття людиною формі. Видаляючи з тексту надмірність, стиснення сприяє шифруванню, що ускладнює пошук шифpу доступним для зломщика статистичним методом.
Необоротне або збиткове стиснення використовується для цифрового запису аналогових сигналів, таких як людська мова або малюнки. Оборотне стиснення особливо важливе для текстів, записаних на природних й на штучних мовах, оскільки в цьому випадку помилки звичайно неприпустимі. Хоча першочерговою областю застосування розглянутих методів є стиснення текстів, що відображає і наша термінологія, однак, ця техніка може знайти застосування й в інших випадках, включаючи оборотне кодування послідовностей дискретних даних.
Існує багато вагомих причин виділяти ресурси ЕОМ з розрахунком на стисле подання, тому що більше швидка передача даних і зменшення простору для їх збереження дозволяють зберегти значні засоби й найчастіше покращити показники ЕОМ. Стиснення ймовірно буде залишатися в сфері уваги через всі зростання обсягів збережених і переданих в ЕОМ даних, крім того його можна використовувати для подолання деяких фізичних обмежень, таких як, наприклад, порівняно низька ширина пропускання телефонних каналів.
Одним із найбільш ранніх і добре відомих методів стиснення є алгоритм Хаффмана, що був і залишається предметом багатьох досліджень. Однак, наприкінці 70-х років завдяки двом важливим переломним ідеям він був витиснутий. Одна полягала у відкритті методу арифметичного кодування , що має схожу з кодуванням Хаффмана функцію, але володіючого декількома важливими властивостями, які дають можливість досягти значної переваги в стисненні. Іншим нововведенням був метод Зіва-Лемпела, що дає ефективне стиснення і застосовуючий підхід, зовсім відмінний від хаффманівського й арифметичного. Обидві ці техніки із часу своєї першої публікації значно вдосконалилися, розвилися й лягли в основу практичних високоефективних алгоритмів.
Існують два основних способи проведення стиснення: статистичний і словниковий. Кращі статистичні методи застосовують арифметичне кодування, кращі словникові - метод Зіва-Лемпела. У статистичному стисненні кожному символу привласнюється код, заснований на ймовірності його появи в тексті. Високоможливі символи одержують короткі коди, і навпаки. У словниковому методі групи послідовних символів або "фраз" замінюються кодом. Замінена фpаза може бути знайдена в деякому "словнику". Тільки останнім часом було показано, що будь-яка практична схема словникового стиснення може бути зведена до відповідної статистичної схеми стиснення, і знайдений загальний алгоритм перетворення словникового методу в статистичний. Тому пpи пошуку кращого стиснення статистичне кодування обіцяє бути найбільш плідним, хоча словникові методи й привабливі своєю швидкістю.
5.Базова термінологія
Стисливі дані називаються по-різному - рядок, файл, текст або введення. Передбачається, що вони виробляються джерелом, що постачає компресор символами, які належать деякому алфавіту. Символами на вході можуть бути букви, літери, слова, крапки, тон сірого кольору або інші подібні одиниці. Стиснення іноді називають кодуванням джерела, оскільки воно намагається видалити надмірність у рядку на основі його передбачуваності. Для конкретного рядка коефіцієнт стиснення є відношення розміру стислого виходу до її первісного розміру. Для його вираження використовуються багато різних одиниць, що ускладнюють порівняння експериментальних результатів. У нашому огляді ми використовуємо біти на символ (біт/символ) - одиницю, незалежну від подання вхідних даних. Інші одиниці - відсоток стиснення, відсоток скорочення й інші коефіцієнти - залежать від подання даних на вході (наприклад 7-або 8-бітовий код ASCII).
6.Моделювання й ентропія
Одним з найбільш важливих досягнень у теорії стиснення за останнє десятиліття з'явилася вперше висловлена ідея поділу пpоцесу на дві частини: на кодувальник, безпосередньо виробляючий стислий потік бітів, і на модератор, що поставляє йому інформацію. Ці дві роздільні частини названі кодуванням і моделюванням. Моделювання привласнює ймовірності символам, а кодування переводить ці ймовірності в послідовність бітів. На жаль, останнє поняття неважко поплутати, оскільки "кодування" часто використовують у широкому змісті для позначення всього процесу стиснення (включаючи моделювання). Існує різниця між поняттям кодування в широкому змісті (весь процес) і у вузькому (виробництво потоку бітів на підставі даної моделі).
Зв'язок між ймовірностями й кодами встановлений в теоремі Шеннона, кодування джерелами, що показує, що символ, очікувана ймовірність появи якого є p найкраще представити -log p бітами(1). Тому символ з високою ймовірністю кодується декількома бітами, тоді як малоймовірний вимагає багатьох бітів. Ми можемо одержати очікувану довжину коду за допомогою усереднення всіх можливих символів, що дається формулою:
p(i) log p(i)
Це значення називається ентропією розподілу ймовірності, тому що це міра кількості порядку (або безладдя) у символах. Завданням моделювання є оцінка ймовірності для кожного символу. Із цих ймовірностей може бути обчислена ентропія. Дуже важливо відзначити, що ентропія є властивість моделі. У даній моделі оцінювана ймовірність символу іноді називається кодовим простором, виділюваним символу, і відповідає розподіленню інтервалу (0,1) між символами, і чим більше ймовірність символу, тим більше такого "простору" відбирається в інших символів.
Найкраща середня довжина коду досягається моделями, у яких оцінки ймовірності як можна більше точні. Точність оцінок залежить від широти використання контекстуальних знань. Наприклад, ймовірність знаходження букви "o" у тексті, про який відомо тільки те, що він англійською мовою, може бути оцінена на підставі того, що у випадково вибраних зразках англійських текстів 6% символів є буквами "o". Це зводиться до коду для "o", довжиною 4.17. Для контрасту, якщо ми маємо фразу "to be or not to be", та оцінка ймовірності появи букви "o" буде становити 99% і її можна закодувати чеpез 0.014 біта. Більшого можна досягти формуючи більше точні моделі тексту.
Модель по суті є набір ймовірностей розподілу, по одному на кожний контекст, на підставі якого символ може бути закодований. Контексти називаються класами умов, тому що вони визначають оцінки ймовірності. Нетривіальна модель може містити тисячі класів умов.
7.Адаптовані й неадаптовані моделі
У поpядку функціональної відповідності декодувальник повинен мати доступ до тієї ж моделі, що й кодувальник. Для досягнення цього є три способи моделювання: статичне, напівадаптоване й адаптоване.
Статичне моделювання використовує для всіх текстів ту саму модель. Вона задається пpи запуску кодувальника, можливо на підставі зразків типу очікуваного тексту. Така ж копія моделі зберігається разом з декодувальником. Недолік полягає в тому, що схема буде давати необмежено погане стиснення щораз, коли кодуючий текст не вписується в обрану модель, тому статичне моделювання використовують тільки тоді, коли важливі в першу чергу швидкість і простота реалізації.
Напівадаптоване моделювання вирішує цю проблему, використовуючи для кожного тексту свою модель, яка будується ще до самого стиснення на підставі результатів попереднього перегляду тексту (або його зразка). Перед тим, як закінчене формування стислого тексту, модель повинна бути пеpедана розкодувальнику. Незважаючи на додаткові витрати по передачі моделі, ця стратегія в загальному випадку окупається завдяки кращій відповідності моделі тексту.
Адаптоване (або динамічне) моделювання йде від пов'язаних із цієї передачі витрат. Спочатку й кодувальник , і розкодувальник привласнюють собі деяку порожню модель, як якби символи всі були рівно ймовірними. Кодувальник використовує цю модель для стиснення наступного символу, а розкодувальник - для його розгортання. Потім вони обоє змінюють свої моделі однаковим чином (наприклад, нарощуючи ймовірність розглянутого символу). Наступний символ кодується й дістається на підставі нової моделі, а потім знову змінює модель. Кодування триває аналогічним розкодуванню чином, яке підтримує ідентичну модель за рахунок застосування такого ж алгоритму її зміни, забезпеченою відсутністю помилок під час кодування. Використовувана модель, яку до того ж не потрібно передавати явно, буде добре відповідати стислому тексту.
Адаптовані моделі пpедставляють собою елегантну й ефективну техніку, і забезпечують стиснення принаймні не гірше вихідного неадаптованими схемами. Воно може бути значно краще, ніж у погано відповідним текстам статичних моделей. Адаптовані моделі, на відміну від напівадаптованих , не роблять їхнього попереднього перегляду, будучи тому більше привабливими й краще стисненими. Тобто алгоритми моделей, описувані в підрозділах, при кодуванні й декодуванні будуть виконаються однаково. Модель ніколи не передається явно, тому збій виникає тільки у випадку недостачі під неї пам'яті.
Важливо, щоб значення ймовірностей, присвоюючих моделлю не були б рівні 0, тому що якщо символи кодуються -log p бітами, то пpи близькості ймовірності до 0, довжина коду прагне до нескінченності. Нульова ймовірність має місце, якщо в прикладі тексту символ не зустрівся ні разу- часто зустрічна ситуація для адаптованих моделей на початковій стадії стиснення. Це відомо як проблема нульової ймовірності, яку можна вирішити декількома способами. Один підхід полягає в тому, щоб додавати 1 до лічильника кожного символу. Альтернативні підходи в основному засновані на ідеї виділення одного лічильника для всіх нових (з нульовою частотою) символів, для наступного використання його значення між ними .
8.Кодування
Завдання заміщення символу з ймовірністю p приблизно -log p бітами називаються кодуванням. Це вузький зміст поняття, а для позначення більше шиpокого будемо використовувати термін "стиснення". Кодувальнику дається безліч значень ймовірностей, що управляє вибором наступного символу. Він робить потік бітів, на основі якого цей символ може бути потім розкодований, якщо використовується той же набір ймовірностей, що й при кодуванні. Ймовірності появи будь-якого конкpетного символу в різних частинах тексту може бути різною.
Добре відомим методом кодування є алгоритм Хаффмана. Однак, він не годиться для адаптованих моделей по двох причинах. По-перше, щораз при зміні моделі необхідно змінювати й весь набір кодів. Хоча ефективні алгоритми роблять це за рахунок невеликих додаткових витрат , їм всеодно потрібно місце для розміщення дерева кодів. Якщо його використовувати в адаптованому кодуванні, то для різних ймовірностей розподілення й відповідних безлічей кодів будуть потрібні свої класи умов для передбачення символу. Оскільки моделі можуть мати їх тисячі, то збереження всіх дерев кодів стає надмірно дорогим. Чітке наближення до кодування Хаффмана може бути досягнуто застосуванням різновиду дерев, що розширюються. Пpи цьому, подання дерева досить компактно, щоб уможливити його застосування в моделях, що мають кілька сотень класів умов.
По-друге, метод Хаффмана неприйнятний в адаптованому кодуванні, оскільки виражає значення -log p цілим числом бітів. Це особливо недоречно, коли один символ має високу ймовірність (що бажано і є частим випадком у складних адаптованих моделях). Найменший код, що може бути зроблений методом Хаффмана має 1 біт у довжину, хоча часто бажано використовувати менший. Наприклад, "o" у контексті "to be or not to be" можна закодувати в 0.014 біта. Код Хаффмана перевищує необхідний вихід в 71 разів, роблячи точне пророкування марним.
Концептуально більше простим і набагато більше привабливим підходом є сучасна техніка, названа арифметичним кодуванням. Найбільш важливими властивостями арифметичного кодування є наступні:
здатність кодування символу ймовірності p кількістю бітів довільно близьким до -log p;
ймовірності символів можуть бути на кожному кроці різними;
дуже незначні вимоги пам'яті незалежно від кількості класів умов у моделі;
більша швидкість.
В арифметичному кодуванні символ може відповідати дробовій кількості вихідних бітів. У нашому прикладі, у випадку появи букви "o" він може додати до нього 0.014 біта. На практиці pезультат повинен, звичайно, бути цілим числом бітів, що відбудеться, якщо кілька послідовних високо ймовірних символів кодувати разом, поки у вихідний потік не можна буде додати 1 біт. Кожний закодований символ вимагає тільки одного цілочисельного множення й декількох додавань, для чого звичайно використовується тільки три 16-бітових внутрішніх регістри. Тому, арифметичне кодування ідеально підходить для адаптованих моделей і його відкриття породило безліч технік, які набагато перевершують ті, що застосовуються разом з кодуванням Хаффмана.
Складність арифметичного кодування полягає в тому, що воно працює з накопичуваною йморівністю розподілу, потребуючої внесення для символів деякої впорядкованості. Відповідному символу накопичується ймовірність, що є сумою ймовірностей всіх символів, що передують йому. Ефективна техніка організації такого розподілу наводиться далі. Далі дається ефективний алгоритм, заснований на двійковій купі для випадку дуже великого алфавіту, другий алгоритм, заснований на деревах, що розширюються, дається також далі. Обоє вони мають приблизно схожі характеристики.
9. Контекстуальні методи моделювання
9.1 Моделі з фіксованим контекстом
Статистичний кодувальник, яким є арифметичний, вимагає оцінки розподілу ймовірності для кожного кодуючого символу. Найлегше присвоїти кожному символу постійну ймовірність, незалежно від його положення в тексті, що створює просту контекстуально-вільну модель. Наприклад, в англійській мові ймовірності символів ".", "e", "t" і "k" звичайно становлять 18%, 10%, 8% і 0.5% відповідно (символ "." використовується для позначення пробілів). Отже в цій моделі дані букви можна закодувати оптимально 2.47, 3.32, 3.64 і 7.62 бітами за допомогою арифметичного кодування. У такій моделі кожний символ буде представлений у середньому 4.5 бітами. Це є значенням ентропії моделі, заснованої на ймовірності розподілення букв в англійському тексті. Ця проста статична контекстуально-вільна модель часто використовується разом з кодуванням Хаффмана.
Ймовірності можна оцінювати адаптивно за допомогою масиву лічильників - по одному на кожний символ. Спочатку всі вони встановлюються в 1 (для запобігання проблеми нульової ймовірності), а після кодування символу значення відповідного лічильника збільшується на одиницю. Аналогічно, пpи декодуванні відповідного символу розкодувальник збільшує значення лічильника. Ймовірність кожного символу визначається його відносною частотою. Ця проста адаптивна модель незмінно застосовується разом з кодуванням Хаффмана.
Більш складний шлях обчислення ймовірностей символів лежить чеpез визначення їхньої залежності від попереднього символу. Наприклад, імовірність проходження за буквою "q" букви "u" становить більше 99%, а без обліку попереднього символу - усього 2.4%(2). З урахуванням контексту символ "u" кодується 0.014 біта й 5.38 біта в протилежному випадку. Ймовірність появи букви "h" становить 31%, якщо поточним символом є "t", і 4.2%, якщо він невідомий, тому в першому випадку вона може бути закодована 1.69 бітами, а в другому - 4.6 бітами. Пpи використанні інформації про попередні символи, середня довжина коду (ентропія) становить 3.6 біта/символ у порівнянні з 4.5 біта/символ у простих моделях.
Цей тип моделей можна узагальнити відносно попередніх символів, використовуваних для визначення ймовірності наступного символу. Це визначає контексно-обмежену модель ступеня o. Перша розглянута нами модель мала ступінь 0, тоді як друга +1, але на практиці звичайно використовують ступінь 4. Модель, де всім символам присвоюється одна ймовірність, іноді позначається як та, що має ступінь, -1, тобто більше примітивна, ніж модель ступеня 0.
Контексно-обмежені моделі незмінно застосовуються адаптивно, оскільки вони мають можливість пристосовуватися до особливостей стисливого тексту. Оцінки ймовірності в цьому випадку являють собою просто лічильники частот, формовані на основі вже переглянутого тексту.
Неправильно думати, що модель більшого ступеня завжди досягає кращого стиснення. Ми повинні вміти оцінювати ймовірності щодо контексту будь-якої довжини, коли кількість ситуацій наростає експонтеціально ступеня моделі. Для обробки більших зразків тексту потрібно багато пам'яті. В адаптивних моделях розмір зразка збільшуються поступово, тому більші контексти стають більше виразними в міру здійснення стиснення. Для оптимального вибору - великого контексту при гарному стисненні й маленькому контексті пpи недостатності зразка - треба застосувати змішану стратегію, де оцінки ймовірностей, зроблені на підставі контекстів різних довжин, поєднуються в одну загальну ймовірність. Існує кілька способів виконувати перемішування.
9.2 Контекстуально-змішані моделі
Змішані стратегії використовуються разом з моделями різного порядку. Один шлях об'єднання оцінок складається в присвоєнні ваги кожної моделі й обчисленню зваженої суми ймовірностей. У якості окремих варіантів цього загального механізму можна розглядати безліч різних схем перемішування.
Нехай p(o,Ф) є ймовірність, привласнена символу Ф вхідного алфавіту A контекстуально-обмеженою моделлю порядку o. Це ймовірність була привласнена адаптивно й буде змінюватися в тексті від місця до місця. Якщо вага, дана моделі порядку o є w(o), а максимально використовуваний порядок є m, то змішані ймовірності p(Ф) будуть обчислюватися по формулі:
m
p(ф) = S w(o) p(о,ф)
о = -1
Сума ваг повинна бути рівна 1. Обчислення ймовірностей і ваг, значення яких часто використовуються, будемо робити за допомогою лічильників, пов'язаних з кожним контекстом. Нехай c(o,Ф) означає кількість появ символу Ф у поточному контексті порядку o. Позначимо через C(o) загальну кількість переглядів контексту. Тоді
C(о) = S C(про,ф)
Ф з А
Простий метод перемішування може бути сконструйований вибором оцінки окремого контексту як
p(o,Ф)=
c(o,Ф)
C(o)
Це означає, що вони будуть дорівнювати нулю для символів, які в цьому контексті ще не зустрічалися. Необхідно, однак, щоб кінцева змішана ймовірність кожного символу була б не рівною нулю. Для забезпечення цього особлива модель порядку -1 оцінює кожний символ з однаковою ймовірністю 1/q, де q - кількість символів у вхідному алфавіті.
Друга проблема полягає в тому, що C(o) буде дорівнює нулю, якщо контекст порядку o до цього ніколи ще не з'являвся. Для моделей ступенів 0,1,2,...,m існує деякий найбільший порядок l<=m, для якого контекст розглядається попередньо. Усе більше короткі контексти також будуть обов'язково розглянуті, оскільки для моделей більш низького порядку вони являють собою підстрічки рядків контекстів моделей більш високого порядку. Присвоєння нульової ваги моделям порядків l+1,...,m гарантує застосування тільки переглянутих контекстів.
9.3 Ймовірність відходу
Тепер розглянемо як вибирати ваги. Один шлях складається в присвоєнні заданої безлічі ваг моделям різних порядків. Іншої, для набуття більшої виразності моделям вищих порядків, - в адаптації ваг у міру виконання стиснення. Однак, жоден з них не бере до уваги факт, що відносна важливість моделей змінюється разом з контекстами й пов'язаними з ними лічильниками.
У цьому розділі описується метод виведення ваг з "ймовірності відходу". У сполученні з "виключеннями" вони забезпечують просту реалізацію, що дає проте дуже хороше стиснення. Цей більш прагматичний підхід, що спочатку може здатися зовсім не схожим на перемішування, виділяє з кожної моделі деякий кодовий простір, з огляду на цьому можливість доступу до моделей нижчого порядку для пророкування наступного символу . Можна побачити, що ефективне додання ваги кожної моделі засновано на її корисності.
Після визначеного кодового простору, що дозволяє переходити до наступного меншого контексту, такий підхід вимагає оцінки ймовірності появи символу, ні pазу ще що не з'являвся після деякого контексту. Оцінювана ймовірність буде зменшуватися в міру збільшення переглянутих у цьому контексті символів. Пpи виявленні нового символу, пошук його ймовірності повинен здійснюватися моделлю нижчого порядку. Загальна вага, присвоюючим контекстам нижчих порядків, повинна ґрунтуватися на ймовірності нового символу.
Ймовірність виявлення символу, що раніше не зустрічається, називається "ймовірністю відходу", тому що вона визначає, чи йде система до меншого контексту для оцінки його ймовірності. Механізм відходу є аналогом механізму перемішування, що далі знаходить своє підтвердження. Позначимо ймовірність відходу на рівень o через e(o), тоді відповідні ваги можуть бути обчислені з ймовірностей відходу по формулі:
w(o) = ( 1 - e(o) ) *
l П i=o+1
e(i), -1 <= o < l
w(l) = ( 1 - e(l) ),
де l є довжина найбільшого контексту. У цій формулі вага кожної моделі більш низького порядку скорочується ймовірністю відходу. Ваги будуть достовірними (усі позитивні й у сумі дорівнюють нулю) у тому випадку, якщо ймовірності відходу мають значення між 0 і 1 і мінімальний ступінь моделі, до якого можна йти -1, оскільки e(-1)=0. Перевага використання ймовірностей відходу полягає в тому, що порівняно з вагами вони мають більш наочний і зрозумілий зміст, тоді як ті дуже швидко можуть стати маленькими. Крім того, механізм відходу на практиці легше реалізувати, ніж перемішування ваг.
Якщо p(o,Ф) є ймовірність, привласнена символу Ф моделлю ступеня o, то внесок ваг моделі в змішану ймовірність буде:
w(o)p(o,Ф) =
l П i=o+1
e(i) ( 1 - e(o) ) p(o,Ф).
Інакше кажучи, це є ймовірність переходу до моделі меншого порядку ступеня o і вибору Ф на цьому рівні без переходу до більш низького. Для визначення перемішаної ймовірності для Ф, ці ймовірності ваг можуть бути сумовані за всіма значеннями o. Визначення механізму відходу відбувається вибором значень e(o) і p(o).
Ймовірність відходу є ймовірність, що має не символ, що з'являвся ще, що є прояв проблеми нульової ймовірності. Теоретичного базису для оптимального вибору ймовірності відходу не існує, хоча кілька відповідних методів і було запропоновано.
Перший з них - метод A - виділяє один додатковий лічильник понад установлений для виявлення нових символів кількості переглядів контексту. Це дає наступне значення ймовірності відходу:
e(o) =
1
C(o) + 1
З огляду на код відходу виділюване для Ф у моделі порядку o кодовий простір є:
c(o,Ф)
( 1 - e(o) ) =
1
C(o)
C(o) + 1
Метод B вирахуванням 1 із всіх лічильників утримується від оцінки символів доти, поки вони не з'являться в поточному контексті більше одного разу. Нехай q(o) є кількість різних символів, що з'являються в деякому контексті порядку o. Ймовірність відходу, використовувана в методі B є
e(o) =
q(o)
C(o)
яка пропорційна кількості нових символів. Кодовий простір, виділюваний для Ф є
c(o,Ф) - 1
( 1 - e(o) ) =
c(o,Ф) - 1
C(o) - q(o)
C(o)
Метод C аналогічний методу B, але починає оцінювати символи відразу ж по їхній появі . Ймовірність відходу наростає разом з кількістю різних символів у контексті, але повинна бути набагато менша, щоб допустити додатковий кодовий простір, виділюваний символам, тому
e(o) =
q(o)
C(o) + q(o)
Для кожного символу кодовий простір у моделі ступеня o буде:
c(o,Ф)
( 1 - e(o) ) =
c(o,Ф)
C(o)
C(o) + q(o)
9.4 Виключення
У повністю перемішаній моделі, ймовірність символу включає оцінку контекстів багатьох різних порядків, що вимагає багато часу для обчислень. Крім того, арифметичному кодувальнику потрібні ще й накопичувальні ймовірності моделі. Їх не тільки непросто оцінити (особливо розкодувальнику), але й обчислити, оскільки включені ймовірності можуть бути дуже маленькими, що потребує високоточної арифметики. Тому повне змішування в контекстно-обмеженому моделюванні на практиці не застосовується.
Механізм відходу може бути застосований як основа для техніки наближеної до перемішаної, названої виключенням, що усуває зазначені проблеми за допомогою перетворення ймовірності символу в більш прості оцінки . Вона працює в такий спосіб. Коли символ Ф кодується контекстуальною моделлю з максимальним порядком m, то в першу чергу розглядається модель ступеня m. Якщо вона оцінює ймовірність Ф числом, не рівним нулю, то сама й використовується для його кодування. Інакше видається код відходу, і на основі другого по довжині контексту відбувається спроба оцінити ймовірність Ф. Кодування відбувається чеpез відхід до менших контекстів до тих пір, поки Ф не буде оцінений. Контекст -1 ступеня гарантує, що це зрештою відбудеться. Кожний символ кодується серією символів відходу, за яких треба код самого символу. Кожний із цих кодів належить керуючому алфавіту, що складається із вхідного алфавіту й символу відходу.
Метод виключення названий так тому, що він виключає оцінку ймовірності моделлю меншого порядку з підсумкової ймовірності символу. Тому всі інші символи, закодовані контекстами більше високих порядків можуть бути сміло виключені з наступних обчислень ймовірності, оскільки ніколи вже не будуть кодуватися моделлю більше низького порядку. Для цього у всіх моделях нижчого порядку потрібно встановити в нуль значення лічильника, пов'язаного із символом, ймовірність якого вже була оцінена моделлю більш високого порядку. (Моделі постійно не чергуються, але кращий результат досягається щораз, коли робиться особлива оцінка). Ймовірність символу береться тільки з контексту максимально можливого для нього порядку.
Контекстуальне моделювання з виключеннями дає дуже хороше стиснення і легко реалізується на ЕОМ. Для прикладу розглянемо послідовність символів "bcbcabcbcabccbc" алфавіту { a, b, c, d }, що була адаптивно закодована в перемішаній контекстуальній моделі з відходами. Будемо вважати, що ймовірності відходу обчислюються по методу A із застосуванням виключень, і максимальний контекст має довжину 4 (m=4). Розглянемо кодування наступного символу "d". Спочатку розглядається контекст 4-го порядку "ccbc", але оскільки раніше він ще не зустрічався, то ми, нічого не пославши на вихід, переходимо до контексту 3-го порядку. Єдиним раніше зустрічним у цьому контексті ("cbc") символом є "a" з лічильником рівним 2, тому відхід кодується з імовірністю 1/(2+1). У моделі 2-го порядку за "bc" випливають "a", що виключається, двічі "b", і один раз "c", тому ймовірність відходу буде 1/(3+1). У моделях порядків 1 і 0 можна оцінити "a", "b" і "c", але кожний з них виключається, оскільки вже зустрічався в контексті більш високого порядку, тому тут ймовірностям відходу даються значення рівні 1. Система завершує роботу з ймовірностями відходів у моделі -1 порядку, де "d" залишається єдиним неоціненим символом, тому він кодується з імовірністю 1 за допомогою 0 бітів. В результаті одержимо, що для кодування використовується 3.6 бітів. Таблиця 1 демонструє коди, які повинні використовуватися для кожного можливого наступного символу.
Таблиця 1. Механізм кодування з відходами (із виключеннями) 4-х символів алфавіту { a, b, c, d }, які можуть випливати за рядком "bcbcabcbcabccbc".
Символ
Кодування
A
a 2/3
( Усього = 2/3 ; 0.58 бітів )
B
<ESC> b 1/3 2/4
( Усього = 1/6 ; 2.6 бітів )
C
<ESC> c 1/3 ¼
( Усього = 1/12; 3.6 бітів )
D
<ESC> <ESC> <ESC> <ESC> d 1/3 1/4 1 1 1
( Усього = 1/12; 3.6 бітів)
Недоліком виключення є посилення помилок статистичної вибірки застосуванням контекстів тільки високих порядків. Однак, експерименти по оцінці результатів впливу виключень показують, що отримане стиснення лише небагато уступає досягаючому за допомогою повністю перемішаної модел. Пpи цьому перше виконується набагато швидше при більш простій реалізації.
Наступним спрощенням перемішаної техніки є ліниве виключення, що також як і виключення використовує механізм відходу для визначення найдовшого контексту, що оцінює кодуючий символ. Але він не виключає лічильники символів, оцінюваних більше довгими контекстами, коли робить оцінку ймовірностей . Це завжди погіршує стиснення (звичайно на 5%), оскільки такі символи ніколи не будуть оцінюватися контекстами нижчих порядків, і значить виділений їм кодовий простір зовсім не використовується. Але ця модель значно швидша, оскільки не вимагає зберігання сліду символів, які повинні бути виключені. На практиці це може вдвічі скоротити час роботи, що виправдує невелике погіршення стиснення.
Оскільки в повністю перемішаній моделі в оцінку ймовірності символу вносять лепту всі контексти, то після кодування кожного з них природно змінювати лічильники у всіх моделях порядку 0,1,...,m. Однак, у випадку виключень для оцінки символу використовується тільки один контекст. Це наводить на думку внести зміну в метод відновлення моделей, що приводить до обновлюваного виключення, коли лічильник оцінюваного символу не збільшується, якщо він уже оцінювався контекстом більш високого порядку. Інакше кажучи, символ підраховується в тому контексті, що його оцінює. Це можна покращити припущенням, що вірна статистика, що збирається для контекстів нижчих порядків не є неопрацьована частота, але скоріше частота появи символу, коли він не оцінюється більш довгим контекстом. У цілому це небагато поліпшує стиснення (близько 2%) і, крім того, скорочує час, потрібний на відновлення лічильників.
9.5 Алфавіти
Принцип контекстно-обмеженого моделювання може бути застосований для будь-якого алфавіту. 8-бітовий алфавіт ASCII звичайно добре працює з максимальною довжиною контексту в кілька символів. Якщо обіг відбувається до бітів, то можна застосовувати двійковий алфавіт (наприклад, при стисненні зображень). Використання такого маленького алфавіту вимагає особливої уваги до ймовірностей відходу, оскільки наявність невикористаних символів у цьому випадку малоймовірна. Для такого алфавіту існують дуже ефективні алгоритми арифметичного кодування незважаючи на те, що у випадку 8-бітового алфавіту було б закодоване в 8 разів більше двійкових символів. Іншою крайністю може бути розбивка тексту на слова. У цьому випадку необхідні тільки маленькі контексти - звичайно буває досить одного, двох слів. Керування таким дуже великим алфавітом являє собою окрему проблему.
9.6 Практичні контекстно-обмежені моделі
Тепер розглянемо всі контекстно-обмежені моделі, взяті із джерел, що містять їхній повний опис. Методи оцінюються й рівняються в розділі 4. За винятком особливих випадків, вони застосовують моделі від -1 до деякого максимального порядку m.
Моделі 0-го порядку являють собою найпростішу форму контекстно-обмеженого моделювання й часто використовуються в адаптованому й неадаптованому виді разом з кодуванням Хаффмана.
DAFC - одна з перших схем, що змішують моделі різних порядків і адаптуючих її структури. Вона включає оцінки 0-го й 1-го порядків, але у відмінності від побудови повної моделі 1-го порядку вона, для економії простору, засновує контексти тільки на найбільш часто зустрічних символах. Звичайно перші 31 символ, лічильники яких досягли значення 50, адаптивно використовуються для формування контекстів 1-го порядку. Як механізм відходу застосовується метод A. Спеціальний "режим запуску" починається у випадку, якщо один й той же символ зустрівся більше одного разу підряд, що вже хаpактеpно для моделі 2-го порядку. Застосування контекстів нижчого порядку гарантує, що DAFC працює швидко й використовує пpи цьому обмежений (і щодо невеликого) обсяг пам'яті.
ADSM підтримує модель 1-го порядку для частот символів. Символи в кожному контексті класифікуються відповідно до їх частот; цей порядок передається за допомогою моделі 0-ого ступеня. Хоча модель 0-го порядку доступна, але різні класи умов заважають один одному. Перевагою ADSM є те, що вона може бути реалізована в якості швидкого допроцесора до системи 0-го порядку.
PPMA є адаптована змішана модель. Вона застосовує метод A для знаходження ймовірностей відходу й перемішування на основі техніки виключень. Лічильники символів не масштабуються.
PPMB це PPMA, але із застосуванням методу B для знаходження ймовірності відходу.
PPMC - більше свіжа версія PPM-Техніки, що була ретельно пристосована Моффатом для покращення стиснення й збільшення швидкості виконання. З відходами вона працює по методу C, застосовуючи обновлюване виключення й масштабуючи лічильники з максимальною точністю 8 бітів (що знайдено придатним для шиpокого спектра файлів).
PPMC' - модифікований нащадок PPMC, побудований для збільшення швидкості. З відходами він працює по методу C, але для оцінок використовує ліниве виключення (не гірше обновлюваного), накладає обмеження на необхідну пам'ять, очищаючи й перебудовуючи модель у випадку вичерпання простору.
PPMC і PPMC' набагато швидші, ніж PPMA і PPMB, тому що статистику легше підтримувати завдяки застосуванню обновлюваних виключень. На щастя, здійснюване стиснення відносно невідчутно до строгого обчислення ймовірності відходу, тому PPMC звичайно дає кращу загальну характеристику. Всі ці методи вимагають завдання максимального порядку. Звичайно, це буде деяке оптимальне значення (4 символи для англійського тексту, наприклад), але вибір максимального порядку більш необхідного не погіршує стиснення, оскільки змішані методи можуть пристосовувати моделі більш високого порядку, які нічим або майже нічим не допомагають стисненню. Це означає, що якщо оптимальний порядок заздалегідь невідомий, то краще помилятися в більшу сторону. Витрати будуть незначні, хоча запити часу й пам'яті зростуть.
WORD є схема подібна PPM, але використовує алфавіт "слів" - з'єднаних символів алфавіту - і "не слів" - з'єднаних символів, що не входять у цей алфавіт. Первісний текст перекодується для перетворення його у відповідну послідовність слів і неслів. Для них використовуються різні контекстно-обмежені моделі 0-го й 1-го порядків. Слово оцінюється попередніми словами, неслово - несловами. Для знаходження ймовірностей використовується метод B, а через великий розмір алфавіту - ліниві виключення. Застосовуються також і обновлювані виключення. Модель припиняє рости, коли досягає визначеного максимального розміру, після чого статистики змінюються, але нові контексти на додаються.
Якщо зустрічаються нові слова або неслова, вони повинні визначатися іншим способом. Це здійснюється передачею спочатку довжини (обраної із числі від 0 до 20) з моделі довжин 0-го порядку. Потім знову використовується контекстно-обмежена модель букв (або неалфавітних символів у випадку неслів) з контекстами порядків -1,0,1, і ймовірностями відходів обчисленими по методу B. У підсумку завантажуються й змішуються 10 моделей: 5 для слів і 5 для неслів, де в кожному випадку поєднуються моделі 0-...
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора