Дослідження та удосконалення методу стиснення даних текстових файлів

САЛОГУБ, Ілля
Please use this identifier to cite or link to this item: https://er.chdtu.edu.ua/handle/ChSTU/8670
Title:	Дослідження та удосконалення методу стиснення даних текстових файлів
Authors:	МИРОНЮК, Тетяна САЛОГУБ, Ілля
Keywords:	КОМПРЕСІЯ ДАНИХ;СТИСНЕННЯ БЕЗ ВТРАТ;ПОСЛІДОВНІСТЬ ФІБОНАЧЧІ;ПРОГРАМНА РЕАЛІЗАЦІЯ;МЕТОД СТИСНЕННЯ ДАНИХ
Issue Date:	2023
Abstract:	Досліджувана тема кваліфікаційної роботи магістра є актуальною через недостатній розвиток технологій збереження даних на фізичних носіях у порівнянні зі збільшенням обсягу даних в мережі Інтернет. Метою виконання кваліфікаційної роботи на здобуття освітнього ступеня «магістр» є дослідження та удосконалення методу стиснення даних текстових файлів. Об’єктом дослідження є ефективність стиснення даних текстових файлів, під час компресії даних розробленою бібліотекою Предметом метод стиснення даних текстових файлів. Основним методом дослідження є аналіз недоліків стандартного методу стиснення на базі кодів Фібоначчі та створення рішення для подолання цих недоліків при стисненні реальних даних. Практичним результатом виконання даної кваліфікаційної роботи магістра є покращений метод стиснення даних на основі кодів Фібоначчі та розроблена програмна реалізація у вигляді бібліотеки для мови C#, яка містить в собі методи для компресії даних стандартним та вдосконаленим методом на основі кодів Фібоначчі. Основну увагу приділено збільшенню ефективності стиснення реальних даних. Проаналізовано основні недоліки стандартного методу та запропоновано часткове рішення проблем у вигляді вдосконаленого методу. Розроблена програмна реалізація являє собою бібліотеку до мови програмування C#. Реалізована бібліотека містить набір функцій для виконання компресії файлів будь-якого типу стандартним чи вдосконаленим методом. Також бібліотека має ряд тестів, які перевіряють коректність роботи окремих елементів алгоритму, а також всього алгоритму в цілому. Весь код програмної реалізації виконаний в ООП стилі об’єктно- орієнтованого програмування для забезпечення легкості вдосконалення та масштабування бібліотеки. Загальний обсяг роботи становить 109 сторінок. У кваліфікаційній роботі 18 рисунків, 21 таблиць. Для виконання роботи використано 21 літературне джерело.
URI:	https://er.chdtu.edu.ua/handle/ChSTU/8670
Appears in Collections:	123 Комп’ютерна інженерія (Системне програмування)
Files in This Item:
File	Description	Size	Format
1_ТИТУЛКА__Салогуб_ДРУК-merged.pdf Restricted Access		5.68 MB	Adobe PDF	View/Open Request a copy
Show full item record
Extracted text
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
ЧЕРКАСЬКИЙ ДЕРЖАВНИЙ ТЕХНОЛОГІЧНИЙ УНІВЕРСИТЕТ
ФАКУЛЬТЕТ ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ І СИСТЕМ
КАФЕДРА ІНФОРМАЦІЙНОЇ БЕЗПЕКИ ТА КОМП’ЮТЕРНОЇ
ІНЖЕНЕРІЇ
Пояснювальна записка
до кваліфікаційної роботи магістра
на тему: «Дослідження та удосконалення методу
стиснення даних текстових файлів»
ЧДТУ.232276.004 ПЗ
Виконав: студент 2 курсу, групи МСП-2206
спеціальності 123 – Комп’ютерна інженерія
за освітньою програмою – Системне
програмування
Ілля САЛОГУБ
Керівник
к.т.н., доцент Тетяна МИРОНЮК
Н. контроль
Світлана ГРЕСЬКО
Рецензент
начальник відділу персоналу, к.т.н., доцент
Віталій ЗАЖОМА
«ЗАХИСТ ДОЗВОЛЯЮ»
Завідувач кафедри ІБ та КІ
д.т.н., професор __________ Віра БАБЕНКО
Черкаси 2023 року
Форма № Н-9.01
Черкаський державний технологічний університет
Факультет інформаційних технологій і систем
Кафедра інформаційної безпеки та комп‘ютерної інженерії
Освітньо-кваліфікаційний рівень Магістр
Спеціальність 123 – Комп’ютерна інженерія
Освітня програма Системне програмування
«ЗАТВЕРДЖУЮ»
Завідувач кафедри _____ Володимир РУДНИЦЬКИЙ
«10» жовтня 2023 року
ЗАВДАННЯ
на кваліфікаційну роботу магістра студенту
Салогубу Іллі Валентиновичу
(прізвище, ім‘я, по батькові)
1. Тема роботи Дослідження та удосконалення методу стиснення даних
текстових файлів
Керівник роботи Миронюк Т.В., к.т.н., доцент
(прізвище, ім’я, по батькові, науковий ступінь, вчене звання)
затверджені наказом університету від «06» жовтня 2023 р. № 267/04
2. Строк подання студентом роботи
3. Вихідні дані до роботи:
1. Метод компресії даних: стиснення даних на базі кодів Фібоначчі
2. Типи підтримуваних даних: текстові файли
3. Платформа: Windows 7, Windows 8, Windows 10
4. Мова програмування: C#
5. Інтегроване середовище розробника: Visual Studio 2022
4. Зміст розрахунково-пояснювальної записки (перелік питань, що їх належить розробити):
Вступ
Розділ 1 Характеристика методу стиснення даних текстових файлів та постановка задачі
Розділ 2 Удосконалення методу стиснення даних текстових файлів
Розділ 3 Обрання технології розробки та мови програмування програмної реалізації
Розділ 4 Розробка програмної реалізації удосконаленого методу стиснення текстових даних
Висновки
Перелік умовних скорочень; Список використаних джерел
Додатки
5. Перелік графічного матеріалу (з точним зазначенням обов’язкових креслень, плакатів):
1. Специфікація
2. Текст програми
3. Інструкція системного програміста
6. Консультанти розділів роботи
Підпис, дата
Розділ Прізвище, ініціали та
посада завдання видав завдання прийняв
консультанта
7. Дата видачі завдання 10 жовтня 2023 року
КАЛЕНДАРНИЙ ПЛАН
Строк
№ з/п Назва етапів кваліфікаційної роботи магістра виконання Примітка
етапів роботи
1 Збір матеріалу 10.10 – 14.10 виконано
2 Обробка матеріалу 15.10 – 23.10 виконано
3 Обґрунтування актуальності виконання 24.10 – 30.10 виконано
досліджень
4 Оцінка стану проблеми, виокремлення виконано
дослідницьких задач, постановка задачі 01.11 – 05.11
дослідження
5 Покращення методу та аналіз результатів 06.11 – 12.11 виконано
6 Програмна реалізація 13.11 – 23.11
7 Оформлення результатів в пояснювальну записку 24.11 – 30.11 виконано
8 Подання роботи на відгук та рецензування 01.12.20 виконано
9 Захист випускної роботи 06.12.20
Студент-магістрант ____________________________ Ілля САЛОГУБ
(підпис)
Керівник роботи ____________________________ Тетяна МИРОНЮК
(підпис)
АНОТАЦІЯ
Досліджувана тема кваліфікаційної роботи магістра є актуальною
через недостатній розвиток технологій збереження даних на фізичних носіях
у порівнянні зі збільшенням обсягу даних в мережі Інтернет.
Метою виконання кваліфікаційної роботи на здобуття освітнього
ступеня «магістр» є дослідження та удосконалення методу стиснення даних
текстових файлів.
Об’єктом дослідження є ефективність стиснення даних текстових
файлів, під час компресії даних розробленою бібліотекою
Предметом метод стиснення даних текстових файлів.
Основним методом дослідження є аналіз недоліків стандартного
методу стиснення на базі кодів Фібоначчі та створення рішення для
подолання цих недоліків при стисненні реальних даних.
Практичним результатом виконання даної кваліфікаційної роботи
магістра є покращений метод стиснення даних на основі кодів Фібоначчі та
розроблена програмна реалізація у вигляді бібліотеки для мови C#, яка
містить в собі методи для компресії даних стандартним та вдосконаленим
методом на основі кодів Фібоначчі. Основну увагу приділено збільшенню
ефективності стиснення реальних даних. Проаналізовано основні недоліки
стандартного методу та запропоновано часткове рішення проблем у вигляді
вдосконаленого методу.
Розроблена програмна реалізація являє собою бібліотеку до мови
програмування C#. Реалізована бібліотека містить набір функцій для
виконання компресії файлів будь-якого типу стандартним чи вдосконаленим
методом. Також бібліотека має ряд тестів, які перевіряють коректність
роботи окремих елементів алгоритму, а також всього алгоритму в цілому.
Весь код програмної реалізації виконаний в ООП стилі об’єктно-
орієнтованого програмування для забезпечення легкості вдосконалення та
масштабування бібліотеки.
Загальний обсяг роботи становить 109 сторінок. У кваліфікаційній
роботі 18 рисунків, 21 таблиць. Для виконання роботи використано 21
літературне джерело.
Ключові слова: КОМПРЕСІЯ ДАНИХ, СТИСНЕННЯ БЕЗ ВТРАТ,
ПОСЛІДОВНІСТЬ ФІБОНАЧЧІ, ПРОГРАМНА РЕАЛІЗАЦІЯ, МЕТОД
СТИСНЕННЯ ДАНИХ.
ANNOTATION
The research topic of the master's qualification work is relevant due to the
insufficient development of data storage technologies on physical media in
comparison with the increase in the amount of data on the Internet.
The purpose of the qualification work for the master's degree is to research
and improvement of the method of data compression of text files.
The object of the study is the efficiency of data compression of text files
during data compression by the developed library.
The subject of the study is a method of compression text file data.
The main method of research is to analyze the shortcomings of the standard
method of compression based on Fibonacci codes and create a solution to
overcome these shortcomings by compressing real data.
The practical result of this master's work is an improved a method of data
compression on based the Fibonacci’s codes and developed a software
implementation in the form of a library for the C # language, which includes
methods for data compression by standard and advanced methods on based the
Fibonacci’s codes. The focus is on increasing the compression efficiency of real
data. The main shortcomings of the standard method are analyzed and a partial
solution of the problems in the form of an improved method is proposed.
The software implementation was developed for the C # programming
language. The implemented library contains a set of functions for performing
compression of files of any type by standard or advanced method. The library also
has a number of tests that verify the correct operation of individual elements of the
algorithm, as well as the whole algorithm as a whole. The entire software
implementation code is made in the OOP style of object-oriented programming to
ensure ease of improvement and scaling of the library.
The total volume of the work is 109 pages. In the qualifying work 18
figures, 21 tables. 21 literary sources were used to perform the work.
Keywords: DATA COMPRESSION, LOSS-FREE COMPRESSION,
FIBONACHI SEQUENCE, SOFTWARE IMPLEMENTATION, DATA
COMPRESSION METHOD.
2
ЗМІСТ
ВСТУП..................................................................................................................4
РОЗДІЛ 1 ХАРАКТЕРИСТИКА МЕТОДУ СТИСНЕННЯ ДАНИХ
ТЕКСТОВИХ ФАЙЛІВ ТА ПОСТАНОВКА ЗАДАЧІ....................................8
1.1 Визначення актуальності дослідження та характеристики принципу
стиснення даних.............................................................................................8
1.2 Алгоритми стиснення даних.................................................................16
1.3 Аналіз загального принципу стандартного методу на основі коду
Фібоначчі......................................................................................................21
1.4 Дослідження способу генерації кодованої таблиці для стандартного
методу...........................................................................................................22
1.5 Дослідження та визначення основних недоліків стандартного методу
стиснення даних...........................................................................................29
1.6 Постановка задачі на виконання...........................................................35
1.7 Висновки до розділу 1...........................................................................37
РОЗДІЛ 2 УДОСКОНАЛЕННЯ МЕТОДУ СТИСНЕННЯ ДАНИХ
ТЕКСТОВИХ ФАЙЛІВ.....................................................................................39
2.1 Розширення таблиці кодів стандартного методу на базі коду
Фібоначчі......................................................................................................39
2.2 Додання виключень в таблицю кодів для удосконаленого методу
стиснення текстових даних.........................................................................42
2.3 Висновки до розділу 2...........................................................................46
РОЗДІЛ 3 ОБРАННЯ ТЕХНОЛОГІЇ РОЗРОБКИ ТА МОВИ
ПРОГРАМУВАННЯ ПРОГРАМНОЇ РЕАЛІЗАЦІЇ........................................47
3.1 Технологія Microsoft .Net/C#.................................................................47
3.2 Поняття об’єктно-орієнтоване програмування (ООП)........................49
3.3 Висновки до розділу 3...........................................................................54
3
РОЗДІЛ 4 РОЗРОБКА ПРОГРАМНОЇ РЕАЛІЗАЦІЇ УДОСКОНАЛЕНОГО
МЕТОДУ СТИСНЕННЯ ТЕКСТОВИХ ДАНИХ...........................................55
4.1 Проектування моделі класів удосконаленого методу стиснення
текстових файлів..........................................................................................55
4.2 Розробка класів для зберігання даних..................................................56
4.3 Розробка класів генерації таблиці кодування та обрахунку частоти
символів........................................................................................................59
4.4 Реалізація сервісу стиснення текстового файлу та класів стиснення
текстових даних...........................................................................................65
4.5 Реалізація тестових рішень для перевірки ефективності
удосконаленого методу стиснення текстових файлів...............................68
4.6 Підключення реалізованої бібліотеки..................................................70
4.6.1 Застосування методів бібліотеки...........................................72
4.6.2 Застосування тестів в процесі тестування бібліотеки..........73
4.7 Висновки до розділу 4...........................................................................74
ВИСНОВКИ.......................................................................................................76
ПЕРЕЛІК СКОРОЧЕНЬ ТА УМОВНИХ ПОЗНАЧЕНЬ................................78
СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ..........................................................79
ДОДАТКИ:
А – 482.ЧДТУ.32276-01 Дослідження та удосконалення методу
стиснення даних текстових файлів
4
ВСТУП
Зберігання даних на електронних носіях насьогодні витісняє інші
способи збереження даних. Постійний розвиток комп’ютерної техніки,
технологій передачі та зберігання даних зумовило перенесення персональних
даних користувачів на електронні носії або хмарні сховища [19, 21].
Паралельно до цього, відповідно до розвитку кількість даних, що
зберігаються кожним користувачем збільшується щоденно [18] відносно
збільшення розміру файлів.
Відповідно збільшення розміру файлів різноманітних форматів (фото,
відео, аудіо тощо) призвело до покращення якості даних файлів (поліпшення
роздільної здатності, бітрейту тощо). Але не дивлячись на розвиток
електронних носіїв даних співвідношення вільного та зайнятого місця на
електронних носіях, при цьому, не покращується.
А тому, для збереження місця на електронних носіях досить давно
застосовують компресію даних. «Компресія даних» (стиснення даних) (Data
compression) [7] являється алгоритмічним перетворенням даних, що
виконується з метою зменшити об'єму місця, яке займають дані.
Використовується для більш раціонального застосування пристроїв
зберігання та передачі даних. Зворотну до компресії даних процедуру
називають відновленням даних (декомпресією, розпакуванням).
Стиснення даних сформоване на усуненні надмірності, яка може
міститися у вихідних даних [15]. Найпростішим прикладом надмірності може
бути повторення фрагментів в тексті (наприклад, слів машинної або
природної мови). Схожа надмірність здебільшого усувається заміною
повторюваної послідовності на посилання із вже закодованим фрагментом із
вказанням його довжини. Другий вид надмірності відповідає тому, що деякі
значення даних, що підлягали стисненню, зустрічаються набагато частіше
5
інших. Відповідно скорочення обсягу даних можна досягти за рахунок заміни
даних, які часто зустрічаються, короткими кодовими словами, а тих, що
рідше – довгими кодовими словами, тобто, застосувати так зване ентропійне
кодування. Компресія даних, які не володіють властивістю надмірності
(наприклад, білий шум або випадковий сигнал, зашифровані повідомлення),
принципово неможлива без втрат.
Актуальність теми. У даний час є актуальною проблема зменшення
обсягу даних, які зберігаються та передаються. Незважаючи на ефективність
розвитку технологій зберігання та передачі даних дані послуги все ж
залишаються дороговартісними. А це означає, що за зберігання або передачу
файлів покращеної якості користувачеві доведеться заплатити більше, аніж
при передачі чи зберіганні файлів у гіршій якості. При застосуванні
стиснення (компресії) даних з’являється можливість зменшення розміру
даних, що передаються чи зберігаються, що відповідно, принесе значну
економічну вигоду, і при цьому зменшить навантаження на Інтернет ресурси.
Відповідно до викладеного вище можна зробити висновок про те, що
процес зменшення об’єму інформації, яку необхідно зберігати або
передавати являється важливим питанням сьогодення. Компресія (стиснення)
даних частково вирішує дане питання, яке не є ідеально дослідженим.
Необхідність подальшого розвитку цієї технології визначається постійною
появою нових або вдосконалених алгоритмів компресії даних.
Отже, можна визначити, що тема кваліфікаційної роботи магістра
«Дослідження та удосконалення методу стиснення даних текстових файлів»
являється важливою і актуальною на теперішній час.
Мета і завдання дослідження. Метою дослідження кваліфікаційної
роботи магістра є дослідження та удосконалення ефективності стиснення
даних текстових файлів.
Для досягнення поставленої мети були сформульовані і вирішенні такі
завдання:
6
- провести дослідження та аналіз ефективності методу стиснення
(компресії) текстових файлів застосовуючи коди Фібоначчі [11];
- визначити та дослідити основні переваги та недоліки методу
стиснення текстових даних для унікальних символів з різною частотою
розподілу;
- на основі визначених недоліків удосконалити метод підвищення
ефективності стиснення текстових файлів;
- розробити у вигляді бібліотеки для мови програмування С#
програмну реалізацію (надалі ПР) стандартного та удосконаленого методу
стиснення текстових файлів;
- оцінити ефективність стандартного та вдосконаленого методу
стиснення даних на основі отриманих результатів роботи бібліотеки.
Об’єкт дослідження – ефективність стиснення даних текстових
файлів, під час компресії даних розробленою бібліотекою.
Предмет дослідження – метод стиснення даних текстових файлів [9].
Методи дослідження. Під час удосконалення методу стиснення даних
текстових файлів та програмної реалізації у вигляді бібліотеки застосовується
математичний апарат статистики, систем числення, теорії інформації, методів
дискретної математики, алгебри та теорії груп, а також теорія та закони
алгебри логіки.
Наукова новизна одержаних результатів. У процесі дослідження та
вирішення поставлених завдань у роботі отримано наступні результати:
1) проведено удосконалення методу стиснення даних застосовуючи
коди Фібоначчі, що надало можливість підвищити ефективність компресії
даних, зокрема, текстових файлів;
2) реалізовано програмне рішення у вигляді бібліотеки, що, в свою
чергу, надає можливість використовувати стандартний та удосконалений
метод стиснення даних використовуючи коди Фібоначчі, в процесі розробки
програмного забезпечення для стиснення даних, зокрема, текстових файлів.
7
Практичне значення отриманих результатів. Практична цінність
проведеного дослідження полягає у удосконалені методу стиснення даних
текстових файлів та реалізації алгоритму у вигляді бібліотеки для мови
програмування C#.
Публікації. Основні результати дослідження даної кваліфікаційної
роботи магістра доповідалися та обговорювалися на:
другій Міжнародній науково-практичній Інтернет-конференції «Іновації
та перспективні шляхи розвитку інформаційних технологій (ІПШРІТ-2023)»,
Черкаси, 6 грудня 2023 р.
Структура і обсяг роботи. Робота складається із вступу, чотирьох
розділів, висновків, списку скорочень, додатків та списку використаної
літератури. Загальний обсяг кваліфікаційної роботи магістра 112 сторінок.
Основний зміст викладений на 81 сторінці, у тому числі 21 таблиця та 18
рисунків. Список використаних джерел містить 21 найменування.
8
РОЗДІЛ 1 ХАРАКТЕРИСТИКАМЕТОДУ СТИСНЕННЯ ДАНИХ
ТЕКСТОВИХ ФАЙЛІВ ТА ПОСТАНОВКА ЗАДАЧІ
1.1 Визначення актуальності дослідження та характеристики
принципу стиснення даних
Компресія (стиснення) даних використовується для скорочення часу
передачі даних. Враховуючи той факт, що на стиснення даних передавальна
сторона витрачає додатковий час, до якого необхідно ще додати відповідні
витрати часу на декомпресію (розпаковування) цих даних приймальною
стороною, то користь від скорочення часу на передачу стиснених даних часто
буває помітною лише для низькошвидкісних каналів. Таким порогом
швидкості для сучасної апаратури є близько 64 Кбіт/с. Багато програмних та
апаратних засобів комп’ютерної мережі здатні виконувати динамічне
стиснення даних на відміну від статичного – коли дані попередньо
стискаються (наприклад, при використанні архіваторів), а вже потім
надсилаються до мережі [7, 18].
На практиці може бути застосовано ряд алгоритмів компресії, кожний з
який використовується до визначеного типу даних. Поодинокі модеми дають
можливість розробки адаптивної компресію, використовуючи яку в
залежності від даних, що передаються, обирається деякий алгоритм
компресії. Розглянемо деякі із загальних алгоритмів стиснення (компресії)
даних.
Десяткове упакування. Дані складаються тільки з чисел, і суттєву
економію можна отримати шляхом зменшення кількості біт, що
використовується на цифру, з 7 до 4, при цьому застосовуючи просте
двійкове кодування десяткових цифр взамін коду ASCII. Дослідження
таблиці ASCII показало, що старші три біти усіх кодів десяткових цифр
вміщують комбінацію 011. Якщо всі дані в інформаційному кадрі
9
складаються з десяткових цифр, то можна істотно скоротити довжину кадру,
помістивши у заголовок кадру відповідний керуючий символ [7].
Відносне кодування. Альтернативою десятковому упакуванню під час
передачі числових даних між послідовними цифрами з невеликими
відхиленнями є передача лише цих відхилень спільно з відомим опорним
значенням. Даний метод використовується, в тому числі, у методі цифрового
кодування голосу ADPCM (Adaptive differential pulse-code modulation), що
передає в кожному такті тільки різницю між сусідніми вимірами голосу [18].
Символьне подавлення. Часто дані, що передаються, містять велике
число повторюваних байтів. Наприклад, під час передачі чорно-білого
зображення чорні поверхні будуть утворювати велику кількість нульових
значень, а найбільше освітлені ділянки зображення - велику кількість байт,
які складаються з усіх 1. Передавач сканує послідовність байт, що
передається і, у випадку, коли виявляє послідовність із трьох або більше
однакових байт, заміняє послідовність спеціальною трьохбайтовою
послідовністю, у якій вказується значення байту, кількість його повторень, а
також спеціальний керуючий символ, що відзначає початок даної
послідовності [10].
Коди змінної довжини. У цьому методі кодування враховується той
факт, що не усі символи в кадрі, що передаються, зустрічаються з однаковою
частотою. А тому у великій кількості схемах кодування коди символів, які
часто зустрічаються міняють кодами меншої довжини, а коди, що
зустрічаються рідше - кодами більшої довжини. Такий вид кодування
називається статистичним кодуванням. Враховуючи той факт, що символи
мають різну довжину, то під час передачі кадру можлива тільки біт-
орієнтована передача.
Під час використання статистичного кодування коди обираються так,
щоб при аналізі послідовності біт можливо було однозначно визначити
відповідність певної порції біт тому або іншому символу забороненої
10
комбінації біт. У випадку, якщо обрана послідовність біт є забороненою
комбінацією, то до неї необхідно додати ще один біт та повторити аналіз.
Однозначно, нерівномірне кодування найефективніше у випадку, коли
нерівномірність розподілу частот символів, що передаються, досить значна,
як і під час передачі довгих текстових рядків. Під час передачі двійкових
даних, наприклад, кодів програм, таке кодування малоефективне, оскільки
восьмибітові коди при цьому розподілені практично рівномірно.
Одним з найрозповсюдженіших алгоритмів, на основі яких будуються
нерівномірні коди, являється алгоритм Хафмана, що дозволяє будувати коди
автоматично, на основі відомих частот символів. Також існують адаптивні
модифікації методу Хафмана, що надають можливість будувати дерево кодів
„на льоту”, по мірі надходження даних від джерела [7, 18].
Більшість моделей комунікаційного обладнання, такі як модеми,
комутатори, мости та маршрутизатори, підтримують протоколи динамічної
компресії, що надає можливість скоротити обсяг інформації, яка
передається, у чотири, а інколи й у вісім разів. У таких випадках кажуть, що
протокол забезпечує коефіцієнт стиснення 1:4 чи 1:8. Наявні стандартні
протоколи компресії, наприклад, V.42bis, a також велике число
нестандартних, фірмових протоколів. Реальний коефіцієнт компресії
(стиснення) залежить від типу даних, що передається, наприклад, графічні і
текстові дані зазвичай стискаються добре, а ось коди програм - гірше [10].
На сьогоднішній день кількість інформації, що зберігається на
електронних носіях весь час збільшується, а тому, проблема нестачі вільного
місця є розповсюдженою проблемою [18]. З розвитком технологій
електронних носіїв розвиваються також і технології для зберігання та
форматування даних.
Також не потрібно забувати про дані, які передаються. Наприклад,
об’єм щомісячного трафіку у 2011-2016 роках збільшився майже в 7 разів, а
саме, з 0,5 ексабайт (далі Еб) до 3,5 Еб. Результати такого зростання наведено
на рисунку 1.1. Велика частина даного трафіку зберігається та не видаляється
11
протягом багатьох років, що в свою чергу, призводить до накопичування
даних.
Рисунок 1.1 – Кількість трафіку в місяць в Еб
Натомість обсяг жорстких дисків за даний період зріс з 1500 Гб до 4500
Гб [12], тобто в 3 рази. Результати такого зростання наведено на рисунку 1.2.
Звідси можна зробити висновок, щоб зберігати таку кількість трафіку
потрібно весь час збільшувати число жорстких дисків, що не є можливим
завжди.
Рисунок 1.2 – Середній показник обсягу одного жорсткого диску
12
Одним із способів вирішення визначених проблем являється
зменшення обсягу трафіку, що можливе під час використання стиснення
(компресії) даних. За допомогою стиснення даних можна зменшити розмір
даних, що передаються або зберігаються, що в свою чергу несе значну
економічну вигоду при цьому зменшуючи навантаження на інтернет ресурси.
Одним із таких ефективних методів стискання текстових повідомлень
та невеликих файлів являється метод компресії на основі кодів Фібоначчі, що
реалізується за рахунок генерації кодів змінної довжини. Але даний метод
має недоліки, що відображаються під час стискання файлів великих розмірів
з відносно рівномірним розподілом частоти символів. Враховуючи даний
недолік удосконалений метод повинен підвищувати ефективність стиснення
текстових файлів великих розмірів та файлів середнього розміру, що
забезпечить ефективне застосування даного методу під час стиснення
текстових файлів.
Тема, що досліджується, являється досить актуальною, оскільки метод
стиснення даних, що розглядається, тільки розпочинає свій розвиток, а його
удосконалення може підвищити ефективність компресії текстових файлів.
Удосконалений метод повинен зменшити визначені недоліки оригінального
методу, а також може бути основою подальшого удосконалення методу в
цілому.
Для подальшого дослідження та удосконалення обраного методу
розглянемо види стиснення даних.
Стиснення даних є алгоритмічне перетворення даних, що виконується з
метою зменшення займаного ними об'єму. Даний процес застосовується, щоб
більш раціонально використовувати пристрої зберігання та передачі даних.
Зворотна процедура стиснення даних називається відновленням даних
(декомпресією, розпакуванням).
Стиснення даних сформоване на усуненні надмірності, яка може
міститися у вихідних даних [15]. Найпростішим прикладом надмірності може
бути повторення фрагментів в тексті (наприклад, слів машинної або
13
природної мови). Схожа надмірність здебільшого усувається заміною
повторюваної послідовності на посилання із вже закодованим фрагментом із
вказанням його довжини. Другий вид надмірності відповідає тому, що деякі
значення даних, що підлягали стисненню, зустрічаються набагато частіше
інших. Відповідно скорочення обсягу даних можна досягти за рахунок заміни
даних, які часто зустрічаються, короткими кодовими словами, а тих, що
рідше – довгими кодовими словами, тобто, застосувати так зване ентропійне
кодування. Компресія даних, які не володіють властивістю надмірності
(наприклад, білий шум або випадковий сигнал, зашифровані повідомлення),
принципово неможлива без втрат [12].
Стиснення даних без втрат надає можливість повністю відновити
вихідне повідомлення, оскільки не зменшує в ньому кількості інформації, не
зважаючи на зменшення довжини.
В основі усіх способів стиснення даних лежить модель надмірності. Це
означає, що для стиснення даних застосовуються деякі апріорні відомості про
те, якого типу дані стискаються. Не знаючи відповідні відомості про
джерело, неможливо зробити жодних припущень щодо перетворення, яке
надало б можливість зменшити обсяг повідомлення. Методи, які дозволяють
на основі вхідних даних змінити модель надмірності інформації, називаються
адаптивними. Вузькоспеціалізовані алгоритми зазвичай являються
неадаптивними, а тому застосовуються для роботи з даними, які мають добре
визначені та незмінні характеристики. Більша частина доволі універсальних
алгоритмів являються в тій або іншій мірі адаптивними [12].
Усі методи стиснення даних поділяться на два основних класи:
- стиснення без втрат;
- стиснення із втратами.
Під час використання стиснення даних без втрат можливе повне
відновлення вихідних даних. Стиснення даних з втратами надає можливість
відновити дані із спотвореннями, здебільшого несуттєвими з точки зору
наступного застосування відновлених даних. Стиснення даних без втрат
14
переважно застосовується для передачі та зберігання текстових даних або
комп'ютерних програм, в меншій мірі - для скорочення обсягу аудіо- та
відеоданих, цифрових фотографій та ін.., для випадків, коли спотворення
неприпустимі або ж небажані. Стиснення із втратами, яке володіє значно
більшою ефективністю аніж стиснення без втрат, переважно
використовується, щоб скоротити обсягу аудіо та відеоданих, цифрових
фотографій в тому випадку, коли це скорочення являється пріоритетним, а
повної відповідності вихідних та відновлених даних не має потреби [18].
Давайте розглянемо, що являють собою дані та зосередимось на
стисненні (компресії) саме текстових даних (файлів), при якому метод, що
основується на коді Фібоначчі виявляє свою найкращу ефективність.
Дані – це деякі фрагменти інформації, що переважно відформатовані
спеціальним способом. Вони можуть бути представлені в різних формах,
наприклад, цифри або текст на паперових носіях; біти і байти, які
зберігаються в електронній пам'яті. Бітом є найменша одиниця даних, яка
зберігається на персональному комп’ютері. Хоч і персональні комп'ютери
здебільшого надають інструкції, що можуть тестувати та управляти бітами,
вони переважно призначені, щоб зберігати дані та виконувати інструкції у
бітних множинах, що називаються байтами. Байт складається із восьми бітів.
У більшій частині систем чотири восьмибітні байти або октети утворюють
32-х розрядне слово. А тому, для таких систем тривалість інструкцій деколи
виражається словом, тобто, складається з 32 біт у довжину або напівсловом,
тобто 16 біт у довжину.
Компресія даних визначається представлення даних так, що область
зберігання, яка необхідна для цільових даних менша, аніж розмір вхідних
даних. Як було визначено вище, існує два алгоритми стиснення даних: один
безпосередньо стискає дані, тобто, перетворює дані таким способом, щоб
вихідна кількість бітів була меншою аніж вхідна, та другий, що здійснює
реконструкцію стиснутих даних до початкового стану.
15
Стиснення даних, зокрема, тексту є важливою областю стиснення
даних без втрат. Дуже важливим є, щоб текст отриманий під час декомпресії
був ідентична тексту оригіналу, оскільки навіть дуже маленькі відмінності
можуть привести до висловлювань із різними визначеннями. Символи
переважно представленні у вигляді ASCII коду [1], де міститься 256
символів. Частота появи для кожного ASCII коду відмінна одна від одної. У
випадку, коли текстові дані застосовуються як введення, то деякі символи
можуть зустрічатися частіше, а також багато символів, що ніколи не будуть
використані на вході. В більшості випадків використовують алфавіт, цифри і
деякі спеціальні символи [21]. У алфавіті найчастіше використовуваними
символами є голосні букви. В таблиці 1.1 наведено значення
середньостатистичної частоти появи букв та пропусків між словами в тексті
українською мовою.
Таблиця 1.1 – Середнє значення частоти появи пропуску та букв
між словами в тексті українською мовою
Символ ___ о я ь н б а г и
Частота 0,138 0,086 0,019 0,016 0,068 0,013 0,064 0,013 0,055
Символ ч в х т ї і ц р й
Частота 0,011 0,046 0,011 0,045 0,010 0,044 0,010 0,043 0,009
Символ е ю с ж к ш м є у
Частота 0,042 0,008 0,037 0,007 0,033 0,005 0,029 0,005 0,027
Символ щ д ф л п з ґ
Частота 0,004 0,027 0,003 0,027 0,025 0,020 0.000
Таким же способом розглянемо статистику появи символів для
англійського алфавіту [13], яку наведено в таблиці 1.2.
Під час стиснення тексту 256 символів майже не використовується.
Різниця в такій частоті символів надає гарну можливість для компресії даних,
причому не фіксованої довжини кодом, а кодом змінної довжини.
16
Таблиця 1.2 – Середнє значення частоти букв для англійської мови
Символ e m t w a f o g i
Частота 0,127 0,024 0,091 0,023 0,082 0,022 0,076 0,021 0,070
Символ y n p s b h v r k
Частота 0,020 0,067 0,019 0,063 0,015 0,061 0,010 0,060 0,007
Символ d j l x c q u z
Частота 0,042 0,002 0,040 0,001 0,028 0,001 0,027 0,001
1.2 Алгоритми стиснення даних
Розроблено багато практичних алгоритмів для стиснення даних, але всі
вони основуються на 3-х теоретичних способах зменшення надлишковості
даних. Перший спосіб заключається в зміні вмісту даних; другий - у зміні
структури даних; третій - в одночасній зміні як структури, так і вмісту даних.
У випадку коли під час стиснення даних відбувається зміна їх вмісту,
то метод стиснення являється незворотнім, тобто під час відновлення
(розархівування) даних з архіву не виконується повне відновлення
інформації. Розглянуті методи досить часто називаються методами стиснення
з регульованими втратами інформації [7]. Відповідно ці методи можливо
використовувати тільки для тих типів даних, для яких втрата частини вмісту
не призведе до суттєвого спотворення інформації. Такими типами даних
є відео- та аудіодані, а також графічні дані. Метод стиснення з
регульованими втратами інформації забезпечує суттєво більший ступінь
стиснення, але його не можна застосовувати до текстових даних. Прикладами
форматів для стиснення з втратами інформації можуть бути: MPG - для
відеоданих; JPEG (Joint Photographic Experts Group) для графічних даних;
MP3 - для аудіоданих.
У випадку, коли під час стиснення даних виконується тільки зміна
структури даних, то метод стиснення вважається зворотнім. У цьому випадку
з архіву можна відновити повністю інформацію. Зворотні методи стиснення
застосовуються до будь-яких типів даних, але, при цьому, надають менший
17
ступінь стиснення даних у порівнянні з незворотними методами стиснення.
Приклади форматів стиснення даних без втрати інформації: GIF, TIFF - для
графічних даних; AVI - для відеоданих; ZIP, RAR, ARJ, LH, CAB - для
довільних типів даних [7].
Сьогодні є багато різноманітних практичних методів стиснення даних
без втрати інформації, які мають різну ефективність для різних обсягів та
різних типів даних. Але, в основі даних методів лежить три теоретичних
алгоритми:
1) алгоритм RLE (Run Length Encoding);
2) алгоритми групи KWE (KeyWord Encoding);
3) алгоритм Хафмана.
Алгоритм RLE (метод кодування довжин серій). В основі даного
алгоритму лежить ідея виявлення послідовностей даних, які повторюються,
та заміни визначених послідовностей більш простою структурою, в якій
зазначається код даних та коефіцієнт повторення. Наприклад, нехай задано
наступну послідовність даних, яка підлягається стисненню:
1 1 1 1 2 2 3 4 4 4
В алгоритмі RLE запропоновано замінити її такою структурою: 1 4 2 2
3 1 4 3, де першим числом кожної пари чисел є код даних, а другим зазначено
коефіцієнт повторення. Якщо для збереження кожного елементу даних
вхідної послідовності відводиться 1 байт, то вся послідовність в пам’яті
займе 10 байт, тоді як стиснений варіант вихідної послідовності займатиме в
пам’яті 8 байт.
Коефіцієнт стиснення даних визначається як відношення обсягу
нестислих вихідних даних до обсягу стислих. Його можна обчислити за
наступною формулою (1.1) [7] :
�� = ����
�� (1.1)
��
де k- коефіцієнт стиснення,
18
Vx- обсяг пам'яті, необхідної для зберігання вихідної (результуючої)
послідовності даних, Vn - обсяг пам'яті, необхідної для зберігання вхідної
послідовності даних.
Таким чином, чим вище коефіцієнт стиснення, тим алгоритм
ефективніше.
- якщо к = 1, то алгоритм не виконує стиснення, тобто вихідне
повідомлення за обсягом рівне вхідному;
- якщо к <1, то алгоритм породжує повідомлення більшого розміру,
ніж до стиснення, тобто, алгоритм виконує "шкідливу" роботу.
Було визначено, що алгоритм RLE буде надавати кращий ефект під час
стиснення більшої довжини послідовності даних, яка повторюється. У
випадку, розглянутого вище прикладу, коли вхідна послідовність матиме
наступний вигляд: 1 1 1 1 1 3 3 4 4 4, то коефіцієнт стиснення буде
дорівнювати 60%. Враховуючи це, було визначено, що з найбільша
ефективність алгоритму RLE буде досягнута під час стиснення графічних
даних (особливо, у випадку, однотонових фонових зображень).
Алгоритми групи KWE (словниковий метод). В основі даного
алгоритму стиснення по ключовим словам покладено принцип кодування
лексичних одиниць групами байт фіксованої довжини. Прикладом такої
лексичної одиниці може бути звичайне слово. У практичному використанні,
в ролі лексичних одиниць обираються послідовності символів, які
повторюються, та кодуються ланцюжком символів (кодом) меншої довжини.
Результати кодування записуються в таблицю, утворюючи словник [9].
Існує досить багато реалізацій даного алгоритму, найбільш
поширенішим з яких є алгоритм Лемпеля-Зіва (алгоритм LZ) та його
модифікація алгоритм Лемпеля-Зіва-Велча (алгоритм LZW). Словником для
даного алгоритму являється потенційно нескінченний список фраз. Даний
алгоритм починає працювати майже з пустим словником, який містить лише
один закодований рядок, який називається NULL-рядок. Під час зчитування
чергового символу вхідної послідовності даних, символ додається до
19
поточного рядка. Процес виконується до тих пір, поки поточний рядок
відповідає якійсь фразі зі словника. Як тільки поточний рядок перестає
відповідати якій-небудь фразі словника, у цей момент, поточний рядок являє
собою останній збіг зі словником кодер видає код, який складається з індексу
збігу та наступного за ним символу, що порушив збіг рядків. Окрім цього,
нова фраза, яка складається з індексу збігу та наступного за ним символу,
додається в словник. Наступного разу, коли дана фраза з’явиться в
повідомленні, вона може бути застосована для побудови більш довгої фрази,
яка підвищує міру стиснення інформації [7].
Алгоритм LZW побудований на основі таблиці фраз (словника), що
відображає рядки символів повідомлення, що стискається, в коди фіксованої
довжини. Таблиця містить так звану властивість передування, тобто для усіх
фраз словника, що складаються з деякої фрази w та символу К, фраза w
також міститься в словнику. У випадку, коли всі частинки словнику повністю
заповнені, то кодування перестає бути адаптивним. Алгоритми стиснення
розглянутої групи найефективніші під час стиснення текстових даних
великих обсягів та малоефективні при роботі з файлами малих розмірів,
оскільки необхідно зберігати словник.
Алгоритм Хафмана (або ентропійний метод). Алгоритм Хафмана
полягає в кодуванні бітовими групами. На початку виконується частотний
аналіз вхідної послідовності даних, тобто визначається частота входження
кожного символу, який зустрічається у послідовності. Після цього символи
сортуються за спаданням відносно частоти входження [7, 10].
Основною ідею даного алгоритму являється наступне твердження: чим
частіше зустрічається символ, тим меншою кількістю біт він кодується.
Результати кодування зводяться в словник, який необхідний для
декодування.
Для прикладу, розглянемо приклад, який показує роботу алгоритму
Хафмана.
20
Нехай задано текст, в якому літера ‘А’ зустрічається 10 разів, літера ‘B’
- 8 разів, ‘C’- 6 разів , ‘D’ - 5 разів, ‘E’ та ‘F’ - по 4 рази. Тоді одним з
можливих варіантів для кодування на основі алгоритму Хафмана наведено в
таблиці 1.3.
Таблиця 1.3 – Варіанти кодування тексту на основі алгоритму
Хафмана
Символ A B C D E
Частота входження 10 8 6 5 4
Бітовий код 00 01 100 101 110
Як видно з таблиці 1.3 розмір вхідного тексту до стиснення рівний 37
байт, тоді як після стиснення - 93 біт, тобто близько 12 байт без врахування
довжини словника. Для даного випадку коефіцієнт стиснення дорівнює 32%.
Алгоритм Хафмана є універсальним, тобто його можна використовувати під
час стиснення даних будь-яких типів, але він також є малоефективним для
файлів малих розмірів, оскільки є необхідність зберігати словник [7].
На практиці програмні засоби, що використовують стиснення даних
синтезують усі ці три «чистих» алгоритми, оскільки ефективність кожного з
них залежить від типу та обсягу даних, що необхідно стискати. У таблиці 1.4
наведено найпоширеніші формати стиснення даних та відповідні їм
програми-архіватори, що застосовуються на практиці.
Таблиця 1.4 – Формати стиснення даних та програми-архіватори
Формат стиснення ARJ RAR ZIP
Програма архівування / WinArj.exe WinRar.exe WinZip.exe
розархівування
Крім цього, сучасні архіватори надають користувачам повний спектр
послуг для роботи з архівами, основними з яких є [7,8]:
21
1) створення нового архіву;
2) додавання файлів в існуючий архів;
3) розпакування файлів з архіву;
4) створення архівів, які саморозпаковуються (self-extractor archive);
5) створення розподілених архівів фіксованих розмірів для носіїв малої
ємності;
6) захист архівів паролями від несанкціонованого доступу;
7) перегляд вмісту файлів різних форматів без попереднього
розархівування;
8) пошук файлів і даних всередині архіву;
9) перевірка на віруси в архіві до розпакування;
10) вибір та налаштування коефіцієнта стиснення.
1.3 Аналіз загального принципу стандартного методу на основі
коду Фібоначчі
Для подальших досліджень було обрано метод стиснення даних на
основі кодів Фібоначчі [8], що генерує код змінної довжини. Застосовується
традиційний метод заміни введених символів на специфічний код, що
являється ентропійним методом, наприклад, певні кодові слова і ряд
Фібоначчі для реалізації компресії даних.
У математиці числа Фібоначчі [11] являє собою послідовність ряду
чисел, для якого кожне наступне число рівне сумі двох попередніх 1; 1; 2; 3;
5; 8; 13; 21; 34; 55; 89; 144. Нерідко, особливо в теперішньому використанні,
в послідовність додано ще один елемент, який і є початковим, тобто нулем: 0;
1; 1; 2; 3; 5; 8; 13; 21; 34; 55; 89; 144.
У математичній термінології послідовність чисел Фібоначчі Fn
визначається за формулою (1.1).
���� = ����−1 + ����−2,
(1.1)
де, наприклад, F1 = 1 та F2 = 2 або F0 = 0 та F1 = 1.
22
Під час стисненні даних кожне число Фібоначчі із послідовності показує
кількість кодових слів, а на довжину цього кодового слова вказує номер
числа із послідовності + 1. Для стиснення даних, що наводяться через ASCII-
код, максимально буде використано тринадцять перших чисел із
послідовності, так як сума перших дванадцяти чисел: 0 + 1 + 1 + 2 + 3 + 5 + 8
+ 13 + 21 + 34 + 55 + 89 = 233, що в, свою чергу, менше 256, тобто мінімально
необхідною кількістю є тринадцять чисел.
Наведемо результати послідовності в таблиці 1.5.
Таблиця 1.5 – Необхідна послідовність Фібоначчі
На основі визначеної послідовності буде побудовано код стиснення
текстових даних.
Процес компресії (стиснення) даних із застосуванням послідовності
Фібоначчі виконується відповідно до визначених наступних етапів [9]:
1. Зчитується вхідний файл та визначається частота появи символів;
2. Відсортовується частота появи символу в порядку спадання;
3. Обраховується код Фібоначчі для кожного символу відповідно до
його появи;
4. Формується таблиця для кодування символів;
5. Використовуючи вхідний файл та таблицю кодування виконати
стиснення даних.
1.4 Дослідження способу генерації кодованої таблиці для
стандартного методу
Ефективне самостійно розмежоване подання довільного числа являє
собою кодування Фібоначчі [10]. Основою коду Фібоначчі є те, що будь-яке
23
натуральне число n можна буде однозначно виразити як суму різних чисел
Фібоначчі, що дає в результаті, не можливість отримання двох однакових
послідовних чисел. А це показує, що у випадку використання бінарного
представлення коду Фібоначчі не буде випадку двох послідовних одиниць.
Процес кодування (шифрування) можна записати у форматі наступного
алгоритму [9].
Нехай n є числом, яке відображає символ, що відповідає ASCII коду,
S – вихідний масив, F(i) являється числом із послідовності Фібоначчі.
Щоб провести подальше дослідження необхідно:
1. Знайти найбільше число , яке буде меншим за вхідне значення;
2. Додати i до вихідного масиву S;
3. Замінити число n на n – F(i);
4. Перейти до кроку 1.
Під час використання динамічного коду у процесі стиснення текстових
даних необхідно буде розробити унікальний ключ, для необхідності мати
можливість коректного розпізнання закодованих даних та подальшої
декомпресії їх.
Застосовуючи отримані дані та розглянутого алгоритму можна
створити таблицю кодування, що вигляд якої наведено в таблиці 1.6.
Таблиця 1.6 – Представлення чисел на основі коду Фібоначчі
24
Продовження таблиці 1.6
Оскільки в послідовності не може бути двох послідовних одиниць,
можна це застосувати. Звідси випливає, що найкоротшим можливим кодом,
який буде відображати закінчення кодового слова – “11”.
Таблиця 1.7 – Результати обрахунку стиснення текстового
повідомлення
25
Виконавши дослідження та підрахунок наведених в таблиці 1.7
результатів було визначено [21]:
- загальна кількість байтів до компресії даних – 160;
- загальна кількість байтів після компресії даних – 90.
Для того, щоб визначити ефективність стиснення даних застосуємо
формулу (1.2).
100 − ��∗100
�� = ��, (1.2)
де x – кількість бітів після стиснення текстового повідомлення; y –
кількість бітів до стиснення текстового повідомлення; Z – ефективність
стиснення текстового повідомлення.
26
Підставивши наведені в таблиці 1.7 результати у формулу (1.2)
отримаємо наступне значення ефективності стиснення текстового
повідомлення, а саме:
100 − 90∗100
160 = 43,75%, (1.3)
Відповідно до обрахунків отриманого вище відсотку даних визначено,
що символи, які займали в пам’яті по вісім біт після компресії даних почали
займати від двох до семи біт кожен. У випадку, коли кількість різних
символів збільшиться, необхідно буде застосовувати більше рангів під час
кодування.
У таблицях 1.1 та 1.2 було приведено частоту появи літер в мовах.
Застосовуючи ці дані, як середнє значення появи символу, визначимо середнє
значення ефективності методу стиснення текстових даних на основі чисел
Фібоначчі для англійської та української мов.
Середнє значення ефективності методу компресії текстових даних для
української мови на основі чисел Фібоначчі наведено в таблиці 1.8.
27
Таблиця 1.8 – Ефективність методу стиснення символів
українського алфавіту [21]
Символ Частота Ранг Код Фібоначчі Кількість Кількість
На 1000 бітів до бітів після
символів компресії компресії
___ 138 1 11 1104 276
о 86 2 011 688 258
н 68 3 0011 544 272
а 64 4 1011 512 256
и 55 5 00011 440 275
в 46 6 01011 368 230
т 45 7 10011 360 225
і 44 8 000011 352 264
р 43 9 100011 344 258
е 42 10 010011 336 252
с 37 11 001011 296 222
к 33 12 101011 264 198
м 29 13 0000011 232 203
у 27 14 1000011 216 189
д 27 15 0100011 216 189
л 27 16 0010011 216 189
п 25 17 1010011 200 175
з 20 18 0001011 160 140
я 19 19 1001011 152 133
ь 16 20 0101011 128 112
б 13 21 00000011 104 104
г 13 22 10000011 104 104
ч 11 23 01000011 88 88
28
Продовження таблиці 1.8
Обчислимо ефективність стиснення текстових даних для українського
алфавіту:
- загальна кількість бітів до стиснення даних – 8000;
- загальна кількість бітів після стиснення даних – 5197.
Підставивши наведені та визначені у таблиці 1.8 результати у
формулу (1.2) отримуємо відповідне значення ефективності стиснення
символів алфавіту:
100 − 5197∗100
8000 = 35,04% (1.4)
Середнє значення ефективності методу стиснення текстових даних на
основі чисел Фібоначчі для англійського алфавіту наведено в таблиці 1.9.
Визначимо ефективність стиснення даних для англійської алфавіту:
- загальна кількість бітів до стиснення даних – 8000;
- загальна кількість бітів після стиснення даних – 4918.
29
Таблиця 1.9 – Ефективність стиснення даних для англійського
алфавіту [21]
Символ Частота Ранг Код Фібоначчі Кількість Кількість
На 1000 бітів до байтів після
символів компресії компресії
e 127 1 11 1016 254
t 91 2 011 728 273
a 82 3 0011 656 328
o 76 4 1011 608 304
i 70 5 00011 560 350
n 67 6 01011 536 335
s 63 7 10011 504 315
h 61 8 000011 488 366
r 60 9 100011 480 360
d 42 10 010011 336 252
l 40 11 001011 320 240
c 28 12 101011 224 168
u 27 13 0000011 216 189
m 24 14 1000011 192 168
w 23 15 0100011 184 161
f 22 16 0010011 176 154
g 21 17 1010011 168 147
y 20 18 0001011 160 140
p 19 19 1001011 152 133
b 15 20 0101011 120 105
v 10 21 00000011 80 80
k 7 22 10000011 56 56
j 2 23 01000011 16 16
30
Продовження таблиці 1.9
x 1 24 00100011 8 8
q 1 25 10100011 8 8
z 1 26 00010011 8 8
Підставивши визначені в таблиці 1.9 результати для англійського
алфавіту у формулу (1.2) отримаємо відповідне значення ефективності
стиснення символів алфавіту:
100 − 4918∗100
8000 = 38,52% (1.5)
Виконавши дослідження визначених вище результатів було визначено,
що в обох випадках ефективність стиснення символів алфавіту показує
високий рівень і не дуже сильно поступається результатам отриманими в
першому прикладі. Головною проблемою є те, що отримані результати лише
для 34 та 26 унікальних символів відповідно, що на реальних текстових
даних не є можливим. Дослідивши дані з таблиці 1.8 можна побачити, що під
час кодування літери «ґ» уже було використано 9 бітів. А це означає, що під
час кодуваннія такого символу ефективність стиснення даних буде
знижуватися.
1.5 Дослідження та визначення основних недоліків стандартного
методу стиснення даних
Розглянувши та дослідивши результати, отримані та наведені в
таблиці 1.8, можна побачити, що далі деякі символи під час компресії будуть
займати більше ніж вісім біт та максимальне значення займання тринадцять
біт, за умови, що у файлі, як є вхідним використовуються майже усі символи
із таблиці ASCII [1]. Для такого випадку, навпаки, вихідний файл може
займати більше місця, ніж вхідний. Необхідно також зазначити, що займане
місце також дуже залежить від частоти розподілу символів. Тобто, чим більш
31
рівномірною буде розподіллено частоту символів, тим менш ефективним
буде стиснення даних.
Розглянемо приклад при якому буде досягнуто найменшої
ефективності алгоритму стиснення даних. Для цього, використаємо
повідомлення розміром близько 160 біт, при цьому, символи в даному
повідомленні не можуть повторюватися [21].
Виконаємо стиснення повідомлення, а отримані результати наведемо в
таблиці 1.10.
Таблиця 1.10 – Результати стиснення повідомлення на 160 біт під
час найменшої ефективності алгоритму
32
Продовження таблиці 1.10
Приклад повідомлення: «1234567890йцукенгшщз». Це Воно містить 20
різних символів розмір яких складає 160 біт.
Виконавши обрахунок наведених в таблиці 1.10 результатів було
визначено, що:
- загальна кількість байтів до компресії даних – 160;
- загальна кількість байтів після компресії даних – 114.
Підставивши визначені в таблиці 1.10 результати у формулу (1.2) було
отримано відповідне значення ефективності стиснення даних, наведене в
формулі (1.6):
100 − 114∗100
160 = 28,75% (1.6)
Виконавши порівняння отриманих результатів із результатами
отриманими в першому прикладі наведеному вище було визначено, що
ефективність стиснення даних для даного прикладу зменшилась на 15%.
Для подальшого дослідження розглянемо ще один приклад, для якого
тестове повідомлення складатиметься із 10 унікальних символів, що не
33
будуть повторюватися. Для даного прикладу повідомлення буде в повному
обсязі займати 80 біт. Нехай дане повідомлення буде включати в себе 10
цифр: «1234567890». Результати стиснення даних для даного повідомлення
наведемо в таблиці 1.11.
Таблиця 1.11 – Результати стиснення даних повідомлення розміром
80 біт під час найменшої ефективності алгоритму
Виконавши обрахунок визначених в таблиці 1.11 результатів було
визначено, що:
- загальна кількість байтів у повідомленні до стиснення – 80;
- загальна кількість байтів у повідомленні після стиснення – 46.
Підставивши визначені результати у формулу (1.2) було отримано
відповідне значення ефективності стиснення повідомлення наведені нижче:
100 − 46∗100
80 = 42,5% (1.7)
34
Аналогічно можна обрахувати компресію для повідомлення, що буде
складатися із 30 унікальних символів і буде рівне 240 бітам.
Результати обрахунків для такого повідомлення наведено в
таблиці 1.12.
Таблиця 1.12 – Результати стиснення повідомлення розміром 240 біт
під час найменшої ефективності алгоритму [21]
Символ Частота Ранг Код Фібоначчі Кількість Кількість
бітів до байтів після
компресії компресії
1 1 1 11 8 2
2 1 2 011 8 3
3 1 3 0011 8 4
4 1 4 1011 8 4
5 1 5 00011 8 5
6 1 6 01011 8 5
7 1 7 10011 8 5
8 1 8 000011 8 6
9 1 9 001011 8 6
0 1 10 010011 8 6
й 1 11 100011 8 6
ц 1 12 101011 8 6
у 1 13 0000011 8 7
к 1 14 1000011 8 7
е 1 15 0100011 8 7
н 1 16 0010011 8 7
г 1 17 1010011 8 7
ш 1 18 0001011 8 7
35
щ 1 19 1001011 8 7
з 1 20 0101011 8 7
Продовження таблиці 1.12
ф 1 21 00000011 8 8
і 1 22 10000011 8 8
в 1 23 01000011 8 8
а 1 24 00100011 8 8
п 1 25 10100011 8 8
р 1 26 00010011 8 8
о 1 27 10010011 8 8
л 1 28 01010011 8 8
д 1 29 00001011 8 8
ж 1 30 10001011 8 8
Виконавши підрахунок наведених в таблиці 1.12 результатів було
визначено, що:
- загальна кількість байтів повідомлення до стиснення – 240;
- загальна кількість байтів повідомлення після стиснення – 194.
Підставивши у формулу (1.2) визначені, як результат в таблиці 1.12
значення ефективності стиснення даних отримуємо наступне:
100 − 194∗100
240 = 19,17% (1.8)
Виконавши порівняння результатів з таблиць 1.10, 1.11 та 1.12 було
визначено, що в результаті рівномірного розподілу символів ефективність
стиснення даних значно знижується під час збільшення кількості унікальних
символів. Під час порівняння результатів із таблиці 1.12 з результатами
таблиць 1.8 та 1.9, в яких кількість унікальних символів приблизно однакова
можна в черговий раз переконатись в досить сильній залежності
36
продуктивності методу від частоти розподілених символів.
37
1.6 Постановка задачі на виконання
Метою кваліфікаційної роботи магістра є дослідження та
удосконалення методу стиснення даних текстових файлів.
Задачею кваліфікаційної роботи є покращення методу стиснення даних
текстових файлів та розробці програмної реалізації алгоритму
удосконаленого методу стиснення текстових файлів, яка б надала можливість
показати перевагу покращеного методу в порівнянні зі стандартним під час
стиснення реальних текстових даних. Крім удосконаленого методу також
буде розглянуто реалізацію стандартного методу стиснення даних на основі
кодів Фібоначчі, і на основі автоматизованих тестів виконано порівняння
роботи стандартного та удосконаленого методів.
На сьогоднішній день більшість текстових файлів, що написані навіть
однією мовою, будуть вміщувати велику кількість унікальних символів.
Наприклад, український алфавіт, що містить 33 літери – символи, буде
відображений 66 унікальними символами, оскільки великі та малі літери
являються різними символами в таблиці ASCII [1]. Додаймо сюди ж 10 цифр,
пунктуаційні знаки та знак пропуску і отримуємо понад 90 унікальних
символів. Також, не потрібно забувати про застосування спеціальних
символів та іншого роду алфавітів (наприклад в підручниках фізики,
математики, статтях із посиланнями або цитати на інших мовах), а також той
факт, що кількість унікальних символів в тексті може перевищити значення в
120 символів [13]. Відносно цих даних стандартний метод генерації коду
Фібоначчі [10] буде менше ефективний з огляду на збільшення рівномірності
розподілу частоти символів, факт чого і буде основою для його
удосконалення. Також, не потрібно забувати про форматування тексту,
оскільки в різних текстових редакторах воно відрізняється та під час
зчитування одного і того ж самого тексту для різних форматів можлива поява
значної кількості унікальних символів, що відповідальні за форматування
тексту. Для таких випадків кількість унікальних символів розпочинає
38
перевищувати 150-180 символів та стандартний метод генерації коду
Фібоначчі вже буде не ефективний відповідно до його основних недоліків
[15].
В значній кількості випадків не в текстових файлах такий розподіл
символів є досить рівномірним, що і служить причиною для покращення
вихідного методу.
Для досягнення поставленої задачі під час реалізації необхідно
виконати наступні вимоги наведені нижче.
1. Вимоги щодо реалізації вдосконаленого методу:
1) ефективність стиснення даних текстових файлів для
вдосконаленого методу повинна бути більшою відповідно до кількості
унікальних символів, що є більшою ніж 120 символів в порівнянні з вихідним
методом при порівняно рівномірного розподілу частоти символів;
2) ефективність стиснення текстових даних для вдосконаленого
методу має змогу бути меншою аніж у вихідному методі при чисельності
унікальних символів рівній менше ніж 120 символів;
3) час здійснення стиснення текстових даних для вдосконаленого
методу не повинен перевищувати час компресії вихідного методу більше
аніж на 10%.
2. Вимоги до програмної реалізації:
1) увесь код програми повинен бути написаний відповідно до
вимог ООП [3];
2) кожний елемент алгоритму повинен бути реалізований
відповідно як клас або сервіс;
3) усі класи та сервіси повинні підтримувати масштабування та
бути логічно розподілені;
4) для усіх розроблених класів, що являються логічною частиною
розробленого алгоритму мають бути реалізовані тести для його легкої
перевірки на працездатність;
39
5) кінцевий програмний код повинен виконувати стиснення
текстових даних відповідно до вдосконаленого методу, які подаються в
будь-якому текстовому форматі і записувати отримані результати у
вихідний файл, що має розширення .bin
Враховуючи той факт, що основною метою являється написання саме
бібліотеки [2], а не розробка програмного забезпечення, що буде реалізовано
з графічним інтерфейсом, яке можна надавати як готовий продукт
користувачам, то основним способом перевірки роботи програмної реалізації
будуть саме результати розроблених та написаних автоматизованих тестів.
1.7 Висновки до розділу 1
В першому розділі було проведено аналіз та доведено актуальність
досліджуваної тематики, проаналізувавши дані відповідно до збільшення
інтернет трафіку та розвитку технологій, які використовуються під час
збереження інформації на електронних носіях. Було визначено, що розвиток
технологій, що застосовується під час збереження даних на електронних
носіях, розвивається не достатньо швидко, щоб підтримувати збереження
усіх даних без фізичного розширення місць для зберігання даних (raid
масивів, серверів, тощо), що і є доведенням необхідності зменшення об’єму
інформації.
Проведено огляд та дослідження загального принципу компресії
(стиснення) даних, її різновидів та проаналізовано можливість застосування
стиснення текстових даних на основі кодів динамічного розміру та зв’язок
поміж розподілом частоти вживання визначених літер; розглянуто загальний
принцип стиснення текстових даних на основі кодів Фібоначчі та виділено
загальний алгоритм для стиснення даних обраного методу.
Також було проведено огляд загального принципу побудови таблиць
кодування розглянуто методу та виконано практичні обрахунки його
ефективності для випадків розподілу символів відповідно до статистики та
під час рівномірного розподілу символів.
40
На основі отриманих обрахунків ефективності стиснення даних для
різних випадків було виділено основні недоліки методу для подальшого його
удосконалення. Дослідивши отримані результати було сформульовано
основну мету та задачу роботи, що реалізується, та визначено вимоги щодо
удосконаленого методу та реалізованої бібліотеки.
41
РОЗДІЛ 2 УДОСКОНАЛЕННЯМЕТОДУ СТИСНЕННЯ ДАНИХ
ТЕКСТОВИХ ФАЙЛІВ
2.1 Розширення таблиці кодів стандартного методу на базі коду
Фібоначчі
Як було визначено в підрозділі 1.6 стандартний метод дуже сильно
залежить від ефективності частоти розподілення символів під час
використання великої кількості унікальних символів. Також необхідно
зазначити, що результати, що було наведено в розділі 1 являються
теоретичними, так як не було враховано особливості зберігання таких даних.
Якщо розглянути файл у форматі .txt, де записано 1000 символів взятих з
таблиці 1.8, то він буде займати 1771 байт, а не 1000 байт. Якщо говорити
про тексти, що зберігаються в інших форматах, то вони можуть займати ще
більше місця, адже ще також зберігаються і дані про форматування, шрифт
тощо. А це значить, що ці дані також будуть мати вплив на кількість та
розподіл унікальних символів під час стиснення даних.
Не дивлячись на це, головний факт, а саме, ефективність методу дуже
зменшується при використанні значної кількості унікальних символів з їх
рівномірним розподілом, все ж таки буде працювати в будь-якому випадку.
Спираючись на даний факт та метод генерації таблиці кодів, що описаний в
підрозділі 1.5 можна зробити наступний висновок, що проблема полягає саме
в таблиці. У разі відсутності значної переваги частоти символів для яких
відводиться 2, 3 та 4 байти (а це 4 символи) ефективність стиснення падає.
У разі збільшення рівномірності розподілення з’являється можливість
збільшити ефективність стиснення даних за рахунок розширення таблиці, але
при цьому, необхідно, ввести новий або нові унікальні закінчення для того,
щоб мати можливість подальшої декомпресії. Для стандартного алгоритму
таке закінчення визначено лише одне, а саме «11». При цьому в умові
зазначено, що в коді не повинна зустрічатися комбінація «11», вона тільки
42
може служити як закінчення, при цьому комбінація «11» являється
найкоротшою і є кодом для символу, який зустрічається найчастіше. Як було
визначено раніше, в процесі збільшення рівномірності розподілу
ефективність даних комбінацій буде зменшуватись, а процесі збільшення
кількості унікальних символів, кількість символі, яка буде кодуватися
дев’яти і більше символами збільшиться. Відповідно до отриманих в
результаті дослідження даних, одним із рішень може бути зміна певних
обмежень на закінчення.
Головним правилом запропонованого удосконаленого методу є
розширення таблиці кодування шляхом введення додаткових закінчень,
тобто крім «11», також додати закінчення «1111», «111111» і т. д. Необхідно
пам’ятати, що код символу може розпочинатися з «1», а це означає, що не
можна ввести непарні закінчення. Навіть у випадку, коли зустрічається «1»
на початку наступного закодованого символу, то кількість символів «1», що
зустрічатимуться підряд буде непарною. Відповідно до правила про
закінчення символу, яке говорить, що закінчення має складатися із парної
кількості одиниць постійно можна буде легко встановити символи та
виконати декомпресію.
Отже, можна встановити перше нове правило, що говорить, що буде
існувати декілька закінчень у закодованих символів, яке являтиме собою
парну кількість символу «1».
Непотрібно забувати, що в процесі використання лише одного
визначеного правила може виникнути наступна ситуація: наприклад, один із
символів було закодовано, як «11», а інший - «111111». Дані два символи
знаходилися в тексті поряд, а це значить, що у закодованому варіанті вони
будуть виглядати як «11111111». Проблема буде складатися в тому, що не
буде змоги сказати чи це два символи «11» та «111111» чи може це інші два
символи «1111» та «1111». Звідси випливає друге правило, що говорить про
те, що закінчення не може кодувати символ. Себто, найменший за розміром
символ, згідно визначеного правила, може бути закодовано лише
43
комбінацією «011». Відповідно до цього правила, застосовані для прикладу
символи повинні бути закодовані комбінаціями «011» і «0111111», а у
закодованому варіанті це повинно було б виглядати наступним чином –
«0110111111». Застосовуючи таке кодування можна чітко визначити, що ці
символи є символами «011» і «0111111».
Для кращого розуміння застосування другого правила в якості
прикладу розглянемо його застосування для перших 14 символів. Результати
такого застосування наведемо в таблиці 2.1.
Таблиця 2.1 – Таблиця кодування символів відповідно до
удосконаленого методу на основі кодів Фібоначчі
Ранг 1 2 3 4 5 6 7
Код згідно нового 011 0011 1011 00011 10011 01011 01111
методу
Ранг 8 9 10 11 12 13 14
Код згідно нового 000011 100011 010011 001011 101011 001111 101111
методу
Відповідно до даної таблиці можна чітко побачити, що тепер
найкоротшим кодом є «011» в порівнянні зі стандартним методом, де
найкоротшим кодом є «11». Відповідно до цього можна й визначити, що
даний факт і є головною втратою удосконаленого методу. Натомість, з
іншого боку можна побачити, що п’яти символьним кодам в таблиці
відповідають 4-и коди, а не 3-и, як було визначено раніше. А це означає, що
при збільшенні розміру таблиці кількість додаткових кодів, що будуть
слугувати стисненню даних буде збільшуватись.
Для перевірки ефективності удосконаленого методу буде застосовано
програмну реалізацію у вигляді бібліотеки для стандартного та
удосконаленого алгоритму для декількох різних за розмірністю текстових
44
документів. Результати отриманих перевірок для двох методів наведено в
таблиці 2.2.
Таблиця 2.2 – Отримані результати порівняння ефективності
стиснення текстових файлів для стандартного та удосконаленого методів
Розмір Кількість Розмір у байтах Розмір в байтах після
файлу в унікальних після стиснення стиснення даних
байтах символів даних удосконаленим
стандартним методом
методом
60825 137 47860 45762
43010 119 31670 31007
1173 29 590 639
93458 184 95034 87153
6944 99 4468 4545
131134 256 170591 155819
Дослідивши отримані в таблиці 2.2 результати можна сказати, що
розроблений метод більш ефективніший за вихідний метод в процесі
використання більше 110-120 унікальних символів.
2.2 Додання виключень в таблицю кодів для удосконаленого
методу стиснення текстових даних
В процесі дослідження необхідно приділити увагу ще одному
визначеному аспекту, а саме, що іноді комбінація «11», «1111» і т. д., все ж
таки може бути застосована в процесі кодування. Для прикладу, розглянемо
випадок коли повідомлення складається з наступного тексту: «тест».
Розглянувши повідомлення було визначено, що воно складається всього з 3-х
унікальних символи, а це значить, що таблиця відповідно до удосконаленого
методу буде виглядати, як наведено в таблиці 2.3.
45
Дослідивши таблицю можна помітити, що наступні комбінації «1111»,
«111111» і т. д., відсутні в таблиці. А це значить, що для даного випадку
можна б було використати комбінацію «11» для кодування символу, що
зустрічається найчастіше. Як результат отримаємо комбінації після
відповідних перетворень даних з таблиці 2.3 та наведемо їх в таблиці 2.4.
Таблиця 2.3 – Отримані результати стиснення даних удосконаленим
методом
Символ Частота Ранг Код на основі Кількість Кількість
Фібоначчі бітів до бітів після
стиснення стиснення
т 2 1 011 8 3
с 1 3 1011 8 4
е 1 2 0011 8 4
Таблиця 2.4 – Отримані результати стиснення текстових даних
удосконаленим методом із виключенням
Символ Частота Ранг Код на основі Кількість Кількість
Фібоначчі бітів до бітів після
стиснення стиснення
т 2 1 11 8 2
с 1 3 0011 8 4
е 1 2 011 8 3
Виконавши дослідження наведених в таблиці 2.4 результатів було
визначено, що отриманий результат, такий же, що був би під час
використання стандартного методу, але це лише є дієвим для даного випадку.
Розглянемо, як приклад, інше повідомлення, що складається з восьми
унікальних символів «1111222223333444444444444556667778». Відповідно
до даних з таблиці 2.1, для даного типу повідомлення, будуть наявні як
комбінація «11», так і «1111». А це означає, що використання комбінації «11»
46
не є можливим, але для даної таблиці є відсутньою комбінація «111111».
Побудуємо таблицю 2.5 для повідомлення, що використовується для
прикладу.
Провівши дослідження результатів, що наведено в таблиці 2.5 було
визначено, що в таблицю можна додати «1111», як нову кодову комбінацію,
не зважаючи навіть на той факт, що після кодування можуть зустрічатися
випадки «011111111» або «0111111». Оскільки в таблиці немає визначених
кодових комбінацій, то можна легко розрізнити їх для обох випадків
відповідно, як «01111» та «1111» і «011» та «1111». В таблиці 2.6 наведено
результати додавання нових кодових комбінацій.
Таблиця 2.5 – Результати стиснення текстового повідомлення за
допомогою удосконаленого методу
Символ Частота Ранг Код на основі Кількість Кількість
Фібоначчі бітів до бітів після
стиснення стиснення
4 12 1 011 96 36
2 5 2 0011 40 20
3 4 4 00011 32 20
1 4 3 1011 32 16
7 3 6 01011 24 15
6 3 5 10011 24 15
8 1 8 000011 8 6
5 2 7 01111 16 10
Дослідивши отримані в таблиці 2.5 результати було визначено, що
кількість байт після стиснення текстового повідомлення дляв деяких
випадків зменшилося.
Дослідивши отримані результати для останніх двох прикладів було
визначено ще одне, а саме, третє правило, яке можна назвати, як правило
виключення. Воно передбачає, що в таблиці кодування може бути присутня
47
кодова комбінація, що складається з n-пар символів «1», у випадку, якщо
відсутнє в таблиці закінчення, що складається з n+1 пари символів «1».
Таблиця 2.6 – Результати стиснення текстового повідомлення за
допомогою вдосконаленим методом з виключенням
Символ Частота Ранг Код на основі Кількість Кількість
Фібоначчі бітів до бітів після
стиснення стиснення
4 12 1 011 96 36
2 5 2 0011 40 20
3 4 4 1111 32 16
1 4 3 1011 32 16
7 3 6 10011 24 15
6 3 5 00011 24 15
8 1 8 01111 8 5
2 2 7 01011 16 10
Введення даного виключення в процесі кодування надає можливість
збільшення ефективності стиснення текстових повідомлень додатково на 1-
4%. Результати щодо порівняння ефективності досліджених методів наведено
в таблиці 2.7.
Таблиця 2.7 – Отримані результати порівняння ефективності
стиснення текстових повідомлень дослідженими методами
Розмір Кількість Розмір в Розмір в байтах Розмір в
файлу в унікальних байтах після після стиснення байтах після
байтах символів стиснення текстового стиснення
даних повідомлення текстового
методом удосконаленим повідомлення
Фібоначчі методом методом з
виключенням
60825 137 47860 45762 45359
43010 119 31670 31007 30606
48
Продовження таблиці 2.7
131134 256 170591 155819 153231
6944 99 4468 4545 4542
93458 184 95034 87153 86378
1173 29 590 639 636
2.3 Висновки до розділу 2
В процесі дослідження наведених в таблиці 2.7 результатів було
визначено, що для більшості випадків удосконалений метод з виключенням
показує кращий відсоток стиснення текстових повідомлень над стандартним
методом, але при цьому результати досить сильно залежать від частотного
розподілу символів. Але, в процесі кодування повідомлення з великою
кількістю унікальних символів, але із великою перевагою в частоті кількох
символів застосування стандартного методу може дати кращий показник
стиснення текстового повідомлення в порівнянні з удосконаленим.
До переваг розробленого удосконаленого методу можна віднести те,
що даний метод направлений на стиснення саме текстових повідомлень, де
застосовується декілька мов, спеціальні символи тощо, а також може
використовуватися під час стиснення файлів будь-якого формату, адже
стандартний метод під час такого застосування показує малий або, навіть,
від’ємний показник стиснення.
До недоліків розробленого удосконаленого методу можна віднести те,
що метод може мати від’ємний показник стиснення даних в процесі
стиснення деяких файлів, але його показник, навіть, для таких випадків,
перевищує показник для стандартного методу не менше ніж на 20%.
Розроблений удосконалений метод лише частково вирішує проблему
оригінального стандартного методу і в подальшому може бути
удосконаленим для повного вирішення його недоліків.
49
РОЗДІЛ 3 ОБРАННЯ ТЕХНОЛОГІЇ РОЗРОБКИ ТА МОВИ
ПРОГРАМУВАННЯ ПРОГРАМНОЇ РЕАЛІЗАЦІЇ
3.1 Технологія Microsoft .Net/C#
Microsoft .NET є програмною технологією, що запропонована фірмою
Microsoft як платформа створення як для звичайних програм, так і веб-
додатків. Дана технологія є продовженням ідей та принципів, що покладена в
технологію Java. Однією з ідей .NET являються сумісність служб, які
написані на різних мовах. Хоча дана можливість рекламується Microsoft як
перевага .NET, Java платформа також має таку ж можливість.
Всі бібліотеки (збірки) в .NET мають свідоцтво про свою версію, що
надає можливість усунути конфлікти між різними версіями збірок.
Платформа .NET ділиться на дві основні частини – середовище
виконання (тобто, віртуальна машина) та інструментарій розробки [2].
Середовища розробки .NET-програм є Visual Studio .NET (C++, C#, J#),
Borland Developer Studio (Delphi, C#), SharpDevelopта інші.
.NET Framework складається з загальномовного середовища виконання,
яке має назву середовище CLR та бібліотеки класів .NET Framework.
Середовище CLR являється основою платформи .NET Framework. CLR
можна вважати агентом, що керує кодом в процесі виконання та надає
основні служби, такі як управління потоками, управління пам'яттю та
віддалена взаємодія. Середовище виконання накладає умови суворої типізації
та деякі інші види перевірки точності коду, які забезпечують захист та
надійність.
.NET Framework може вміщуватися, як некерованими компонентами,
що завантажують середовище CLR у свої процеси та запускають виконання
керованого коду, при цьому створюючи програмне середовище таким чином,
що надає можливість використовувати ресурси, як керованого, так і
некерованого виконання [2].
50
Бібліотека класу платформи .NET Framework представляє собою
колекцію типів даних, що щільно інтегруються із середовищем CLR.
Бібліотека класів являється об'єктно-орієнтованою та надає типи даних,
відповідно до яких керований код користувача має можливість
успадковувати функції. Це в свою чергу надає можливість не тільки
спростити роботу з типами .NET Framework, але й зменшити час, який
витрачається для вивчення нових засобів платформи .NET Framework. До
того ж, компоненти незалежних виробників можна досить легко поєднувати
із класами платформи .NET Framework [6].
Платформа .NET Framework застосовується під час розробки наступних
типів додатків та служб:
- Windows Forms – додатки Windows із графічним інтерфейсом
користувача;
- консольні додатки;
- WPF – додатки Windows Presentation Foundation;
- додатки ASP.NET;
- WCF – сервісно-орієнтовані додатки за допомогою Windows
Communication Foundation;
- служби Windows;
- WF – додатки, які підтримують бізнес-процеси Windows Workflow
Foundation.
Мова C# є об'єктно-орієнтованою мовою програмування, що має
безпечну систему типізації для платформи .NET.
Синтаксис C# схожий із С++ та Java. Мова забезпечує строгу статичну
типізацію та підтримує наступні функції такі як поліморфізм, вказівники на
функції-члени класів, перевантаження операторів, атрибути, властивості,
події, коментарі у форматі XML та винятки. Взявши багато чого від своїх
попередників (мов Delphi, С++, Модула та Smalltalk) мова С#, опираючись на
практику їхнього застосування виключила деякі моделі, які зарекомендували
себе як проблемні під час розробки програмних систем. Таким прикладом
51
може слугувати множинне успадкування класів (що на використовується в
C++) [3].
Мова C# реалізовувалася як мова програмування для прикладного
рівня CLR, а тому вона залежить, в першу чергу, від можливостей самої
CLR. Це стосується, в першу чергу, системи типів C#. Наявність або
відсутність тих чи інших особливостей виразів мови продиктоване тим, що
конкретна мовна особливість може бути відтрансльована у певні конструкції
CLR. Тому в процесі розвитку CLR від версії 1.1 до 2.0 неабияк збагатилася і
сама мова C#; схожої взаємодії необхідно чекати і далі. Хоча дану
закономірність буде порушено з виходом C# 3.0, що являється розширеннями
мови, яка не спирається на розширення платформи .NET. CLR надає мові C#,
як і усім іншим .NET-орієнтованим мовам, досить багато можливостей, які не
передбачені в «класичних» мовах програмування. Приккладом може
слугувати функція збірки сміття, що не реалізовано в самому C#, а
проводиться CLR для програм, що написані на C# точно так же, як це
робиться для програм написаних на мовах VB.NET, J# тощо.
Мова C# містить «препроцесорні директиви», що основуються на
препроцесорі C, а це, в свою чергу, надає можливість програмісту визначити
символи, але не макроси. Умовні директиви, типу #if, #endif, або #else також
можливі. Директиви типу #region натякають редактору про згортання
фрагментів коду [4].
3.2 Поняття об’єктно-орієнтоване програмування (ООП)
Об'єктно-орієнтоване програмування (ООП) є методологією
програмування, що основується на представленні програмного забезпечення
у вигляді сукупності об'єктів, кожен з яких являється екземпляром
визначеного класу, а класи створюють ієрархію спадкування [5].
Ідеологічно ООП являється підходом до програмування, як до
моделювання інформаційних об'єктів, що вирішує на новому рівні основне
завдання структурного програмування, а саме, структурування інформації зі
52
сторони керованості, що досить сильно поліпшує керованість самим
процесом моделювання, а це, в свою чергу, особливо важливо в процесі
реалізації великих проектів.
Керованість в контексті ієрархічних систем показує мінімізацію
надмірності даних, що є аналогом нормалізації, та їх цілісність, а це означає,
що створене програмне рішення зручно керованим і буде зручно розумітися.
Тому, через гнучку задачу керованості виконується стратегічне завдання
транслювання розуміння завдання програмістом в найбільш зручну форму
для подальшого використання [3].
Основні принципи структурування у випадку ООП тісно пов'язані з
різними сторонами базового розуміння предметного завдання, що необхідно
для найкращого із можливих управління відповідною моделлю [6]:
- принцип інкапсуляції, що використовується для швидкої та
безпечної організації саме ієрархічної керованості, тобто, щоб було
достатньо виконати просту команду «що робити», без уточнення як саме це
робити, оскільки це вже є іншим рівнем управління;
- принцип абстрагування застосовується для виділення в
модельований предмет важливого в процесі вирішення визначеного завдання
по предмету, як результат - контекстне розуміння предмету, що
формалізується у вигляді класу;
- принцип поліморфізму застосовується для визначення точки, в якій
єдине управління найкраще розпаралелити чи навпаки зібрати воєдино;
- принцип успадкування застосовується для швидкої та безпечної
організації спадкового поняття, тобто, щоб було досить на кожному
ієрархічному кроці враховувати тільки зміни, при цьому не дублюючи все
інше, що було враховано на попередніх кроках.
Себто, мова фактично йде про прогресуючу організації інформації
відповідно до первинних семантичних критеріїв: «ключове / подробиці»,
«важливе / неважливе», «єдине / множинне», «батьківське / дочірнє». Процес
53
прогресування, в тому числі, на останньому етапі надає можливість
переходити на наступний рівень деталізації, який замикає загальний процес.
Звичайна людська мова в цілому відображає ідеологію ООП, яка
розпочинається з інкапсуляції уявлення про предмет у виді його імені, а
закінчується поліморфізмом застосування слова в переносному сенсі, що в
результаті, розвиває вираження думки через ім'я предмету до повного
поняття-класу [5].
Основні елементи ООП та особливості.
 Абстракція даних. Поняття абстрагування визначає виділення
вагомої інформації та виключення з огляду неважливої. В ООП досліджують
лише абстракцію даних («абстракція»), маючи на думці набір найбільш
вагомих характеристик об'єкту, які доступні решті програми.
 Інкапсуляція. Інкапсуляція являється властивістю системи, яка надає
можливість об'єднати дані та методи, що працюють з ними в класі.
 Спадкування. Спадкування є властивістю системи, яка надає
можливість описати новий клас на основі існуючого, при цьому частково чи
повністю запозичуючи функціональність. Клас, від якого виконується
успадкування називається базовим, батьківським чи суперкласом. Новий клас
при цьому має назву нащадок, спадкоємець, дочірній або похідний клас.
 Поліморфізм підтипів. Поняття поліморфізм підтипів
(«поліморфізм») є властивістю системи, яка надає можливість застосовувати
об'єкти з однаковим інтерфейсом без інформації про тип та внутрішню
структуру об'єкту. Ще один вид поліморфізму, а саме, параметричний в
ООП має назву узагальнене програмування.
 Клас. Клас являється універсальним, комплексним типом даних,
який складається з тематично єдиного набору «полів», тобто змінних більш
елементарних типів, та «методів», що є функціями для роботи з цими
полями. А це означає, що клас є моделлю інформаційної сутності із
внутрішнім та зовнішнім інтерфейсами, що застосовуються для оперування
своїм вмістом, а саме значеннями полів. Особливо, в класах широко
54
застосовуються спеціальні блоки з одного чи частіше двох спарених методів,
які несуть відповідальність за елементарні операції з визначеним полем,
тобто, організація інтерфейсу присвоювання та зчитування значення, що
імітують безпосередній доступ до поля. Дані блоки називаються
«властивостями» і майже повністю збігаються за конкретним іменем із своїм
полем (наприклад, ім'я поля починається з малої літери, а ім'я його
властивості - з великої літери). Іншим вираженням інтерфейсної природи
класу являється те, що під час копіювання відповідної змінної через
присвоювання копіюється лише інтерфейс, але не власне дані, тобто клас є
контрольним типом даних. Змінна-об'єкт, яка відповідає заданому класом
типу називається екземпляром даного класу. За цих обставин в деяких
виконуючих системах клас може представлятися деяким об'єктом під час
виконання програми при допомозі динамічної ідентифікації типу даних.
Переважно класи розробляють таким способом, щоб мати можливість
забезпечити відповідність природі об'єкту та задачі, що розв'язується,
цілісності даних об'єкту, а також зручний та простий інтерфейс. Відповідно,
цілісність предметної області об'єктів та їх інтерфейсів, і зручність їх
проектування забезпечується принципом успадкування [4].
 Об'єкт. Є сутністю в адресному просторі обчислювальної системи,
яка з'являється в процесі створення екземпляру класу; наприклад, після
запуску результату компіляції та зв'язування вихідного коду на виконання.
 Поля даних. Параметри об'єкту, які необхідні в програмі, що задають
його стан, тобто, властивість об'єкту предметної області. Інколи поля даних
об'єкту називаються властивостями об'єкту, через що може виникнути
плутанина. Фактично поля представляють собою значення (константи,
змінні), оголошені як ті, що належать класу.
 Методи. Процедури та функції, що пов'язані з класом. Вони
визначають дії, що можуть бути виконані над об'єктом такого типу, і ті, що
сам об'єкт може виконувати.
55
Класи володіють можливістю успадковуватися один від одного. Клас-
нащадок одержує всі поля та методи класу-батька, але при цьому, мають
змогу доповнювати їх власними чи перевизначать вже існуючі. Більшість
частина мов програмування підтримує лише одиничне успадкування, тобто
клас може мати лише один клас-батько, і тільки в деяких мовах допускається
множинне успадкування, тобто породження класу від двох або більше класів-
батьків. Множинне успадкування утворює цілий ряд проблем, як логічних,
так і в процесі реалізації, а тому його підтримка в повному обсязі не
поширена. Натомість в 1990 роки з'явилося та стало активно
впроваджуватися в об'єктно-орієнтовані мови поняття інтерфейсу. Інтерфейс
являє собою клас без полів та без реалізації, який включає лише заголовки
методів. У випадку коли якийсь клас успадковує (іншими словами реалізує)
інтерфейс, йому необхідно реалізувати усі методи, що в нього входять.
Використання інтерфейсів дає можливість реалізації відносно дешевої
альтернативи множинного спадкоємства [6].
Взаємодія об'єктів в повній мірі забезпечується викликом ними методів
один одного.
Поняття інкапсуляції забезпечується такими засобами наведеними
нижче.
Контроль доступу. Так як методи класу можуть бути як внутрішніми,
які забезпечують логіку функціонування об'єкту, так і зовнішніми,
застосовуючи які виконується взаємодія об'єктів, потрібно забезпечити
прихованість перших в процесі доступності ззовні других. Для цього в мови
вводяться спеціальні синтаксичні конструкції, для яких явно задається
область видимості для кожного члену класу. Зазвичай цими модифікаторами
є public, protected та private, які позначають відкриті члени класу та члени
класу, що доступні всередині класу та з класів-нащадків та приховані, що
доступні тільки всередині класу. Конкретну номенклатуру модифікаторів та
їх точний зміст розрізняються для різних мов.
56
Методи доступу. Поля класу для загального випадку не повинні бути
доступні ззовні, так як такий доступ надав можливість випадковим чином
змінювати внутрішній стан об'єктів. А тому поля переважно оголошуються
прихованими, а для доступу до даних, що знаходяться в полях, застосовують
спеціальні методи, що називаються методами доступу. Дані методи чи
повертають значення того або іншого поля, чи роблять запис в дане поле
нового значення. Під час запису метод доступу може проконтролювати
допустимість значення, що записується і, при необхідності, виконати інші
маніпуляції із даними об'єкту, щоб дані залишалися коректними, тобто,
внутрішньо узгодженими. Методи доступу називаються ще аксесорами, а
окремо - геттерами та сетерами [5].
Програмна реалізація удосконаленого методу стиснення текстових
даних у вигляді бібліотеки буде написано на базі принципів ООП, щоб
забезпечити максимальну простоту розуміння коду, підтримку легкої
масштабованості для подальшого удосконалення алгоритму і можливості
інтеграції розробленої бібліотеки в різні системи.
3.3 Висновки до розділу 3
В третьому розділі було проведено огляд технології для розробки та
мови програмування, що будуть використовуватися в процесі розробки
програмної реалізації у вигляді бібліотеки.
Об’єктно-орієнтоване програмування було обрано в якості загальної
структури та стилізації коду, оскільки воно найкраще підходить для
масштабування програмної реалізації та підтримання можливості
редагування коду. Застосування ООП надасть можливість змінювати окремі
елементи алгоритму стиснення даних, що забезпечить можливість легко
удосконалювати алгоритм.
Для реалізації програмної реалізації було обрано мову програмування
C#, оскільки обрана мова надає гарну інтеграцію з функціями операційної
системи Windows та забезпечена рядом вбудованих функцій для роботи з
файловою системою. Обрана для реалізації мова програмування також
забезпечує легкість реалізації графічного інтерфейсу, при необхідності.
57
РОЗДІЛ 4 РОЗРОБКА ПРОГРАМНОЇ РЕАЛІЗАЦІЇ
УДОСКОНАЛЕНОГОМЕТОДУ СТИСНЕННЯ ТЕКСТОВИХ ДАНИХ
4.1 Проектування моделі класів удосконаленого методу стиснення
текстових файлів
Для реалізації програмного рішення для початку було спроектовано
наступну UML діаграма [14], яку наведено на рисунку 4.1:
Рисунок 4.1 – Модель класів програмного рішення
Для початку розглянемо структуру класів [4] для реалізованої
програмної бібліотеки:
- Клас Program використовується для ініціалізації роботи програми;
- ByteFileCompressorService. Модуль, що приймає вхідний файл, далі
за допомогою SetBiteFile записує даний файл у байтовому представлені.
Наступним кроком за допомогою інших класів проводиться обрахунок
частоти символів, генерація таблиці кодування та виконання стиснення
текстового файлу;
58
- ByteFile. Даний клас зберігає основні параметри вхідного файл та
його представлення у байтовому вигляді;
- FiboFrequency – включає метод для обрахунку частоти символів;
- FiboRank_sCode. Метод, що на основі таблиці частоти символів,
відповідно до стандартного методу, виконує генерацію таблиці кодування;
- ByteFileCharacterFrequency. Даний клас зберігає просортовану
таблицю частоти символів;
- FiboRanksUpgraded. Метод, що на основі таблиці частоти символів,
відповідно до удосконаленого методу, виконує генерацію таблиці кодування;
- ByteFileCompressor. Метод, що на основі згенерованої таблиці
кодування виконує стиснення текстового файлу;
- ByteFileHeader. Даний клас, що зберігає згенеровану таблицю
кодування;
- CompressedByteFile. Даний клас зберігає стиснений файл і таблицю
для подальшої декомпресії.
В процесі дослідження розглянемо більш детально алгоритми роботи
програми для кожного класу в наступних розділах.
4.2 Розробка класів для зберігання даних
Для збереження вхідного файлу застосовується клас ByteFile.
Розроблений клас зберігає основну інформацію про файл, що
користувач має намір стиснути: сам файл у вигляді масиву байтів, назву
файлу, його початковий розмір та шлях до файлу.
Під час завантаження файлу в класі ByteFileCompressorService
створюється новий об’єкт [5], який має тип ByteFile, і в нього записуються
певні дані.
Поля name та path застосовуються в процесі формування вихідного
файлу і його збереження у відповідному місці на диску.
Поле data підлягає обробці, щоб встановити частоту символів та для
подальшого кодування даного поля.
59
Поле size застосовується для виконання порівняння розміру вихідного
файлу з розміром вхідного для встановлення ефективності стиснення
текстових файлів.
Структуру класу ByteFile наведено на рисунку 4.2.
Рисунок 4.2 – Структура класу ByteFile
Клас ByteFileCharacterFrequency використовується для зберігання
результатів обрахованої частоти символів.
Реалізований клас містить в собі тільки одне поле characterFrequency,
що представляє собою dictionary [5], де зберігається код символу і частота
його повторення у файлі.
Дане поле безпосередньо застосовується для генерації таблиці
кодування та подальшої стиснення вхідного файлу.
Структуру класу, що було реалізовано наведено на рисунку 4.3.
Для того, щоб мати можливість декомпресії вихідного файлу потрібно
також зберігати таблицю кодування. Для цього розроблено клас
ByteFileHeader.
60
Рисунок 4.3 – Структура класу ByteFileCharacterFrequency
Розроблений клас містить поле fileHeader, що визначається як
dictionary, в якому зберігається стандартний код символу і його код після
стиснення.
Дане поле застосовується як під час стиснення так і під час
декомпресії.
На рисунку 4.4 наведено структуру класу для зберігання коду символу.
Рисунок 4.4 – Структура класу ByteFileHeader
Клас CompressedByteFile використовується для зберігання вихідного
файлу і його запису на диск.
Розроблений клас має два поля [3] – compressedData та fileHeader.
Поле fileHeader – поле, що має тип ByteFileHeader, і зберігає таблицю
кодування, що отримати можливості декомпресії файлу.
Поле compressedData використовується для збереження вже
закодованого файлу. Оскільки довжина кодів є динамічною величиною, то
увесь закодований код було об’єднано, потім поділено по 8 біт та закодовано
відповідно до ASCII таблиці в новий файл.
61
А це означає, що для декомпресії даних необхідно буде
використовуючи таблицю ASCII кодів спочатку перетворити файл у
бінарний вигляд, а далі використовуючи поле fileHeader розшифрувати
закодований файл.
На рисунку 4.5 наведено структуру класу для зберігання і запису
вихідного файлу на диск.
Рисунок 4.5 – Вигляд структури класу CompressedByteFile
4.3 Розробка класів генерації таблиці кодування та обрахунку
частоти символів
Реалізований клас FiboFrequency є класом в якому виконується
обрахунок частоти символів у вхідному класі.
Для того, щоб обрахувати частоту використовується метод
CalculateFrequencyForByteFile. Даний метод працює наступним чином, він
приймає вхідний файл, а далі, на основі цього файлу, створює список, де
записуються унікальні символи та кількість їх повторень. Потім, даний
список сортується за кількостю повторень та записується як Dictionary< byte,
int >, що відповідно далі записується в поле characterFrequency класу
ByteFileCharacterFrequency.
На рисунку 4.6 наведено структуру класу для обрахунку частоти появи
символів.
Для побудови таблиці кодування застосовується два класи –
FiboRank'sCode і FiboRanksUpgraded. Перший клас будує таблицю кодування,
62
відповідно до стандартного методу, в свою чергу, другий клас відповідно до
удосконаленого методу.
Розробка стандартного та удосконаленого методів, в свою чергу, мають
спільні та відмінні методи.
Рисунок 4.6 – Структура класу обрахунку частоти появи символів
FiboFrequency
Для початку розглянемо спільні методи реалізації двох класів.
Спільні методи. Одним із спільних методів є метод GenerateFiboCode,
який після отримання параметру виконує підрахунок кількості унікальних
символів для обох класів.
Метод GenerateFiboCode будує результуючий список та заповнює його
даними отриманими з методу GenerateFiboRanks. Наступним кроком, всі
значення зі списку дзеркально відображаються, і до кожного визначеного
значення додається закінчення «1». Для дзеркального відображення та
додавання закінчення реалізовано методи ReverseCode і AddEnding.
Метод ReverseCode зчитує кожне значення зі списку при цьому
перетворюючи його в масив типу char та при допомозі вбудованого в
платформу методу для списків Array.Reverse дзеркально відображає список,
далі перетворює відображений масив до типу string та повертає його.
Метод AddEnding дописує символ одиниці в кінець одержаного
параметру типу string та повертає результат.
Даний результат замінює попереднє значення, що містилося в
результуючому списку у методі GenerateFiboCode.
63
Тепер розглянемо процес генерації таблиці. Для цього застосовується
метод GenerateFiboRanks. Даний метод приймає визначену кількість
унікальних символів та, при цьому, формує список для даної кількості
елементів. Побудований список містить в собі коди Фібоначчі, які ще не
інвертовані та не включають закінчення. Далі, відповідно до визначеного
правила методу, яке говорить про те, що два символи одиниці не можуть
стояти в коді поряд, список перетворюється та записується певними
унікальними бінарними числами, що обраховуються в методі
AddBinaryDigits. За допомогою методу CheckBinnaryDigitsOnFiboCorrectness
список перевіряється на коректність відповідно до визначених правил для
удосконаленого методу. Відповідно, в зміну fiboDigit методу
GenerateFiboRanks записується початкове бінарне число «1» та додається до
результуючого списку. В подальшому дане число збільшується на 1 на
кожному кроці, відповідно до правил додавання бінарних чисел у циклі, та
змінна fiboDigit перезаписується новим значенням. У випадку, коли нове
значення змінної fiboDigit проходить перевірку на коректність, то відповідно
воно додається до результуючого списку, і навпаки, відповідно не додається,
у випадку, коли число не пройшло перевірку. Коли число було додане до
списку, то в цьому випадку лічильник циклу збільшується на 1. Цикл
виконуватиметься до тих пір, поки лічильник не досягне числа, що рівне
кількості унікальних символів. Після закінчення роботи циклу результуючий
список буде заповнено бінарними числами, що задовольняють вимогам для
стандартного методу на базі кодів Фібоначчі.
Після того, як буде повернуто розроблений список до методу
GenerateFiboCode для кожного значення списку буде проведено додаткову
обробку, що реалізована в методах ReverseCode і AddEnding.
Відмінні методи. Після того, як результуючий список буде повернуто
до методу CreateDecodingTable для реалізованого списку буде проведено
декілька різних етапів обробки. Для початку розглянемо обробку
результуючого списку відповідно до стандартного методу.
64
Одержаний список буде об’єднано із попередньо переданим в даний
метод параметром fiboFrequency та записано в результуючу зміну, що має
тип Dictionary<byte, string> [4], куди записано код, який являється
стандартним кодом змінної та код відповідно до згенерованої таблиці.
На рисунку 4.7 наведено структуру класу стандартного методу
FiboRank'sCode.
Рисунок 4.7 – Структура класу для побудови таблиці кодування
FiboRank'sCode
Наступним розглянемо алгоритм реалізації удосконаленого методу.
Перед тим, як виконається метод GenerateFiboCode необхідно виконати
метод SetMaxGenerateRank. Даний метод повинен визначити, яке саме із
виключень можна додати в таблицю та, відповідно, скільки необхідно
згенерувати додаткових таблиць, що будуть об’єднуватися в результуючу
таблицю.
Тепер, розглянемо більш детально метод SetMaxGenerateRank. Він
основується на використанні виключень, що описані в розділі 2.2, а саме на
базі таблиці 2.1. Логіка роботи даного методу заключається в наступному, що
при використанні певної кількості унікальних символів можна вводити
виключення в таблицю. Такими числами являються «7», «26», «79», «221». А
65
це означає, що у випадку кількість унікальних символів меншої ніж 7, можна
ввести виключення у вигляді коду «11». У випадку, коли кількість символів
знаходиться між 7 та 26, можна ввести виключення «1111» і т. д. Ще однією
властивістю методу є те, на основі кількості унікальних символів він може
визначати скільки додаткових таблиць необхідно згенерувати.
Розглянемо тепер метод CreateDecodingTable. Після визначення за
допомогою введення виключення скільки додаткових таблиць необхідно
згенерувати, виконується метод GenerateFiboCode. Коли кількість унікальних
символів була меншою за 7 символів, то в результуючу таблицю буде
записано виключення у вигляді коду «11», а далі буде дописано результат
роботи методу GenerateFiboCode. У випадку, коли кількість унікальних
символів знаходилася в межах від 7 до 26 символів, то в результуючу
таблицю буде записано результати виконання методу GenerateFiboCode, а
вже потім буде додано виключення у вигляді коду «1111». Наступним
кроком є виконання методу CreateNewRankLayer в який передається, як
результат, виконання методу GenerateFiboCode.
За допомогою методу CreateNewRankLayer до всіх значень із
попереднього списку додається закінчення у вигляді коду «11», оскільки це і
є всією відмінністю між таблицями різних рангів.
Розглянемо більш детально поняття таблиць різних рангів на базі
прикладу, що наведено в таблиці 4.1.
Таблиця 4.1 – Таблиця кодів Фібоначчі відповідно до
удосконаленого методу стиснення текстових файлів
Ранг 1 2 3 4 5 6 7
Код згідно 011 0011 1011 00011 10011 01011 01111
нового
методу
Ранг 8 9 10 11 12 13 14
Код згідно 000011 100011 010011 001011 101011 001111 101111
нового
66
методу
Проведемо дослідження кодів, що знаходяться під рангом 1 та 7, а це
відповідно «011» та «01111». Також для прикладу візьмемо ранг 3 та 14.
Розглянувши обрані приклади можна побачити, що якщо закінчення
відкинути в даних кодах, то ці коди є однаковими.
А це означає, що принцип генерації таблиці кодів, що було розглянуто
вище складається з наступних етапів:
 генерація базової таблиці, куди записані бінарні числа, які
задовольняють вимоги щодо удосконаленого методу;
 додання закінчення;
 дзеркальне відображення базової таблиці.
Як було вказано у пунктах 2.1 та 2.2 щодо удосконаленого методу, а
саме, що таблиця розширюється за рахунок введення нових закінчень. Це
говорить про те, що вимоги до бінарних чисел для базової таблиці не
змінюються. Згідно з чим, удосконалений метод також можна представити як
декілька однакових таблиць, де коди відрізняються тільки закінченнями.
Об’єднавши дані таблиці і відсортувавши їх за зростанням довжини коду
можна отримати дані наведені в таблиці 4.2.
Таблиця 4.2 – Таблиця кодів на базі кодів Фібоначчі до 26 рангу
відповідно до удосконаленого методу
Ранг 1 2 3 4 5 6 7
Код 011 0011 1011 00011 10011 01011 01111
згідно
нового
методу
Ранг 8 9 10 11 12 13 14
Код 000011 100011 010011 001011 101011 001111 101111
згідно
нового
методу
Ранг 15 16 17 18 19 20 21
Код 0000011 1000011 0100011 0010011 1010011 0001011 1001011
67
згідно
нового
методу
Продовження таблиці 4.2
Ранг 22 23 24 25 26
Код 0101011 0001111 1001111 0101111 0111111
згідно
нового
методу
Провівши дослідження результатів наведених в таблицях 4.1 та 4.2
було визначено, що закінчення кодів у даних таблицях відрізняється лише на
парну кількість символів «11». Це показує, що з початкової таблиці можна
одержати таблицю 2-го рангу, після того, як додамо до всіх кодів закінчення
«11». Відповідно, з таблиці 2-го рангу аналогічним способом можна
отримати таблицю 3-го рангу знову ж додавши до всіх кодів закінчення «11».
Отже, метод CreateNewRankLayer просто будує нові таблиці на базі
переданої даному методу таблиці з додаванням, відповідно, до всіх кодів
закінчення «11».
Знову повернемося до дослідження методу CreateDecodingTable. Після
того, як буде створено таблицю 2-го рангу вона записується в результуючу
таблицю. А це означає, що в результуючій таблиці буде міститися таблиця 1-
го рангу, з виключенням у вигляді коду «1111» та таблиця 2-го рангу.
Аналогічно застосувавши наведені вище етапи, можна згенерувати, у разі
необхідності, таблиці для 3-го та 4-го рангів.
Після виконання визначених операцій результуюча таблиця сортується
за довжиною коду та повертається як результат.
На рисунку 4.8 наведено структуру класу для удосконаленого методу.
4.4 Реалізація сервісу стиснення текстового файлу та класів
стиснення текстових даних
Стиснення даних виконує у класі BiteFileCompressor.
68
До методу CompressByteFile виконується передача вхідного файлу та
згенерований fileHeader. Після цього, в циклі проходить покрокове
виконання вхідного файлу та заміна усіх символів на відповідні коди. Для
даних цілей використовується метод EncryptCharacter. Даний метод повертає
код відповідного символу із таблиці fileHeader. Після закінчення заміни усіх
символів результат суцільно в один ряд переписується, а потім розбивається
по 8 біт і знову кодується застосовуючи таблиці ASCII.
Рисунок 4.8 – Структура класу FiboRanksUpgraded
Метод CompressByteFile повертає результат у вигляді об’єкту типу
CompressedByteFile після виконання всіх операцій.
Також в реалізованому класі є метод WriteBinaryToFile, що може
записувати одержаний результат у виді бінарного файлу з розширенням .bin.
На рисунку 4.9 наведено структуру класу для стиснення текстових
даних.
69
Рисунок 4.9 – Структура класу стиснення даних BiteFileCompressor
Сервіс ByteFileCompressorService виконує повний алгоритм роботи
програмної реалізації, від зчитування вхідного файлу до повернення
результуючого файлу. На вхід методу CompressFile надходить вхідний файл,
після зчитання який записується у об’єкт типу ByteFile.
Далі використовуючи метод CalculateCharacterFrequency виконуємо
виклик методу CalculateFrequencyForBiteFile із класу FiboFrequency. Як
результат отримуємо таблиці частоти повторень символів.
Після того, як було отримано таблиці частота передається у метод
GenerateByteFileHeader, з якого викликається метод CreateDecodingTable із
класу FiboRanksUpgraded для стиснення даних реалізованим удосконаленим
методом, або із класу FiboRank'sCode для стиснення даних стандартним
вихідним методом. Як результат повертається таблиця кодів відповідно до
обраного методу.
Одержана таблиця передається до методу CompressByteFile, в якому за
допомогою виклику методу CompressByteFile із класу ByteFileCompressor
виконується стиснення текстового файлу.
На рисунку 4.10 наведено структуру сервісу ByteFileCompressorService.
70
Рисунок 4.10 – Структура сервісу ByteFileCompressorService
4.5 Реалізація тестових рішень для перевірки ефективності
удосконаленого методу стиснення текстових файлів
Для перевірки роботи реалізованих алгоритмів було розроблено ряд
тест кейсів [16] (ТК) та методів. Основними трьома тестовими класами [17]
являються FiboRank_SCodeTest, FiboRanksUpgradedCodeTest та
CompressorPerformanceTest.
Реалізований клас FiboRank_SCodeTest містить тести, які розроблені
для перевірки роботи усіх логічних елементів класу FiboRank`sCode.
Реалізований клас містить тести, що виконують перевірку процесу додавання
бінарних чисел, перевірки правил на коректність та загальні тести щодо
перевірки роботи взаємодії усіх методів в класі.
На рисунку 4.11 наведено структуру класу FiboRank_SCodeTest.
71
Рисунок 4.11 – Структура класу FiboRank_sCodeTest для перевірки всіх
логічних елементів класу
Клас FiboRanksUpgradedCodeTest містить тест кейси для перевірки усіх
способів роботи класу FiboRanksUpgraded. Аналогічно до роботи класу
FiboRank_SCodeTest методи даного класу перевіряють бінарне додавання,
перевірку дотримання правил коректності і взаємодію сервісів (методів)
генерації таблиці. Окрім цього, клас містить також тести щодо перевірки
роботи системи рангів таблиць, створення декількох таблиць та об’єднання їх
в результуючу таблицю.
На рисунку 4.12 наведено структуру класу FiboRanksUpgradedCodeTest
що містить тести для перевірки усіх способів роботи класу.
72
Рисунок 4.12 – Структура тестів класу FiboRanksUpgradedCodeTest
Клас CompressorPerformanceTest вміщує в себе декілька тест-кейсів
[16], за допомогою яких виконується порівняння затраченого часу та
ефективності стиснення текстових повідомлень різними методами. Клас, що
розглядається, містить три тести – для стандартного методу, удосконаленого
методу і методу з виключенням.
Кожен з розглянутих методів емулює роботу [17] для класу
ByteFileCompressorService, для якого у методі GenerateByteFileHeader
вказується потрібний метод для генерації таблиці кодів.
Ще для даних методів задано заміри часу та виведення інформації
щодо закодованого файлу, щоб відслідковувати ефективність та
закономірності в роботах методів.
На рисунку 4.13 наведено структуру класу CompressorPerformanceTest.
73
Рисунок 4.13 – Структура класу CompressorPerformanceTest
Більш детально особливості усіх методів та класів приведено в Додатку
Б, де наведено детальний код реалізації бібліотеки. Реалізований код
програми, ще не являється фінальним, а є тільки базовим та може бути
удосконаленим в залежності від потреби різних систем.
4.6 Підключення реалізованої бібліотеки
Щоб підключити реалізовану бібліотеку до проекту в Visual Studio
2022 потрібно відкрити контекстне меню проекту. Вигляд контекстного
меню проекту приведено на рисунку 4.14.
Наступний крок – перейти в розділ «Додати» (Add) та вибрати пункт
«Посилання» (Reference), як наведено на рисунку 4.15.
Далі повинен відкритися менеджер посилань (Reference manager). В
даній вкладці заходимо у розділ «Огляд» (Browse) в меню розділів та
натискаємо кнопку «Огляд» (Browse).
На рисунку 4.16 наведено вигляд менеджера посилань.
У провіднику потрібно вказати шлях до файлу реалізованої бібліотеки
FiboCompressor.h. Наступним кроком, для подальшої роботи з бібліотекою
необхідно додавати рядок #include «FiboCompressor.h» в класах, де будуть
застосовані методи бібліотеки, яка додається.
74
Рисунок 4.14 – Вигляд контекстного меню проекту
Рисунок 4.15 – Вигляд меню «Додати»
Рисунок 4.16 – Вигляд менеджеру посилань
75
4.6.1 Застосування методів бібліотеки
Для застосування методів бібліотеки потрібно після підключення
реалізованої бібліотеки створити об’єкт типу ByteFileCompressorService. При
допомозі даного сервісу можна виконати, як повний алгоритм стиснення
текстового файлу, так і поетапно виконувати увесь алгоритм.
Короткий огляд деяких методів. Метод CompressFile(byte[] byteFile,
string path) отримує на вхід файл, що перетворений у масив байтів, та шлях
до даного файлу. Застосовуючи даний метод увесь алгоритм стиснення даних
буде пройдений автоматично із використанням удосконаленого методу
стиснення текстових повідомлень. На виході буде отримано об’єкт типу C
ompressedByteFile, що містить всю потрібну інформацію про стиснутий файл.
Метод SetByteFile(byte[] file) приймає на свій вхід масив з байтів та
записує їх у об’єкт типу ByteFile. На виході буде отримано саме об’єкт цього
типу. Даний метод в алгоритмі необхідно виконувати першим.
Метод CalculateCharacterFrequency(ByteFile file) приймає на свій вхід
об’єкт типу ByteFile. Цей метод обчислює частоту повторень символів у
вхідному файлі. На виході буде отримано об’єкт типу
ByteFileCharacterFrequency. Цей метод потрібно виконувати після методу
SetByteFile.
Наступним описуваним методом є GenerateByteFileHeader
(ByteFileCharacter Frequency characterFrequency), що приймає на вхід об’єкт
типу ByteFileCharacterFrequency та, відповідно, генерує таблицю кодування.
Саме для цього методу передбачена можливість змінити метод стиснення
даних. Для зміни методу стиснення цього необхідно в рядку
FiboRanksUpgraded fiboRank = new FiboRanksUpgraded() змінити клас на
FiboRank_sCode, щоб використати стандартний метод. На виході даний
метод поверне об’єкт типу ByteFileHeader. Обраний метод має виконуватися
після методу CalculateCharacterFrequency.
Останнім являється метод CompressByteFile(ByteFile file,
ByteFileHeader fileHeader, string path). На вході зявляється об’єкт типу B
76
yteFile, ByteFileHeader і шлях до самого файлу. Даний метод виконує
стиснення текстового файлу та повертає об’єкт типу CompressedByteFile.
Даний метод повинен виконуватися після методу GenerateByteFileHeader.
Під час удосконалення або додання нових методів порядок
застосування методів може бути зміненим.
4.6.2 Застосування тестів в процесі тестування бібліотеки
Щоб перевірити роботу поточних методів або перевірити методи після
їх удосконалення розроблено ряд тестових класів.
До основних тестових класів та їх застосування відносяться класи
наведені нижче.
Клас FiboFrequencyTest застосовується, щоб перевірити правильність
визначення кількості унікальних символів та сортування на коректність
результуючої таблиці. В процесі зміни алгоритму роботи класу FiboFrequency
потрібно перевірити роботу нового реалізованого алгоритму застосовуючи
даний тестовий клас.
Клас FiboRank_sCodeTest включає ряд тестів щодо перевірки роботи
усіх методів класу FiboRank_sCode, що несе відповідалбність за стандартний
алгоритм стиснення даних. В процесі зміни даного класу необхідно виконати
перевірку нового реалізованого алгоритму на основі тестів цього класу. Під
час додання нових методів до класу FiboRank_sCode потрібно реалізувати
тести, що перевірятимуть роботу даного методу.
Клас FiboRanksUpgradedCodeTest включає тести щодо перевірки
роботи удосконаленого методу, а саме, класу FiboRanksUpgraded. Подібно до
попереднього класу під час внесення змін до поточних методів потрібно
перевірити новий реалізований алгоритм на основі існуючих тестів даного
класу, або ж розробити нові тести в процесі додавання нових методів до
класу FiboRanksUpgraded.
Клас CompressorPerformanceTest виконує перевірку на швидкість та
ефективність роботи для стандартного та удосконаленого методів.
77
Застосовуючи даний клас можна переглянути згенеровані таблиці, також
кількість витраченого часу на стиснення даних і розмір файлу до та після
стиснення.
Клас ByteFileCompressorServiceTest емітуючи роботу класу
ByteFileCompressorService перевіряє сукупну роботу всього алгоритму. При
допомозі даного класу можна перевірити привильність роботи класу
ByteFileCompressorService.
4.7 Висновки до розділу 4
В четвертому розділі було приведено загальну діаграму класів,
елементами якої є всі класи та взаємозв’язки між ними, а також наведено
список усіх класів та вказано їхнє призначення.
В розділі детально описано структуру кожного класу, що відповідає за
збереження даних в процесі виконання стиснення текстових повідомлень.
Також, було проведено огляд принципу та приведено алгоритм
обрахунку частоти унікальних символів та особливості зберігання даних.
В процесі дослідження було проведено огляд особливостей всіх
методів, що відповідальні за генерацію таблиць кодування. Як результат,
було виділено спільні та відмінні методи між класами FiboRank'sCode і
FiboRanksUpgraded. Також було проведено аналіз особливостей генерації
таблиці кодування, на основі прикладу наведеному в таблиці 4.1, для
удосконаленого методу. Як результат, було визначено загальний алгоритм
генерації таблиці саме для удосконаленого методу. На базі таблиць 4.1 та 4.2
було визначено та виведено закономірність щодо введення виключення в
таблицю кодування.
У результаті, було проведено огляд загального принципу стиснення
даних та описано детальний алгоритм методів, що виконують стиснення
даних, а також наведено опис тестів та особливостей їх застосування для
перевірки коректної роботи програмної реалізації.
78
В розділі наведено етапи щодо підключення до проекту в V
isual Studio 2022 розробленого програмного рішення у вигляді бібліотеки.
79
ВИСНОВКИ
Під час виконання кваліфікаційної роботи магістра було розглянуто
тему дослідження та удосконалення методу стиснення даних текстових
файлів. В процесі дослідження було виділено основні недоліки для
стандартного методу стиснення даних. Врахувавши визначені недоліки було
реалізовано удосконалений метод, що збільшує ефективність стиснення
даних текстових файлів з великою кількістю унікальних символів.
Реалізований метод повинен забезпечити подальший розвиток стиснення
даних текстових файлів.
В процесі виконання кваліфікаційної роботи було реалізовано
програмне рішення у вигляді бібліотеки для мови програмування C#, що
містить в собі алгоритми стиснення даних як стандартним, так і
удосконаленим методом із виключенням. Реалізоване програмне рішення
побудоване на базі об’єктно-орієнтованого програмування з відкритим
кодом, щоб мати можливість його вдосконалення в подальшому та розвитку
даного методу стиснення даних текстових файлів в цілому.
В роботі було проведено дослідження актуальності та доцільності
стиснення даних на сьогоднішній день. В процесі дослідження було
встановлено відношення між кількістю інформаційного трафіку, що потрібно
зберігати та розвитком технологій зберігання даних на жорстких дисках. На
базі отриманих даних було визначено, що розвиток стиснення даних є
важливим питанням в наш час.
В першому розділі роботи було досліджено загальний принцип
компресії даних, його різновидів та проаналізовано зв’язок поміж розподілом
частоти вживання деяких літер та можливістю застосування стиснення даних
на базі кодів динамічного розміру. Також розглянуто загальний принцип
80
стиснення даних на основі кодів Фібоначчі та способи побудови таблиць
кодування для методу, що досліджується.
На основі одержаних результатів було проведено практичні обрахунки
ефективності методу у випадку розподілу символів відповідно до статистики
та під час рівномірного розподілу символів. Виконавши дослідження
отриманих, як результат, обрахунків ефективності стиснення даних для
різних випадків було виділено основні недоліки методу та подальшого
удосконалення його алгоритму.
В другому розділі наведено опис методу удосконалення оригінального
методу, показники ефективності удосконаленого методу та визначено
можливість введення виключень в таблицю кодування, для подальшого
збільшення ефективності стиснення даних.
В третьому розділі було проаналізовано основні технології, що
застосовувалися під час розробки програмного рішення. Було вибрано мову
C# для реалізації програмного рішення та максимальної ефективності роботи
із файловою системою Windows. Як основу структури коду бібліотеки було
обрано об’єктна-орієнтоване програмування.
В розділі 4 було приведено загальну діаграму класів програмної
реалізації та виконано аналіз детальної роботи всіх класів та методів.
А також в розділі було окреслено декілька закономірностей щодо
генерації таблиць кодування та наведено опис призначення тестів в
реалізованому програмному рішенні.
Реалізована бібліотека повинна забезпечити можливість розвитку як
стандартного методу, так і удосконаленого методу стиснення даних
текстових файлів. Розроблене програмне рішення може бути легко
удосконалено та масштабовано. Також реалізоване програмне рішення у
вигляді бібліотеки може бути застосовано під час розробки програмного
забезпечення, що направлене на стиснення даних текстових файлів.
81
ПЕРЕЛІК СКОРОЧЕНЬ ТА УМОВНИХ ПОЗНАЧЕНЬ
ASCII American standard code for information interchange
CLR Common Language Runtime
UML Unified modeling language
Еб Ексабайт
ООП Об’єктно-орієнтоване програмування
ПЗ Програмне забезпечення
ПР Програмне рішення
ТК Тест кейс
82
СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ
1. ASCII Table and description / asciitable.com – official website
[Electronic resource]. – Access mode : http://www.asciitable.com.
2. Building a class library with C# and .NET Core in Visual Studio 2017 /
docs.microsoft.com – official developer documentation [Electronic resource]. –
Access mode : https://docs.microsoft.com/en-us/dotnet/core/tutorials/library-with-
visual-studio.
3. C# Object-oriented programming / docs.microsoft.com – official
developer documentation [Electronic resource]. – Access mode :
https://docs.microsoft.com/en-us/dotnet/articles/csharp/programming-
guide/concepts/object-oriented-programming.
4. C# Class organization / docs.microsoft.com – official developer
documentation [Electronic resource]. – Access mode :
h t tps : / /docs .microsof t . com/en-us /do tne t /a r t i c les /csharp / language-
reference/keywords/class.
5. C# tutorials / msdn.microsoft.com – official developer site [Electronic
resource]. – Access mode : https://msdn.microsoft.com/uk-
ua/library/aa288436(v=vs.71).aspx.
6. C# Write a binary file / docs.microsoft.com – official developer
documentation [Electronic resource]. – Access mode :
https://social.msdn.microsoft.com/Forums/vstudio/en-US/005f0060-09c1-4ba9-
8a40-cc7fa7284320/c-write-a-binary-file?forum=csharpgeneral .
7. Data compression / britannica.com – official website [Electronic
resource]. – Access mode : https://www.britannica.com/technology/data-
compression.
8. Data Compression using Fibonacci Sequence / academia.Edu – official
website [Electronic resource]. – Access mode : http://www.academia.
edu/32058265/Data_Compression_using_Fibonacci_Sequence.
83
9. Fast Fibonacci Encoding Algorithm / ceur-ws.org – official website
[Electronic resource]. – Access mode : http://ceur-ws.org/Vol-567/paper14. pdf.
10. Fibonacci Data Compression / code.activestate.com – official website
[Electronic resource]. – Access mode : http://code.activestate.com/recipes/577554-
fibon acci-data-compression.
11. Fibonacci sequence / mathsisfun.com official – official website
[Electronic resource]. – Access mode :
https://www.mathsisfun.com/numbers/fibonacci-sequen ce.html
12. History of the hard drive / cloudwards.net – official website [Electronic
resource]. – Access mode : https://www.cloudwards.net/history-of-the-hard-drive/.
13. Letter frequency of different languages / letterfrequency.org – official
website [Electronic resource]. – Access mode : https://www.
joyofdata.de/blog/frequency-of-character-combi nations/
14. The Unified Modeling Language / uml-diagrams.org – official website
[Electronic resource]. – Access mode : https://www.uml-diagrams.org/.
15. Using Fibonacci Compression Codes as Alternatives to Dense Codes /
ieeexplore.ieee.org – official website [Electronic resource]. – Access mode :
https://ieeexplore.ieee.org/document/4483325.
16. Unit testing best practices / docs.microsoft.com – official developer
documentation [Electronic resource]. – Access mode :
https://docs.microsoft.com/en-us/dotnet/core/testing/unit-testing-best-practices.
17. Unit testing C# with NUnit and .NET Core / docs.microsoft.com –
official developer documentation [Electronic resource]. – Access mode :
https://docs.microsoft.com/en-us/dotnet/core/testing/unit-testing-with-nunit.
18. Зростання світового обсягу даних / ukraine.emc.com – офіційний
сайт [Електронний ресурс]. – Режим доступу : https://
ukraine.emc.com/about/news/press/2011/20110628-01. htm.
19. Історія розвитку жорстких дисків / interteam.com.ua – офіційний
сайт [Електронний ресурс]. – Режим доступу : https://interteam.com.ua/istoriya-
zhestkix-diskov-ot-pervogo-hdd-do-ssd/.
84
20. Частоти повторюваності букв і біграм у відкритих текстах
українською мовою / ecobio.nau.edu.ua – офіційний сайт [Електронний
ресурс]. – Режим доступу :
http://ecobio.nau.edu.ua/index.php/ZI/article/viewFile/ 1968/1959.
21. Чепеленко А.В. Вдосконалення методу компресії даних на основі
коду Фібоначчі / А.В. Чепеленко, Т.В. Миронюк / Вісник Черкаського
державного технологічного університету. Серія: Технічні науки: наук.-техн.
журн. / Черкас. держ. технол. ун-т. – Черкаси: ЧДТУ, 2018. – Вип. 4. – с.
94100.
ДОДАТОК А
«ЗАТВЕРДЖУЮ»
Завідувач кафедри ІБ та КІ
д.т.н., професор Віра БАБЕНКО
__________________
«___» _____________ 2023 р.
Дослідження та удосконалення методу стиснення
даних текстових файлів
Специфікація
482.ЧДТУ.32276-01
Листів 2
Розробник _______________ Ілля САЛОГУБ
Керівник _______________ Тетяна МИРОНЮК
Черкаси 2023
2
482.ЧДТУ.32276-01
Позначення Найменування Примітка
Документація
482.ЧДТУ.32276-01 12 01 Текст програми
482.ЧДТУ. 32276-01 32 01 Інструкція системного
програміста
ДОДАТОК Б
Дослідження та удосконалення методу стиснення
даних текстових файлів
Текст програми
482.ЧДТУ.32276-01 12 01
Листів 23
Розробник: Ілля САЛОГУБ
Черкаси 2023
2
482.ЧДТУ.32276-01 12 01
1. Код класу ByteFile:
namespace FiboCompressor.Entity.ByteFileEntity
{
public class ByteFile
{
public byte[] data { get; set; }
}
}
2. Код класу ByteFileCharacterFrequency:
namespace FiboCompressor.Entity.ByteFileEntity
{
public class ByteFileCharacterFrequency
{
public Dictionary<Byte, int> characterFrequency { get; set; }
}
}
3. Код класу ByteFileCompressor
namespace FiboCompressor.Entity.ByteFileEntity
{
public class ByteFileCompressor
{
public CompressedByteFile CompressByteFile(ByteFile byteFile, ByteFileHeader
fileHeader, string path)
{
CompressedByteFile compressedByteFile = new CompressedByteFile();
compressedByteFile.fileHeader = fileHeader;
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < byteFile.data.Length; i++)
{
stringBuilder.Append(EncryptCharacter(byteFile.data[i], fileHeader));
}
compressedByteFile.compressedData = stringBuilder.ToString();
using (
BinaryWriter binaryWriter =
new BinaryWriter(File.Open(path + "\\test2.bin", FileMode.Create))
)
{
WriteBinaryToFile(stringBuilder.ToString(), binaryWriter);
3
482.ЧДТУ.32276-01 12 01
binaryWriter.Close();
}
return compressedByteFile;
}
private string EncryptCharacter(byte _byte, ByteFileHeader fileHeader)
{
foreach (var k in fileHeader.fileHeader)
{
if (k.Key == _byte)
{
return k.Value;
}
}
return null;
}
private void WriteBinaryToFile(string data, BinaryWriter binaryWriter)
{
int dataSize = data.Length;
byte[] bytesToWrite;
bool rem = false;
if (dataSize % 8 != 0)
{
bytesToWrite = new byte[dataSize / 8 + 1];
rem = true;
}
else
{
bytesToWrite = new byte[dataSize / 8];
}
Console.WriteLine("New size: " + bytesToWrite.Length);
for (int j = 0; j < dataSize / 8; j++)
{
var x = Convert.ToByte(data.Substring(j * 8, 8), 2);
bytesToWrite[j] = x;
}
if (rem)
4
482.ЧДТУ.32276-01 12 01
{
bytesToWrite[dataSize / 8] = Convert.ToByte(data.Substring((dataSize / 8) * 8-1,
dataSize % 8),2);
}
foreach (var k in bytesToWrite)
{
binaryWriter.Write(k);
}
}
}
}
4. Код класу ByteFileHeader
namespace FiboCompressor.Entity.ByteFileEntity
{
public class ByteFileHeader
{
public Dictionary<byte, string> fileHeader { get; set; }
}
}
5. Код класу CompressedByteFile
namespace FiboCompressor.Entity.ByteFileEntity
{
public class CompressedByteFile
{
public string compressedData { get; set; }
public ByteFileHeader fileHeader { get; set; }
}
}
6. Код класу FiboFrequency
namespace FiboCompressor.Entity
{
public class FiboFrequency
{
static public Dictionary<byte, int> CalculateFrequencyForByteFile(ByteFile byteFile)
{
Dictionary<byte, int> result = byteFile.data.GroupBy(c => c)
.Select(c => new { Byte = c.Key, Count = c.Count() })
.OrderByDescending(c => c.Count)
.ToDictionary(c => c.Byte, c => c.Count);
5
482.ЧДТУ.32276-01 12 01
return result;
}
}
}
7. Код класу FiboRank_sCode
namespace FiboCompressor.Entity
{
public class FiboRank_sCode
{
public Dictionary<byte, string> CreateDecodingTable(ByteFileCharacterFrequency
fiboFrequency)
{
var fiboCode = GenerateFiboCode(fiboFrequency.characterFrequency.Count);
int i = 0;
Dictionary<byte, string> result = new Dictionary<byte, string>();
foreach (var k in fiboFrequency.characterFrequency)
{
result.Add(k.Key, fiboCode[i]);
i++;
}
return result;
}
public List<string> GenerateFiboCode(int n)
{
var fiboRanks = GenerateFiboRanks(n);
List<string> fiboCode = new List<string>();
fiboCode = AddEnding(ReverseCode(fiboRanks));
return fiboCode;
}
public List<string> ReverseCode(List<long> code)
{
List<string> result = new List<string>();
for (int i = 0; i < code.Count; i++)
{
result.Add(ReverseString(code[i].ToString()));
}
return result;
}
public List<string> AddEnding(List<string> code)
6
482.ЧДТУ.32276-01 12 01
{
var result = code;
for (int i = 0; i < result.Count; i++)
{
result[i] = AddExtraEndingForRank(result[i].ToString());
}
return result;
}
public List<long> GenerateFiboRanks(int n)
{
List<long> fiboRanks = new List<long>();
int k = 0;
long fiboDigit = 1;
fiboRanks.Add(1);
while (k < n - 1)
{
var digit = AddBinaryDigits(fiboDigit, 1);
if (CheckBinaryDigitsOnFiboCorrectness(digit))
{
fiboRanks.Add(digit);
k++;
}
fiboDigit = digit;
}
return fiboRanks;
}
public long AddBinaryDigits(long digit1, long digit2)
{
int i = 0;
long rem = 0;
List<long> sum = new List<long>();
string result = "";
while (digit1 != 0 || digit2 != 0)
{
sum.Add((digit1 % 10 + digit2 % 10 + rem) % 2);
i++;
rem = (digit1 % 10 + digit2 % 10 + rem) / 2;
digit1 = digit1 / 10;
digit2 = digit2 / 10;
}
7
482.ЧДТУ.32276-01 12 01
if (rem != 0)
{
sum.Add(rem);
}
for (i = sum.Count - 1; i >= 0; i--)
{
result += sum[i];
}
return Convert.ToInt64(result);
}
public bool CheckBinaryDigitsOnFiboCorrectness(long digit)
{
string digitInString = digit.ToString();
for (int i = 1; i < digitInString.Length; i++)
{
if (digitInString[i] == '1' && digitInString[i - 1] == '1')
{
return false;
}
}
return true;
}
public string ReverseString(string s)
{
char[] charArray = s.ToCharArray();
Array.Reverse(charArray);
return new string(charArray);
}
public string AddExtraEndingForRank(string s)
{
return s + '1';
}
}
}
8. Код класу FiboRanksUpgraded
namespace FiboCompressor.Entity
{
public class FiboRanksUpgraded
{
8
482.ЧДТУ.32276-01 12 01
public Dictionary<byte, string> CreateDecodingTable(ByteFileCharacterFrequency
fiboFrequency)
{
var firstLevelCode = GenerateFiboCode(fiboFrequency.characterFrequency.Count);
int i = 0;
int numberOfCharacters = firstLevelCode.Capacity;
var secondLevelCode = new List<string>();
secondLevelCode.AddRange(firstLevelCode);
secondLevelCode = AddDoubleEnding(secondLevelCode);
var thirdLevelCode = new List<string>();
thirdLevelCode.AddRange(secondLevelCode);
thirdLevelCode = AddDoubleEnding(thirdLevelCode);
var fourthLevelCode = new List<string>();
fourthLevelCode.AddRange(thirdLevelCode);
fourthLevelCode = AddDoubleEnding(fourthLevelCode);
var fifthLevelCode = new List<string>();
fifthLevelCode.AddRange(fourthLevelCode);
fifthLevelCode = AddDoubleEnding(fifthLevelCode);
var sixthLevelCode = new List<string>();
sixthLevelCode.AddRange(fifthLevelCode);
sixthLevelCode = AddDoubleEnding(sixthLevelCode);
var seventhLevelCode = new List<string>();
seventhLevelCode.AddRange(sixthLevelCode);
seventhLevelCode = AddDoubleEnding(seventhLevelCode);
var summaryCode = new List<string>();
summaryCode.AddRange(firstLevelCode);
summaryCode.AddRange(secondLevelCode);
summaryCode.AddRange(thirdLevelCode);
summaryCode.AddRange(fourthLevelCode);
summaryCode.AddRange(fifthLevelCode);
9
482.ЧДТУ.32276-01 12 01
summaryCode.AddRange(sixthLevelCode);
summaryCode.AddRange(seventhLevelCode);
summaryCode.Remove("11");
List<string> sortedSummary = summaryCode.OrderBy(c =>
c.Length).Take(numberOfCharacters).ToList();
Dictionary<byte, string> result = new Dictionary<byte, string>();
foreach (var k in fiboFrequency.characterFrequency)
{
result.Add(k.Key, sortedSummary[i]);
i++;
}
return result;
}
public List<string> GenerateFiboCode(int n)
{
var fiboRanks = GenerateFiboRanks(n);
List<string> fiboCode = new List<string>();
fiboCode = AddEnding(ReverseCode(fiboRanks));
return fiboCode;
}
public List<long> GenerateFiboRanks(int n)
{
List<long> fiboRanks = new List<long>();
int k = 0;
long fiboDigit = 1;
//fiboRanks.Add(1);
while (k < n - 1)
{
var digit = AddBinaryDigits(fiboDigit, 1);
if (CheckBinaryDigitsOnFiboCorrectness(digit))
{
fiboRanks.Add(digit);
k++;
}
fiboDigit = digit;
}
10
482.ЧДТУ.32276-01 12 01
return fiboRanks;
}
public long AddBinaryDigits(long digit1, long digit2)
{
int i = 0;
long rem = 0;
List<long> sum = new List<long>();
string result = "";
while (digit1 != 0 || digit2 != 0)
{
sum.Add((digit1 % 10 + digit2 % 10 + rem) % 2);
i++;
rem = (digit1 % 10 + digit2 % 10 + rem) / 2;
digit1 = digit1 / 10;
digit2 = digit2 / 10;
}
if (rem != 0)
{
sum.Add(rem);
}
for (i = sum.Count - 1; i >= 0; i--)
{
result += sum[i];
}
return Convert.ToInt64(result);
}
public bool CheckBinaryDigitsOnFiboCorrectness(long digit)
{
string digitInString = digit.ToString();
for (int i = 1; i < digitInString.Length; i++)
{
if (digitInString[i] == '1' && digitInString[i - 1] == '1')
{
return false;
}
}
return true;
}
public List<string> ReverseCode(List<long> code)
11
482.ЧДТУ.32276-01 12 01
{
List<string> result = new List<string>();
for (int i = 0; i < code.Count; i++)
{
result.Add(ReverseString(code[i].ToString()));
}
return result;
}
public string ReverseString(string s)
{
char[] charArray = s.ToCharArray();
Array.Reverse(charArray);
return new string(charArray);
}
public List<string> AddEnding(List<string> code)
{
var result = code;
for (int i = 0; i < result.Count; i++)
{
result[i] = AddExtraEndingForRank(result[i].ToString());
}
return result;
}
public List<string> AddDoubleEnding(List<string> code)
{
var result = code;
for (int i = 0; i < result.Count; i++)
{
result[i] = AddExtraEndingForRank(result[i].ToString());
result[i] = AddExtraEndingForRank(result[i].ToString());
}
return result;
}
public string AddExtraEndingForRank(string s)
{
return s + '1';
}
}
}
9. Код класу ByteFileCompressorService
12
482.ЧДТУ.32276-01 12 01
namespace FiboCompressor.Service
{
public class ByteFileCompressorService
{
public CompressedByteFile CompressFile(byte[] file, string path)
{
ByteFile byteFile = SetByteFile(file);
ByteFileCharacterFrequency characterFrequency =
CalculateCharacterFrequency(byteFile);
ByteFileHeader fileHeader = GenerateByteFileHeader(characterFrequency);
CompressedByteFile result = CompressByteFile(byteFile, fileHeader, path);
return result;
}
private ByteFile SetByteFile(byte[] file)
{
ByteFile byteFile = new ByteFile();
byteFile.data = file;
return byteFile;
}
private ByteFileCharacterFrequency CalculateCharacterFrequency(ByteFile file)
{
ByteFileCharacterFrequency result = new ByteFileCharacterFrequency();
result.characterFrequency = FiboFrequency.CalculateFrequencyForByteFile(file);
return result;
}
private ByteFileHeader GenerateByteFileHeader(ByteFileCharacterFrequency
characterFrequency)
{
ByteFileHeader result = new ByteFileHeader();
FiboRanksUpgraded fiboRank = new FiboRanksUpgraded();
result.fileHeader = fiboRank.CreateDecodingTable(characterFrequency);
return result;
13
482.ЧДТУ.32276-01 12 01
}
private CompressedByteFile CompressByteFile(ByteFile file, ByteFileHeader fileHeader,
string path)
{
ByteFileCompressor fileCompressor = new ByteFileCompressor();
CompressedByteFile result = fileCompressor.CompressByteFile(file, fileHeader, path);
return result;
}
}
}
10. Код класу CompressorController
namespace FiboCompressor.Controller
{
class CompressorController
{
CompressedByteFile compressedByteFile;
public string CompressFile(byte[] byteFile, string path)
{
ByteFileCompressorService compressorService = new ByteFileCompressorService();
compressedByteFile = compressorService.CompressFile(byteFile, path);
return compressedByteFile.compressedData;
}
}
}
11. Код класу ByteFileCompressorServiceTest
namespace CompressorTest
{
[TestClass]
public class ByteFileCompressorServiceTest
{
[TestMethod]
public void CompressFileTest()
{
string text = "test";
var file = Encoding.ASCII.GetBytes(text);
14
482.ЧДТУ.32276-01 12 01
ByteFileCompressorService compressorService = new ByteFileCompressorService();
var expectedResult = "11011001111";
var actualResult = compressorService.CompressFile(file,"\\test.dat");
Assert.AreEqual(expectedResult, actualResult.compressedData);
}
}
}
12. Код класу FiboFrequencyTest
namespace CompressorTest
{
[TestClass]
public class FiboFrequencyTest
{
[TestMethod]
public void CalculateFrequencyForTextFileTest()
{
TextFile testTextFile = new TextFile();
testTextFile.data = "test";
Dictionary<Char, int> expectedResult = new Dictionary<char, int>();
expectedResult.Add('t', 2);
expectedResult.Add('e', 1);
expectedResult.Add('s', 1);
Dictionary<Char, int> actualResult =
FiboFrequency.CalculateFrequencyForTextFile(testTextFile);
CollectionAssert.AreEquivalent(expectedResult.ToList(), actualResult.ToList());
}
[TestMethod]
public void CalculateFrequencyForByteFileTest()
{
ByteFile byteFile = new ByteFile();
string text = "test";
byteFile.data = Encoding.ASCII.GetBytes(text);
var actualResult = FiboFrequency.CalculateFrequencyForByteFile(byteFile);
Dictionary<Byte, int> expectedResult = new Dictionary<Byte, int>();
15
482.ЧДТУ.32276-01 12 01
expectedResult.Add(116, 2);
expectedResult.Add(101, 1);
expectedResult.Add(115, 1);
CollectionAssert.AreEquivalent(expectedResult.ToList(), actualResult.ToList());
}
}
}
13. Код класу FiboRank_sCodeTest
namespace CompressorTest
{
[TestClass]
public class FiboRank_sCodeTest : FiboRank_sCode
{
[TestMethod]
public void GenerateFiboRanksTest()
{
FiboRank_sCode fiboRank = new FiboRank_sCode();
int n = 3;
List<long> expectedResult = new List<long>();
expectedResult.Add(1);
expectedResult.Add(10);
expectedResult.Add(100);
List<long> actualResult = fiboRank.GenerateFiboRanks(3);
CollectionAssert.AreEquivalent(expectedResult, actualResult);
}
[TestMethod]
public void GenerateFiboRanksForLargeNumberOfElemTest()
{
FiboRank_sCode fiboRank = new FiboRank_sCode();
int n = 256;
List<long> actualResult = fiboRank.GenerateFiboRanks(n);
}
[TestMethod]
public void AddBinaryDigitsTest()
{
FiboRank_sCode fiboRank = new FiboRank_sCode();
16
482.ЧДТУ.32276-01 12 01
int digit1 = 10;
int digit2 = 10;
int expectedResult = 100;
long actualResult = fiboRank.AddBinaryDigits(digit1, digit2);
Assert.AreEqual(expectedResult, actualResult);
}
[TestMethod]
public void CheckBinaryDigitsOnFiboCorrectnessTest()
{
FiboRank_sCode fiboRank = new FiboRank_sCode();
int digit1 = 1010;
int digit2 = 10110;
int digit3 = 11001;
int digit4 = 01001;
Assert.IsTrue(fiboRank.CheckBinaryDigitsOnFiboCorrectness(digit1));
Assert.IsTrue(fiboRank.CheckBinaryDigitsOnFiboCorrectness(digit4));
Assert.IsFalse(fiboRank.CheckBinaryDigitsOnFiboCorrectness(digit2));
Assert.IsFalse(fiboRank.CheckBinaryDigitsOnFiboCorrectness(digit3));
}
[TestMethod]
public void GenerateFiboCodeTest()
{
FiboRank_sCode fiboRank = new FiboRank_sCode();
int n = 3;
List<string> expectedResult = new List<string>();
expectedResult.Add("11");
expectedResult.Add("011");
expectedResult.Add("0011");
List<string> actualResult = fiboRank.GenerateFiboCode(3);
CollectionAssert.AreEquivalent(expectedResult, actualResult);
}
[TestMethod]
public void CreateDecodingTableForTextFileTest()
{
TextFile testTextFile = new TextFile();
17
482.ЧДТУ.32276-01 12 01
testTextFile.data = "test";
Dictionary<Char, string> expectedResult = new Dictionary<char, string>();
expectedResult.Add('t', "11");
expectedResult.Add('e', "011");
expectedResult.Add('s', "0011");
Dictionary<Char, int> frequency =
FiboFrequency.CalculateFrequencyForTextFile(testTextFile);
FiboRank_sCode fiboRank = new FiboRank_sCode();
TextFileCharacterFrequency characterFrequency = new TextFileCharacterFrequency();
characterFrequency.characterFrequency = frequency;
var actualResult = fiboRank.CreateDecodingTable(characterFrequency);
CollectionAssert.AreEquivalent(expectedResult, actualResult);
}
[TestMethod]
public void CreateDecodingTableForByteFileTest()
{
ByteFile byteFile = new ByteFile();
string text = "test";
byteFile.data = Encoding.ASCII.GetBytes(text);
Dictionary<Byte, string> expectedResult = new Dictionary<byte, string>();
expectedResult.Add(Encoding.ASCII.GetBytes("t")[0], "11");
expectedResult.Add(Encoding.ASCII.GetBytes("e")[0], "011");
expectedResult.Add(Encoding.ASCII.GetBytes("s")[0], "0011");
var frequency = FiboFrequency.CalculateFrequencyForByteFile(byteFile);
FiboRank_sCode fiboRank = new FiboRank_sCode();
ByteFileCharacterFrequency characterFrequency = new ByteFileCharacterFrequency();
characterFrequency.characterFrequency = frequency;
var actualResult = fiboRank.CreateDecodingTable(characterFrequency);
foreach (var k in actualResult)
{
Console.WriteLine(k.Key + " " + k.Value);
}
CollectionAssert.AreEquivalent(expectedResult, actualResult);
}
18
482.ЧДТУ.32276-01 12 01
[TestMethod]
public void CreateDecodingTableForByteFileLOngTextTest()
{
ByteFile byteFile = new ByteFile();
string text = "test";
byteFile.data = Encoding.ASCII.GetBytes(text);
Dictionary<Byte, string> expectedResult = new Dictionary<byte, string>();
expectedResult.Add(Encoding.ASCII.GetBytes("t")[0], "11");
expectedResult.Add(Encoding.ASCII.GetBytes("e")[0], "011");
expectedResult.Add(Encoding.ASCII.GetBytes("s")[0], "0011");
var frequency = FiboFrequency.CalculateFrequencyForByteFile(byteFile);
FiboRank_sCode fiboRank = new FiboRank_sCode();
ByteFileCharacterFrequency characterFrequency = new ByteFileCharacterFrequency();
characterFrequency.characterFrequency = frequency;
var actualResult = fiboRank.CreateDecodingTable(characterFrequency);
foreach (var k in actualResult)
{
Console.WriteLine(k.Key + " " + k.Value);
}
CollectionAssert.AreEquivalent(expectedResult, actualResult);
}
}
}
14. Код класу FiboRanksUpgradedCodeTest
namespace CompressorTest
{
[TestClass]
public class FiboRanksUpgradedCodeTest : FiboRanksUpgraded
{
[TestMethod]
public void GenerateFiboRanksTest()
{
FiboRanksUpgraded fiboRank = new FiboRanksUpgraded();
int n = 3;
List<long> expectedResult = new List<long>();
expectedResult.Add(10);
expectedResult.Add(100);
19
482.ЧДТУ.32276-01 12 01
expectedResult.Add(101);
List<long> actualResult = fiboRank.GenerateFiboRanks(3);
CollectionAssert.AreEquivalent(expectedResult, actualResult);
}
[TestMethod]
public void GenerateFiboRanksForLargeNumberOfElemTest()
{
FiboRanksUpgraded fiboRank = new FiboRanksUpgraded();
int n = 256;
List<long> actualResult = fiboRank.GenerateFiboRanks(n);
}
[TestMethod]
public void AddBinaryDigitsTest()
{
FiboRanksUpgraded fiboRank = new FiboRanksUpgraded();
int digit1 = 10;
int digit2 = 10;
int expectedResult = 100;
long actualResult = fiboRank.AddBinaryDigits(digit1, digit2);
Assert.AreEqual(expectedResult, actualResult);
}
[TestMethod]
public void CheckBinaryDigitsOnFiboCorrectnessTest()
{
FiboRanksUpgraded fiboRank = new FiboRanksUpgraded();
int digit1 = 1010;
int digit2 = 10110;
int digit3 = 11001;
int digit4 = 01001;
Assert.IsTrue(fiboRank.CheckBinaryDigitsOnFiboCorrectness(digit1));
Assert.IsTrue(fiboRank.CheckBinaryDigitsOnFiboCorrectness(digit4));
Assert.IsFalse(fiboRank.CheckBinaryDigitsOnFiboCorrectness(digit2));
Assert.IsFalse(fiboRank.CheckBinaryDigitsOnFiboCorrectness(digit3));
}
20
482.ЧДТУ.32276-01 12 01
[TestMethod]
public void GenerateFiboCodeTest()
{
FiboRanksUpgraded fiboRank = new FiboRanksUpgraded();
int n = 3;
List<string> expectedResult = new List<string>();
expectedResult.Add("011");
expectedResult.Add("0011");
expectedResult.Add("1011");
List<string> actualResult = fiboRank.GenerateFiboCode(3);
CollectionAssert.AreEquivalent(expectedResult, actualResult);
}
[TestMethod]
public void CreateDecodingTableForByteFileTest()
{
ByteFile byteFile = new ByteFile();
string text = "test";
byteFile.data = Encoding.ASCII.GetBytes(text);
Dictionary<Byte, string> expectedResult = new Dictionary<byte, string>();
expectedResult.Add(Encoding.ASCII.GetBytes("t")[0], "011");
expectedResult.Add(Encoding.ASCII.GetBytes("e")[0], "0011");
expectedResult.Add(Encoding.ASCII.GetBytes("s")[0], "1011");
var frequency = FiboFrequency.CalculateFrequencyForByteFile(byteFile);
FiboRanksUpgraded fiboRank = new FiboRanksUpgraded();
ByteFileCharacterFrequency characterFrequency = new ByteFileCharacterFrequency();
characterFrequency.characterFrequency = frequency;
var actualResult = fiboRank.CreateDecodingTable(characterFrequency);
foreach (var k in actualResult)
{
Console.WriteLine(k.Key + " " + k.Value);
}
CollectionAssert.AreEquivalent(expectedResult, actualResult);
}
21
482.ЧДТУ.32276-01 12 01
[TestMethod]
public void CreateDecodingTableForByteFileLOngTextTest()
{
ByteFile byteFile = new ByteFile();
string text = "test";
byteFile.data = Encoding.ASCII.GetBytes(text);
Dictionary<Byte, string> expectedResult = new Dictionary<byte, string>();
expectedResult.Add(Encoding.ASCII.GetBytes("t")[0], "011");
expectedResult.Add(Encoding.ASCII.GetBytes("e")[0], "0011");
expectedResult.Add(Encoding.ASCII.GetBytes("s")[0], "1011");
var frequency = FiboFrequency.CalculateFrequencyForByteFile(byteFile);
FiboRanksUpgraded fiboRank = new FiboRanksUpgraded();
ByteFileCharacterFrequency characterFrequency = new ByteFileCharacterFrequency();
characterFrequency.characterFrequency = frequency;
var actualResult = fiboRank.CreateDecodingTable(characterFrequency);
foreach (var k in actualResult)
{
Console.WriteLine(k.Key + " " + k.Value);
}
CollectionAssert.AreEquivalent(expectedResult, actualResult);
}
}
}
15. Код класу CompressorPerformanceTest
namespace CompressorTest
{
[TestClass]
public class CompressorPerformanceTest
{
[TestMethod]
public void UpgradedFibboPerformanceTest()
{
var watch = Stopwatch.StartNew();
ByteFileHeader fileHeader = new ByteFileHeader();
ByteFileCharacterFrequency characterFrequency = new ByteFileCharacterFrequency();
byte[] file = File.ReadAllBytes("../../test.txt");
22
482.ЧДТУ.32276-01 12 01
ByteFile byteFile = new ByteFile();
byteFile.data = file;
characterFrequency.characterFrequency =
FiboFrequency.CalculateFrequencyForByteFile(byteFile);
FiboRanksUpgraded fiboRank = new FiboRanksUpgraded();
fileHeader.fileHeader = fiboRank.CreateDecodingTable(characterFrequency);
//Console.WriteLine("Character count: ");
//foreach (var k in characterFrequency.characterFrequency)
//{
// Console.WriteLine("Key: " + k.Key + ", Value: " + k.Value);
//}
Console.WriteLine("File header: ");
foreach (var k in fileHeader.fileHeader)
{
Console.WriteLine("Key: " + k.Key + ", Value: " + k.Value);
}
Console.WriteLine("Nuber of dif bytes: " + fileHeader.fileHeader.Count);
Console.WriteLine("Bytes in file: " + file.Length);
CompressedByteFile result = new CompressedByteFile();
ByteFileCompressor byteFileCompressor = new ByteFileCompressor();
result = byteFileCompressor.CompressByteFile(byteFile, fileHeader, "../../");
watch.Stop();
Console.WriteLine("Elapsed time: " + watch.ElapsedMilliseconds.ToString() + " ms");
}
[TestMethod]
public void StandartFibboPerformanceTest()
{
var watch = Stopwatch.StartNew();
ByteFileHeader fileHeader = new ByteFileHeader();
23
482.ЧДТУ.32276-01 12 01
ByteFileCharacterFrequency characterFrequency = new ByteFileCharacterFrequency();
byte[] file = File.ReadAllBytes("../../test.txt");
ByteFile byteFile = new ByteFile();
byteFile.data = file;
characterFrequency.characterFrequency =
FiboFrequency.CalculateFrequencyForByteFile(byteFile);
Console.WriteLine(characterFrequency.characterFrequency.Count);
FiboRank_sCode fiboRank = new FiboRank_sCode();
fileHeader.fileHeader = fiboRank.CreateDecodingTable(characterFrequency);
Console.WriteLine("File header: ");
foreach (var k in fileHeader.fileHeader)
{
Console.WriteLine("Key: " + k.Key + ", Value: " + k.Value);
}
Console.WriteLine("Nuber of dif bytes: "+fileHeader.fileHeader.Count);
Console.WriteLine("Bytes in file: " + file.Length);
CompressedByteFile result = new CompressedByteFile();
ByteFileCompressor byteFileCompressor = new ByteFileCompressor();
result = byteFileCompressor.CompressByteFile(byteFile, fileHeader, "../../");
watch.Stop();
Console.WriteLine("Elapsed time: " + watch.ElapsedMilliseconds.ToString() + " ms");
}
}
}
ДОДАТОК В
Дослідження та удосконалення методу стиснення
даних текстових файлів
Інструкція системного програміста
482.ЧДТУ.32276-01 32 01
Листів 5
Розробник: Ілля САЛОГУБ
Черкаси 2023
2
482.ЧДТУ.32276-01 32 01
Підключення бібліотеки
Для підключення бібліотеки до проекту в Visual Studio 2022 необхідно
відкрити контекстне меню проекту (рисунок В.1).
Рисунок В.1 – Відображення контекстного меню проекту
Після цього, необхідно перейти в розділ «Додати» (Add) та обрати
пункт «Посилання» (Reference), як приведено на рисунку В.2.
Рисунок В.2 – Відображення меню «Додати»
3
482.ЧДТУ.32276-01 32 01
Після цього має відкритись менеджер посилань (Reference manager).
Необхідно перейти у розділ «Огляд» (Browse) в меню розділів та натиснути
кнопку «Огляд» (Browse) (рисунок В.3).
Рисунок В.3 – Відображення менеджера посилань
У провіднику необхідно вказати шлях до файлу бібліотеки F
iboCompressor.h. Далі, для подальшої роботи потрібно додавати #include
«FiboCompressor.h» в класах, де будуть використані методи бібліотеки, що
додається.
Використання методів бібліотеки
Для використання методів бібліотеки необхідно після підключення
бібліотеки створити об’єкт типу ByteFileCompressorService. За допомогою
цього сервісу можна виконати, як повний алгоритм компресії файлу, так і
виконувати весь алгоритм поетапно.
4
482.ЧДТУ.32276-01 32 01
Короткий огляд методів
Метод CompressFile(byte[] byteFile, string path) приймає на вхід файл
перетворений у масив байтів та шлях до файлу. Використовуючи цей метод
весь алгоритм компресії буде пройдений автоматично з використанням
вдосконаленого методу компресії. На виході отримуємо об’єкт типу C
ompressedByteFile, який містить всю необхідну інформацію про стиснутий
файл.
Метод SetByteFile(byte[] file) приймає на вхід масив байтів і записує їх
у об’єкт типу ByteFile. На виході отримуємо саме об’єкт даного типу. Цей
метод необхідно виконувати першим в алгоритмі.
Метод CalculateCharacterFrequency(ByteFile file) приймає на вхід
об’єкт типу ByteFile. Даний метод вираховує частоту повторення символів у
вхідному файлі. На виході отримуємо об’єкт типу
ByteFileCharacterFrequency. Даний метод необхідно виконувати після методу
SetByteFile.
Наступним є метод GenerateByteFileHeader (ByteFileCharacter
Frequency characterFrequency), який приймає на вхід об’єкт типу
ByteFileCharacterFrequency і генерує таблицю кодування. Саме в цьому
методі можна змінити метод компресії. Для цього в рядку FiboRanksUpgraded
fiboRank = new FiboRanksUpgraded() необхідно змінити клас на
FiboRank_sCode для використання стандартного методу. На виході цей метод
повертає об’єкт типу ByteFileHeader. Даний метод повинен виконуватися
після методу CalculateCharacterFrequency.
Останнім методом є CompressByteFile(ByteFile file, ByteFileHeader
fileHeader, string path). На вхід подається об’єкт типу ByteFile, ByteFileHeader
та шлях до файлу. Цей метод виконує компресію файлу і повертає об’єкт
типу CompressedByteFile. Цей метод має виконуватися після методу G
enerateByteFileHeader.
5
482.ЧДТУ.32276-01 32 01
При вдосконаленні чи доданні нових методів порядок використання
методів може змінюватися.
Використання тестів бібліотеки
Для перевірки роботи поточних методів, або перевірки методів після їх
вдосконалення реалізовано ряд тестових класів.
Основні тестові класи та їх використання.
Клас FiboFrequencyTest використовується для перевірки правильності
визначення кількості унікальних символів та коректності сортування
результуючої таблиці. При зміні алгоритму роботи класу FiboFrequency
необхідно перевірити роботу нового алгоритму за допомогою цього
тестового класу.
Клас FiboRank_sCodeTest містить ряд тестів для перевірки роботи всіх
методів класу FiboRank_sCode, який відповідає за стандартний алгоритм
компресії. При зміні даного класу потрібно виконати перевірку нового
алгоритму за допомогою тестів даного класу. При доданні нових методів до
класу FiboRank_sCode необхідно реалізувати тести, які б перевіряли роботу
цього методу.
Клас FiboRanksUpgradedCodeTest містить тести для перевірки роботи
вдосконаленого методу, а саме класу FiboRanksUpgraded. Аналогічно до
попереднього класу при внесенні змін до поточних методів необхідно
перевірити новий алгоритм за допомогою існуючих тестів цього класу, або
реалізувати нові тести при доданні нових методів до класу
FiboRanksUpgraded.
Клас CompressorPerformanceTest перевіряє швидкість та ефективність
роботи стандартного та вдосконаленого методу. За допомогою цього класу
можна переглянути згенеровані таблиці, кількість витраченого часу на
компресію та розмір файлу до та після компресії.
Клас ByteFileCompressorServiceTest перевіряє сукупну роботу всього
алгоритму емітуючи роботу класу ByteFileCompressorService. За допомогою
6
482.ЧДТУ.32276-01 32 01
цього класу можна перевіряти коректність роботи класу
ByteFileCompressorService.
ChSTU repository

ChSTU repository preserves and enables easy and open access to all types of digital content including text, images, moving images, mpegs and data sets
