Phân tích trình LZW 12 nhằm mô phỏng thuật toàn kỹ thuật nén dữ liệu - pdf 16

Download miễn phí Đề tài Phân tích trình LZW 12 nhằm mô phỏng thuật toàn kỹ thuật nén dữ liệu



GIẢI THÍCH CHƯƠNG TRÌNH LZW12.CPP.
Chúng ta sử dụng cấu trúc từ điển sau ;
struct dictionary
{
int code_value;
int parent_code;
char character;
}
*dict;
Cấu trúc trên có thể chứa đựng cây từ điển. Mỗi phần tử của cấu trúc biểu diễn 1 đỉnh. Đỉnh được xác định bởi 3 thành phần:
Code_value: đây là số được gán cho xâu được kết thúc tại đỉnh này. Nó cũng chính là index mà trình nén đưa ra trong dãy token.
Parent_code: do đặc điểm của thuật toán LZ78, mỗi phrase trong từ điển có một xâu cha ngắn hơn nó 1 ký tự. Parent_code là code_value của đỉnh cha này.
Character: đó là ký tự cho riêng đỉnh này.
Trong cây trên thì 256 đỉnh đầu tiên là các đỉnh đặc biệt. Nó ứng với 256 ký tự của bng mã ASCII (từ 0 đến 255), các đỉnh này không có đỉnh cha. Chúng coi như luôn có và do END_OF_STREAM =256 nên FIRST_CODE=257.
Trong cấu trúc trên không có biến để trỏ tới đỉnh con, vậy chúng ta di chuyển trong cây này như thế nào? Để làm việc này, chúng ta dùng hàm băm. Dùng hàm băm chúng ta có không thể di chuyển lên trong cây, nhưng việc nén chỉ cần di chuyển xuống.
 



Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí

Tóm tắt nội dung tài liệu:

Lời nói đầu
Ngày nay, cùng với sự phát triển không ngừng của khoa học và công nghệ thì máy tính đóng vai trò không thể thiếu trong cuộc sống xã hội loài người.
Việc trao đổi thông tin của con người trong tất cả các ngành, các lĩnh vực của đời sống ngày càng trở nên cấp thiết và quan trọng, chính vì thế mà các thiết bị thông tin mới liên tục ra đời nhằm đáp ứng các yêu cầu này. Tuy nhiên, vì một số phần mềm đòi hỏi rất nhiều bộ nhớ để hoạt động trao đổi thông tin nên người ta đã nghĩ ra một phương pháp nhằm giải quyết vấn đề này, đó là phương pháp nén dữ liệu mà vẫn bảo toàn thông tin.
Nén dữ liệu là một kỹ thuật quan trọng trong rất nhiều lĩnh vực khác nhau. Chính nhờ có kỹ thuật nén dữ liệu mà ngày nay chúng ta có những phương tiện truyền thông hiện đại phục vụ cho cuộc sống như truyền hình cáp, điện thoại, thư điện tử ... và rất nhiều khía cạnh khác. Do đó kỹ thuật nén dữ liệu ngày càng được quan tâm và phát triển nhiều hơn. ở Việt Nam, hầu hết các trường Đại học đều quan tâm đến việc nén dữ liệu và điều này được thể hiện ở việc đưa kỹ thuật nén trở thành môn học chính thức trong giai đoạn chuyên ngành .
Trong phạm vi môn học “ Mã - mã nén” . tui đưa ra bài phân tích trình LZW 12 nhằm mô phỏng thuật toàn kỹ thuật nén dữ liệu.
Tuy nhiên do trình độ còn hạn chế, thời gian và kinh nghiệm chưa nhiều, nên bài phân tích này không thể tránh khỏi sự sai sót trong quá trình phân tích. Do vậy tui rất mong được sự quan tâm tham gia góp ý Thầy Cô cũng như cùng toàn thể các bạn Sinh Viên để bài phân tích này rõ dàng hơn.
Cuối cùng Em xin chân thành Thank thày Nguyễn Lê Anh đã hướng dẫn và giảng dạy Em trong thời gian qua.
Giải thích stdio.h
Các hàm thư viện I/O được định nghĩa trong STDIO.H chỉ làm việc ở mức byte, đó là các hàm putc(), getc(), fread(), fwrite(). Chúng ta cần viết các thủ tục vào/ra ở mức bit.
Cấu trúc BIT_FILE được định nghĩa như sau:
typedef struct bit_file
{
FILE *file;
unsigned char mask;
int rack;
int pacifier_counter;
}
BIT_FILE;
Các thành phần "rack" và "mask" được dùng để quản lý theo bit. Rack để chứa byte dữ liệu hiện thời được đọc từ tệp hay được ghi vào tệp. Mask chứa 1 bit cờ để đánh dấu vị trí của bit đang được xử lý trong byte.
Các hàm
BIT_FILE *OpenInputFile(char *name)
BIT_FILE *OpenOutputFile(char *name)
void CloseInputBitFile(BIT_FILE *bit_file)
void CloseOutputBitFile(BIT_FILE *bit_file)
được dùng để mở tệp hay đóng tệp khi ghi hay đọc. Các hàm này tương đối đơn giản nên chúng tui không gì thích gì thêm.
Hai kiểu thủ tục I/O được định nghĩa trong BITIO.H. Hai thủ tục đầu dùng để đọc và ghi mỗi bit một lần. Hai thủ tục khác dùng để đọc hay ghi nhiều bit một lần. Đó là các hàm:
void OutputBit( BIT_FILE *bit_file, int bit)
void OutputBits( BIT_FILE *bit_file, unsigned long code, int count)
int InputBit( BIT_FILE *bit_file)
unsigned long InputBits( BIT_FILE *bit_file, int bit_count)
void OutputBit( BIT_FILE *bit_file, int bit)
Trong BITIO.H, bit cao nhất trong byte được đọc hay ghi là bít đầu tiên, bit nhỏ nhất trong byte là bít được xử lý cuối. Điều đó có nghĩa là phần tử mask ban đầu sẽ được đặt bằng 0x80. Nếu bit được ghi vào tệp là 1 thì thực hiện lệnh
bit_file->rack |= bit_file->mask,
sau đó mask được dịch sang trái 1 bit bằng lệnh
bit_file->mask >>=1.
Nếu mask=0 tức là đã tích được đủ 8 bit thì lúc đó mới ghi vào tệp bằng lệnh
putc(bit_file->rack, bit_file->file)
Cứ xử lý được 2048 byte thì một ký tự (là dấu chấm) lại được đưa ra màn hình. Sau đó bắt đầu một rack mới bằng các lệnh
bit_file->rack = 0;
bit_file->mask = 0x80;
void OutputBits( BIT_FILE *bit_file, unsigned long code, int count)
Biến count chỉ ra số bit cần ghi (nhiều nhất là 16 bit). Giá trị cần ghi được lưu ở biến code.
int InputBit( BIT_FILE *bit_file)
Nếu bit_file->mask==0x80 thì đọc một byte mới từ tệp ra biến bit_file->rack bằng lệnh
bit_file->rack=getc(bit_file->file).
Lấy bit ra bằng lệnh
value=bit_file->rack & bit_file->mask
sau đó dịch mask đi một vị trí bằng lệnh
bit_file->mask >>=1.
Nếu bit_file->mask==0 thì nó được đặt lại bằng 0x80.
unsigned long InputBits( BIT_FILE *bit_file, int bit_count)
Đọc bit_count bit từ tệp ra biến return_value. Trong quá trình đọc, các bit được lấy ra từ bit_file->rack. Nếu bit_file->mask==0x80 thì mới đọc byte mới từ tệp ra bằng lệnh
bit_file->rack=getc(bit_file->file)
Một số hàm khác
file_size(char *name) trở về độ dài của tệp.
print_ratios(char *input, char *output) cho biết tỷ lệ nén.
fatal_error(char *fmt,...) thông báo về lỗi mà chúng ta gặp phi. Nó có dùng cấu trúc và các hàm rất đặc trưng cho C, đó là cấu trúc va_list, các hàm va_start và va_end.
prog_name(char *program_name) dùng để lấy riêng tên của chưng trình đang chạy (bỏ phần đường dẫn và phần mở rộng của tên tệp). Nó được dùng kèm khi hướng dẫn cách chạy chưng trình bằng biến Usage.
Chương Trình LZW12.CPP
#include "bitio.c"
void usage_exit(char *prog_name);
void CompressFile(FILE *input,BIT_FILE *output,int argc,char *argv[]);
void ExpandFile(BIT_FILE *input,FILE *output,int argc,char *argv[]);
char *CompressionName="LZW 12 Bit Encoder ";
char *Usage="in-file out-file \n\n";
void usage_exit(char *prog_name)
{ char *short_name;
char *extension;
short_name = strrchr(prog_name,'\\');
if (short_name == NULL) short_name=strrchr(prog_name,':');
if (short_name!= NULL) short_name++;
else short_name=prog_name;
extension=strrchr(short_name,'.');
if (extension != NULL) *extension='\0';
printf("\nUsage : %s %s \n",short_name,Usage);
exit(0);
}
/*==================================*/
#define BITS 12
#define MAX_CODE ((1<<BITS)-1)
#define TABLE_SIZE 5021
#define END_OF_STREAM 256
#define FIRST_CODE 257
#define UNUSED -1
unsigned int find_child_node(int parent_code,int child_character);
unsigned int decode_string(unsigned int offset,unsigned int code);
struct dictionary { int code_value;
int parent_code;
char character;
} dict;
char decode_stack;
void CompressFile(FILE *input,BIT_FILE *output,int argc,char *argv[])
{int next_code;
int character;
int string_code;
unsigned int index;
unsigned int i;
next_code=FIRST_CODE;
for (i=0;i<TABLE_SIZE;i++) dict.code_value=UNUSED;
if ((string_code=getc(input))==EOF) string_code=END_OF_STREAM;
while ((character=getc(input))!=EOF)
{ index=find_child_node(string_code,character);
if (dict[index].code_value !=-1)
string_code=dict[index].code_value;
else
{ if (next_code <= MAX_CODE)
{ dict[index].code_value=next_code++;
dict[index].parent_code=string_code;
dict[index].character=(char)character;
}
OutputBits(output,(unsigned long)string_code,BITS);
string_code=character;
}
}
OutputBits(output,(unsigned long)string_code,BITS);
OutputBits(output,(unsigned long)END_OF_STREAM,BITS);
while (argc-- >0)
printf("Unknown argument :%s\n",*argv++);
}
/*======================*/
void ExpandFile(BIT_FILE *input,FILE *output,int argc,char *argv[])
{ int next_code;
int new_code;
int old_code;
int character;
unsigned int count;
next_code=FIRST_CODE;
old_code=(unsigned int)InputBits(input,BITS);
if (old_code==END_OF_STREAM) return;
character=old_code;
putc(old_code,output);
while((new_code=(unsignedint) InputBits(input,BITS)) != END_OF_STREAM)
{ if (new_code >= next_code)
{ decode_stack[0]=(char)character;
count=decode_string(1,old_code);
}
else count=decode_string(0,new_code);
character=decode_stack[count-1];
while(count>0) putc(decode_stack[--count],output);
if (next_code <= MAX_CODE)
{ dict[next_code].parent_code=old_code;
dict[next_code].character=(char)character;
next_code++;
}
old_co...

Tài liệu, ebook tham khảo khác

Music ♫

Copyright: Tài liệu đại học © DMCA.com Protection Status