ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
НАЦІОНАЛЬНИЙ АВІАЦІЙНИЙ УНІВЕРСИТЕТ
ПОЛЯКОВ Гліб Олександрович
УДК 519.676:681.51.09
Методи ущільнення даних без втрат інформації
з використанням конкуруючих моделей
інформаційного джерела
05.13.06 – Автоматизовані системи управління та
прогресивні інформаційні технології
Автореферат дисертації на здобуття наукового ступеня
кандидата технічних наук
Київ – 2003
Дисертацією є рукопис.
Робота виконана на кафедрі математичного забезпечення ЕОМ Дніпропетровського національного університету Міністерства освіти і науки України.
Науковий керівник:
кандидат фізико-математичних наук, доцент ГОРІН Олександр Кузьмич, Дніпропетровський національний університет, доцент.
Офіційні опоненти:
доктор технічних наук, професор СИДОРОВ Микола Олександрович, Національний авіаційний університет, декан факультету;
кандидат технічних наук, доцент КОРНЕЙКО Олександр Васильович, спеціальний факультет СБ України у складі ВІТІ НТУУ “КПІ”, заступник начальника факультету.
Провідна установа:
Інститут кібернетики ім. В.М.Глушкова НАН України, відділ автоматизації програмування, м. Київ.
Захист відбудеться 06 листопада 2003 р. о 1500 годині на засіданні спеціалізованої вченої ради Д .062.01 при Національному авіаційному університеті за адресою: 03058, м. Київ, проспект Космонавта Комарова, 1.
З дисертацією можна ознайомитись у бібліотеці Національного авіаційного університету за адресою: 03058, м. Київ, проспект Космонавта Комарова, 1.
Автореферат розісланий “03” жовтня 2003 р.
Вчений секретар
спеціалізованої вченої ради ГУЗІЙ М.М.
ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
Актуальність теми. В даний час спостерігається швидке збільшення кількості інформації, що зберігається, передається та обробляється. Прогрес в галузі технічних засобів передачі і збереження інформації не встигає за потребами людства в інформації. Запровадження в дію нових високопродуктивних комунікаційних систем коштує досить дорого.
Тому важливо з максимальною ефективністю використовувати наявні системи збереження і передачі інформації. Для цього потрібно подавати наявну інформацію меншою кількістю даних за рахунок використання ущільнення (стиснення) даних без втрат інформації – кодування інформації з мінімальною інформаційною надмірністю. Це дозволяє зберігати більше інформації на тім же носії, передавати більше інформації за одиницю часу по каналу зв'язку тієї ж пропускної здатності.
Таким чином, очевидна економічна вигода від оптимізації подання інформації та актуальність розробки ефективних методів ущільнення даних.
Теоретичною основою ущільнення даних служать теорія інформації і теорія кодування. Родоначальником теорії інформації є К.Шеннон (C.E.Shannon). Важливі теоретичні результати в цій галузі належать А.М.Колмогорову, О.Я.Хінчіну, І.М.Гельфанду, А.Файнстейну (A.Fienstein), Дж.Вольфовіцу (J.Wolfowitz), Л.Бріллюену (L.Brillouin), П.Елайєсу (P.Elias), Р.Фано (R.M.Fano), Б.Мак-Міллану (B.McMillan).
Перший практичний метод ущільнення даних був запропонований незалежно один від одного К.Шенноном, Р.Фано і (у трохи зміненому вигляді) Д.Хаффманом (D.A.Huffman). Найбільший внесок до розробки практичних методів ущільнення даних внесли Дж.Ріссанен (J.J.Rissanen), Дж.Ленгдон (G.G.Langdon), Дж.Зів (J.Ziv), А.Лемпел (A.Lempel), Т.Белл (T.C.Bell), І.Віттен (I.H.Witten), Дж.Клірі (J.G.Cleary).
Однак у теорії і практиці ущільнення даних без втрат лишилося чимало невирішених проблем. Не надана загальна класифікація існуючих алгоритмів ущільнення з врахуванням особливостей методів побудови моделей джерел інформації, що лежать у їх основі. Не запропоновано досить зручної універсальної оцінки стискаючої здатності методів. Недостатньо досліджені можливості побудови моделей і алгоритмів, що добре пристосовуються до різких змін характеру вхідних даних. Остання проблема особливо актуальна у світі тенденції, що з'явилася в сучасних комп'ютерних системах – комбінування в одному файлі даних різних типів (текст, аудіодані, графічна інформація та ін.), що служать для вирішення однієї задачі.
Таким чином, у дисертаційній роботі була поставлена та вирішена актуальна науково-технічна задача – розробка удосконалених методів ущільнення даних без втрат інформації, які відрізняються від існуючих підвищеною стискаючою здатністю на більшості класів даних, які підлягають ущільненню без втрат, та поліпшеною адаптивністю до даних, статистичний характер (розподіли ймовірностей символів) яких різко змінюється.
Зв'язок дисертаційної роботи з планами науково-дослідних робіт. Результати дисертаційної роботи отримані з 1997 по 2000 р. відповідно до тематичного плану науково-дослідних робіт: держбюджетна тема 01__ДНУ “Розробка автоматизованої системи зберiгання, обробки та прогнозу стану природного середовища при техногенному впливi на основi сучасних iнформацiйних технологiй (регiон Кривбасу)” ГР 0198U003757.
Мета і задачі дослідження. Науковою задачею є розробка удосконалених методів ущільнення даних без втрат, що мають підвищену, у порівнянні з існуючими методами, стискаючу здатність на основних класах даних, яки підлягають ущільненню без втрат інформації.
Метою роботи є підвищення стискаючої здатності методів ущільнення даних без втрат та поліпшення їх адаптивності до різких змін статистичних властивостей даних, що ущільнюються.
Для досягнення поставленої мети у роботі сформульовані та вирішені наступні взаємопов’язані задачі дослідження:
1.
Визначити найбільш перспективні з наявних методів ущільнення даних без втрат, на підставі аналізу варіантів їхньої реалізації і наявних недоліків запропонувати удосконалені методи та алгоритми ущільнення.
2.
Реалізувати запропоновані удосконалені алгоритми у вигляді програмного середовища, що дозволяє довести підвищену ефективність запропонованих методів та впровадити їх у практичних задачах.
3.
Запропонувати зручну схему оцінювання стискаючої здатності методів ущільнення за експериментальними результатами.
4.
Провести повну класифікацію наявних методів ущільнення без втрат з погляду особливостей використовуваних у них моделей джерела.
Об'єктом дослідження в дисертаційній роботі є процеси передачі та збереження інформації у інформаційних комп’ютерних системах.
Предметом дослідження є адаптивні методи ущільнення даних без втрат інформації.
Методами дослідження, використаними у роботі, є методи теорії інформації та теорії кодування (при аналізі існуючих та при розробці нових алгоритмів ущільнення, при розробці методики оцінювання ентропії даних), методи теорії оптимізації (при розробці блочно-оптимального словникового розбору) та аналізу алгоритмів (при виборі оптимального метода сортування в алгоритмах блочно-оптимального розбору та оцінювання ентропії даних).
Наукова новизна одержаних результатів дисертаційної роботи полягає в тому, що вперше запропоновано:
1.
Комбінований словниково-статистичний метод ущільнення даних без втрат OptLZ, який відрізняється від відомих словниково-статистичних методів (Лемпела-Зіва-Хаффмана та ін.) завчасним розбиттям даних на блоки великого розміру (сотні тисяч символів) та застосуванням нової стратегії словникового розбору, яка дозволяє мінімізувати на множині припустимих словникових розборів довжину коду для кожного з блоків. Блочно-оптимальний словниковий розбір шукається з допомогою метода динамічного програмування, його використання дозволяє суттєво підвищити стискаючу здатність у порівнянні з класичною стратегією “жадібного розбору”.
2. Статистичний контекстуальний метод ущільнення даних без втрат MPPM, який є новим варіантом схеми стиснення з допомогою передбачення по часткових збігах (PPM). Метод відрізняється від відомих методів одночасним застосуванням декількох конкуруючих моделей джерела інформації, які будуються за аналогічними алгоритмами, але із зсувом у часі. Для кодування використовується та з моделей, яка у даній момент часу дає більш точні передбачення ймовірностей символів. Це дозволяє поліпшити адаптивність метода стиснення до різких змін статистичних характеристик (розподілів ймовірностей символів) вхідних даних, завдяки чому покращується ущільнення змішаних даних.
3. Метод експериментального оцінювання стискаючої здатності (потужності) алгоритмів ущільнення даних без втрат, який дозволяє ранжирувати їх за цим параметром. Пропонований метод відрізняється використанням завчасного оцінювання ентропії тестових даних, що дозволяє використати як міру стискаючої потужності коефіцієнт зменшення надмірності вхідних даних тим чи іншим алгоритмом, та застосуванням спеціально підібраного набору тестових файлів, який містить усі основні класи даних, що стискаються з допомогою методів ущільнення даних без втрат.
Практичне значення одержаних результатів дисертаційної роботи полягає в тому, що:
1.
Розроблено нові алгоритми ущільнення даних, що використовують блочно-оптимальну схему словарно-статистичного ущільнення і новий багатомодельний підхід до моделювання інформаційного джерела контекстуальними методами. Запропоновані алгоритми реалізовано у вигляді файлового архіватора CMArc, і в результаті експериментального порівняння з аналогами показали підвищену стискаючу здатність і адаптивність.
2.
З використанням запропонованих нових алгоритмів ущільнення даних реалізована автоматизована система резервного копіювання інформації, що відрізняється від аналогів меншими потребами в обсязі запам'ятовуючих пристроїв для збереження резервних копій даних. Таким чином, доведена практична цінність запропонованих алгоритмів ущільнення даних.
3.
Реалізовано ефективне програмне забезпечення для оцінювання ентропії повідомлень інформаційного джерела.
4.
Розроблено алгоритм і реалізовано програмні засоби для експериментального оцінювання стискаючої здатності методів ущільнення на різних класах даних.
5.
З використанням алгоритмів оцінювання ентропії інформаційного джерела розроблено обчислювальні схеми та реалізовано програмне середовище для аналізу взаємозалежностей у системі інформаційних джерел.
Результати досліджень, які отримані у дисертаційній роботі, впроваджені у Дніпропетровських електричних мережах ВАТ “ЕК "Дніпрообленерго"” (м. Дніпропетровськ) у вигляді системи резервного копіювання даних технологічного інформаційного комплексу та у концерні “Укррудпром” (м. Кривий Ріг) у вигляді програмного середовища для вибору раціонального набору водозабірних свердловин при проведенні екологічного моніторингу.
Особистий внесок здобувача в роботах, виконаних у співавторстві, полягає в наступному: у роботі [7] запропоновано оцінка потужності методів ущільнення даних, обрано методи ущільнення для порівняльного аналізу; у роботі [8] запропоновано застосування блочно-сортуючого перетворення з метою зменшення вимог до оперативної пам'яті, реалізовано відповідний алгоритм і отримано нижні оцінки ентропії.
Апробація результатів. Результати дисертаційної роботи доповідалися на Міжгалузевому міжрегіональному семінарі Наукової ради НАН України “Технічні засоби захисту інформації”, Міжнародній науково-методичній конференції “Комп'ютерне моделювання” (Дніпродзержинськ, 1999), 1-й і 2-й Міжнародних науково-технічних конференціях “Авіа-99” (Київ, 1999) та “Авіа-2000” (Київ, 2000), 4-й і 5-й Українських конференціях з автоматичного управління “Автоматика-97” (Черкаси, 1997) і “Автоматика-98” (Київ, 1998), 2-й Всеукраїнській молодіжній науково-практичній конференції з міжнародною участю “Людина і космос” (Дніпропетровськ, 2000), Науково-технічній конференції “Проблеми створення нових машин і технологій” (Кременчук, 1998), підсумковій науковій конференції ДДУ за 1999 р.
Публікації. Основні результати дисертаційної роботи опубліковано у восьми статтях [1–8] у спеціальних виданнях, включених ВАК України до переліку видань, що можуть публікувати результати дисертаційних досліджень (у тому числі шість статей без співавторів), а також у чотирьох тезах доповідей на конференціях [9–12].
Структура й обсяг роботи. Дисертаційна робота складається з вступу, чотирьох розділів, висновків, що містять основні результати, списку літератури і шести додатків. 13 ілюстрацій, 12 таблиць, список літератури – 130 джерел. Загальний обсяг роботи – 165 сторінок (з них: основна частина – 120, малюнки і таблиці – 2, список літератури – 11, додатки – 32).
ОСНОВНИЙ ЗМІСТ РОБОТИ
У вступі сформульована задача дослідження, обґрунтована її актуальність, визначена мета роботи і коло розв'язуваних задач, зазначені її наукова новизна і практичне значення.
У першому розділі розглянуто і проаналізовано наявні методи оптимального подання інформації, поставлена задача їхнього удосконалення.
Дано короткий аналіз теоретичних розробок і практичних досягнень у даній галузі науки. Коротко висвітлено основні поняття теорії інформації і теорії кодування, на яких базується ущільнення даних без втрат.
З урахуванням проведеного аналізу наявних результатів у даному напрямку науки поставлена задача розробки методів ущільнення даних, що відрізняються від існуючих підвищеною стискаючою здатністю на основних класах даних, що ущільнюються, і поліпшеною адаптивністю до різких змін статистичних характеристик вхідних даних.
Обумовлено необхідність проведення досліджень у наступних напрямках:
1.
Розробка універсальної методики порівняльної оцінки стискаючої здатності методів ущільнення без втрат для різних класів вхідних даних і алгоритмів ущільнення.
2.
Одержання удосконалених методів ущільнення даних без втрат, що мають підвищену стискаючу здатність та поліпшену адаптивність до різких змін статистичних характеристик вхідних даних.
3.
Реалізація розроблених удосконалених алгоритмів ущільнення у вигляді програмного забезпечення для ущільнення даних, що задовольняє всім сучасним вимогам до подібного ПЗ.
4.
Порівняння стискаючої здатності отриманої реалізації нових методів ущільнення даних без втрат з існуючими методами.
У другому розділі розглянуто питання класифікації та експериментального оцінювання стискаючої здатності методів ущільнення даних без втрат.
З метою систематизації досліджень по підвищенню стискаючої здатності методів ущільнення без втрат запропоновано класифікувати наявні методи ущільнення даних за особливостями використовуваних моделей інформаційного джерела.
На основі аналізу існуючих методів ущільнення даних запропоновано схема адаптивного ущільнення даних без втрат (рис. ), яка, на відміну від класичної схеми Ріссанена-Ленгдона, містить препроцесор вхідних даних, наявність якого дозволяє розглядати всі існуючі практичні алгоритми ущільнення як різновиди даної схеми.
Рис. . Схема адаптивного ущільнення даних без втрат
Класичні статистичні схеми ущільнення (кодування Хаффмана, Шеннона-Фано та ін.) і чисто словникові методи (різновиди алгоритму Лемпела-Зіва та ін.) є окремими випадками пропонованої схеми – у першому випадку маємо виконуючий тотожне перетворення препроцесор, а в другому випадку – вироджений кодувальник.
Запропоновано таксономічні ознаки для класифікації моделей інформаційного джерела і препроцесорів даних. Серед них – порядок і адаптивність моделі, вхідний алфавіт моделювальника, універсальність препроцесора або його орієнтованість на певні дані. З допомогою таксономічних ознак та врахуванням схеми ущільнення даних (див. рис. ) запропонована загальна класифікація існуючих практичних схем ущільнення. Дана класифікація відрізняється від тих, що пропонувалися раніше (Белл-Клірі-Віттен, Кохманюк), також більш широким охопленням різноманітних алгоритмів ущільнення.
У роботі введено наступні позначення:
та – алфавіти (скінчені) вхідного і ущільненого наборів даних,
та – потужності цих алфавітів,
– множина можливих вхідних наборів даних (скінчених послідовностей символів алфавіту )
– вхідний тестовий набір даних (),
– довжина набору даних (у символах),
– ентропія експериментального набору даних (у бітах на символ),
– дискретне бієктивне відображення множини припустимих вхідних наборів даних в множину ущільнених наборів даних, яке здійснює досліджуваний алгоритм ущільнення даних,
– тотожне перетворення даних (таке, що ).
Для експериментального порівняльного оцінювання стискаючої здатності практичних схем стиску даних без втрат і їхнього ранжирування за цим показником сформульовані вимоги до шуканої оцінки стискаючої здатності:
-
оцінка
залежить від
,
,
та
;
- при фіксованих вхідному наборі даних
і алфавітах
та
оцінка має бути спадаючою функцією від розміру
стисненого набору даних;
- наявність фіксованих (незалежних від вхідного набору даних
) значень оцінки для тотожного перетворення даних
та “ідеального” методу ущільнення (який зменшує надмірність довільних даних до нуля за рахунок генерації коду довжиною
).
Згаданим вимогам до оцінки стискаючої здатності добре відповідає відношення початкової надмірності тестового набору даних до надмірності даних після ущільнення з допомогою досліджуваного стискаючого перетворення .
Тому в роботі запропоновано наступну оцінку стискаючої здатності :
, (1)
де ентропія розуміється у сенсі Шеннона:
, (2)
де – множина всіх -грамм (послідовностей символів) в алфавіті ,
– довільна -грамма з множини ,
– імовірність її появи у наборі даних .
Множина значень оцінки – піввісь .
Для оцінювання ентропії тестових наборів даних запропонована обчислювальна схема, що дозволяє одержувати оцінку ентропії порядку для набору даних розмиру за операцій при використанні оперативної пам'яті розміром . Алгоритм передбачає попереднє лексикографічне сортування всіх наявних у дослідному наборі даних ланцюжків символів. Це дозволяє оцінювати ентропію великих порядків не звертаючись до створення надмірно великої кількості лічильників частот.
Для проведення лексикографічного сортування контекстів запропоновано застосовувати метод швидкого сортування Хоара. Доведено, що в даному випадку цей метод у 2–3 рази ефективніше за кількістю операцій чим bucket-сортировка, яка часто використовується у подібних випадках.
Розроблено схему експериментального оцінювання стискаючої здатності методів ущільнення, що базується на введеній оцінці . Схема передбачає оцінювання на декількох дослідних файлах даних різних класів (текстові, бінарні, змішані), а також на широко застосованому у світовій практиці тестовому наборі Calgary Corpus, і виведення інтегральної оцінки. Ентропія дослідних наборів даних попередньо оцінюється по описаній вище методиці.
Розроблена схема дозволила ранжирувати методи ущільнення даних по їх середній стискаючій здатності або по стискаючій здатності на окремих класах даних. Це, у свою чергу, дало можливість виявити найбільш перспективні методи ущільнення і визначити першочергові напрямки в дослідженнях з розробки більш ефективних схем ущільнення.
Отримані результати порівняльного оцінювання дозволили обрати базовими для розробки нових схем ущільнення наступні методи:
-
комбіновані словниково-статистичні методи LZH та LZAri (словниковий розбір за алгоритмом LZ77 (Лемпел-Зів, 1977) з безконтекстною динамічною статистичною моделлю для отриманих словникових посилань);
- статистичний контекстуальний метод високого порядку PPM (стиснення з допомогою передбачення по часткових збігах).
У третьому розділі розглянуте питання побудови нових схем ущільнення даних, що відрізняються підвищеної стискаючою здатністю й адаптивністю. Основою для розробки послужили існуючі методи, виділені в попередньому розділі як найбільш ефективні.
На основі методів ущільнення LZH і LZAri запропонована схема OptLZ оптимального LZ77-розбору. Оптимальність розуміється як мінімальна довжина результуючого коду (стисненого повідомлення) на множині припустимих LZ77-розборів. Провідною ідеєю схеми OptLZ є розбиття даних на блоки великої довжини (сотні тисяч символів і більше) та мінімізація довжини результуючого коду для кожного блоку даних.
На відміну від схем, що пропонувалися раніше, ця схема розбору дозволяє мінімізувати довжину одержуваного коду для блоку даних великого розміру при статистичному кодуванні (Хаффмана, арифметичному або ін.) послідовності отриманих (згідно з алгоритмом LZ77) словникових посилань з допомогою безконтекстної моделі, яка не враховує залежність розподілу ймовірностей словникових посилань від значення попереднього посилання та оцінює ці ймовірності як їх частоти по вже обробленим даним.
Введемо наступні позначення:
– блок даних, що підлягають ущільненню,
– довільний припустимий LZ77-розбір блоку даних , який є послідовністю словникових посилань, що повністю покриває (без перекриття) блок даних ,
– номер словникового посилання в цьому розборі,
– -ое посилання у LZ77-розборі , яке є парою , – зміщення у LZ77-словнику, – кількість співпадаючих символів,
– множина всіх припустимих LZ77-розборів для блоку даних ,
– довжина коду розбору або окремого посилання при його статистичному кодуванні з допомогою безконтекстної імовірнісної моделі.
Тоді задача полягає у розшукуванні для блоку даних такого LZ77-розбіру , для якого сумарна довжина коду є мінімальною:
, (3)
Запропонований алгоритм знаходження оптимального LZ77-розбору з умови (3) заснований на застосуванні динамічного програмування, правомірність використання якого у даному випадку доведена. Для кожного символу у блоці даних обирається той варіант словникового розбору, що доставляє мінімум сумарної довжині коду від першого символу блоку до поточного.
Експериментальне порівняння запропонованого методу з відомою схемою “жадібного розбору” показало, що значення оцінки стискаючої здатності нового метода на 1,5–30% більше (у залежності від типу вхідних даних). Найбільшої ефективності пропонований метод досягає на файлах реляційних баз даних та штучних текстах (перевага на цих даних ставить 16–30%).
На основі відомих контекстуальних алгоритмів ущільнення даних PPM (Клірі-Віттен) запропоновано новий метод Multi-PPM (MPPM). Він базується на ідеї динамічного розбиття вхідних даних на блоки згідно з статистичними властивостями даних та кодуванні кожного з блоків за допомогою окремої статистичної моделі інформаційного джерела (модель інформаційного джерела тут розуміється за Ріссаненом та Ленгдоном). Таким чином досягається підвищення адаптивності контекстуальної схеми ущільнення, завдяки чому поліпшується ущільнення нестаціонарних (комбінованих) даних.
Схема стиснення даних з використанням декількох контекстуальних PPM-моделей подана на рис. .
Рис. . Схема запропонованого метода ущільнення даних MPPM
У запропонованих трьох алгоритмах багатомодельного моделювання кожна з моделей використовує ідентичний алгоритм, однак максимальна кількість збережених у моделі контекстів може бути різною. Провідна ідея алгоритмів – побудова моделей зі зсувом у часі. Завдяки цьому різні моделі містять статистичні властивості різних відділків вхідного набору даних, що перекриваються. Це дозволяє підвищити адаптивність контекстуального моделювальника до мінливих властивостей інформаційного джерела.
При оцінюванні ймовірностей символів у кожен момент часу використовується лише одна з моделей. Для керування моделями і вибору поточної моделі для оцінювання ймовірностей використовується блок вибору, що вибирає для оцінювання ймовірностей ту з моделей, яка у даний час систематично дає кращі оцінки ймовірностей символів. Вибір моделі за номером здійснюється у разі виконання умови
, (4)
де – індекс (положення) поточного символу вхідного повідомлення,
– один з попередніх символів,
– довжина його коду при кодуванні на базі моделі за номером ,
– кількість моделей,
– константа кумулятивності, від значення якої залежить чутливість блоку вибору до змін характеристик вхідних даних (оптимальне значення залежить від типу даних і знаходиться у проміжку 10–100).
Крім того, блок вибору періодично починає побудову нової моделі, для чого може обнуліти ту з існуючих моделей, яка не використовувалась для кодування найбільший проміжок часу. Процес ущільнення комбінованих даних з використанням двох моделей відображено на рис. . Різні за статистичними властивостями дані позначено різним кольором. Світлим штрихуванням позначено процес побудови моделі без її використання, темним – використання моделі для кодування. Побудова нової моделі починається з періодом (позначено стрілками). Зміна статистичних параметрів даних відбувається у момент , відповідний перехід до іншої моделі – у момент .
Рис. . Приклад ущільнення нестаціонарних даних схемою MPPM (дві моделі)
Експериментально доведена перевага запропонованих схем MPPM перед звичайними алгоритмами PPM при рівному обсязі використовуваної оперативної пам'яті. Перевага полягає в підвищенні значень оцінки стискаючої здатності на бінарних і змішаних даних на 1–20% за рахунок підвищення адаптивності.
Можливість однозначного декодування даних, які ущільнені з допомогою запропонованих схем, теоретично обґрунтована.
Таким чином, у третьому розділі запропоновано два нових метода ущільнення даних: OptLZ та MPPM. Обґрунтовано, що нові методи мають перевагу за стискаючої здатністю перед існуючими методами на 1,5–30% та 1–20% відповідно.
У четвертому розділі розглянуті питання практичної реалізації запропонованих у попередніх розділах алгоритмів і результати їхньої апробації.
Розроблено реалізацію алгоритму оцінювання ентропії інформаційного джерела у вигляді програмного середовища ENTROPY. Попереднє лексикографічне сортування всіх наявних контекстів здійснюється методом швидкого сортування Хоара.
З використанням розробленої програми було оцінено ентропію файлів експериментального набору даних з 40 файлів, що включає широко застосований у світовій практиці тестовий набір Calgary Corpus, а також 26 файлів з даними різних типів (тексти на природних і штучних мовах, файли, що виконуються, файли баз даних, аудіо- та графічні дані). Отримано оцінки для ентропії різних порядків (до 64).
Розроблено програмне середовище EFFECT для експериментального порівняльного оцінювання стискаючої здатності методів ущільнення даних з використанням запропонованої автором оцінки стискаючої здатності.
За допомогою програми EFFECT проведене оцінювання стискаючої здатності 12 реалізацій, що представляють різні алгоритми ущільнення. При оцінюванні використовувався вищезгаданий тестовий набір даних з 40 файлів. За результатами тестування виділені найбільш перспективні методи ущільнення, визначені найбільш придатні методи для різних класів даних.
Запропонована в попередньому розділі інформаційна технологія високоефективного ущільнення даних реалізована у вигляді програми-архіватора CMArc. Один з реалізованих алгоритмів заснований на словниково-статистичний схемі з використанням блочно-оптимального LZ-розбору OptLZ. Другий – на багатомодельній контекстуальній схемі моделювання джерела MPPM. Реалізація алгоритмів здійснювалася мовою C із використанням оптимізуючих компіляторів Microsoft Visual C++ 6.0 та Sybase Watcom C/C++ 11.0, що забезпечує можливість перенесення програми до різних обчислювальних платформ і високу ефективність реалізації.
Архіватор CMArc має стандартний для програм такого типу інтерфейс командного рядка і задовольняє усім вимогам до подібних програмних засобів.
Коректність програмної реалізації архіватора обґрунтована методом статистичного моделювання. У ході тестування проведено ущільнення та декодування 24855 файлів, що є як реальними даними, так і спеціально створеними екстремальними наборами даних. У результати усі тестові файли після декодування повністю співпали з вхідними, що свідчить про коректність реалізації розробленого програмного забезпечення (з коефіцієнтом довіри 0,9 імовірність вірного ущільнення-декодування одного файлу не менш ніж 99,991%).
Результати проведених порівняльних випробувань стискаючої здатності реалізацій запропонованих схем ущільнення з відомими програмами-архіваторами ARJ, PKZIP, WinRAR і НА (частина отриманих згідно з формулою (1) оцінок наведено у табл. та графічно відображено на рис. ) дозволяють зробити висновок про кращу стискаючу здатність запропонованих алгоритмів на переважної більшості класів даних, що підлягають ущільненню без втрат. Особливо помітна перевага над кращім з результатів конкурентів на текстах штучного походження (AT) – 14% та файлах баз даних (DB) – 22%. Загальна оцінка, яка є середньою по всім 40 файлам тестового набору, на 14% перевищує оцінку архіватора HA та майже на 24% – архіватора WinRAR.
Таблиця 1
Результати порівняння стискаючої здатності
розробленого архіватора CMArc з архіваторами WinRAR і HA |
Оцінки по розділах тестового набору даних
Програма | CC
(3141622) | NT
(4025135) | AT
(2236931) | DB
(4736390) | EX
(1997013) | GR
(3058240) | AU
(1229988)
WinRAR 2.60
(метод 5) | 8,66
(921902) | 5,36
(1374650) | 12,70
(302417) | 16,18
(493621) | 6,43
(1002846) | 2,36
(2347563) | 2,64
(1088002)
HA 0.999c |
9,77
(844731) | 7,28
(1209598) | 12,68
(308337) | 13,55
(542994) | 4,76
(1035161) | 4,68
(2051531) | 3,69
(1074640)
CMArc 0.98.2 | 10,70
(835461)
110% | 7,30
(1206643)
100% | 14,48
(278757)
114% | 19,67
(436336)
122% | 6,57
(992478)
102% | 4,63
(2058707)
99% | 3,73
(1073358)
101%
Примітка. Розділи тестового набору даних: CC – Calgary Corpus (міжнародний стандартний тестовій набір даних), NT – природні тексти, AT – штучні тексти, DB – файли баз даних, EX – файли, що виконуються, GR – графічні дані, AU – аудіодані. У дужках наведені початкові розміри розділів тестового набору та розміри ущільнених відповідним методом даних. У останньому рядку також наведено відносна стискаюча здатність архіватора CMArc у порівнянні з кращим з результатів суперників.
Рис. . Результати порівняння стискаючої здатності
розробленого архіватора CMArc з архіваторами WinRAR і HA
З використанням файлового архіватора CMArc розроблена автоматизована система резервного копіювання інформації в середовищі обчислювальної мережі. Система дозволяє через задані проміжки часу в автоматичному режимі здійснювати резервне копіювання зазначених даних зі створенням компактних (за рахунок застосування архіватора CMArc) копій даних на локальних запам’ятовуючих пристроях або на сервері мережі. У разі потреби користувач може здійснити швидке відновлення даних з резервних копій. Система особливо ефективна при резервуванні файлів баз даних, протоколів роботи програмних систем і інших подібних даних, що обумовлюється особливо високою стискаючою здатністю розробленого архіватора на даних такого типу.
Система була впроваджена в Дніпропетровських електричних мережах ВАТ “Енергопостачальна компанія Дніпрообленерго” (м. Дніпропетровськ) для резервного копіювання даних інформаційного комплексу збору та обробки показань телевимірювань і телесигналізації на електропідстанціях напругою 35–750 кВ, що працює в реальному часі під керуванням ОС Windows 2000 Server. Впровадження системи резервного копіювання дозволило підвищити надійність інформаційного комплексу, а також зберігати інформацію за проміжок часу в 6 раз більше при збільшенні об’єму запам’ятовуючих пристроїв лише у 1,5 рази.
Розроблена методика оцінювання ентропії використана при рішенні задачі вибору раціонального набору свердловин при проведенні екологічного моніторингу. З використанням поняття інформаційної залежності були запропоновані алгоритми та обчислювальні схеми оцінювання інформаційної залежності джерел і вибору максимального по інформативності підмножини джерел із заданої множини. Дані алгоритми реалізовані в програмному середовищі IDEPEND.
У результаті використання даного середовища для обробки гідрохімічних даних по мережі водозабірних свердловин у районі ПівнічГЗК Кривбасу з заданої множини 24 свердловин обраний раціональний набір з 12 свердловин, що дозволяє удвічі зменшити витрати на проведення моніторингу та отримати при цьому понад 81% усієї інформації від свердловин. Отримані рекомендації з подальшого проведення гідрохімічного моніторингу використовуються концерном “Укррудпром” (м. Кривий Ріг) при оцінці гідрохімічного становища і техногенного впливу в даному районі.
ОСНОВНІ РЕЗУЛЬТАТИ РОБОТИ Й ВИСНОВКИ
Науковою задачею, яка вирішена, є розробка удосконалених методів ущільнення даних без втрат інформації, які відрізняються від існуючих підвищеною стискаючою здатністю на більшості класів даних, що підлягають ущільненню без втрат інформації. Основними результатами даної роботи є:
1.
Розроблено два удосконалених методи ущільнення даних: словниково-статистичний метод OptLZ, який відрізняється від відомих методів LZH і LZAri підвищеною стискаючою здатністю за рахунок застосування алгоритму блочно-оптимального розбору, що мінімізує сумарну довжину коду для блоку даних великого розміру; статистичний контекстуальний метод MPPM, який відрізняється поліпшеною адаптивністю до мінливих статистичних характеристик вхідних даних за рахунок використання кількох працюючих зі зсувом у часі конкуруючих моделей джерела в схемі ущільнення PPM.
2.
Запропоновані алгоритми реалізованo у вигляді універсального файлового архіватора CMArc, коректність реалізації якого обґрунтовано з допомогою статистичного моделювання. Архіватор CMArc використано при розробці універсальної системи резервного копіювання інформації.
3.
Запропоновано методику експериментального оцінювання стискаючої здатності алгоритмів ущільнення, що базується на введеній автором оцінці стискаючої здатності методу. Методика враховує відмінність в ентропії різних класів експериментальних даних і залежність стискаючої здатності методів від вхідних даних. Запропонована методика реалізована у вигляді програмних засобів ENTROPY та EFFECT, що здійснюють оцінювання ентропії наборів даних і стискаючої здатності різних реалізацій методів ущільнення відповідно.
4.
Проведено експериментальне порівняння запропонованих алгоритмів ущільнення даних з існуючими схемами шляхом обчислення оцінок їхньої стискаючої здатності на різних вхідних даних і їхнього порівняння з відповідними оцінками існуючих методів. Отримані результати переконливо доводять, що розроблені алгоритми мають, у цілому, поліпшені показники стискаючої здатності і можуть бути рекомендовані до практичного застосування в програмному забезпеченні для ущільнення даних і резервного копіювання інформації.
5.
Розроблено класифікацію методів ущільнення даних без втрат, що ґрунтується на особливостях моделей інформаційного джерела і препроцесорів даних, що використовуються у методах ущільнення.
6.
Розроблено обчислювальні схеми та реалізовано програмне середовище IDEPEND для аналізу взаємозалежності у системі інформаційних джерел та вибору їх оптимальної за інформативністю підмножини. Програмне середовище застосовано у задачі вибору раціонального набору свердловин при проведенні екологічного моніторингу.
ОСНОВНІ ПУБЛІКАЦІЇ ЗА ТЕМОЮ ДИСЕРТАЦІЇ
1.
Поляков Г.А. Оптимизация кодирования данных комбинированными словарно-статистическими методами сжатия // Актуальнi проблеми автоматизацiї та iнформацiйних технологiй: Т. . Науковий ред. акад. НАН України В..Моссаковський. Зб. наук. пр. – Днiпропетровськ: Навчальна книга, 1999. – C. –97.
2.
Поляков Г.А. Оптимизация представления информации с использованием моделей информационных источников // Актуальні проблеми автоматизації та інформаційних технологй. Т. . Науковий ред. акад. НАН України В..Моссаковський. Зб. наук. пр. – Дніпропетровськ: Навчальна книга. – 1999. – С. –106.
3.
Поляков Г.А. Классификация методов сжатия данных, основанная на особенностях используемой модели информационного источника // Актуальні проблеми автоматизації та інформаційних технологй. Т. . Науковий ред. акад. НАН України В..Моссаковський. Зб. наук. пр. – Дніпропетровськ: Навчальна книга. – 2000. – С. –143.
4.
Поляков Г.А. Методика экспериментального оценивания сжимающей способности методов сжатия данных // Захист інформації. – 2001. – №3. – С. –63.
5.
Поляков Г.А. Оценивание энтропии потоков данных, сгенерированных стационарными источниками // Придніпровський науковий вісник. – 1998. – №67. – С. –73.
6.
Поляков Г.А. О выборе оптимального метода сжатия данных // Придніпровський науковий вісник. – 1998. – №101. – С. –40.
7.
Горин А.К., Поляков Г.А. Сравнительная оценка эффективности методов сжатия данных // Вопросы прикладной математики и математического моделирования. Сб. науч. тр. – Днепропетровск: ДГУ, 1998. – С. –31.
8.
Горин А.К., Поляков Г.А. Оценивание энтропии потоков данных различного происхождения // Питання прикладної математики та математичного моделювання. Зб. наук. пр. – Дніпропетровськ: ДДУ, 1999. – С. –42.
9.
Поляков Г.А. Выбор оптимального кодирования при сжатии данных комбинированными словарно-статистическими методами // Міждержавна науково-методична конференція “Комп’ютерне моделювання”. – Дніпродзержинськ: ДДТУ, 1999. – С. –151.
10.
Поляков Г.А. Классификация методов сжатия данных, основанная на особенностях используемых алгоритмов моделирования источника информации // II Всеукраїнська молодіжна науково-практична конференція з міжнародною участю “Людина космос”: Збірник тез. – Дніпропетровськ: НЦАОМУ, 2000. – С. .
11.
Горин А.К., Поляков Г.А. Разработка методов сжатия данных, основанных на построении моделей источников информации, и оценка их эффективности // 4-а Українська конференція з автоматичного управління “Автоматика-97”. – Черкаси: ЧТ. – 1997. – Т. . – С. .
12.
Горин А.К., Поляков Г.А. Повышение эффективности сжатия потоков данных, являющихся результатами измерений физической величины // Праці 5- Українсько конференції з автоматичного управління “Автоматика-98”. – Київ: НТУУ “КП”. – 1998. – Ч. . – С. –54.
АнотацІЇ
Поляков Г.О. Методи ущільнення даних без втрат інформації з використанням конкуруючих моделей інформаційного джерела. – Рукопис.
Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.06 – автоматизовані системи управління та прогресивні інформаційні технології. – Національний авіаційний університет, Київ, 2003.
Дисертацію присвячено розробці нових методів ущільнення даних без втрат, які відрізняються від існуючих підвищеною стискаючою здатністю та поліпшеною адаптивністю до змін статистичних характеристик вхідних даних. Запропоновано обчислювальні схеми та алгоритми для порівняльного оцінювання стискаючої здатності схем ущільнення, реалізовано відповідне програмне забезпечення. Запропоновано два нових метода ущільнення даних, які відрізняються від існуючих підвищеною стискаючою здатністю за рахунок використання алгоритму блочно-оптимального LZ-розбору, що дозволяє мінімізувати довжину коду для блоку даних великого розміру, а також поліпшеною адаптивністю за рахунок використання декількох конкуруючих моделей джерела інформації, які працюють у схемі PPM зі зсувом у часі. Розроблені методи реалізовані у вигляді програмного забезпечення для ущільнення даних CMArc. Перевага запропонованих методів доведена шляхом експериментального порівняння з популярними програмними засобами ущільнення даних – архіваторами ARJ, PKZIP, WinRAR, HA. З використанням розробленого архіватора реалізована система резервного копіювання інформації, яка впроваджена для резервування даних інформаційного комплексу збору та обробки технологічної інформації у галузі енергетики.
Ключові слова: ущільнення даних, кодування, оптимальне подання інформації, джерело інформації, модель джерела інформації.
Поляков Г.А. Методы сжатия данных без потерь информации с использованием конкурирующих моделей информационного источника. – Рукопись.
Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.06 – автоматизированные системы управления и прогрессивные информационные технологии. – Национальный авиационный университет, Киев, 2003.
Работа посвящена разработке новых методов сжатия данных без потерь, отличающихся от известных повышенной сжимающей способностью и адаптивностью к изменяющимся статистическим характеристикам исходных данных.
Предложена обобщенная структурная схема практических методов сжатия данных, проведена классификация имеющихся методов построения моделей информационного источника и препроцессоров входных данных. На основе полученных результатов в дальнейшем построена классификация методов сжатия данных, базирующаяся на особенностях используемых в алгоритме сжатия моделей источника информации и препроцессоров исходных данных.
Для экспериментального сравнительного оценивания эффективности алгоритмов сжатия данных предложена методика оценивания их сжимающей способности, учитывающая энтропию входных (тестовых) данных и позволяющая получать оценки сжимающей способности алгоритмов сжатия на различных классах входных данных. Для оценивания энтропии данных предложен быстрый алгоритм, использующий предварительную лексикографическую сортировку контекстов. Разработаны вычислительные схемы и алгоритмы оценивания сжимающей способности методов сжатия, а также соответствующая программная среда.
На основе сравнительного анализа эффективности имеющихся методов сжатия данных выбраны наиболее перспективные из имеющихся алгоритмов сжатия, на основе которых предложены два новых алгоритма.
Предложенный алгоритм OptLZ позволяет повысить сжимающую способность комбинированных словарно-статистических схем сжатия LZH и LZAri за счет использования динамического программирования для получения блочно-оптимального LZ-разбора, что позволяет минимизировать суммарную длину кода для блока данных большого размера (от нескольких сот тысяч до нескольких миллионов символов). Оптимальность предложенной схемы доказана.
Второй разработанный алгоритм (MPPM) основан на использовании многомодельного подхода к моделированию источника информации и позволяет повысить адаптивность статистических методов, использующих модели высокого порядка, за счет применения нескольких конкурирующих моделей, работающих со сдвигом во времени. Для предсказания вероятностей символов в каждый момент времени используется лишь одна модель, но обновляются поступающими на вход алгоритма символами все действующие модели. Предусмотренный специальный блок выбора модели осуществляет переключение моделей в случае, когда некоторая модель начинает систематически давать лучшие предсказания символов, чем текущая используемая для кодирования. Этот же блок по мере надобности осуществляет обнуление ненужных моделей с целью их повторного построения.
С использованием предложенных алгоритмов реализовано программное обеспечение для сжатия данных (архиватор) CMArc. Разработанный архиватор реализует стандартный для подобных программ набор функций. Корректность его реализации экспериментально обоснована методом статистического моделирования.
Преимущество предложенных схем сжатия перед существующими реализациями на большинстве классов данных, которые обычно подвергаются сжатию без потерь, доказано путем экспериментального сравнения сжимающей способности использующего их архиватора CMArc с популярными программными средствами сжатия данных – архиваторами ARJ, PKZIP, WinRAR, HA. Полученные результаты свидетельствуют о преимуществе разработанных алгоритмов сжатия почти на всех классах данных. Наибольшее преимущество (уменьшение остаточной избыточности файлов на 16–30% по сравнению с результатами упомянутых архиваторов) достигается на текстах искусственного происхождения и файлах баз данных.
Архиватор CMArc использован при разработке системы резервного копирования информации в среде ЛВС. Система резервного копирования внедрена в Днепропетровских электрических сетях ОАО “ЭК Днепрооблэнерго” (г. Днепропетровск) для резервирования технологической информации, собираемой с электроподстанций напряжением 35–750 кВ. Применение данной системы резервирования позволило повысить надежность технологического информационного комплекса и увеличить продолжительность хранения информации при небольшом увеличении необходимой емкости запоминающих устройств.
Предложенная методика оценивания энтропии источников информации была использована при решении задачи выбора рационального набора водозаборных скважин при проведении экологического мониторинга. С использованием понятия информационной зависимости источников были предложены алгоритмы и вычислительные схемы оценивания информационной зависимости и выбора максимального по информативности подмножества из заданного множества источников. Алгоритмы реализованы в программной среде IDEPEND, которая использована для обработки гидрохимических данных по сети водозаборных скважин в районе СевГОКа Кривбасcа.
Ключевые слова: сжатие данных, кодирование, оптимальное представление информации, источник информации, модель источника информации.
Polyakov G.A. Loseless data compression schemes using competition models of information source. – Manuscript.
Thesis for a doctor candidate’s degree by speciality 05.13.06 – automated control systems and progressive information technologies. – National Aviation University, Kyiv, 2003.
The thesis deals with design of new loseless data compression schemes which differ from known ones with higher compression ratio and better adaptability to changes in statistical parameters of input data. Computational schemes and algorithms for comparison estimation of data compression techniques’ compression power are proposed and implemented in software. Two new data compression schemes are proposed. These algorithms differ from known ones with higher compression power due to used block-optimal LZ parsing strategy (code size minimization in large data blocks) and better adaptability due to used multiply concurrent data source models in PPM scheme which work with time difference. Proposed compression schemes are implemented in high-efficient data compression tool (archiver) CMArc. New compression
