64796

АЛГОРИТМИ АРХІВАЦІЇ НА ОСНОВІ СИСТЕМИ ЧИСЛЕННЯ ШТЕРНА-БРОКО

Автореферат

Информатика, кибернетика и программирование

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

Украинкский

2014-07-11

18.8 MB

1 чел.

PAGE   \* MERGEFORMAT 1


Початок

Чисельник та знаменник дробу

Початок

Двійкова комбінація довжиною n

еретворення 2

Двійкова комбінація довжиною n

Кінець

Перетворення 1

Чисельник та знаменник дробу

Кінець

КИЇВСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ

ІМЕНІ ТАРАСА ШЕВЧЕНКА

ГЛИНЧУК Людмила Ярославівна

                                                                                                УДК 681.3

АЛГОРИТМИ АРХІВАЦІЇ НА ОСНОВІ СИСТЕМИ ЧИСЛЕННЯ ШТЕРНА-БРОКО

01.05.03 – математичне та програмне забезпечення
обчислювальних машин
і систем

Автореферат

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

Київ – 2010


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

Робота виконана на кафедрі інформаційних систем факультету кібернетики Київського національного університету імені Тараса Шевченка.

Науковий керівник:         Доктор фізико-математичних наук, професор

Провотар Олександр Іванович,

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

Шевченка, завідувач кафедри інформаційних систем факультету кібернетики

Офіційні опоненти:           Доктор фізико-математичних наук, професор

Лавріщева Катерина Михайлівна,

Інституту програмних систем НАН України,

завідувач відділу

Кандидат фізико-математичних наук

Єршов Сергій Володимирович,

Інституту кібернетики ім. В.М. Глушкова НАН України,

старший науковий співробітник

Захист відбудеться “14” жовтня 2010 р. о 14.00 годині на засіданні спеціалізованої вченої ради Д 26.001.09 Київського національного університету імені Тараса Шевченка за адресою: Київ, пр. Глушкова, 2, корп.6, факультет кібернетики, ауд. 40. (Тел. 521-33-66. Факс 259-70-44, E-mail: rada@unicyb.kiev.ua)

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

Автореферат розісланий “10” вересня 2010 р.

Вчений секретар

спеціалізованої вченої ради                                                    Шевченко В.П.

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

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

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

Питаннями стиснення почав займатися ще Клод Шеннон. Вагомий внесок у цю теорію внесли Хартлі, Фано, Хаффман, Лемпел, Зів, Клірі, Уїттен. Проте останні та найновіші ідеї вирішення проблем стиснення розглядалися у працях М. А. Смирнова, І. А. Пилипенко, В. Б. Чередниченко, А. А. Борисенко, Т. А. Протасова, И. А. Кулик, С. Н. Харченко та інші.

Проблемами поєднання стиснення та шифрування інформації займалося і займається багато вчених. Зокрема, дослідження об’єднання методів шифрування і стиснення розглядалися у працях А. А. Борисенко, А. М. Моргун, В. П. Майданюк, А. В. Шевченко, С. А. Піддубчак та інші.

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

Зв’язок роботи з науковими програмами, планами, темами. Дисертація виконана в Київському національному університеті імені Тараса Шевченка на кафедрі інформаційних систем в рамках наукової теми “Створення теоретичних основ, методів та засобів інтелектуалізації інформаційно-комунікаційних технологій для розподілених комп’ютерних систем”, номер державного реєстру 06БФ015-01.

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

Для досягнення поставленої мети в роботі розв’язувались наступні задачі:

  •  аналіз існуючих методів стиснення та захисту інформації;
  •  дослідження та вивчення властивостей дерева (системи числення) Штерна-Броко;
  •  розробка алгоритму стиснення з ключем;
  •  дослідження складності розробленого алгоритму;
  •  дослідження стійкості алгоритму;
  •  порівняльний аналіз алгоритму стиснення з відомими алгоритмами шифрування та програмами стиснення;
  •  розробка та дослідження алгоритму стиснення двійкових кодів та бінарних зображень;
  •  побудова алгоритмів стиснення з ключем у візуальному середовищі програмування.

Об’єкт даного дослідження – стиснення інформації, система числення Штерна-Броко.

Предмет дослідження – методи та алгоритми стиснення інформації.

Методи досліджень. При виконанні роботи використовувались методи теорії інформації, стиснення інформації, теорії складності обчислень, теорії стійкості, дискретної математики, теорії чисел.

Наукова новизна.  В дисертації одержані наступні нові результати:

  •  запропоновано новий метод стиснення з використанням ключа та спосіб побудови хеш-функції;
  •  досліджено властивості дерева Штерна-Броко;
  •  розроблено новий алгоритм стиснення з ключем символьної інформації та досліджена оцінка складності і питання стійкості алгоритму;
  •  запропоновано новий алгоритм стиснення двійкових кодів та бінарних зображень;
  •  розроблено та реалізовано алгоритм стиснення для надвеликих чисел;
  •  розроблена і реалізована оболонка експертної системи з вбудованим  алгоритмом для захисту і стиснення бази знань.

Теоретичне та практичне значення. Результати дисертаційної роботи мають головним чином практичне значення. В роботі досліджені властивості системи числення Штерна-Броко, розроблені і обґрунтовані алгоритми для стиснення з використанням ключа, а також для надвеликих чисел. Побудований та досліджений алгоритм для стиснення двійкових кодів та бінарних зображень. Особливістю алгоритмів є їх простота в практичній реалізації.

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

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

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

Апробація. Основні результати дисертаційної роботи доповідалися та обговорювалися на семінарах:

  •  кафедри математичних методів захисту інформації Київського політехнічного інституту /2009 р./;
  •  факультету кібернетики Київського національного університету імені Тараса Шевченка /2007-2009 рр./;
  •  Інституту програмних систем НАН України/2010 р./;
  •  Інституту кібернетики ім. В.М. Глушкова НАН України /2010 р./;

а також на конференціях:

  •  ІV Міжнародна конференція “Теоретичні та прикладні аспекти побудови програмних систем” – TAAPSD’2007, Бердянськ, 2007 р.;
  •  VI Міжнародна науково-практична конференція з програмування УкрПРОГ-2008, Київ, 2008 р.;
  •  XV Всеукраїнська наукова конференція “Сучасні проблеми прикладної математики та інформатики”, Львів, 2008 р.;
  •  VI міжнародна науково-практична конференція “Математичне та програмне забезпечення інтелектуальних систем” – MPZIS-2008, Дніпропетровськ, 2008 р.;
  •  Міжнародна науково-практична конференція “Сучасні засоби та технології розроблення інформаційних систем”, Харків, 2008 р.

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

Публікації. За темою дисертації опубліковано 12 наукових праць, з них 4 – у фахових виданнях ВАК України.

Структура та обсяг роботи. Дисертація складається зі вступу, чотирьох розділів, висновків та списку використаних джерел, що містить 100 найменувань. Загальний обсяг роботи – 139 сторінок, об’єм основної частини – 129 сторінок.

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

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

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

У другому розділі розглядається система числення Штерна-Броко. Подаються загальні алгоритми переведення з однієї системи числення в іншу. Головна увага приділяється дослідженню та вивченню властивостей дерева Штерна-Броко. Зокрема в пункті 2.2. досліджується побудова системи числення Штерна-Броко.

Дерево Штерна-Броко – це звичайне двійкове (бінарне) дерево, вершини якого додатково занумеровані раціональними числами. Тобто, дерево Штерна-Броко – це спосіб побудови множини всіх невід’ємних дробів. Суть цього способу полягає у тому, щоб почати з двох дробів , а потім повторити необхідну кількість разів наступну операцію: вставити  між двома сусідніми дробами  і . Новий дріб  називається медіантою дробів  і . Наприклад, перший крок дає одну нову вставку між  і : , ,; наступний крок дає дві вставки: ,, , ,; ще один крок дає чотири вставки: ,  , ,  , ,  ,  ,  ,.

Потім додається 8, 16 і т. д. нових вставок. Всю сукупність вставок можна представити у вигляді нескінченого бінарного дерева.

В пункті 2.3. розглядається класифікація систем числення та досліджується система числення на основі дерева Штерна-Броко.  

Зокрема показано, що система числення Штерна-Броко відноситься до ітераційних: система числення Штерна-Броко є ітераційною системою числення з породжуючою функцією .

Формула  рівносильна умовному оператору: якщо , то , інакше . Ітерації  породжують дерево базових точок системи числення Штерна-Броко. Далі для запису числа будемо використовувати три цифри –  зі значеннями відповідно .

Теореми 2.1.-2.3 виражають властивості системи числення Штерна-Броко.

Теорема 2.1. Будь-яке натуральне число  – базова точка -го рівня системи числення Штерна-Броко, записується у ній словом .

Наслідок. , .

Теорема 2.2. Нехай , де дроби  і   нескоротні,  – базова точка системи числення Штерна-Броко, а  і  – найближчі до неї базові точки вище лежачих рівнів. Тоді .

Наслідок. Усі раціональні числа і тільки вони є базовими точками системи числення Штерна-Броко.

Тоді, наприклад,   , , , , і т. д.

Теорема 2.3. Дроби, чисельник і знаменник яких є сусідніми числами послідовності Фібоначчі, утворюють в дереві базових точок системи числення Штерна-Броко нескінченний низхідний зигзагоподібний шлях:  , , , ,  і т.д. Інший аналогічний шлях утворюють дроби, чисельник і знаменник яких стоять у послідовності Фібоначчі через номер: ,  , , , ,  і т.д.

В пункті 2.4. подається спосіб створення хеш-функції тільки для числових даних.

Вершинами дерева Штерна-Броко є раціональні числа у вигляді невід’ємних нескоротних дробів. Основна властивість дерева полягає в тому, що у ньому представлені всі раціональні числа, причому кожне – тільки один раз. Кожному дробу можна поставити у відповідність деякий рядок, що складається з символів L і R (L – переміщення по лівих гілках дерева, R – переміщення по правих гілках дерева). Якщо букви L і R замінити цифрами 0 і 1, то в результаті кожен дріб буде мати двійковий номер. Наприклад, дріб 2/5 буде мати номер 001, дріб 2/3 – 01, 3/1 – 11, і т.д. В результаті такої нумерації дроби, що стоять справа від вершини дерева 1/1, будуть мати двійковий номер, який буде починатися з 1 і всі будуть неправильними; відповідно дроби, які стоять зліва від вершини 1/1 будуть мати двійковий номер, який буде починатися з 0 і  всі будуть правильними.

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

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

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

Доведені наступні твердження:

Твердження 2.1. На -тому рівні дерева максимальне десяткове число, яке утвориться після перетворення двійкового номера дробу буде визначатися за формулою:

а)   для правої вітки дерева;

б)   для лівої вітки дерева.

Твердження 2.2. На -му рівні дерева найбільший чисельник рівний найбільшому знаменнику і обчислюється за формулою , де  – найбільший чисельник та знаменник ()-го рівня дерева, а – найбільший чисельник та знаменник ()-го рівня дерева.

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

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

В пункті 3.1. розглядаються питання розробки алгоритмів стиснення з ключем на основі дерева Штерна-Броко (АСК).

Для алгоритму стиснення повинна виконуватись нерівність . Де   початкових вхідний текст, а   стиснутий.

Перетворення вхідних даних за алгоритмом стиснення з ключем аналогічне способу побудови хеш-функції. Однак необхідність врахування потреби відновлення даних до початкового вигляду дозволяє використовувати тільки праве піддерево дерева Штерна-Броко (ліве піддерево  не використовується бо дає неоднозначне відтворення). Тому виникає необхідність коригувати перетворювані дані, в зв’язку з чим з’являється поняття ключа, який містить різниці.

Зворотній алгоритм полягає у виконанні наступної послідовності кроків: результуюче число з десяткової системи числення переводиться у двійкову; двійковому рядку шукається відповідний дріб у дереві Штерна-Броко; далі чисельник і знаменник знову переводиться до двійкової стрічки і т.д. Процес продовжується певну кількість кроків, яка має бути відома користувачеві (кількість кроків архівації = кількості кроків розархівації).

Враховуючи, що:

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

алгоритм стиснення з ключем завершує роботу з такими можливими результатами:

  1.  ключ разом зі стиснутим рядком  вхідної послідовності – стиснення не відбулося (відбулося шифрування);
  2.  ключ + стиснутий рядок  вхідної послідовності – стиснення відбулося, тобто можливе;
  3.  стиснутий рядок  вхідного рядка – відбулося так зване чисте стиснення без використання ключа.

Таким чином, використання ключа виправдане у випадках:

1) коли потрібно покращити результат стиснення (але тоді потрібно слідкувати, щоб ключ не погіршував загальний результат стиснення);

2) коли числа, які розглядаються на всіх рівнях перетворення, не задовольняють необхідним умовам.

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

