Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Дослідження алгоритмів архівації
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
УІ
Кафедра:
Не вказано
Інформація про роботу
Рік:
2014
Тип роботи:
Лабораторна робота
Предмет:
Програмний захист інформації
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ "ЛЬВІВСЬКА ПОЛІТЕХНІКА"
кафедра ЗІ
Звіт
до лабораторної роботи № 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%.
Отже, алгоритм є найефективнішим для текстових файлів.
20.05.2016 23:05-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора