Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
СТИСНЕННЯ ІНФОРМАЦІЇ МЕТОДОМ LZW
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра САПР
Інформація про роботу
Рік:
2008
Тип роботи:
Звіт про виконання лабораторної роботи
Предмет:
Методи i засоби комп'ютерних інформаційних технологій
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет «Львівська політехніка»
Кафедра САПР
ЗВІТ
про виконання лабораторної роботи №3
на тему: «СТИСНЕННЯ ІНФОРМАЦІЇ МЕТОДОМ LZW»
з курсу:
« Методи та засоби комп’ютерних інформаційних технологій»
Львів – 2008
МЕТА РОБОТИ
Мета роботи - вивчення методу Лемпеля-Зіва-Велча (LZW) для стиснення даних та його програмної реалiзацiї для практичного використання.
КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ
2.1. Стиснення даних.
З метою компактного представлення інформації в ПЕОМ для її збереження (архівації) чи передачі по каналу зв’язку широко використовується стиснення даних. Методи стиснення даних поділяються на дві групи: стиснення без втрат і стиснення з втратами. Крім того, методи групуються в залежності від характеру інформації, що стискається: стиснення символьної інформації (документів), стиснення нерухомих графічних зображень (JPEG) і стиснення рухомих графічних зображень (MPEG). Основним параметром, що характеризує рівень стиснення інформації є коефіцієнт стиснення, який визначається відношенням обсягу нестиснених даних до обсягу стиснених (наприклад 5:1).
2.2. Метод LZW.
Відомі методи оптимального кодування різнозначними кодами (кодами різної довжини), які базуються на врахуванні різної частоти символів в тексті. Найбільш відомі з них: метод Шеннона-Фано та метод Хаффмана. Ці методи забезпечують достатньо ефективне стиснення без втрат. Для підвищення рівня стиснення даних доцільно перейти від оптимального кодування окремих символів до кодування буквосполучень. Саме таке кодування забезпечує метод LZW.
Метод базується на побудові таблиці фраз (словника), яка відображає стрічки символів повідомлення, що стискається, в коди фіксованої довжини (12 біт). Таблиця має властивість попередництва, тобто для кожної фрази словника, яка складається з деякої фрази w і символа K, фраза w теж міститься в словнику і представляється відповідним номером n.
Програмна реалізація методу здійснюється за наступним алгоритмом (ілюструється на прикладі кодування фрази МАМАМАЛАЛАМУ з представленням словника у вигляді таблиці:
У словник заносяться односимвольні фрази w, що відповідають символам вхідного алфавіту (ініціація словника).
Біжучий вказівник встановлюється на перший символ тексту (фраза М).
Здійснюється пошук фрази М у словнику (фраза є за номером 1).
Фраза М доповнюється наступним символом А і здійснюється пошук розширеної фрази МА у словнику (фраза відсутня).
Знайдена раніше частина розширеної фрази МА (фраза М) кодується її номером 1, а нова фраза МА заноситься у словник під номером 5 і представляється (у формі nK) кодом 1А.
Після цього, вказівник встановлюється на останній символ А розширеної фрази МА, який розглядається і кодується як нова фраза, аналогічно як у п. 3.
Фраза А є у словнику під номером 2.
Фраза А доповнюється наступним символом М і здійснюється пошук розширеної фрази АМ у словнику (фраза відсутня).
Знайдена частина розширеної фрази АМ (фраза а) кодується її номером 2, а нова фраза АМ заноситься в словник під номером 6 і представляється кодом 2М.
Вказівник встановлюється на останній символ М розширеної фрази АМ, який у свою чергу розглядається і кодується як нова фраза.
Здійснюється пошук фрази М у словнику (фраза є за номером 1).
Фраза М доповнюється наступним символом А і здійснюється пошук розширеної фрази МА у словнику (фраза є за номером 5).
Фраза МА доповнюється наступним символом М і здійснюється пошук розширеної фрази МАМ (фраза відсутня).
Знайдена частина (фраза МА) розширеної фрази МАМ кодується відповідним номером 5, а відсутня фраза МАМ заноситься у словник під номером 7.
Кроки циклічно повторюються до закінчення послідовності кодованих символів.
Результати кодування представлені на рис. 1 і таблицею словника.
М А М А М А Л А Л А М У
1 2 5 5 3 2 9 1 4
Рис 1. Результати кодування послідовності символів.
Таблиця 1
Номер фрази у словнику
Фраза у словнику
Код фрази у словнику
1
М
1
2
А
2
3
Л
3
4
У
4
5
МА
1А
6
АМ
2М
7
МАМ
5М
8
МАЛ
5Л
9
ЛА
3А
10
АЛ
2Л
11
ЛАМ
9М
12
МУ
1У
Декодування тексту здійснюється по таких кроках:
Закодований текст передається чи зберігається разом з проініційованою частиною (алфавітом) словника (перші чотири рядки словника)
Вибирається перший номер коду 1 і заміщається відповідною фразою М із словника.
Вибирається наступний номер коду 2 і заміщається фразою А.
З фраз М і А формується нова фраза у словнику МА і її код 1А (як при кодуванні).
Наступний номер коду 5 має код фрази 1А, що відповідає відновленій фразі МА.
По відомій фразі А та фразі МА формується нова фраза АМ, яка з кодом фрази 2М заноситься у шостий рядок словника.
Фраза МА записується і для наступного коду 5.
Починаючи з останнього символа М нової фрази АМ здійснюється пошук у словнику фрази МА (фраза є під номером 5), а потім нової розширеної фрази МАМ, яка відсутня у словнику і заноситься туди під номером 7, як при кодуванні.
Починаючи з останнього символа М нової фрази МАМ здійснюється пошук фраз М та МА (обидві фрази є).
Дописується фраза Л для коду 3.
З фраз МА та Л формується нова фраза МАЛ, яка відсутня в словнику і записується туди під номером 8.
Починаючи з останнього символа Л (код якого у словнику 3) фрази МАЛ для коду 2 дописується фраза А і формується нова фраза ЛА, яка відсутня в словнику і записується туди під номером 9.
Береться останній символ фрази ЛА і до нього дописується фраза ЛА для коду 9.
Здійснюється формування фрази АЛ , пошук її у словнику і так як фраза відсутная, то відбувається занесення фрази АЛ у словник під номером 10.
З останнього символа фрази АЛ формуються фрази Л та ЛА, які є у словнику.
Для відомого коду 1 записується фраза М і формується фраза ЛАМ, яка відсутня в словнику і заноситься у рядок під номером 11.
Вибирається останній символ М фрази ЛАМ, який є у словнику і до нього по відомому коду 4 дописується фраза У .
Відсутня нова фраза МУ заноситься у словник і на цьому відновлення словника і закодованого і стисненого тексту закінчується.
3, ІНДИВІДУАЛЬНЕ ЗАВДАННЯ
Побудувати словник і стиснути заданий текст методом LZW. Показати як відновлюється початковий текст. Текст: МОМОНОМАМОМАНО
4. ВИКОНАННЯ ЗАВДАННЯ ВРУЧНУ.
Текст: МОМОНОМАМОМАНО
5. ТЕКСТ ПРОГРАМИ
#include <stdio.h>
#include <conio.h>
#define BITS 12
#define HASHING_SHIFT BITS-8
#define MAX_VALUE (1 << BITS) - 1
#define MAX_CODE MAX_VALUE - 1
#if BITS == 14
#define TABLE_SIZE 18041
#endif
#if BITS == 13
#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];
main(int argc, char *argv[])
{
FILE *input_file;
FILE *output_file;
FILE *lzw_file;
char input_file_name[81], lzw_f_n[81], output_f_n[81],parameter;
code_value=malloc(TABLE_SIZE*sizeof(unsigned int));
prefix_code=malloc(TABLE_SIZE*sizeof(unsigned int));
append_character=malloc(TABLE_SIZE*sizeof(unsigned char));
clrscr();
if (code_value==NULL || prefix_code==NULL || append_character==NULL)
{
printf("Fatal error allocating table space!\n");
exit();
}
if (argc==4)
{strcpy(input_file_name,argv[2]);
strcpy(lzw_f_n,argv[3]);
parameter=argv[1][0];}
else
{
printf("Press 'c' to compress or 'd' to decompress: ");
scanf("%c",¶meter);
printf("\nInput file name: ");
scanf("%s",&input_file_name);
printf("\nOutput file name: ");
scanf("%s",&lzw_f_n);
}
input_file=fopen(input_file_name,"rb");
lzw_file=fopen(lzw_f_n,"wb");
if (input_file==NULL || lzw_file==NULL)
{
printf("Fatal error opening files.\n");
exit();
};
//Стиснення файлу
if((parameter=='c')||(parameter=='C')){
compress(input_file,lzw_file);
fclose(input_file);
fclose(lzw_file);
free(code_value);
}
else if((parameter=='d')||(parameter=='D')){
lzw_file=fopen(input_file_name,"rb");
output_file=fopen(lzw_f_n,"wb");
if (lzw_file==NULL || output_file==NULL)
{
printf("Fatal error opening files.\n");
exit();
};
//Розтиснення файлу
decompress(lzw_file,output_file);
fclose(lzw_file);
fclose(output_file);
}
else {printf("\nPARAMETER ERROR!\n"); exit();}
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;
for (i=0;i<TABLE_SIZE;i++)
code_value[i]=-1;
i=0;
printf("Compressing...");
string_code=getc(input);
while ((character=getc(input)) != (unsigned)EOF)
{
if (++i==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;
}
}
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;
}
}
//Функція розтиснення
decompress(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("Decompressing...");
old_code=input_code(input);
character=old_code;
putc(old_code,output);
while ((new_code=input_code(input)) != (MAX_VALUE))
{
if (++counter==1000) { counter=0; printf("."); }
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;
}
}
6. ВИСНОВКИ
На цій лабораторній роботі я вивчив метод Лемпеля-Зіва-Велча (LZW) для стиснення даних та його програмну реалiзацiю для практичного використання.
10.02.2013 23:02-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора