Дослідження алгоритмів архівації. Лабораторна робота з Програмний захист інформації. Робота № 528245

Дослідження алгоритмів архівації

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Не вказано

Факультет:

УІ

Кафедра:

Не вказано

Інформація про роботу

Рік:

2016

Тип роботи:

Лабораторна робота

Предмет:

Програмний захист інформації

Завантажити

Частина тексту файла (без зображень, графіків і формул):

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ "ЛЬВІВСЬКА ПОЛІТЕХНІКА" кафедра ЗІ Звіт до лабораторної роботи № 1 з курсу: "Програмний захист інформації " на тему: “ Дослідження алгоритмів архівації ” Мета роботи: Розглянути основні методи стиску інформації. Навчитися на практиці реалізовувати дані алгоритми. Засвоїти поняття: • архівація даних; • архів даних; • програма-архіватор; • неперервне архівування; • багатотомні архіви; • архіви, які містять засіб для розшаровування (SFX); • відновлення даних; • відновлювальні томи; • коментар до архіву; • протокол помилок. Вміти: • створювати архіви даних; • переглядати вміст архіву, видобувати файли, від ображати коментарі та інформацію про архів; • відновлювати фізично пошкоджений архів; • видобувати файли за допомогою середовища WinRAR Завдання: Розробити програму стиснення файлів одним із наведених у таблиці №1 алгоритмом згідно свого варіанту. Варіант Алгоритми програм 5 Алгоритм Лемпеля-Зива-Велча (Lempel-Ziv-Welch - LZW) Короткі теоретичні відомості: Всі алгоритми стиснення оперують вхідним потоком даних, мінімальною одиницею яких є біт, а максимальною – декілька біт, байт або декілька байтів. Метою процесу стиснення є отримання більш компактного вихідного потоку інформаційних одиниць з некомпактного вхідного потоку за допомогою перетворення. Основними технічними характеристиками процесів стиснення і результатів їх роботи є : • степінь стиснення (compress rating) або відношення (retion) об’ємів вхідного і вихідного потоків; • швидкість стиснення – час, який витрачається на стиснення деякого об’єму інформації вхідного потоку, до отримання з нього еквівалентного вихідного потоку; • якість стиснення – величина, яка вказує, на скільки сильно упакований вихідний потік, за допомогою застосування до нього повторного стиснення за цим або іншим алгоритмом. Всі способи стиснення можна поділити на дві категорії: зворотнє і не зворотнє. Під зворотнім стисненням розуміють таке перетворення вхідного потоку даних, при якому вихідний потік, в контексті певного формату даних, представляє достатньо схожий за зовнішніми характеристиками на вхідний потік об’єкт, але відрізняється від нього об’ємом. Рівень схожості вхідного і вихідного потоків визначається рівнем відповідності деяких властивостей об’єкта (тобто, стисненої і не стисненої інформації у відповідності до деякого визначеного формату даних). Алгоритм Лемпеля-Зива-Велча (Lempel-Ziv-Welch - LZW) Даний алгоритм відрізняють висока швидкість роботи як при упаковці, так і при розпаковуванні, досить скромні вимоги до пам'яті і проста апаратна реалізація. Недолік - низька міра стиснення в порівнянні з схемою двоступінчастого кодування. Передбачимо, що у нас є словник, що зберігає рядки тексту і що містить порядку від 2-ох до 8-ми тисяч пронумерованих гнізд. Запишемо в перших 256 гнізд рядки, що складаються з одного символу, номер якого дорівнює номеру гнізда. Алгоритм переглядає вхідний потік, розбиваючи його на підрядки і додаючи нові гнізда в кінець словника. Прочитаємо декілька символів в рядок s і знайдемо в словнику рядок t - щонайдовший префікс s. Хай він знайдений в гнізді з номером n. Виведемо число n у вихідний потік, перемістимо покажчик вхідного потоку на length(t) символів вперед і додамо в словник нове гніздо, що містить рядок t+c, де с - черговий символ на вході (відразу після t). Алгоритм перетворить потік символів на вході в потік індексів комірок словника на виході. При практичній реалізації цього алгоритму слід врахувати, що будь-яке гніздо словника, окрім найперших, таких, що містять одно-символьні ланцюжки, зберігає копію деякого іншого гнізда, до якої в кінець приписаний один символ. Внаслідок цього можна обійтися простою обліковою структурою з одним зв'язком. Приклад: ABCABCABCABCABCABC - 1 2 3 4 6 5 7 7 7 1 A 2 B 3 C 4 AB 5 BC 6 CA 7 ABC 8 CAB 9 BCA Текст програми: #include <stdio.h> #define BITS 12 /* новлення довжини коду рівної 12, 13 */ #define HASHING_SHIFT BITS-8 /* або 14 бітам. */ #define MAX_VALUE (1 << BITS) - 1/* при довжині коду 14 біт */ #define MAX_CODE MAX_VALUE - 1 /* необхідно використовувати */ /* large-модель. */ #if BITS == 14 #define TABLE_SIZE 18041 /* Розмір таблиці та рядків повинен бути */ #endif /* простим числом, більшим, */ #if BITS == 13 /* ніж 2**BITS. */ #define TABLE_SIZE 9029 #endif #if BITS <= 12 #define TABLE_SIZE 5021 #endif void *malloc(); /* це масив для значень кодів */ int *code_value; /* цей масив префиксів кодоів */ unsigned int *prefix_code; /* це масив додаткових символів */ unsigned char *append_character; /* масив декодованих рядків */ unsigned char decode_stack[4000]; /******************************************************************* ** Програма отримує ім'я файлу з командної стрічки. ** вона запаковує файл ** посилаючи вихідний потік в файл test.lzw. Потім розпаковує ** test.lzw в test.out. Test.out повинен бути точною копією test.lzw ********************************************************************/ main(int argc, char *argv[]) { FILE *input_file; FILE *output_file; FILE *lzw_file; char input_file_name[81]; /* ** ці три буфери необхідні для розпакування. */ code_value=malloc(TABLE_SIZE*sizeof(unsigned int)); prefix_code=malloc(TABLE_SIZE*sizeof(unsigned int)); append_character=malloc(TABLE_SIZE*sizeof(unsigned char)); if (code_value==NULL || prefix_code==NULL || append_character==NULL) { printf("Fatal error allocating table space!\n"); exit(); } /* ** отримуємо ім'я файлу, відкриваємо його і відкриваємо вихідний lzw-файл. */ if (argc>1) strcpy(input_file_name,argv[1]); else { printf("Input file name? "); scanf("%s",input_file_name); } input_file=fopen(input_file_name,"rb"); lzw_file=fopen("test.lzw","wb"); if (input_file==NULL || lzw_file==NULL) { printf("Fatal error opening files.\n"); exit(); }; /* ** Стиснення файлу. */ compress(input_file,lzw_file); fclose(input_file); fclose(lzw_file); free(code_value); /* ** відкриваємо файли для розпакування. */ lzw_file=fopen("test.lzw","rb"); output_file=fopen("test.out","wb"); if (lzw_file==NULL || output_file==NULL) { printf("Fatal error opening files.\n"); exit(); }; /* ** Розпакування файлу. */ expand(lzw_file,output_file); fclose(lzw_file); fclose(output_file); free(prefix_code); free(append_character); } /* ** Процедура стиснення. */ compress(FILE *input,FILE *output) { unsigned int next_code; unsigned int character; unsigned int string_code; unsigned int index; int i; next_code=256; /* Next_code - наступний доступний код рядка */ for (i=0;i<TABLE_SIZE;i++)/*очистка таблиці рядків перед стартом */ code_value[i]=-1; i=0; printf("Compressing...\n"); string_code=getc(input); /* Get the first code*/ /* ** Основний цикл. він виконується до тих пір, поки можливе читання ** вхідного потоку. Він он припиняє заповнення таблиці ** рядків після того, як всі можливі коди були використані. */ while ((character=getc(input)) != (unsigned)EOF) { if (++i==1000) /* Друкує * через ккожні 1000 */ { /* читання вхідних символів */ i=0; printf("*"); } /* Перевіряє чи є рядок */ index=find_match(string_code,character); if (code_value[index] != -1) /* в таблиці. Якщо є,*/ string_code=code_value[index];/* отримує значення коду*/ else /* Якщо нема, додає його*/ { /* в таблицю. */ if (next_code <= MAX_CODE) { code_value[index]=next_code++; prefix_code[index]=string_code; append_character[index]=character; } output_code(output,string_code);/*Коли помічається, що*/ string_code=character; /*рядка нема в таблиці, */ } /*виводиться останній рядок*/ } /*перед додаванням нового */ /* ** End of the main loop. */ output_code(output,string_code); /* Вивід останнього коду */ output_code(output,MAX_VALUE); /* Вивід ознаки кінця потоку */ output_code(output,0); /* Очищення буфера виводу */ printf("\n"); } /* ** Процедура хешування. Вона намагається знайти співпадіння для рядка ** префікс+символ в таблиці рядків. Якщо знайдено, повертається індекс. ** Якщо ні, то повертається перший доступний індекс. */ find_match(int hash_prefix,unsigned int hash_character) { int index; int offset; index = (hash_character << HASHING_SHIFT) ^ hash_prefix; if (index == 0) offset = 1; else offset = TABLE_SIZE - index; while (1) { if (code_value[index] == -1) return(index); if (prefix_code[index]==hash_prefix &&append_character[index]==hash_character) return(index); index -= offset; if (index < 0) index += TABLE_SIZE; } } /* ** Процедура розпакування. Вона читає файл LZW-формату и распаковує ** його в вихідний файл. */ expand(FILE *input,FILE *output) { unsigned int next_code; unsigned int new_code; unsigned int old_code; int character; int counter; unsigned char *string; char *decode_string(unsigned char *buffer,unsigned int code); next_code=256; /* Наступний доступний код. */ counter=0; /* Використовується при виводі на екран.*/ printf("Expanding...\n"); old_code=input_code(input);/*Читаєтся перший код, ініціалізується*/ character=old_code; /* змінна character і надсилається перший */ putc(old_code,output); /* код в вихідний файл. */ /* ** Основний цикл розпакування. Читаються коди з LZW-файлу до тих пір, ** поки не зустрінеться спеціальний код, що вказує на кінець даних. */ while ((new_code=input_code(input)) != (MAX_VALUE)) { if (++counter==1000) { counter=0; printf("*"); } /* ** Перевірка коду для спеціального випадку ** STRING+CHARACTER+STRING+CHARACTER+ ** STRING, коли генерується невизначений код. ** це заставляє його декодувати останній код, ** додавши CHARACTER в кінець декод. рядка. */ if (new_code>=next_code) { *decode_stack=character; string=decode_string(decode_stack+1,old_code); } /* ** інакше декодується новий код. */ else string=decode_string(decode_stack,new_code); /* ** Виводиться декодуючий рядок в зворотньому порядку. */ character=*string; while (string >= decode_stack) putc(*string--,output); /* ** Якщо можливо, додається новий код в таблицю рядків. */ if (next_code <= MAX_CODE) { prefix_code[next_code]=old_code; append_character[next_code]=character; next_code++; } old_code=new_code; } printf("\n"); } /* ** Процедура простого декодування рядка з таблиці рядків, * синхронізуюча ** результат в буфер. Цей буфер потім може бути виведений ** в зворотньому порядку програмою разпакування. */ char *decode_string(unsigned char *buffer,unsigned int code) { int i; i=0; while (code > 255) { *buffer++ = append_character[code]; code=prefix_code[code]; if (i++>=4094) { printf("Fatal error during code expansion.\n"); exit(); } } *buffer=code; return(buffer); } /* ** наступні дві процедури управляють вводом/виводом кодів ** змінної довжини. */ input_code(FILE *input) { unsigned int return_value; static int input_bit_count=0; static unsigned long input_bit_buffer=0L; while (input_bit_count <= 24) { input_bit_buffer|=(unsigned long)getc(input)<<(24-input_bit_count); input_bit_count += 8; } return_value=input_bit_buffer >> (32-BITS); input_bit_buffer <<= BITS; input_bit_count -= BITS; return(return_value); } output_code(FILE *output,unsigned int code) { static int output_bit_count=0; static unsigned long output_bit_buffer=0L; output_bit_buffer|=(unsigned long)code<<(32-BITS-output_bit_count); output_bit_count += BITS; while (output_bit_count >= 8) { putc(output_bit_buffer >> 24,output); output_bit_buffer <<= 8; output_bit_count -= 8; } } Результати виконання програми: Стиснення файлу типу .jpg: початковий обсяг файлу: 884987КБ – 100% обсяг файлу після стиснення: 867737 байт – 98,05%. Стиснення файлу типу .txt: початковий обсяг файлу: 6511 байт – 100% обсяг файлу після стиснення: 2919 байт – 44,2%. Стиснення файлу типу .exe: початковий обсяг файлу: 768512 байт – 100% обсяг файлу після стиснення: 767838 байт – 99,81%. Висновок: Під час виконання лабораторної роботи я розглянула метод Лемпеля-Зива-Велча Протестувала програму на різних типах файлів і порівняла результат: для файлу .jpg обсяг зменшився з 100% до 98,05%; для .txt – з 100% до 44,2%; для .exe – з 100% до 99,81%. Отже, алгоритм є найефективнішим для текстових файлів.

Лабораторна робота Програмний захист інформації

lila95

20.05.2016 23:10

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

поділитись