Удосконалення методів стиснення змішаної інформації

Размещено на http://www.allbest.ru/

Київський Національний університет імені Тараса Шевченка

Спеціальність 05.13.06 - Інформаційні технології

УДК 519.676:681.51

Автореферат

дисертації на здобуття наукового ступеня кандидата технічних наук

УДОСКОНАЛЕННЯ МЕТОДІВ СТИСНЕННЯ ЗМІШАНОЇ ІНФОРМАЦІЇ

Блавацька Наталія

Миколаївна

Київ - 2009

Дисертацією є рукопис.

Робота виконана в Державному університеті інформаційно-комунікаційних технологій Міністерства транспорту та зв'язку.

Науковий керівник - кандидат технічних наук, доцент Браіловський Микола Миколайович, Державний університет інформаційно-комунікаційних технологій, завідувач кафедри комп'ютерних систем та мереж

Офіційні опоненти: доктор технічних наук, професор Жердєв Микола Костянтинович, Військовий інститут Київського національного університету імені Тараса Шевченка, професор кафедри бойового застосування і експлуатації (радіоелектронного озброєння);

кандидат технічних наук, доцент Козюра Валерій Дмитрович, Державний університет інформаційно-комунікаційних технологій, доцент кафедри систем захисту інформації.

Захист відбудеться «12» червня 2009 року в 14.00 годин на засіданні спеціалізованої вченої ради Д26.001.40 Київського національного університету імені Тараса Шевченка за адресою: 03680, Київ-680, просп. Глушкова, 2, корп. 8

З дисертацією можна ознайомитись у бібліотеці Київського національного університету імені Тараса Шевченка за адресою: 01033, Київ-33, вул. Володимирська 58, зал 12.

Автореферат розісланий «12» травня 2009 р.

Вчений секретар спеціалізованої вченої ради С.О. Пашков

1. ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. В даний час спостерігається швидке збільшення кількості інформації, що зберігається, передається та обробляється. Прогрес у галузі технічних засобів передачі і збереження інформації не встигає за потребами суспільства в інформації. Впровадження в дію нових високопродуктивних комунікаційних систем потребує значних коштів. Тому є важливим використання наявних систем збереження і передачі інформації з максимальною ефективністю. Для цього потрібно представляти наявну інформацію меншою кількістю даних за рахунок її кодування з мінімальною інформаційною надмірністю. Це дозволяє зберігати більше інформації на тому ж носії, передавати більше інформації за одиницю часу по каналу зв'язку тієї ж пропускної здатності.

Однак у теорії і практиці стиснення інформації лишилось чимало невирішених проблем. Слід зазначити, що не надана загальна класифікація існуючих алгоритмів стиснення з врахуванням особливостей методів побудови моделей джерел інформації, що лежать у її основі. Не запропоновано досить зручної універсальної оцінки стискаючої здатності методів. Існують резерви підвищення ефективності стиснення інформації регулярної структури, до якої належать, приміром, файли реляційних баз інформації. Покращення стиснення такої інформації може помітно скоротити потребу систем резервного копіювання інформації в об'ємах запам'ятовуючих пристроїв. Недостатньо досліджені можливості побудови моделей і алгоритмів, що добре пристосовуються до різних змін характеру вхідної інформації. Ця проблема особливо актуальна у світі тенденції, що з'явилась в сучасних комп'ютерних системах, до комбінування в одному файлі інформації різних типів (текст, аудіо дані, графічна інформація та ін.), що служать для вирішення однієї задачі.

Таким чином, наукова задача, сутністю якої є удосконалення методів стиснення інформації так, щоб вони мали підвищену стискаючу здатність на широкому спектрі інформації та поліпшену адаптивність до інформації, характер якої різко змінюється, є актуальною.

Зв'язок дисертаційної роботи з планами науково-дослідних робіт. Результати роботи отримані відповідно до виконання НДР «Безпека 07» згідно з постановою Кабінету Міністрів України №01086 від 25 грудня 2005 року. Особисто автором розроблено методику експериментального оцінювання стискаючої здатності алгоритмів стиснення.

Мета і завдання дослідження. Метою роботи є обґрунтування технічних рішень, сприятливих для підвищення стискаючої здатності та поліпшення адаптивності методів стиснення інформації.

Задачі, які необхідно вирішити для досягнення поставленої мети:

1) узагальнити поняття моделі інформаційного джерела для алгоритмів стиснення інформації;

2) провести класифікацію наявних методів стиснення з погляду особливостей використання у них моделей джерела;

3) розробити схему оцінювання стискаючої здатності методів стиснення на основі експериментальних результатів;

4) визначити перспективні з наявних методів стиснення інформації, на підставі аналізу варіантів їхньої реалізації і наявних недоліків, запропонувати удосконалені алгоритми стиснення;

5) реалізувати удосконалені алгоритми у вигляді програмного середовища, що дає змогу довести підвищену ефективність запропонованих методів.

Об'єкт дослідження: технологія і процеси обробки інформації.

Предмет дослідження: методи стиснення змішаної інформації в процесі її обробки.

Методи дослідження: методи теорії інформації та теорії кодування (при аналізі існуючих та при розробці нових алгоритмів стиснення, при розробці методики оцінювання ентропії інформації), методи теорії оптимізації (при розробці блочно-оптимального словникового розбору) та аналізу алгоритмів.

Наукова новизна одержаних результатів роботи полягає в тому, що вперше запропоновано:

1. Метод стиснення інформації OptLZ, заснований на комбінованих словниково-статистичних методах типу LZH та LZAri. Він є удосконаленням загальних методів та відрізняється від них застосуванням стратегії словникового розбору, яка гарантує мінімізацію довжини коду для блоку інформації великого розміру (сотні кілобайт). Блочно-оптимальний словниковий розбір шукається за допомогою метода динамічного програмування, його використання дозволяє суттєво підвищити стискаючу здатність у порівнянні з класичною схемою «жадібного розбору» .

2. Метод стиснення інформації ММКНЗ, який базується на статичних методах групи ММКЗ, що використовують контекстуальні моделі джерела інформації. Він є удосконаленням загальних методів та відрізняється від них використанням багатомодельного підходу до моделювання джерела інформації. Застосування декількох конкуруючих моделей, які будуються із зсувом часу, дозволяє поліпшити адаптивність метода до змін характеру вхідної інформації. У наслідок чого покращується стиснення бінарної і змішаної інформації.

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

Практичне значення одержаних результатів роботи полягає в тому, що:

1. Удосконалено алгоритми стиснення інформації, що використовують блочно-оптимальну схему словарно-статистичного стиснення і новий багатомодельний підхід до моделювання інформаційного джерела контекстуальними методами. Запропоновані алгоритми реалізовано у вигляді файлового архіватора, показали підвищену стискаючу здатність і адаптивність в результаті експериментального порівняння з аналогами.

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

3. Реалізовано ефективне програмне забезпечення для оцінювання ентропії повідомлень джерела інформації.

4. Розроблено алгоритм і реалізовано програмні засоби для експериментального оцінювання стискаючої здатності методів стиснення на різних типах інформації.

Основні результати досліджень, що отримані у дисертаційній роботі, впроваджені у Державному університеті інформаційно-комунікаційних технологій та військовій частині К-1410, що підтверджується відповідними актами.

Особистий внесок здобувача. Основні наукові й прикладні результати дисертаційної роботи отримані здобувачем самостійно. У спільних наукових працях особисто здобувачу належить: у [1] : розробка алгоритму стиснення інформації, у [2] : запропонована класифікація методів стиснення інформації, у [3] : запропонована універсальна оцінка методики порівняння ефективності методів стискання для різних класів вхідної інформації, у [4] : зроблена оцінка взаємозалежності інформаційних джерел між собою, у [6]: проведена оптимізація адаптивності методів стиснення інформації.

Апробація результатів дисертації. Результати досліджень оприлюднені на науково-практичній конференції «Інформаційна безпека» (2009 р., м.Київ), IV Міжнародній науково-практичній конференції «Військова освіта та наука: сьогодення та майбутнє» (2008р., м. Київ), міжвідомчому міжрегіональному семінарі вченої ради Національної академії наук України «Технічний захист інформації 2008-2009р.» та науково-практичних семінарах Національної академії СБ України в 2006-2009 рр.

Публікації. Основні результати дисертаційної роботи опубліковано в 7 статтях (дві статті без співавторів) у наукових фахових виданнях, а також у 2 тезах доповідей на наукових конференціях.

Структура дисертації. Дисертаційна робота складається з вступу, 4 розділів, висновків, що містять основні результати, 4 додатків і списку використаних джерел. Загальний об'єм складає 134 сторінки машинописного тексту, з яких 15 сторінок займають ілюстрації, таблиці та список використаних джерел, який складається з 128 найменувань.

2. ОСНОВНИЙ ЗМІСТ

У вступі сформульовано актуальність роботи, мету та завдання дослідження, визначено наукову новизну та практичне значення отриманих результатів, наведено апробації й публікації, а також основні положення, що виносяться на захист.

У першому розділі розглянуті і проаналізовані наявні методи оптимального представлення інформації, поставлена задача їхнього удосконалення.

Здійснено аналіз теоретичних розробок і практичних досягнень у даній галузі науки. Коротко висвітлені основні поняття теорії інформації і теорії кодування, на яких базується стиснення інформації.

З урахуванням проведеного аналізу наявних результатів у даному напрямку науки зроблено висновок, що не дивлячись на велику кількість наявних методів стиснення інформації без втрат, залишаються наступні проблеми:

1) існує великий розрив між вартістю кодування, що досягається універсальними методами стиснення інформації та теоретичною границею стиснення інформації - ентропією джерела;

2) наявні алгоритми, що наближаються за вартістю кодування до ентропії, орієнтовані на певні класи даних (до інших даних вони не можуть бути застосовані) і, як правило, потребують зберігання великих словників, що на практиці є незручним;

3) найбільш ефективні серед наявних універсальних методів стиснення інформації (методи передбачення по частковим збігам - ММКЗ) дуже добре працюють на текстовій інформації, проте на бінарній і змішаній інформації їх ефективність помітно погіршується через недостатню адаптивність.

Виходячи з цього, поставлена задача розробки методів стиснення інформації, що відрізняються від існуючих підвищеною стискаючою здатністю на широкому спектрі інформації і поліпшеною адаптивністю до статистичних характеристик вхідної інформації, що змінюються.

Обумовлено необхідність проведення досліджень у наступних напрямках:

1. Розробка методики порівняльної оцінки стискаючої здатності методів стиснення для різних класів вхідної інформації і алгоритмів стиснення.

2. Дослідження можливості використання нових багатомодельних схем моделювання джерела інформації, що відрізняються від наявних використанням декількох працюючих одночасно (конкуруючих) моделей.

3. Удосконалення методів стиснення інформації, таким чином, щоб одержати підвищену стискаючу здатність й адаптивність.

4. Реалізація розроблених удосконалених алгоритмів стиснення у вигляді програмного забезпечення для стиснення інформації, що дозволяє всім сучасним вимогам до подібного програмного забезпечення.

5. Порівняння стискаючої здатності оптимальної реалізації нових методів стиснення інформації з існуючими методами.

У другому розділі розглянуті питання класифікації й експериментального оцінювання стискаючої здатності і методів стиснення інформації.

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

Приведена класифікація відрізняється від раніше запропонованих більш повним об'ємом наявних методів стиснення, а також більш детальним урахуванням особливостей тих чи інших методів, що дало можливість класифікувати за різними підкласами ті методи, які раніше відносилися до одного класу.

У запропонованій схемі, на відміну від класичної, міститься препроцесор вхідної інформації, наявність якого дозволяє розглядати всі існуючі практичні алгоритми стиснення як різновиди даної схеми.

Класичні статистичні схеми стиснення і виключно словникові методи є окремими випадками пропонованої структурної схеми - у першому випадку маємо препроцесор, що виконує тотожне перетворення, а в другому випадку - вироджений кодувальник.

Протилежний по відношенню до алгоритму стиснення інформації алгоритм декодування стисненої інформації має наступну структурну схему.

Запропоновані таксономічні ознаки для класифікації моделей джерела інформації і препроцесорів інформації. Для моделей джерела інформації - порядок, адаптивність моделей та вхідний алфавіт моделювальника, для препроцесорів - універсальність препроцесора або його орієнтованість на певну інформацію. На основі даних ознак класифіковані наявні методи моделювання джерела і побудови препроцесорів.

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

Для експериментального порівняльного оцінювання стискаючої здатності практичних схем стиснення інформації і їхнього ранжування за цим показником сформульовані вимоги, які шукана оцінка повинна задовольняти. Вони включають:

- монотонну залежність від розміру результуючого набору інформації (при фіксованому вхідному наборі);

- слабку залежність від експериментального набору інформації;

- фіксовані значення оцінки для тотожного перетворення інформації і «ідеального» методу стиснення.

Запропоновано наступну оцінку стискаючої здатності, що задовольняє поставлені умови:

де f - досліджуваний метод стиснення,

A - вхідний тестовий набір інформації,

H- ентропія,

ж і - алфавіти вхідного і вихідного (стисненого) наборів інформації відповідно.

Фактично у чисельнику пропонованої оцінки перебуває початкова надмірність тестового набору інформації, у знаменнику - надмірність після стиснення інформації методом f.

Для оцінювання ентропії H тестових наборів інформації запропонована обчислювальна схема, що дозволяє одержувати оцінки ентропії високих порядків при обмежених вимогах до оперативної пам'яті. Алгоритм передбачає попереднє лексикографічне сортування всіх наявних у дослідному наборі інформації ланцюжків символів. Це дозволяє оцінити ентропію (порядку кілька десятків) не створюючи надмірно великої кількості лічильників частот.

Для проведення лексикографічного сортування контекстів запропоновано застосувати метод швидкого сортування. Доведено, що в даному випадку цей метод має найкращі показники ефективності серед існуючих методів.

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

Наведена схема дозволила ранжувати методи стиснення даних по їх середній стискаючій здатності або по стискаючій здатності на окремих класах інформації. Це, у свою чергу, дало можливість виявити найбільш перспективні методи стиснення і визначити першочергові напрямки в дослідженнях з розробки більш ефективних схем стиснення.

Отримані результати свідчать про найкращу ефективність наступних двох схем стиснення інформації.

- комбіновані словниково-статистичні методи LZH та LZAri (словниковий LZ77-розбір із безконтекстною динамічною статистичною моделлю для отримання словникових посилань), які при досить великому розмірі словникового буфера (0,5 - 1 Мбайт і більше) відрізняються високою стискаючою здатністю і значною швидкістю;

- статистичний контекстуальний метод високого порядку ММКЗ (передбачення по часткових збігах), що відрізняється високою стискаючою здатністю на текстовій інформації.

У третьому розділі розглянуто питання побудови нових схем стиснення інформації, що відрізняються підвищеною стискаючою здатністю й адаптивністю. Основою для розробки стали існуючі методи, виділені в попередньому розділі як найбільш ефективні.

На основі методів стиснення LZH і LZAri запропонована схема оптимального LZ-розбору OptLZ. На відміну від схем що пропонувалися раніше, дана схема розбору дозволяє мінімізувати довжину одержуваного коду для блоку інформації великого розміру при кодуванні послідовності отриманих словникових посилань за допомогою без контекстної імовірнісної моделі.

Алгоритм знаходження оптимального LZ77-розбору заснований на застосуванні динамічного програмування та діє шляхом перебору можливих варіантів кодування поточного символу словниковими посиланнями різної довжини. Обирається той варіант словникового розбору, що доставляє мінімум сумарної вартості кодування від першого символу вхідного потоку до поточного.

Оптимальність одержаного кодування в класі подібних кодувань з різними варіантами LZ77-розбору чітко доведена.

Експериментальне порівняння запропонованого методу з відомою схемою «жадібного розбору» продемонструвало перевагу даного методу на 0,3 - 13% у розмірі стиснутої інформації (у залежності від типу вхідної інформації).

Для підвищення стискаючої здатності й адаптивності методів стиснення, що використовують контекстуальні моделі ММКЗ високого порядку, запропоновано багатомодельний підхід. На його базі розроблені нові схеми моделювання ММКНЗ, що відрізняються від відомих використанням кількох конкуруючих ММКЗ-моделей (рис.3).

У запропонованих трьох різновидах схеми багатомодельного моделювання, кожна з моделей використовує ідентичний алгоритм, однак максимальна кількість збережених у моделі контекстів може бути різною. Побудова моделей починається зі зсувом у часі, надалі діючі моделі обновлюються синхронно. При оцінюванні ймовірностей символів у кожен момент часу використовується лише одна з моделей. Для керування моделями і вибору поточної моделі для оцінювання ймовірностей використовується блок вибору, що вибирає для оцінювання ймовірностей ту модель, яка систематично дає кращі оцінки ймовірностей символів. Вибір моделі за номером k здійснюється у разі виконання умови:

де i - індекс поточного символу вхідного повідомлення;

- один з попередніх символів;

- довжина його коду при кодуванні на базі моделі за номером ;

- кількість моделей;

- константа комулятивності, що регулює чутливість блоку вибору до змін характеристик вхідної інформації (її оптимальне значення залежить від типу інформації і знаходиться у проміжку 10-50).

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

Експериментально доведена перевага запропонованих схем ММКНЗ над звичайними ММКЗ при рівному обсязі оперативної пам'яті, що використовується при цьому. Перевага полягає у підвищенні ступеня стиску бінарної і змішаної інформації на 0,2 - 4% за рахунок підвищення адаптивності.

Можливість однозначного декодування інформації, що стиснена за допомогою запропонованих схем, теоретично обґрунтована.

У четвертому розділі розглянуто питання практичної реалізації запропонованих у попередніх розділах алгоритмів і результати їхньої апробації. стиснення інформаційний програмний кодування

Розроблено реалізацію алгоритму оцінювання ентропії інформаційного джерела у вигляді програмного середовища ENTROPY. Попереднє лексикографічне сортування всіх наявних контекстів здійснюється методом швидкого сортування Хоара. При цьому сортуються не самі контексти, а посилання на них. Це дозволило знизити вимоги реалізації до оперативної пам'яті до 13n+0(1) байт, де n - довжина набору інформації.

З використанням розробленої програми було оцінено ентропію файлів експериментального набору інформації з 40 файлів, що включає широко застосований у світовій практиці тестовий набір Calgary Corpus, а також 26 файлів з інформацією різних типів (тексти на природних і штучних мовах, файли, що виконуються, файли баз даних, аудіо- та графічні дані). Отримано оцінки для ентропії різних порядків (до 64).

Розроблено програмне середовище EFFECT для експериментального порівняльного оцінювання стискаючої здатності методів стиснення інформації з використанням запропонованої оцінки стискаючої здатності.

За допомогою програми EFFECT проведено оцінювання стискаючої здатності 12 реалізацій, що представляють різні схеми стиску. При оцінюванні використовувався вищезгаданий тестовий набір інформації з 40 файлів. За результатами тестування виділені найбільш перспективні методи стиснення, визначені найбільш придатні методи для різних класів інформації.

Запропонована в попередньому розділі інформаційна технологія високоефективного стиснення інформації реалізована у вигляді програмного середовища (архіватора) CMArc. Один з реалізованих алгоритмів заснований на словноково-статистичній моделі з використанням блочно-оптимального LZ-розбору. Другий - на багатомодельній контекстуальній схемі моделювання ММКНЗ.

Реалізація алгоритмів здійснювалася мовою C із використанням оптимізуючого компілятора Watcom C/C++11.0 фірми Sybase, Inc., що забезпечує можливість перенесення програм до середовища різноманітних операційних систем і високу ефективність одержуваного об'єктного коду.

Програма-архіватор має стандартний для програм такого типу інтерфейс командного рядка і задовольняє усі вимоги до подібних програмних засобів.

Надійність розробленого архіватора обґрунтована методом статистичного моделювання. У ході тестування проведено стиснення та декодування 24855 файлів, що є як реальною інформацією, так і спеціально створеною експериментальними наборами інформацією. У результаті всі тестові файли після декодування повністю співпали з вихідними, що свідчить про високу надійність розробленого програмного забезпечення.

Результати проведених порівняльних випробувань стискаючої здатності реалізацій запропонованих схем стиснення з популярними програмами-архіваторами ARJ, PKZIP, WinRAR і HA (частина отриманих оцінок представлена у табл.1) дозволяють зробити висновок про кращу стискаючу здатність запропонованих алгоритмів практично на всіх типах інформації, що підлягають стисненню. Особливо помітна перевага на текстах штучного походження (AT) і файлах баз інформації (DB).

Результати порівняння стискаючої здатності архіватора CMArc з архіваторами WinRAR і HA

Таблиця 1

Програма	Оцінки по розділах тестового набору інформації	Загальна оцінка =20425319
	CC =3141622	NT =4025135	AT =2236931	DB =4736390	EX =1997013	GR =3058240	AU =1229988
WinRAR2.60 (метод 5)	8,66 (921902)	5,36 (1374650)	12,70 (302417)	16,18 (493621)	6,43 (1002846)	2,36 (2347563)	2,64 (1088002)	8,00 (7531001)
HA 0.999c	9,77 (844731)	7,28 (1209598)	12,68 (308337)	13,55 (542994)	4,76 (1035161)	4,68 (2051531)	3,69 (1074640)	8,72 (7066992)
CMArc0.98.2	10,70 (835461)	7,30 (1206643)	14,48 (278757)	19,67 (436336)	6,57 (992478)	4,63 (2058707)	3,73 (1073358)	9,91 (6881740)

Примітка. Розділи тестового набору даних: CC - Calgary Corpus, NT - природні тексти, AT - штучні тести, DB - файли баз інформації, EX - файли, що виконуються, GR - графічна інформація, AU - аудіоінформація. У дужках наведені початкові розміри розділів тестового набору та розміри стисненої відповідним методом інформації.

З використанням файлового архіватора CMArc розроблена автоматизована система резервного копіювання інформації в середовищі обчислювальної мережі. Система дозволяє через задані проміжки часу в автоматичному режимі здійснювати резервне копіювання зазначеної інформації зі створенням компактних (за рахунок застосування архіватора CMArc) копій інформації на локальних запам'ятовуючих пристроях або на сервері мережі. У разі потреби користувач може здійснити швидке відновлення інформації з резервних копій. Система особливо ефективна при резервуванні файлів баз інформації, протоколів роботи програмних систем і іншої потрібної інформації, що обумовлюється особливо високою стискаючою здатністю розробленого архіватора на інформації такого типу.

ВИСНОВКИ

У дисертації наведене теоретичне узагальнення і нове вирішення наукової задачі, що виявляється в удосконаленні методів стиснення інформації, таким чином щоб досягти підвищеної стискаючої здатності й адаптивності на широкому спектрі вхідної інформації. Головні наукові та практичні результати роботи:

1. Удосконалено два методи стиснення інформації. Перший словниково-статистичний метод OptLZ відрізняється від відомих методів LZH і LZAri підвищеною стискаючою здатністю за рахунок застосування алгоритму блочно-оптимального розбору, що мінімізує сумарну довжину коду для блоку інформації великого розміру. Другий статистичний контекстуальний метод ММКНЗ відрізняється поліпшеною адаптивністю до мінливих характеристик вхідної інформації за рахунок використання кількох працюючих зі зсувом у часі конкуруючих моделей джерела в системі стиску ММКЗ.

2. Запропоновані алгоритми реалізовано у вигляді універсального файлового архіватора CMArc, що потім використаний при розробці універсальної системи резервного копіювання інформації.

3. Вперше запропоновано методику експериментального оцінювання стискаючої здатності алгоритмів стиснення, що базується на введеній оцінці стискаючої здатності методу. Методика враховує відмінність в ентропії різних класів експериментальної інформації і залежність стискаючої здатності методів від вхідної інформації. Запропонована методика реалізована у вигляді програмних засобів ENTROPY та EFFECT, що здійснюють оцінювання ентропії наборів інформації і стискаючої здатності різних реалізацій методів стиску відповідно.

4. Проведено експериментальне порівняння запропонованих алгоритмів стиснення інформації шляхом обчислення оцінок їхньої стискаючої здатності на різній вхідній інформації і їхнього порівняння з відповідними оцінками існуючих методів. Отримані результати переконливо доводять, що розроблені алгоритми мають у цілому, поліпшені показники стискаючої здатності і можуть бути рекомендовані до практичного застосування в програмному забезпеченні для стиснення інформації і резервного копіювання інформації.

5. Розроблено класифікацію методів стиснення інформації, що спирається на особливості препроцесорів інформації і моделей джерела інформаціі, що використовуються.

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

СПИСОК ОПУБЛІКОВАНИХ АВТОРОМ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Ленков С.В., Хорошко В.А., Браиловский Н.Н., Блавацкая Н.Н. Алгоритмы и принципы сжатия информации // Зб. наук. праць Віськового інституту КНУ ім. Т. Шевченка, №14, 2008. - С. 137-141.

2. Браиловский Н.Н., Блавацкая Н.Н. Принципы построения методов сжатия информации // Вісник СНУ ім. В.Даля, №8 (126), Частина 1, 2008. - С. 29-31.

3. Браиловский Н.Н., Блавацкая Н.Н. Оценка сжимающей способности метода сжатия информации // Захист інформації, спеціальний випуск, 2008.

4. Ленков С.В., Хорошко В.А., Браиловский Н.Н., Блавацкая Н.Н. Оценивание взаимозависимости информационных источников между собой //Вісник Київського національного університету ім. Тараса Шевченка.- К., 2008. - №21. Стр. 90-92.

5. Блавацкая Н.Н. Оптимизация адаптивности методов сжатия информации //Захист інформації, 2009, №2. - с. 101-106.

6. Браиловский Н.Н., Блавацкая Н.Н. Сравнительная оценка эффективности быстрой сортировки в алгоритме оценки энтропии информации //ЗНП «Управління розвитком» 2008, №15. - с.18-20.

7. Блавацкая Н.Н. Особенности реализации программы архиватор //Вісник ДУІКТ, 2008, №6(4). - с. 370-373.

8. Блавацкая Н.Н. Мультимодельный подход к повышению адаптивности методов контекстуального моделирования источников информации //Матеріали науково-практичної конференції «Інформаційна безпека». - Київ, 2009. - С.252-255.

АНОТАЦІЯ

Блавацька Н.М. Удосконалення методів стиснення змішаної інформації. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.06 - інформаційні технології. - Національний університет, Київ, 2009.

Дисертацію присвячено удосконаленню методів стиснення інформації, для досягнення підвищеної стискаючої здатності та поліпшеної адаптивності до змін статистичних характеристик вхідної інформації. В роботі запропоновано обчислювальні схеми та алгоритми для порівняльного оцінювання стискаючої здатності схем стиснення та реалізовано відповідне програмне забезпечення. Запропоновано два удосконалених методи стиснення інформації, які відрізняються від існуючих підвищеною стискаючою здатністю за рахунок використання алгоритму блочно-оптимального LZ-розбору, що дозволяє мінімізувати довжину коду для блоку інформації великого розміру, а також поліпшеною адаптивністю за рахунок використання декількох конкуруючих моделей джерела інформації, які працюють у схемі ММКНЗ зі зсувом у часі. Розроблені методи реалізовані у вигляді програмного середовища для стиснення даних CMArc. Перевага запропонованих методів доведена шляхом експериментального порівняння з популярними програмними засобами стиснення даних - архіваторами ARJ, PKZIP, WinRAR, HA. З використанням розробленого архіватора реалізована система резервного копіювання інформації, що впроваджена для резервування інформації.

Ключові слова: технології обробки інформації, стиснення інформації, кодування, оптимальне представлення інформації, джерело інформації, модель джерела інформації.

Блавацкая Н.Н. Усовершенствование методов сжатия смешанной информации. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.06 - информационные технологии. - Национальный Университет, Киев, 2009.

Диссертация посвящена усовершенствованию методов сжатия информации для достижения повышенной сжимающей способности и адаптивности к изменяющимся статистическим характеристикам исходной информации.

Проведенный в работе анализ теоретических разработок и практических достижений в данной отрасли науки показал, в теории и практике сжатия информации осталось еще немало проблем. Не дана общая классификация существующих схем сжатия на основе особенностей лежащих в их основе методов построения моделей источников. Не предложено достаточно удобной меры сжимающей способности методов, которая позволяет легко ранжировать существующие методы и определять эффективность вновь предлагаемых. Существуют резервы повышения эффективности сжатия информации регулярной структуры, к которым относятся, в частности, файлы реляционных баз информации. Улучшение сжатия такой информации может заметно сократить потребность систем резервного копирования информации в объемах запоминающих устройств. Недостаточно исследованы и возможности построения моделей источников и алгоритмов сжатия, хорошо приспосабливающихся к резким изменениям характера сжимаемой информации. Эта проблема особенно актуальна в свете появившейся в современных компьютерных системах тенденции к комбинированию в одном файле информации различных типов (текст, аудиоданные, графическая информация и т.п.), служащих для решения одной задачи.

