Міністерство освіти і науки України
Національний університет „Львівська політехніка”
Кафедра ЕОМ
Пояснювальна записка
до курсової роботи
з курсу:
„Системне програмне забезпечення”
на тему:
„ Розробка утиліти стискання файлів за алгоритмом RLE ”
АНОТАЦІЯ
В курсовій роботі здійснена розробка утиліти стискання файлів з використанням алгоритму RLE. За допомогою цієї програми можна стискати інформацію за цим алгоритмом. Після стиснення утворюється файл з розширенням .rle, його можна розархівувати скориставшись цією ж програмою.
Курсова робота виконана у середовищі Microsoft Visual Studio 2010, лістинг програми наведений у додатку А. Також у курсовій роботі наведено граф-схеми роботи програми, алгоритм архівування і розархівування, детальний програми з поясненням усіх використовуваних функцій і змінних.
До проекту додано результати тестування програми та опис інтерфейсу та інструкції користувачеві.
Зміст
Вступ……………………………………………………………………4
1.Вибір технології програмування……………………………………5
2.Огляд алгоритму архівації……………………………………………14
3. Розробка утиліти стискання методом RLE…………………………16
4.Опис інтерфейсу та інструкції користувачеві……………………....20
5. Тестування програми……….. ……………………………………….21
Висновок…………………………………………………………………23
Використана література…………………………………………………24
Додаток ………………………………………………………………….25
Вступ
Разом із виникненням комп’ютерів постала проблема збереження інформації на ньому. Саме тому і виникло багато алгоритмів стиснення інформації і програм які їх виконують.
Архіватори - це програми що дозволяють створювати і обробляти архівні копії файлів. При цьому архівні копії мають менший розмір ніж оригінали. За допомогою спеціальних алгоритмів стиску з файлів віддаляється вся надлишкова інформація, а при застосуванні зворотніх алгоритмів розпакування - архівна копія відновлюєть в первісному виді.
Безумовним лідером у світі за останні п’ять років став архіватор RAR. В даний час RAR активно витісняє ZIP як основну утиліту стиску FTP архівів у мережі INTERNET. RAR є єдиною всесвітньо-відомою програмою створеною російським програмістом( за винятком TETRIS). Всі архіватори відрізняються використовуваними алгоритмами стиску, форматами архівних файлів, швидкістю роботи тощо.
Одним із поширених алгоритмів стиску інформації є алгоритм RLE(Run Length Encoding), він використовується PDF i TIFF форматах файлів. Цей алгоритм стиснення інформації є темою моєї курсової роботи.
1.Вибір технології програмування
Серед нових технологій, оголошених microsoft в червні і намічених на уявлення на Конференції Професійних Розробників microsoft (pdc) є мова програмування під назвою c#. c# (оголошений як "Гострий") буде включений в наступний випуск середовища програмування microsoft visual studio.net. Модулі, написані на c# будуть сумісні з модулями, написаними на visual c++ і visual basic, тим самим вперше підтримуючи розвиток перехресної мови на платформі microsoft .net. Як visual basic задовольняв потреби розробників windows в 90-х, так і c# повинен задовольняти потреби продуктивності .net додатків і розробників послуг. Сучасні мови програмування створені з досвіду і знання їх проектувальників.Чим більша кількість людей залучена в проект, тим ширше ядро мов. microsoft говорить, що визначення мови c# було отримане із с та c++ і багато елементів мови відображають це. c# ширше, ніж java, оскільки його проектувальники використовували спадкоємство від c++ (типу structs). Крім того в c# додані нові особливості (типу початкового тексту versioning). Щоб точніше розібратися у всьому цьому, можна розібрати особливості c#, виразно співпадаючі з java, які походять від стандартних with і c++. Як ви побачите надалі, особливості, які c# запозичив у цих мов допоможуть вам розібратися в його структурі.
Особливості c#, запозичені у java:
Класи:
Класів в c#, як і в java дуже багато. Зверніть увагу на слідуючий приклад, що показує використання класів:
using system;
class hello {
static void main() {
console.writeline("hello, world");
}
}
В даному прикладі, ім'я system звертається до namespace, яка містить набір базисних класів с. namespace містить клас console, який використовується в даному прикладі для виведення рядка.
Класи можуть бути абстрактними і кінцевими; клас, який оголошений як abstract може використовуватися тільки як базовий клас. Ключове слово lock (аналог в java - final) означає, що клас буде не абстрактним, але він також не може використовуватися як основа іншого класу.
Інтерфейси:
Як і в java, інтерфейс - абстрактне визначення колекції методів. Коли клас або структура виконує інтерфейс, він повинен виконати всі методи, визначені в цьому інтерфейсі. Одиночний клас може виконувати ряд інтерфейсів.
Булеві операції:
Прямого перетворення між булевим типом будь-яким іншим типом даних немає. Ключовими словами є: булева істина і брехня.
Помилки:
Як і в java, управляти обробкою помилок можна захоплюючи об'єкти виключення.
Управління пам'яттю:
c# Особливості, запозичені у с і c++
Компіляція:
Програми виконують компіляцію безпосередньо в стандартну двійкову здійсниму форму. Якщо попередня програма hello world була збережена в текстовому файлі hello.cs, вона буде скомпільована в здійснимий файл hello.exe.
Структури:
Структури c# - подібні до структур в c++ і повинні містити визначення даних і методи. Проте, на відміну від c++, структури в c# відмінні від класів і не підтримують спадкоємство. Проте, подібно java, структури можуть виконувати інтерфейси.
Препроцесор:
Існують директиви препроцесора для умовної компіляції, попереджень, помилок і контролю. Директиви попередньої обробки:
#define
#undef
#if
#elif
#else
#endif
#warning
#error
#line []
Перевантаження операторів:
Деякі оператори можуть бути переобтяжені, а деякі ні. До того ж жоден з операторів призначення не може бути переобтяжений.
Перенавантажувані унарні оператори
+ -! ~ ++ - true false
Перенавантажувані бінарні оператори
+ - * / % і | ^ <<> > ==! = > < > = < =
Особливості, унікальні для c#:
Визначення в namespace
Коли ви створюєте програму, ви створюєте один або більше (за класамии) в namespace. У ньому ж (поза класом) можливе оголошення інтерфейсів, enums і structs. Використовуючи ключові слова ви можете адресувати вміст іншого namespace.
Фундаментальні типи даних:
В c# існує ширша різноманітність типів даних ніж в с та с++ або java. Типи - bool, byte, ubyte, short, ushort, int, uint, long, ulong, float, double, and decimal. Подібно java, всі типи мають встановлений розмір. Подібно с і с ++ всі типи можуть бути знаковими і без знаковими. Подібно java, char містить 16-ти бітовий unicode символ. У c# новим типом даних є тип decimal, який може містити до 28 десяткових цифр.
Два фундаментальні класи:
Клас object - базовий клас всіх класів. Клас string - також базовий клас. Будучи частиною мови він використовується компілятором, коли ви створюєте рядок у вашій програмі, беручи його в лапки.
Асемблювання:
Асемблювання - колекція компільованих класів і здібність до виконання інших елементів мови, які об'єднані в окремому файлі. Якщо це програма то файл має розширення exe. Якщо це бібліотека - dll.
Ознаки:
Кожен член класу має ознаки: public, protected, internal, protected internal, or private.
public: доступний для всієї коди.
protected: доступний тільки від отриманих класів.
internal: доступний тільки при асемблюванні;
protected internal: доступний тільки від отриманих класів в межах асемблювання.
private: доступний тільки з класу.
Проходження аргументу:
Методи можуть оголошуватися для ухвалення деякого числа аргументів. За умовчанням відбувається передача значень фундаментальним типам даних. Ключове слово ref може використовуватися для передачі значення по певному посиланню, яке дозволяє повертати значення. Ключове слово out також викликає перехід по посиланню без передачі значення.
Віртуальні методи:
Перш, ніж метод в базовому класі буде переписаний, він повинен бути оголошений як virtual. Метод в підкласі, який буде переписаний, повинен бути оголошений за допомогою ключового слова override. Це запобіжить випадковому перезапису методу. Дана особливість покращує легкість для читання і невимушеність обслуговування c# модулів.
Властивості:
com об'єкт, має властивості і тому кожен c# клас може використовуватися як com об'єкт. c# дозволяє визначати властивості всередині будь-якого класу. Всередині c# класу, кожній властивості дається ім'я і тип даних. Ключові слова set accessor і get accessor використовується для оголошення виконуваної коди при читанні або оновленні властивості. Як приклад розгляньте клас, який має властивість caption:
public class button: control {
private string caption;
public string caption {
get {
return caption;
}
set {
caption = value;
repaint();
}
}
}
Ім'я властивості може бути адресоване зовні в затвердженні призначення:
button b = new button();
b.caption = "abc";
string s = b.caption;
b.caption += "def"
Привласнення b.caption викликає метод set. Привласнення значення з b.caption викликає метод get. Операція + = викликає обидва цих методи. Властивість адресує вміст окремого поля в класі.
Визначення версій:
c# дозволяє розробникам підтримувати безліч версій класів в двійковій формі, поміщаючи їх в різних namespace. Це дозволяє як старим, так і новим версіям програмного забезпечення запускатися одночасно. Разом з цим в c# буде здатність підтримувати і управляти безліччю версій початкової коди.
Перевірена і неперевірена оцінка:
перевірений вираз - вираз, який видає виключення при виході за його межі. Неперевірений вираз - вираз, який не видає виключення. Ключові слова checked і unchecked використовуються для явного визначення того, яким чином була виконана оцінка:
int j = checked(а * b);
int до = unchecked(а * b);
Явні і неявні перетворення:
Подібно java, c# враховує неявне перетворення фундаментальних типів даних, поки немає вірогідності втрати даних (перетворення типу byte в int), але якщо є вірогідність втрати даних (перетворення int в byte) виконується явне перетворення. c# розширює цю здатність для інших елементів програми, дозволяючи програмістові визначити як явні, так і неявні перетворення. Наприклад, наступна структура digit може бути неявно призначена типу byte, але повинна бути явно визначена для привласнення іншої digit:
public struct digit {
byte value;
public digit(byte value) {
if(value < 0 || value > 9)
throw new argumentexception();
this.value = value;
}
public static implicit operator byte(digit d){
return d.value;
}
public static explicit operator digit(byte b){
return new digit(b);
}
}
Зовні виконувані методи:
Методи в класі можуть виконуватися зовні. У наступному прикладі, статичний метод removedirectory виконується в бібліотеці під ім'ям kernel32.dll:
class path {
[dllimport("kernel32", setlasterror=true)]
static extern bool removedirectory(string name);
}
Ітерація через члени колекції:
Затвердження foreach може використовуватися для одноразового виконання блоку коди для кожного члена списку або масиву. Наступний приклад одноразово виконує цикл в методі writelist() для кожного члена arraylist:
using system;
using system.collections;
class test {
static void writelist(arraylist list){
foreach(object про in list)
console.writeline(o);
}
static void main() {
arraylist list = new arraylist();
for(int i = 0; i < 10; i++)
list.add(i);
writelist(list);
}
}
Будь-який досвідчений windows програміст, звичайно, знайде щось цікаве для себе із списку особливостей мови c#. Мені особливо подобаються властивості і здібності індексації мови. Існують деякі нові особливості в порівнянні з java. Типи даних фіксованого розміру (32-х бітовий int і 64-х бітовий long) є не тільки високо мобільними, але і спрощують програмування, оскільки ви завжди знаєте точно, з чим ви маєте справу. Дуже зручною є і автоматична "збірка" сміття. В той час, як всі ці особливості мови здаються дуже привабливими. Ще досить рано порівнювати c# ++ або visual basic. Проте, мені подобається c# і якщо надалі послідує його хороша реалізація, то я думаю, що .net розробники прагнутимуть до цього нового інструменту.
2.Огляд алгоритму архівації
Групове кодування Run Lengh Encodind(RLE) –один із самих простих алгоритмів архівації. Стискання RLE відбувається за рахунок заміни однакових байт на пари «лічильник, значення».
Незважаючи на давнє народження RLE як алгоритму стиску зображення і на його сьогоднішню неефективність у світі складності (наявність дрібних деталей) сучасних зображень, всетаки сьогодні існує клас програм, де використання RLE більш виправдано ніж використання інших алгоритмів. Позитивним у цьому алгоритмі є його простота, а значить це зменшує фінансові(між іншим і апаратні) витрати на використання блоків деякої контролюючої системи. Алгоритм застосовується у форматах РСХ, TIFF, ВМР, PDF. Цікава особливість групового кодування РСХ полягає у тому, що степінь архівації для деяких зображень може бути суттєво підвищений всього за рахунок зміни порядку розміщення кольорів в палітрі зображень.
Ось наведено приклад використання даного алгоритму:
Розглянемо зображення, яке має просто чорний текст на сполошному білому фоні. Тут буде багато серій білих пікселів в пустих місцях і багато коротких серій чорних пікселів у тексті. В якості прикладу приведено деякий будь-який рядок зображення в чорно-білому варіанті. Тут B представляє чорний піксель, a W- білий.
W
W
W
W
W
W
B
B
B
B
W
W
W
W
B
B
B
W
W
W
W
W
B
B
B
Якщо ми застосуємо кодування групове довгих серій то ми отримаємо
6W
4B
4W
3B
5W
3B
Попередній запис означає «шість W », «чотири B», «чотири W», «три B», «п’ять W», «три B». Отже ми мали 25 символів , а отримали всього 12 символів.
Звісно RLE кодування має ряд недоліків. Оскільки наприклад якби ми мали таку послідовність
W
B
W
B
W
B
Після стикання ми б отримали
1W
1B
1W
1B
1W
1B
Отже у результаті після стиснення із 6 символів ми отримали 12, а це вже стисненням інформації назвати неможливо швидше навпаки. Тому перед стискання інформації алгоритмом RLE потрібно знати що за інформація містить у файлі, добре його застосовувати на малюнках що не мають багатьох кольорів. Ще одним недоліком цього алгоритму є те що максимальне число однакових підряд символів дорівнює залежить від типу даних на згідно якого здійснюється обчислення.
Методом кодування довгих серій можуть бути і стисненні будь-які файли із двійковими даними, оскільки специфікація на формати файлів часто включає в себе повтори однакових байт в області вирівнювання даних. Тим не менше сучасні системи(наприклад DEFLATE) частіше використовують алгоритм на основі LZ77 що є узагальненням до групового методу кодування довгих серій і оперують послідовностями серій цього виду.
Звукові дані, які мають довгі послідовності серії байт(таких як звукові дані низької якості) можуть бути стиснені за допомогою RLE після того як до них буде застосовано дельта- кодування.
3.Розробка утиліти стискання методом RLE
Для ефективної роботи створюваної програми важливу роль відіграє попереднє складення алгоритму роботи програми, алгоритму написання програми і вибір технології програмування. Дана програма написана мовою C#.
Граф схема алгоритму роботи програми наведена нижче
Рис.1 Граф-схема алгоритму програми
На рисунку наведена граф-схема алгоритму роботи програми 1- початок роботи програми. За стиснення інформації відповідає кнопка архівувати функція private void button1_Click(object sender, EventArgs e)Сам алгоритм стиснення реалізований функцією private void Archive(string InputFileName, string OutputFileName)За розархівування (на рисунку 5)відповідає кнопка архівувати функція private void button2_Click(object sender, EventArgs e)Сам алгоритм розархівування реалізований функцією private void unArchive(string InputFileName, string OutputFileName)
Далі наведено детальну схему роботи програми, а саме граф-схема роботи стиснення файлів і роботи розтиснення файлів.
Рис.2 Граф-схема роботи стиснення файлів
На рисунку 2 наведено схему роботи стиснення файлів.1-початок роботи функції private void Archive(string InputFileName, string OutputFileName)2- створення RLE файлу, воно відбувається за допомогою функції saveFileDialog
3-визначення кількості байт вхідного файлу за допомогою функції FileStream Length. Далі пункти 3,4-це реалізація алгоритму, якщо зустрічаються однакові байти то виконується функція private int PackBlock1(FileStream file_r, string FileName)
лічильник збільшується на1, доки байт буде повторюватись,коли байт не повторюється то реалізовується функція private int PackBlock2(FileStream file_r, string FileName) 6-запис стисненої інформації у файл 7- завершення роботи функції.
Рис.2 Граф-схема роботи розархівування файлів
На рисунку 2 наведено схему роботи стиснення файлів.1-початок роботи функції private void unArchive(string InputFileName, string OutputFileName)
2- створення RLE файлу, воно відбувається за допомогою функції saveFileDialog
3-визначення кількості байт вхідного файлу за допомогою функції FileStream Length Далі пункти 3,4-це реалізація алгоритму, якщо є символи що повторюються вони записують у файл доки лічильник не дорівнюватиме 0.6-запис розархівованої інформації у файл це здійснюється за допомогою функції Binary Writer.Write6- завершення роботи функції.
4.Опис інтерфейсу та інструкції користувачеві
Створена утиліта написана мовою C# .Розроблений простий інтерфейс, архіватор складається з двох кнопок: архівувати і розархівувати
/
При натисненні клавіші архівувати з’являється вікно де потрібно обрати який файл потрібно архівувати
/
Після того як файл обраний, потрібно натиснути клавішу Открыть після чого файл буде архівовано, архівований файл буде мати розширення .rle. Для того щоб розархівувати файл потрібно натиснути клавішу Розахівувати
Після чого знову з’явиться вікно де потрібно обрати файл для розархівування
5.Тестування програми
Щоб перевірити правильність роботи алгоритму проведено такі тестування:
Спочатку перевіримо ввівши у текстовий файл такі дані:
/
Після стиснення став:Перед стисненням його розмір був:
/
Після розархівування інформація залишилась незмінною.
/
Так само перевіряємо простий рисунок намальований у Paint
/
Кількість байт до і після стиснення
/
Висновок
В процесі виконання курсової роботи було виконано наступне:
Розроблено утиліту стискання файлів за алгоритмом RLE мовою С#.
Наведено граф-схема загальної роботи програми
Наведено граф-схема алгоритму стискання і розархівовування інформації RLE
Проведено тестування утиліти на тестових файлах: текстовому і малюнку.
В результаті виконання даної курсової роботи засвоєно стискання інформації методом груповго кодування (RLE).
Використана література
1. Кричевский Р.Е. Сжатие и поиск информации. – М., Радио и связь, 1989
2. Рябко Б.Я. Сжатие информации с помощью стопки книг. // Проблемы передачи информации.- 1980, т.16, №4. С.16-21
3. Кохманюк Д. Сжатие данных: как это делается // Компьютеры+программы,1995.
4. Хоффман Л. Современные методы защиты информации: Пер. с англ. -М.: Сов. радио, 1980, 264с.
5. Зкслер А. Б. Архиваторы (Проґраммы для хранения й обработки информации в сжатом виде). - М: Малое предприятие "Алекс", 1992. - 150 с. 12. Компьютер Пресе. -М: 1994; N 1-5
Додаток (Лістинг програми)
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using System.IO;
namespace RLE1
{
public partial class Form1 : Form
{
const byte AR_SIMPLE = 0;
const byte AR_REPEATED = 1;
public Form1()
{
InitializeComponent();
}
private void Archive(string InputFileName, string OutputFileName)
{
FileStream file_r = new FileStream(@InputFileName, FileMode.OpenOrCreate, FileAccess.Read);
pgBar.Maximum = (int)file_r.Length;
int curByte = file_r.ReadByte();
int nextByte = file_r.ReadByte();
curByte++;
//починає з початку
file_r.Position = 0;
do
{
if (nextByte == curByte)
{
//позначаж що повторюється байт
curByte = PackBlock1(file_r, OutputFileName);
}
else
{
//позначає що не повторюється
curByte = PackBlock2(file_r, OutputFileName);
}
nextByte = file_r.ReadByte();
file_r.Position--;
pgBar.Value = (int)file_r.Position;
Application.DoEvents();
}
while (nextByte != -1);
file_r.Close();
}
private int PackBlock1(FileStream file_r, string FileName)
{
byte count = 1;
int curByte;
int nextByte;
byte[] buf;
FileStream file_w = new FileStream(@FileName, FileMode.Append, FileAccess.Write);
//починає і рахує скільки повторюється
do
{
count++;
curByte = file_r.ReadByte();
nextByte = file_r.ReadByte();
if (nextByte != -1)
file_r.Position--;
if (count == 255)
{
buf = new byte[3] { AR_REPEATED, count, (byte)curByte };
file_w.Write(buf, 0, 3);
count++;
}
}
while (curByte == nextByte);
//позначає блоки що повторюються
buf = new byte[3] { AR_REPEATED, count, (byte)curByte };
file_w.Write(buf, 0, 3);
file_w.Close();
return curByte;
}
private int PackBlock2(FileStream file_r, string FileName)
{
MemoryStream tmp = new MemoryStream();
int curByte;
int nextByte;
byte count = 1;
do
{
count++;
curByte = file_r.ReadByte();
nextByte = file_r.ReadByte();
if (nextByte != -1)
file_r.Position--;
if (curByte != nextByte)
tmp.WriteByte((byte)curByte);
}
while ((curByte != nextByte) && (tmp.Length < 255) && (nextByte != -1));
FileStream file_w = new FileStream(FileName, FileMode.Append, FileAccess.Write);
BinaryWriter sw = new BinaryWriter(file_w);
sw.Write(AR_SIMPLE);
//записується довжина
sw.Write((byte)tmp.Length);
sw.Write(tmp.ToArray(), 0, (int)tmp.Length);
sw.Close();
file_w.Close();
return curByte;
}
private void unArchive(string InputFileName, string OutputFileName)
{
// потік що читає з архіву
FileStream file_r = new FileStream(InputFileName, FileMode.Open, FileAccess.Read);
BinaryReader sr = new BinaryReader(file_r);
// потік що записує у архів
FileStream file_w = new FileStream(OutputFileName, FileMode.Append, FileAccess.Write);
BinaryWriter sw = new BinaryWriter(file_w);
pgBar.Maximum = (int)file_r.Length;
byte curByte;
byte count;
do
{
curByte = sr.ReadByte();
switch (curByte)
{
case AR_SIMPLE:
count = sr.ReadByte();
for (int i = 0; i < count; i++)
{
sw.Write(sr.ReadByte());
}
break;
case AR_REPEATED:
count = sr.ReadByte();
curByte = sr.ReadByte();
for (int i = 0; i < count; i++)
{
sw.Write(curByte);
}
break;
}
pgBar.Value = (int)file_r.Position;
Application.DoEvents();
}
while (sr.PeekChar() != -1);
sr.Close();
file_r.Close();
sw.Close();
file_w.Close();
}
private void button1_Click(object sender, EventArgs e)
{
openFileDialog.Title = "Виберіть файл ...";
openFileDialog.Filter = "Any|*.*";
if (openFileDialog.ShowDialog() == DialogResult.OK)
{
if (File.Exists(openFileDialog.FileName + ".rle"))
{
File.Delete(openFileDialog.FileName + ".rle");
}
pgBar.Value = 0;
pgBar.Visible = true;
lbStatus.Text = "...";
Archive(openFileDialog.FileName, openFileDialog.FileName + ".rle");
lbStatus.Text = "Архівовано";
pgBar.Visible = false;
}
}
private void pgBar_Click(object sender, EventArgs e)
{
}
private void button2_Click(object sender, EventArgs e)
{
openFileDialog.Title = "Виберіть файл для розархівування...";
openFileDialog.Filter = "rle|*.rle";
if (openFileDialog.ShowDialog() == DialogResult.OK)
{
saveFileDialog.InitialDirectory = Path.GetDirectoryName(openFileDialog.FileName);
saveFileDialog.FileName = Path.GetFileNameWithoutExtension(openFileDialog.FileName);
if (saveFileDialog.ShowDialog() == DialogResult.OK)
{
pgBar.Value = 0;
pgBar.Visible = true;
lbStatus.Text = "...";
unArchive(openFileDialog.FileName, saveFileDialog.FileName);
lbStatus.Text = "Розархівовано";
pgBar.Visible = false;
}
}
}
private void lbStatus_Click_Click(object sender, EventArgs e)
{
}
private void openFileDialog_FileOk(object sender, CancelEventArgs e)
{
}
private void openFileDialog_FileOk_1(object sender, CancelEventArgs e)
{
}
private void saveFileDialog1_FileOk(object sender, CancelEventArgs e)
{
}
private void Form1_Load(object sender, EventArgs e)
{
}
}
}