Алгоритм:

  1.  Вхідній послідовності символів (під символами розуміємо всі можливі символи, цифри, букви, і ін.)  ставимо у відповідність числа за якимось законом, правилом. Обов’язкова умова: вхідна послідовність повинна бути рівна  байт. Кількість рівнів перетворення рівна .
  2.  Кількість кроків k_krok=n; кількість елементів вхідної послідовності k_el= ;
  3.   пару сусідніх чисел ,  розглядаємо як дріб  (або підбираємо випадковим чином чисельник і знаменник, отримаємо новий дріб ).
  4.  від даних чисел віднімаємо отримані, тобто , = (де , ) і заносимо в матрицю , яка і буде матрицею-ключем (матриця  має  стовпців, n  рядків, але не буде повністю заповненою: кожен її рядок буде містити у 2 рази менше елементів від попереднього, решта елементів − нулі).
  5.  Парі отриманих з п. 4 чисел (дробу) ставимо у відповідність двійкову послідовність  за деревом Штерна-Броко.
  6.  Двійкову послідовність  перетворюємо у десяткове число Des за алгоритмом переведення з двійкової системи числення у десяткову.
  7.  Десяткове число Des записуємо у проміжний масив.
  8.  
  9.  Виконуємо п.п. 3-8  k_el=k_el/2 разів (кожен раз береться по 2 елементи).
  10.  Десяткові числа, що були записані у проміжний масив у п. 7 переходять як вхідна послідовність до пункту 3.
  11.  
  12.  Виконуємо п.п. 3-11  k_krok  разів.
  13.  Після виконання п.п. 1-10, отримаємо =одне число і матрицю-ключ .
  14.  Кінець алгоритму.

Сформульовані умови коректності роботи алгоритму.

Умова 1. Вхідна послідовність символів повинна бути рівна  байт ().

Умова 2. Числа , , які розглядають як дріб , повинні задовольняти вимогам:

а)  > ;                                                                                                     

б)  дріб  − елемент системи числення Штерна-Броко, (,  – додатне).

Проаналізовані результати роботи алгоритму і сформульовані у вигляді тверджень.

Твердження 3.1. Для вхідного блоку розміром  байт ключ буде містити   елементів.

Під елементом розуміється число, яке може містити певну кількість цифр.

Твердження 3.2. Зашифрований текст для кожного блоку повідомлення розміром  байт  складається з одного елемента.

Твердження 3.3. Для кожного нового блоку вхідного тексту ключ генерується по новому.

Зворотній до АСК алгоритм розпаковування містить такі кроки:

  1.  Вхідний  – число записуємо у проміжну матрицю .  – кількість елементів матриці ; :=кількість рядків матриці-ключа .
  2.   – кількість елементів вихідної матриці,  − біжуча кількість елементів матриці .   
  3.  Перетворюємо елемент матриці  з десяткової системи числення у двійкову, отримуємо  – двійкову послідовність.
  4.  Двійковій послідовності  ставимо у відповідність дріб  за деревом Штерна-Броко.
  5.  Утворюємо вихідний масив  за правилом: ; .
  6.   – оскільки кожен раз утворюється два елементи матриці ;  − оскільки розглядаємо один елемент матриці .
  7.  Виконуємо п.п. 3-6 поки  (поки не розглянемо всі елементи матриці ).
  8.  ;
  9.  Переписуємо масив  у .
  10.  ;
  11.  Виконуємо п.п. 2-10 поки  не стане рівним 1.
  12.  Перетворюємо вихідний масив за протилежним правилом, або законом який використовується в алгоритмі криптографічного стиснення.
  13.  Кінець алгоритму.

У пункті 3.3. досліджується часова та ємнісна оцінка складності  алгоритму стиснення-розпакування. Результати сформульовані у вигляді наступних тверджень.

Твердження 3.4. Алгоритм стиснення з ключем на основі дерева Штерна-Броко (АСК) має лінійну часову складність.

Твердження 3.5. Ємнісна складність АСК – лінійна.

Твердження 3.6. Часова складність зворотного алгоритму – лінійна.

Твердження 3.7. Ємнісна складність зворотного до АСК алгоритму – лінійна.

Результати роботи алгоритму залежать як від вхідних даних так і від способу побудови ключа. Тому пункт 3.4. присвячений способам побудови ключа і питанням стійкості алгоритму. Показано, що

Твердження 3.8. АСК не є абсолютно стійким.

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

Показано, що до даного алгоритму можна застосувати лише метод повного перебору.

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

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

