Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Дослідження алгоритмів архівації
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2016
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Захист програмного забезпечення
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
Кафедра ЗІ
/
Звіт до лабораторної роботи № 1
Дослідження алгоритмів архівації
з навчальної дисципліни: “ Захист програмного забезпечення ”
Мета роботи:
Розглянути основні методи стиску інформації. Навчитися на практиці реалізовувати дані алгоритми.
Теоречні відомості:
Архівація даних
Архіватор — програмне забезпечення, що використовується для об'єднання, в окремих випадках також стиснення інформації.
При збереженні, резервному копіюванні інформації тощо часто буває бажано стиснути файли так, щоб вони займали якомога менше місця. Це робиться за допомогою програм, які звуться архіваторами. Ці програми не тільки стискають інформацію в окремому файлі, але можуть і об'єднати в один архів групу файлів.
Існує багато архіваторів. Серед них найвідоміші: ARJ, DIET, ICE, LHA, LHARC, LZH, LZEXE, NARC, PAK, PKARC, PKLITE, PKXARC, PKPAK, PKZIP, PKUNZIP, RAR, ZOO. Останнім часом з'явилися програми, які, знаходячись у пам'яті комп'ютера резидентно, архівують та розархівовують «на льоту» всі файли, з якими ви працюєте, що дозволяє суттєвим чином заощаджувати простір на жорсткому диску. Такі можливості надають, наприклад, утиліта dblspace для операційної системи MS-DOS та програма DIET (T.Matsumoto, Японія).
Існує декілька методів стиснення інформації, що міститься у файлах. Мабуть, найпростішим із них є алгоритм Хоффмана, який полягає в заміні стандартних 8-бітових ASCII-кодів бітовими рядками змінної довжини в залежності від частоти використання символу так, щоб символи, що використовуються частіше, мали меншу довжину. До речі, легко зрозуміти, що у текстах найчастіше зустрічається символ «пробіл», ASCII-код якого має номер 32. Можна поширити цю ідею на пари, трійки і т. д. символів. При цьому можна одержати суттєвий виграш. Дійсно, візьміть, наприклад, дві пари символів «по» та «хщ». Ви можете назвати багато слів із першим сполученням, тоді як інше зустрічається дуже рідко. А при стандартному ASCII-кодуванні на кожне зі сполучень витрачається порівну бітів — по 16. Серед інших методів, які широко застосовуються в архіваторах для стиснення інформації у файлах можна відзначити алгоритм Лемпеля-Зіва.
Зауважимо нарешті, що комп'ютер не «розуміє» ніяких інших кодувань символів крім ASCII-кодування (чи споріднених кодувань). Тому перед використанням архівований файл повинен бути розархівованим.
Алгоритми стиснення (архівації) даних
Всі алгоритми стиснення оперують вхідним потоком даних, мінімальною одиницею яких є біт, а максимальною – декілька біт, байт або декілька байтів.
Метою процесу стиснення є отримання більш компактного вихідного потоку інформаційних одиниць з некомпактного вхідного потоку за допомогою перетворення.
Основними технічними характеристиками процесів стиснення і результатів їх роботи є :
• степінь стиснення (compress rating) або відношення (retion) об’ємів вхідного і вихідного потоків;
• швидкість стиснення – час, який витрачається на стиснення деякого об’єму інформації вхідного потоку, до отримання з нього еквівалентного вихідного потоку;
• якість стиснення – величина, яка вказує, на скільки сильно упакований вихідний потік, за допомогою застосування до нього повторного стиснення за цим або іншим алгоритмом.
Всі способи стиснення можна поділити на дві категорії: зворотнє і не зворотнє.
Під зворотнім стисненням розуміють таке перетворення вхідного потоку даних, при якому вихідний потік, в контексті певного формату даних, представляє достатньо схожий за зовнішніми характеристиками на вхідний потік об’єкт, але відрізняється від нього об’ємом. Рівень схожості вхідного і вихідного потоків визначається рівнем відповідності деяких властивостей об’єкта (тобто, стисненої і не стисненої інформації у відповідності до деякого визначеного формату даних).
Такі підходи і алгоритми використовуються для стиснення, наприклад, даних растрових графічних файлів з низькою повторюваністю байтів у потоці. При такому підході використовується властивість структури формату графічного файлу і можливість подати графічний рисунок приблизно схожу за якістю зображення (для сприйняття людським оком) декількома способами. Тому, крім рівня або величини стиснення, в таких алгоритмах виникає поняття якості, оскільки вихідне зображення в процесі стиснення змінюється, то під якістю можна розуміти рівень відповідності вхідного і результуючого зображення, що оцінюється суб’єктивно, враховуючи формат даних. Для графічних файлів така відповідність визначається візуально, хоча є і відповідні інтелектуальні алгоритми і програми.
Не зворотнє стиснення неможливо застосовувати тоді, коли потрібно мати точну відповідність структури вхідного і вихідного потоків. Даний підхід реалізовано в популярних форматах подання відео і фото інформації, відомих як JPEG і JFIF алгоритми і JPG і JIF формати файлів.
Зворотнє стиснення завжди призводить до зменшення вихідного потоку даних без зміни його інформативності, тобто – без втрати інформаційної структури.
Більше того, з вихідного потоку, за допомогою поновлювального або декомпресійного алгоритму, можна отримати вхідний, а процес поновлення називається декомпресією або розпакуванням і тільки після процесу розпакування дані можна використовувати для опрацювання у відповідності до їх внутрішнього формату.
Перейдемо тепер безпосередньо до алгоритмічних особливостей зворотних алгоритмів і розглянемо найважливіші теоретичні виклади до стиснення даних, які пов’язані з реалізацією систем , що кодуються та способами стиснення даних.
Стиснення способом кодування серій (RLE)
Найбільш відомий, простий підхід і алгоритм стиснення інформації оборотним шляхом - це кодування серій послідовностей (Run Length Encoding - RLE). Суть методів даного підходу полягає в заміні ланцюжків або серій байтів що повторюються або їх послідовностей на один лічильник, що кодує байт і числа їх повторень.
Приклад: 44 44 44 11 11 11 11 11 01 33 FF 22 22 - вихідна послідовність 03 44 04 11 00 03 01 03 FF 02 22 – послідовність після стиснення.
Перший байт вказує скільки раз потрібно повторити наступний байт. Якщо перший байт рівний 00, то потім пишеться лічильник, що показує скільки за ним йде неповторюваних даних. Даний метод, як правило, досить ефективний для стиснення растрових графічних зображень (BMP, PCX, TIF, GIF), тому що останні містять досить багато довгих серій повторюваних послідовностей байтів. Недоліком методу RLE є досить низька ступінь стиснення.
Результати виконання лабораторної роботи
Програма cтиснення способом кодування серій (RLE).
Лістинг файлу RLEArchivator.cs
using System;
using System.IO;
namespace RLEArchivator
{
public class RLEArchivator
{
private string _fileName;
public RLEArchivator(string path)
{
if (File.Exists(path))
{
_fileName = path;
}
else
{
throw new ArgumentException("File doesn't exist");
}
}
public string Archive()
{
using (var input = File.OpenRead(_fileName))
{
var outputName = _fileName + ".rle";
using (var output = File.OpenWrite(outputName))
{
byte currentByteSequence;
byte currentByteSequenceCount;
byte currentByte;
int inputByte;
inputByte = input.ReadByte();
if (inputByte == -1)
{
return outputName;
}
currentByteSequence = (byte)inputByte;
currentByteSequenceCount = 1;
while ((inputByte = input.ReadByte()) != -1)
{
currentByte = (byte)inputByte;
if (currentByte == currentByteSequence)
{
currentByteSequenceCount++;
}
else
{
output.WriteByte(currentByteSequenceCount);
output.WriteByte(currentByteSequence);
currentByteSequence = currentByte;
currentByteSequenceCount = 1;
}
}
return outputName;
}
}
}
public string Extract()
{
if (Path.GetExtension(_fileName) != ".rle")
{
throw new InvalidDataException("File with not .rle extension");
}
using (var input = File.OpenRead(_fileName))
{
var outputName = Path.GetDirectoryName(_fileName) + Path.GetFileNameWithoutExtension(_fileName);
if (File.Exists(outputName))
{
outputName = Path.GetDirectoryName(outputName) + Path.GetFileNameWithoutExtension(outputName) + "(1)" + Path.GetExtension(outputName);
}
using (var output = File.OpenWrite(outputName))
{
if (output.Length%2 != 0)
{
throw new InvalidDataException("File is damaged");
}
int b;
while ( (b = input.ReadByte()) != -1)
{
byte currentByteSequence = (byte)b;
byte currentByte = (byte)input.ReadByte();
for (int i = 0; i < currentByteSequence; i++)
{
output.WriteByte(currentByte);
}
}
return outputName;
}
}
}
}
}
Лістинг файлу Program.cs
using System;
namespace ArchivatorRLE
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine("Enter path to file");
var path = Console.ReadLine();
var a = new RLEArchivator.RLEArchivator(path);
var newpath = a.Archive();
Console.WriteLine("Archiving complete!");
var b = new RLEArchivator.RLEArchivator(newpath);
b.Extract();
Console.WriteLine("ExtractingComplete");
}
}
}
Файл до архівації:
Файл після архівації:
/
/
Висновок
В лабораторній роботі було розглянуто методи архівації даних. Були проаналізовані існуючі алгоритми архівації. На основі алгоритму RLE була розроблена консольна програма для перевірки ефективності даного методу.
27.12.2016 22:12-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора