Адаптивний метод ущільнення даних на основі відкидання послідовностей нулів та одиниць

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

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

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

Процесом ущільнення даних є алгоритмічне перетворення, яке виконується з метою зменшення надлишковості інформації [2], що міститься у вхідних даних. В основі будь-якого методу ущільнення [3, 4] є модель джерела даних, або, точніше, модель надлишковості. Іншими словами, для ущільнення інформації використовуються відомості про формат та тип вхідних даних. Не володіючи такими відомостями про джерело даних, неможливо зробити ніяких припущень про тип перетворення, який б дозволив зменшити обсяг повідомлення. Модель надлишковості [5] може бути статичною, незмінною для всього повідомлення, або формуватися на етапі ущільнення (і відновлення). Адаптивні методи [6] дозволяють на основі властивостей вхідних даних змінювати модель надлишковості інформації, що забезпечує підвищення ефективності роботи методів ущільнення інформації.

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

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

Постановка задач.

Для досягнення поставленої мети необхідно розв'язати такі задачі:

— розробити метод адаптивного ущільнення даних на основі відкидання послідовностей нулів та одиниць;

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

Правила ущільнення блоків даних.

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

Правило ущільнення Q полягає у відкиданні q однакових символів у старших розрядах блоку, при виконанні умови q > log2 n , де n -- розрядність блоку ущільнюваних даних.

Результатом реалізації цього правила є структура перетвореного блоку STR1 (рис. 1), яка має такі складові:

— type (код правила 001);

— c (символи, що відкидаються, c = 0 або c = 1);

— q (двійковий код кількості однакових символів послідовності, що відкидаються);

— поле Х...Х (код, що залишається без змін).

адаптивний ущільнення комп'ютерний

Рис. 1

Правило ущільнення C2 реалізується аналогічно правилу Q. Відмінність полягає лише у тому, що відбувається відкидання однакових символів в молодших розрядах блоку. При цьому поле type приймає значення 010. Правило ущільнення C3 полягає у відкиданні q однакових символів у внутрішніх розрядах блоку, при виконанні умови q > 2log2 n -- 1.

Результатом реалізації цього правила є структура перетвореного блоку STR3 (рис. 2), яка має такі складові:

— type (код правила 011);

— l (двійковий код кількості символів, що залишається без змін у молодших розрядах, розряд- ність коду log2 n );

— поле X(l)... X(l) (код, що залишається без змін у молодших розрядах, розрядність коду l);

— поле X(h) ... X(h) (код, що залишається без змін у старших розрядах, розрядність коду n -- q -- l -- 2).

Рис. 2

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

Г q > log2 n + 2, якщо q = qh;

\q > 2log2 n + 2, якщо qt Ф qh,

де q = ql + qh , qh (двійковий код числа q, що відкидається у старших розрядах); qt (двійковий код числа q , що відкидається в молодших розрядах).

Результатом реалізації цього правила є структура перетвореного блоку STR4 (рис. 3), яка має такі складові:

— type (код правила 100);

— qmin (двійковий код розрядністю log2 n, який відповідає значенню min, qh));

— Ch (символи, що відкидаються у старших розрядах);

— cl (символи, що відкидаються у молодших розрядах);

'01, якщо q > qh; Г 10, якщо q < qh; 11, якщ° q = qh;

— Aq (різниця значень |q/ -- qh|, розрядність log2 n);

— поле X...X (код, що залишається без змін, розрядність коду n -- q -- 2).

Рис. 3

Коли жодне з правил ущільнення на основі відкидання послідовності однакових символів не може бути реалізоване для блоку даних, то такий блок залишається незмінним, але до нього дописується код 000 в полі type, що відповідає правилу ущільнення С5 (рис. 4).

Рис. 4

З урахуванням вищенаведених структур перетворених блоків Bt маємо структуру ущільнених даних, що наведена на рис. 5.

Рис. 5

Правила відновлення блоків даних

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

Схему відновлення блоку даних за правилом D1 (type = 001) наведено на рис. 6.

Рис. 6

Для реалізації правила Dj виконується така послідовність дій. Зчитується 1 біт с, який визначає відкинуті символи. Зчитується log2 n біт, що є кодом числа q . Визначається число n -- q --1, яке є кількістю бітів, що залишилися без змін. Зчитується така кількість біт з ущільнених даних і записується у відновлений блок. Далі до цих бітів з боку старших розрядів дописується q символів, що визначаються с. Також дописується один символ с протилежний символу с.

Правило відновлення D2 (type = 010) реалізується аналогічно правилу відновлення Dj. Відмінність полягає лише у тому, що q однакових символів дописується у молодші розряди блоку.

Рис. 7

Для реалізації правила D3 виконується така послідовність дій. Зчитується 1 біт с. Зчитується ІО§2 n біт q . Зчитується log2 n біт l -- кількість символів, що залишилися без змін у молодших розрядах. Зчитується ця кількість біт з ущільнених даних і записується у відновлений блок. Внутрішні розряди відновленого блоку заповнюються q символами, що визначаються с, а також двома протилежними символами с по краях послідовності однакових символів. Потім визначається число n -- q --1 -- 2, яке є кількістю бітів у старших розрядах, що залишилися без змін.

Схему відновлення блоку даних за правилом D4 (type = 100) показано на рис. 8.

Рис. 8. Схема відновлення блоку даних за правилом D4