Порівняння було виконано з використанням деякого тестового набору файлів – Calgary Compression Corpus (CalgCC). Набір складається з 14 файлів, основна частина яких - це тексти на англійській мові або мові програмування. Результати роботи алгоритму усереднювались та враховували довжини ключа. Зведені результати порівняння АСК з алгоритмами стиснення приведені в табл. 1.

Таблиця 1.

Експериментні дані архіваторів

ARJ

PKZIP

ACE

RAR

CABARC

7-Zip

ACК

Bib

3,08

3,16

3,38

3,39

3,45

3,62

1,56

Book1

2,41

2,46

2,78

2,80

2,91

2,94

0,92

Book2

2,90

2,95

3,36

3,39

3,51

3,59

1,13

News

2,56

2,61

3,00

3,00

3,07

3,16

1,27

Paper1

2,84

2,85

2,91

2,93

2,99

3,07

1,22

Paper2

2,74

2,77

2,86

2,88

2,95

3,01

1,05

Progc

2,93

2,94

3,00

3,01

3,04

3,15

1,82

Progl

4,35

4,42

4,49

4,55

4,62

4,76

2,23

Progp

4,32

4,37

4,55

4,57

4,62

4,73

2,14

Trans

4,65

4,79

5,19

5,23

5,30

5,56

2,34

Середнє значення

3,278

3,332

3,552

3,575

3,646

3,759

1,568

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

АСК як шифрувальний засіб відноситься до класу симетричних блочних шифрів, тому порівняння проводилося з аналогічними алгоритмами. Найбільш важливими характеристиками блочного шифру є довжина ключа, розмір блоку даних, до яких застосовується шифрування, стійкість. Таким чином, алгоритм стиснення з ключем має схожі характеристики з алгоритмом шифрування Blowfish. Із зростанням блоку вхідних даних довжина ключа зростає. Співвідношення розміру вхідних даних до ключа визначається як 1:7.  

Розглянутий алгоритм стиснення для роботи з текстовою інформацією не може бути безпосередньо використаний для стискання двійкових послідовностей та бінарних зображень. Питанню стиснення двійкової інформації без втрат з використанням елементів системи числення Штерна-Броко і присвячений пункт 3.7.

Алгоритм стиснення (блок-схема рис. 3.1) полягає у переході від бінарної послідовності до дробу, який їй відповідає. Алгоритм відновлення (блок-схема рис. 3.2) – зворотній.

Рис. 3.1 Блок-схема стиснення           Рис. 3.2 Блок-схема відновлення

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

Таблиця 2. 

Середні коефіцієнти стиснення , обчислені на основі середніх довжин

8

16

32

p = варіант 1

1.520

2.500

4.243

p = варіант 2

1.405

2.256

3.751

p = варіант 3

1.233

1.902

3.066

p = варіант 4

1.094

1.615

2.530

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

Запропонований алгоритм виконує відображення рівномірних кодів на нерівномірні. При цьому кодам з кількістю одиниць (нулів) з інтервалів [0; n/4-1] та [3/4n+1; n] ставляться у відповідність коротші відносно n коди, а іншим – довші. Тобто половина кодів відображаються в коротші нерівномірні коди, а інша половина – в довші.

Для порівняння з іншими аналогічними програмами було використано деякий тестовий набір файлів CalgCC (з набору взято 8 файлів).

Аналогічний алгоритм (рис. 3.1) дає можливість стискати бінарні зображення, оскільки вони складаються з двійкових послідовностей. Приклад стиснення такого зображення та відповідні розрахунки подаються у пункті 3.8.

Отже, сумарна довжина  стиснутої -ї бінарної послідовності довжиною  біт обчислюється як:

                                            .                                       (3.8.1)

де,  – кількість біт для зберігання чисельника, аналогічно довжина  − кількість біт для зберігання знаменника.

Коефіцієнт стиснення однієї бінарної послідовності  визначається за формулою

Кількість -бітних послідовностей , на які розбивається бінарне зображення:

де  – висота бінарного зображення в пікселях (точках);  – ширина бінарного зображення в пікселях.

Розмір стисненого зображення можна розрахувати за формулою загальної довжини  усіх стиснутих бінарних послідовностей

Загальний коефіцієнт стиснення бінарного зображення для методу з використанням елементів системи числення Штерна-Броко визначається як

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

Розглянутий алгоритм є досить ефективним для бінарних зображень у випадку переваги одного з кольорів (чорного або білого). Коефіцієнт стиснення залежить від розмірів стискуваних блоків  та розподілення чорних та білих значень яскравості у кожному з блоків. Що більше відхилень розподілення точок від середнього значення , тим більший коефіцієнт стиснення. При збільшенні розміру стискуваного блоку , коефіцієнт стиснення також збільшується, але при цьому зростають часові та апаратно-програмні затрати пов’язані з підрахунком чисельника та знаменника дробу системи числення Штерна-Броко.

Четвертий розділ присвячено питанням розробки АСК у візуальному середовищі. Зокрема, розглядаються питання розробки оболонки ESZ1 для експертної системи з вбудованим АСК та декілька реалізацій алгоритму стиснення з ключем.

В пункті 4.1. приведено основні фрагменти алгоритмів стиснення та розпаковування (відновлення) на мові програмування.

Для функціонування алгоритму стиснення з ключем реалізовані:

  1.  процедура перетворення отриманих чисел у числа, які є елементами ітераційної системи числення Штерна-Броко;
  2.  процедура побудови дерева Штерна-Броко;
  3.  процедура встановлення відповідності між дробом (парою чисел) і двійковою послідовністю за деревом Штерна-Броко;
  4.  процедура перетворення двійкової послідовності у десяткове число за правилом переведення з однієї системи числення в іншу;
  5.  процедура побудови ключа.

Для функціонування зворотного алгоритму реалізовані:

  1.  процедура переведення десяткового числа у двійкову послідовність з правилом переведення;
  2.  процедура встановлення відповідності між двійковою послідовністю і дробом за деревом Штерна-Броко;
  3.  процедура побудови проміжного результату за ключем і шифрованим текстом.

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

В пункті 4.3. розглядаються візуальні засоби оболонки для експертної системи ESZ 1.0.

Сучасні інструментальні середовища візуального програмування дозволяють створювати різноманітні інтерфейси. Основним елементом інтерфейсу системи ESZ 1.0 є форма. Форми містять об’єкти – вікна, кнопки та ін., з якими пов’язані властивості та методи. Кожна кнопка виконує певну дію, яка реалізується за допомогою процедури. Процедури обробки подій або обробки даних відповідно до основного механізму виведення здійснюють перехід між формами або модифікують їх.

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

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

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

  1.  застосовування алгоритму, при умові, що його цифри – символи;
  2.  застосування алгоритму, при умові, що його цифри є цифрами.

Показано, що у другому випадку величина ключа буде у два рази меншою, як у першому.

Пункт 4.5. – демонстраційний. Наводиться реалізація алгоритму стиснення з ключем що дає можливість побачити усі три результати роботи алгоритму: “чисте” стиснення, стиснення з ключем та шифрування.

ВИСНОВКИ

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

Основні результати роботи наступні.

  1.  На основі проведеного, в дисертаційній роботі, аналізу розроблена класифікація методів стиснення. Досліджена система числення Штерна-Броко. Запропоновано спосіб побудови хеш-функції з використанням системи числення Штерна-Броко.
    1.  Розроблено алгоритм стиснення з ключем, як засіб для архівації даних з підсиленою функцією захисту, а саме з використанням ключа при здійсненні безпосередньо стиснення. Сформульовано умови для коректної роботи алгоритму та результати, що визначають його властивості. Досліджено часову та ємнісну складність алгоритму стиснення з ключем.
      1.  Проведено експерименти та обчислення, які демонструють стійкість побудованого алгоритму як криптографічного засобу.
        1.  Проведено порівняльний аналіз побудованого алгоритму стиснення з ключем з відомими методами симетричного шифрування та алгоритмами стиснення.
        2.  Розроблені алгоритми для стиснення та відновлення двійкових кодів та бінарних зображень і досліджено їх властивості.
        3.   Побудована програмна оболонка ESZ1 для розробки експертних систем, які використовують алгоритм стиснення з ключем, що дозволяє стискати інформацію, виконувати зворотну операцію та знаходити необхідні параметри ефективності стиснення інформації.

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

ПРАЦЯХ

  1.  Глинчук Л. Я. Алгоритм криптографічного стиснення інформації за допомогою дерева Штерна-Броко // Проблеми програмування. – 2008. − № 2-3. – С. 575-578.
  2.  Глинчук Л. Я. Дослідження стійкості алгоритму криптографічного стиснення, побудованого на основі дерева Штерна-Броко // Вісник Донецького національного університету, Серія А: Природничі науки. – 2008. Вип. 2. – С. 551-555.
  3.  Глинчук Л. Я. Застосування алгоритму криптографічного стиснення до бази знань експертної системи // Збірник наукових праць “Питання прикладної математики і математичного моделювання 2009”. – 2009. − С. 109-118.
  4.  Глинчук Л. Я. Оцінка ефективності алгоритмів криптографічного стиснення побудованих на основі дерева Штерна-Броко // Проблеми програмування. – 2009. – № 4.С. 71-76.

  1.  Глинчук Л. Я. Криптографічне стиснення з використанням дерева Штерна-Броко в експертних системах // Четверта Міжнародна конференція “Теоретичні та прикладні аспекти побудови програмних систем ” – TAAPSD’2007. 2007. Бердянськ. – С. 148-151.
  2.  Глинчук Л. Я. Про застосування алгоритму криптографічного стиснення до бази знань експертної системи // VI  Міжнародна науково-практична конференція “Математичне та програмне забезпечення інтелектуальних систем (MPZIS-2008)”. 2008. Дніпропетровськ. – С. 87-88.
  3.  Глинчук Л. Я. Про застосування одного алгоритму до бази знань експертної системи з метою її захисту // Міжнародна науково-практична конференція “Сучасні засоби та технології розроблення інформаційних систем”. Збірник наукових статей. 2008. Харків. − № 15 – С. 43.

АНОТАЦІЯ

Глинчук Л.Я., Алгоритми архівації на основі системи числення Штерна-Броко. – рукопис.

Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.03 – математичне та програмне забезпечення обчислювальних машин і систем – Київський національний університет імені Тараса Шевченка, Київ, 2010.

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

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

Розглянуті результати роботи алгоритму стиснення з ключем: “чисте” стиснення, стиснення з ключем та шифрування (відсутність стиснення). Розмір вхідного блоку для алгоритму стиснення з ключем може коливатися, в загальному, вхідна послідовність повинна містити  елементів. Алгоритм працює починаючи з . Довжина ключа залежить від способу побудови ключа та програмної реалізації.

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

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

Для оцінки ефективності алгоритму стиснення двійкових послідовностей та бінарних зображень розглянуті його характеристики та виконані розрахунки середнього коефіцієнта стиснення для кодів довжиною 8, 16, 32 розрядів з різною кількістю одиниць.

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

Ключові слова: алгоритм стиснення, коефіцієнт стиснення, ключ, система числення, дерево Штерна-Броко.

АННОТАЦИЯ

Глынчук Л.Я., Алгоритмы архивации на основе системы исчисления Штерна-Броко. – рукопись.

Диссертация на соискание ученой степени кандидата физико-математических наук по специальности 01.05.03 – математическое и программное обеспечение вычислительных машин и систем – Киевский национальный университет имени Тараса Шевченко, Киев, 2010.

Диссертация посвящена актуальным вопросам разработки алгоритмов сжатия информации. Показана актуальность создания таких алгоритмов для информации реального времени. Исследованы общие вопросы теории сжатия.  

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

Предложен способ построения хеш-функції с операциями, которые выполняются в одну сторону.

Рассмотрены результаты работы алгоритма сжатия с ключом: "чистое" сжатие, сжатие с ключом и шифровка (отсутствие сжатия). То есть, 

  1.  сжатая строка < входной строки – состоялось так называемое чистое сжатие, без использования ключа;
  2.  если ключ + сжатая строка < входной последовательности – сжатие состоялось (возможное);
  3.  если ключ вместе с сжатой строкой ≥ входной – сжатие не состоялось.

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

Особенность алгоритма заключается в присутствии элемента защиты – ключа, который не задается пользователем, а создается во время преобразования информации и позволяет корректировать эти преобразования.

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

Для оценки эффективности алгоритма сжатия двоичных последовательностей и бинарных изображений рассмотрены его характеристики и выполнены расчеты среднего коэффициента сжатия для кодов длиной 8, 16, 32 разрядов с разным количеством единиц.

Рассмотренный алгоритм позволяет сжимать любые двоичные последовательности длиной  и может использоваться для уменьшения кодовой избыточности.

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

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

На основе новых разработанных алгоритмов построено программное обеспечение, способное сжимать текстовые файлы и пересматривать статистику результатов.

Построена программная оболочка ESZ 1.0, для создания экспертной системы в визуальной среде программирования со встроенным программным продуктом, что позволяет сжимать текстовую информацию и выполнять некоторые функции защиты информации.