В ходе исследований была предложена обобщенная структурная схема практических методов сжатия информации и проведена классификация имеющихся методов построения моделей информационного источника и препроцессора входной информации. На основе полученных результатов в дальнейшем построена классификация методов сжатия информации, базирующаяся на особенностях моделей источника информации, которые используются в алгоритме сжатия, и препроцессоров исходной информации.

Для экспериментального сравнительного оценивания эффективности алгоритма сжатия информации предложена методика оценивания их сжимающей способности, учитывающая энтропию входной (тестовой) информации и позволяющая получить оценки сжимающей способности алгоритмов сжатия на различных классах входной информации. Для оценивания энтропии информации предложен алгоритм, использующий предварительную лексикографическую сортировку контекстов. Разработаны вычислительные схемы и алгоритмы оценивания сжимающей способности методов сжатия, а также соответствующая программная среда.

На основе сравнительного анализа эффективности, методов сжатия информации, выбраны наиболее перспективные из имеющихся алгоритмов сжатия.

На основе методов сжатия LZH и LZAri предложена схема оптимального LZ-разбора OptLZ. В отличии от схем, которые предлагались ранее, данная схема разбора позволяет минимизировать длину получаемого кода для блока информации большого размера при кодировании последовательности полученных словарных ссылок с помощью бесконтекстной вероятностной модели.

Для повышения сжимающей способности и адаптивности методов сжатия, которые используют контекстуальные модели ММКЗ высокого порядка, предложено многомодельный подход. На его основе разработаны схемы моделирования ММКНЗ, которые отличаются от известных использованием нескольких конкурирующих ММКЗ-моделей.

С использованием предложенных алгоритмов реализовано программное обеспечение для сжатия информации (архиватор) CMArc. Разработанный архиватор реализует стандартный для подобных программ набор функций. Его надежность экспериментально обоснована методом статистического моделирования.

Преимущество предложенных схем сжатия перед существующими реализациями на широком спектре входной информации доказано путем экспериментального сравнения сжимающей способности использующего их архиватора CMArc с популярными средствами сжатия информации - архиваторами ARJ, PKZIP, WinRAR, HA. Полученные результаты свидетельствуют о преимуществе разработанных алгоритмов сжатия на почти всех классах информации.

Ключевые слова: технологии обработки информации, сжатие информации, кодирование, оптимальное представление информации, источник информации, модель источника информации.

Blavatskaia N.N. Perfection methods for the compression of the mixed information. - Manuscript

Dissertation for the degree of the candidate of technical sciences in the area 05.13.06 - Information technology. - National University, Kyiv, 2009.

The work is dedicated to the development of the new methods for the information compression, the differential characteristic of which lies in the enhanced compression capability and versatility of the constantly changing statistical performance of the initial information.

A new joint structural scheme of the practical methods for the information compression was provided and the classification of the available methods for the model development of the information source and preprocessor of the input information was conducted. The classification of the methods for the information compression was introduced on the basis of the received results with regards to the peculiarities, used in the compression procedure of the information source and initial information preprocessor models.

The evaluating mechanism of their compression capability was introduced for the practical comparative estimation of the procedure for the information compression with reference to the entropy of the entry information (text), which provides a possibility for the evaluation of the compression capability of the compression procedure using different types of the entry information. A new fast procedure, which is using a preliminary lexicographic sort of the context, was introduced for the estimation of the entropy of information. The computational schemes and procedures for the estimation of the compression methods capability with the relevant software were also introduced.

The most advanced of all the current compression procedures were chosen on the basis of the comparative analysis of effectiveness of the available information compression methods.

The compression software (archiver) CMArc was created on the basis of the proposed procedure. The archiver performs the standard amount of functions for this type of programs. Its reliability was experimentally reasoned by means of statistical modeling method.

The advantage of the proposed compression scheme over the existing projects dealing with the wide spectrum of the entry information is proved be means of the experimental comparison of the compression capability of the CMArc and the other popular means of the information compression - ARJ, PKZIP, WinRAR, HA. The received results prove the advantage of the introduced compression procedures for almost all types of information.

Key terms and expressions: technology processing of information, information compression, coding, optimal representation of the information, information source, model of the information source.

Размещено на Allbest.ru

...