Для реалізації правила D4 виконується така послідовність дій. Зчитується log2 n біт числа qmin . Зчитується 1 біт ch , який визначає тип відкинутого символу у старших розрядах. Зчитується 1 біт ci , який визначає тип відкинутого символу у молодших розрядах. Зчитуються 2 біти te типу нерівності qt і qh . Якщо te Ф11, то також зчитується log2 n біт Aq. На основі qmin, te і Aq визначається qt і qh таким чином:

— якщо te =01, то qt = qmin +Aq, qh = qmin;

— якщо te =10, то qt = qmin, qh = qmin + Aq;

— якщо te = 11, то qi = qh = qmin.

Після цього молодші розряди заповнюються qi , а старші qh символами, що визначаються с. До молодших та старших розрядів також дописується один протилежний символ С, якщо q Ф n і qt < n -- 1 та q Ф n і 0 < qh < n -- 1, відповідно. Визначається число n -- q -- 2 , яке є кількістю бітів, що залишилися без змін. Зчитується це число біт з ущільнених даних і записується у відновлений блок.

Відновлення блоку даних за правилом D5 (type = 000) полягає лише у зчитуванні n біт з ущільнених даних.

Результати дослідження.

Для автоматизації експериментального дослідження запропонованого адаптивного методу ущільнення на основі відкидання послідовностей нулів та одиниць розроблено програмний засіб.

Під час проведення дослідження розрядність початкового блоку даних може набувати значень в діапазоні: 16, 32, ..., 2048. Дослідження відбувалося за такими показниками: коефіцієнт ущільнення k , тривалість ущільнення tc, тривалість відновлення tdc .

Результати дослідження запропонованих методів ущільнення за показниками k , tc, ta,c виводяться у табличному та графічному вигляді (рис. 10).

Рис. 10. Головне вікно програмного засобу

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

Для проведення експериментальних досліджень адаптивного методу ущільнення сформовано тестову вибірку із файлів найпоширеніших форматів. Вибірка містить 24 файли таких форматів та розмірів:

— *.doc -- 20 кБ, 100 кБ, 500 кБ;

— *.txt -- 100 кБ, 500 кБ;

— *.bmp -- 20 кБ, 100 кБ, 500 кБ;

— *.gif -- 20 кБ, 80 кБ, 140 кБ;

— *jpg -- 20 кБ, 100 кБ, 550 кБ;

— *.au -- 20 кБ, 160 кБ, 1500 кБ;

— *.mp3 -- 40 кБ, 330 кБ, 500 кБ;

— *.exe -- 340 кБ;

— *.mdb -- 50 кБ, 100 кБ, 600 кБ.

Результати досліджень коефіцієнта ущільнення подано у таблиці та показано як графік на рис. 11.

Табл. 1. Результати дослідження коефіцієнта ущільнення

Рис. 11. Графіки результатів дослідження коефіцієнта ущільнення

З табл. 1 та рис. 11 видно, що більшість файлів піддаються ущільненню запропонованим адаптивним методом, за винятком файлів таких форматів: mp3, у разі розбиття вхідної послідовності на блоки по 16 і 32 розряди; аи, у разі розбиття вхідної послідовності на блоки по 64 і 128 розрядів; bmp при розбитті на блоки по 16 розрядів та exe, у разі розбиття вхідної послідовності на блоки по 16 розрядів. В результаті досліджень найбільшого коефіцієнта ущільнення досягнув файл бази даних (mdb, 50кБ) у разі розбиття на блоки розрядністю 1024, його вдалось ущільнити більше, ніж у 8 разів.

Щодо тривалості ущільнення та відновлення файлів запропонованими методами, то експериментальне дослідження на комп'ютері типу IBM/PC з процесором Intel Core i3 M370 (2.4GHz) і ОЗП розміром у 3 ГБ показало, що для найбільшого файлу (au, 1500 кБ) процедура ущільнення найдовше тривала за найменшої розрядності блоків: від 0,01 с до 0,73 с, а процедура відновлення -- від 0,01 с до 0,44 с.

Встановлено, що запропонований адаптивний метод ущільнення даних на основі відкидання послідовностей однакових символів дозволяє ущільнювати файли різних форматів та розмірів, оскільки обробляє вихідну послідовність даних на бітовому рівні, що дозволяє зменшити її залежність від типу даних. Найбільший коефіцієнт ущільнення забезпечує адаптивний метод при ущільненні файлу бази даних (mdb, 50кБ). У разі розбиття вихідної послідовності даних на блоки розрядністю 1024 біта файл вдалось ущільнити більш ніж у 8 разів.

Література

1. Salomon D. Handbook of Data Compression / D. Salomon, G. Motta. -- London: Springer, 2010. -- 1361 p.

2. Методы сжатия данных / Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин -- М.: ДИАЛОГ-МИФИ, 2002. -- 384 с.

3. Storer J.A. Data Compression: Methods and Theory / Storer J.A. // Computers Science Press. -- 1988. -- V. 47, 1. -- P. 23--29.

4. Lopez D. Important Concepts in Signal Processing, Image Processing and Data Compression. -- University of Delhi, 2012. -- 73 p.

5. Кричевский Р.Е. Сжатие и поиск информации / Р.Е. Кричевский. -- М. : Радио и Связь, 1989. -- 176 с.

6. Рябко Б.Я. Эффективный метод адаптивного арифметического кодирования для источников с большими алфавитами / Б.Я. Рябко, А.Н. Фионова // Проблемы передачи информации. -- 1999. -- С. 34--39.

7. Лужецький В.А. Методи ущільнення даних на основі відкидання послідовностей нулів та одиниць / В.А. Лужецький, Т.М. Чеборака // Інформаційні технології та комп'ютерна інженерія. -- 2014. -- № 1. -- С. 18--26.

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