Ключевые слова: алгоритм сжатия, коэффициент сжатия, ключ, система исчисления, дерево Штерна-Броко.

ABSTRACT

Glynchyk L. I.: Algorithms of archiving are on the basis of scale of notation of Shterna-Broko.The manuscript.

The dissertation submitted for the Candidate Degree in Physics and Mathematics by specialty 01.05.03 – mathematical support and software of computer systems – National Taras Shevchenko University of Kyiv, 2010.

The dissertation is devoted to actual questions of the information compression algorithms development. The actuality creation of such algorithms is shown for the real time information. The information compression general questions are investigated.

Modern compression and renewal algorithms are developed and realized for the text information, binary chain and binary image. The Shtern-Broko sсale of notation (tree) is laid on the algorithms foundation.

The algorithm of compression work results are observed with a key: “clean” compression, compression with a key and encapsulation (absence of compression). Entrance block dimensions for algorithm compression with a key may vary, where the entrance succession must contain elements. The algorithm works starting with . The key length depends on key structure way and program realization.

To estimate the effectiveness of the binary chain compression algorithm and the binary image its characteristics are observed and the calculation of the average compression coefficient for codes with a length 8, 16, 32 digits with different number units are executed.

ESZ 1.0 casing for the expert system forming in the visual programming surrounding with the program product add-in is formed, which allows to compress the text information, to review results statistic and to carry out some information deference functions.

Key words: algorithm of compression, compression coefficient, key, scale of notation, Shtern-Broko tree.


 

А также другие работы, которые могут Вас заинтересовать

2244. Інженерний аналіз характеристик надійності машин та обладнання 1.04 MB
  Коротка характеристика і умови роботи агрегату (вузла) в цілому та основних видів сполучень. Характеристика конструктивно-технологічних особливостей зміцнювальної (відновлювальної) деталі. Аналіз причин, обґрунтування, визначення та описання провідного виду зношення сполученої поверхні деталі. Визначення статистичних характеристик повного ресурсу сполучення за вихідною масовою інформацією.
2245. Основы религиоведения 1.52 MB
  Религия как общественное явление. Происхождение религии и ее ранние формы. Социальное учение мировых религий. Государственно-церковные отношения. Эволюция религии в современном мире.
2246. Проектирование подстанции 1.29 MB
  Выбор аппаратуры и токоведущих частей подстанции. Расчет максимальных рабочих токов основных присоединений подстанции. Выбор и проверка аппаратуры и токоведущих частей. Расчетная схема подстанции. Проверка токоведущих частей, изоляторов и аппаратуры по результатам расчёта токов к.з.
2247. Расчет симметричных и несимметричных коротких замыканий в электроэнергетической системе 695.23 KB
  Расчет реактивных сопротивлений в именованных единицах приближенным методом. Расчет реактивных сопротивлений в относительных единицах точным методом. Построение векторных диаграмм токов и напряжений. Расчет симметричных КЗ в точке K4. Построение векторных диаграмм токов и напряжений
2248. Эффективность разработки электронного изделия 530.79 KB
  Определение затрат на материалы и комплектующие изделия. Определение основных показателей технологичности. Технико-экономические расчёты по определению ресурсов. Разработка сетевого графика технической подготовки производства нового изделия. Определение технико-экономических показателей производства.
2249. Разработка организационной структуры управления объектом сферы услуг, как целеустремленной системой на примере блинной Солнцепек 143.39 KB
  Теоретические основы методологии системного анализа. Системный анализ и моделирование объекта исследования. Предложения по совершенствованию устойчивости функционирования системы.
2250. Проектирование понизительной подстанции электроснабжения электрифицированной железной дороги. 1.13 MB
  Распределительное устройство 110 кВ промежуточной транзитной подстанции. Составление расчетной схемы и схемы замещения. Расчёт токов короткого замыкания. Выбор основного оборудования и токоведущих элементов подстанции. Выбор устройств защиты от перенапряжения.
2251. Сервисный центр по ремонту и обслуживанию офисной техники с использованием средств Microsoft Access 991.23 KB
  Описание бизнес-процесса при помощи методологии структурного анализа и проектирования (SADT). Создание форм с помощью конструктора. Структура таблицы и типы данных.
2252. Мероприятие: В стране невыученных уроков 19.84 KB
  Внеклассное мероприятие посвященное ко дню учителя, отображающее учеников которые не хотят учить уроки.