Bài phân tích trình lzw 15 nhằm mô phỏng thuật toàn kỹ thuật nén dữ liệu.

  • Số trang: 31 |
  • Loại file: PDF |
  • Lượt xem: 8 |
  • Lượt tải: 0
hoangtuavartar

Đã đăng 24635 tài liệu

Mô tả:

Website: http://www.docs.vn Email : lienhe@docs.vn Tel : 0918.775.368 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 2 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‛ . T«i ®­a ra b¯i ph©n tÝch tr×nh LZW 15 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 t«i 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 c¶m ¬n thµy NguyÔn Lª Anh ®· h-íng dÉn vµ gi¶ng d¹y Em trong thêi gian qua. 3 ThuËt to¸n nÐn LZW B-íc 1 C¾t v¨n b¶n míi thµnh c¸c ®o¹n copy nÕu b¶ng ch÷ c¸i cã m ch÷ th× c¸c ch÷ c¸i lµ m ®o¹n copy ®Çu tiªn ®-îc ®¸nh sè tõ 0 ®Õn m-1. B-íc 2 Bá tÊt c¶ phÇn ch÷ thu ®-îc m· nÐn. L-u ý r»ng c¸c ®o¹n copy lÇn l-ît ®-îc t¹o ra vµ phÇn sè cña nã lu«n nhá h¬n sè hiÖu cét mµ nã ®øng. ThuËt to¸n gi¶i nÐn LZW. B¾t ®Çu lµ c¸c cét ®Çu tiªn (trong vÝ dô lµ cét thø 2) lÆp l¹i thao t¸c sau cho ®Õn hÕt. LÊy hai sè liªn tiÕp cña b¶n m· vÝ dô lµ X, Y thay nã vÒ d¹ng X+? vµ Y+$. Trong ®ã kÝ tù ®Çu tiªn cña Y+$ lµ kÝ tù cuèi cïng cña X+?. DÊu ? vµ $ lµ thay cho mét kÝ tù ch-a biÕt. V× X vµ Y kh«ng thÓ lín h¬n chØ sè cét mµ nã ®øng cho nªn chóng ta hoµn toµn t×m ®-îc gi¸ trÞ ®o¹n copy øng víi cét cã chØ sè X, Y vµ thay ®o¹n copy vµo X+? vµ Y+$ t-¬ng øng. Gi¸ tri ? lµ kÝ tù ®Çu cña Y+$ cho nªn lu«n lu«n x¸c ®Þnh. Nh- thÕ chóng ta t×m ®-îc X+?. VÝ dô. NÐn theo LZW 4 B-íc 1 aabababaaababb 0 1 a b 0 1 2 a b aa 0+a 0 1 2 3 a b aa ab 0+a 0+b 0 1 2 3 4 5 a b aa ab ba aba 0+a 0+b 1+a 3+a thay a0 ®-îc 0abababaaababb tõ ®iÓn ®o¹n copy míi aabababaaababb B-íc 2 aabababaaababb thay a0 ®-îc 00bababaaababb tõ ®iÓn ®o¹n copy míi aabababaaababb B-íc 3 00bababaaababb thay b1 ®-îc 001ababaaababb tõ ®iÓn ®o¹n copy míi aabababaaababb B-íc 4 001ababaaababb thay ab3 5 ®-îc 0013abaaababb tõ ®iÓn ®o¹n copy míi aabababaaababb aabababaaababb B-íc 5 0013abaaababb thay aba5 ®-îc 00135aababb 0 1 2 3 4 5 6 a b aa ab ba aba abaa 0+a 0+b 1+a 3+a 5+a 0 1 2 3 4 5 6 7 a b aa ab ba aba abaa aab 0+a 0+b 1+a 3+a 5+a 2+b tõ ®iÓn ®o¹n copy míi aabababaaababb B-íc 6 00135aababb thay aa2 ®-îc 001352babb tõ ®iÓn 6 ®o¹n copy míi aabababaaababb B-íc 7 001352babb 0 1 2 3 4 5 6 7 8 thay ba4 ®-îc 0013524bb a b aa ab ba aba abaa aab bab 0+a 0+b 1+a 3+a 5+a 2+b 4+b tõ ®iÓn ®o¹n copy míi aabababaaababb ThuËt to¸n LZW Trong LZW th× token chØ cã index. §Ó lµm viÖc nµy, tõ ®iÓn khi ®-îc khëi t¹o ®· gåm tÊt c¶ c¸c ký tù ®¬n lÎ cho nªn nã lu«n ®-îc t×m thÊy trong tõ ®iÓn mÆc dï cã thÓ tr-íc ®ã ch-a xuÊt hiÖn trong v¨n b¶n. ThuËt to¸n nÐn cho LZW: Khi míi b¾t ®Çu, tõ ®iÓn ®· gåm tÊt c¶ c¸c ký tù ®¬n lÎ. 7 X©u hiÖn t¹i b¾t ®Çu cã ®é dµi 1. Mçi khi ®äc thªm 1 ký tù th× nã ®-îc thªm vµo x©u hiÖn t¹i. NÕu x©u hiÖn t¹i cßn trïng víi mét trong c¸c phrase ®· cã th× qu¸ tr×nh cø tiÕp tôc. Khi kh«ng cã phrase trong tõ ®iÓn trïng víi x©u hiÖn t¹i n÷a th× : chóng ta cho ra index lµ chØ sè x©u tr-íc ®ã (kh«ng kÓ ký tù võa ®äc vµo) trong tõ ®iÓn. thªm x©u hiÖn t¹i (bao gåm c¶ ký tù võa ®äc vµo) vµo trong tõ ®iÓn. b¾t ®Çu mét x©u míi b»ng ký tù võa ®äc vµo. Pseudocode nÐn cña LZW: string1[0]=getc(input); string1[1]=’\0’; while (!feof(input)) { character=getc(input); if in_dictionary(string1+character) {string1=string1+character;} else { code=look_up_dictionary(string1); output_code(code); add_to_dictionary(string1+character); string1[0]=character; string1[1]=’\0’; } code=look_up_dictionary(string1); output_code(code); 8 Hai lÖnh cuèi cïng lµ ®Ó xö lý khi hÕt file, lóc ®ã ch-a cã phrase míi nªn kh«ng cã lÖnh add_to_dictionary(). Cét ®Çu tiªn lµ string1 (biÕn cña lÖnh add_to_dictionary) bá bít ®i ký tù ®Çu (ký tù nµy cã do c¸c lÖnh string1[0]=character; string1[1]=’\0’; ë phÇn else {} cña b-íc tr-íc), ®©y thùc chÊt lµ c¸c ký tù ®· ®-îc ®äc bëi lÖnh character=getc(input) . Cét thø hai lµ index cña phrase trong tõ ®iÓn (ë ®©y khi phrase chØ cã 1 ký tù th× chóng ta sö dông chÝnh ký tù nµy thay cho index, ®óng ra lµ ph¶i dïng hµm ascii (ký tù)). Cét thø 3 lµ biÕn (string1 + character) trong lÖnh add_to_dictionary (string1 + character) kÌm theo index cña nã trong tõ ®iÓn. VÝ dô: Mçi dßng cña b¶ng sÏ øng víi mét lÇn thùc hiÖn vßng lÆp while (!feof(input)) (trõ dßng ®Çu tiªn). 9 Input String: ‚ WED WE WEE WEB WET‛ Tõ thuËt to¸n nÐn ta thÊy r»ng: - index cña string1 ë b-íc hiÖn t¹i ®-îc ®-a vµo tÖp nÐn. - phrase ®-îc thªm vµo tõ ®iÓn lµ string1 ë b-íc hiÖn t¹i + character, trong ®ã character lµ ký tù ®Çu cña string1 ë b-íc sau ThuËt to¸n gi¶i nÐn nh- sau: §Çu tiªn, ®äc mét index vµo vµ t×m phrase t-¬ng øng víi nã trong tõ ®iÓn. §-a phrase nµy ra tÖp (string1 ë b-íc tr-íc). Vßng lÆp: ®äc index tiÕp theo, tra tõ ®iÓn ®Ó t×m string1 ë b-íc hiÖn t¹i, ®-a nã vµo tÖp gi¶i nÐn thªm (string1 ë b-íc tr-íc + ký tù ®Çu cña string1 ë b-íc hiÖn t¹i) vµo tõ ®iÓn Trong ®o¹n pseudocode sau th× string2 chÝnh l¯ ‘string1 ë b­íc tr­íc’: string2[0]=input_bits(); string2[1]=’\0’; putc(string2[0], output); while ((code=input_bits() )!=EOF) { string1=dictionary_lookup(code); fputs(string1, output); add_to_dictionary(string2+string1[0]); strcpy(string2, string1);} 10 VÝ dô cña viÖc gi¶i nÐn: Trong b¶ng sau ®©y, mçi dßng sÏ t-¬ng øng víi mét lÇn thùc hiÖn vßng lÆp while{}, riªng dßng ®Çu tiªn lµ do c¸c lÖnh string2[0]=input_bits(); string2[1]=’\0’; putc(string2[0], output); Cét thø nhÊt (I) lµ kÕt qu¶ cña lÖnh code =input_bits(); Cét thø hai (II) lµ kÕt qu¶ cña c¸c lÖnh string1=dictionary_lookup(code); fputs(string1, output); 11 Cét thø ba (III) lµ biÕn string2 trong lÖnh add_to_dictionary(string2+ string1[0]). Nã b»ng víi cét thø hai (string1) ë b-íc tr-íc do lÖnh strcpy(string2, string1). Cét thø t- (IV) lµ ký tù ®Çu cña cét thø II (string1[0]). Cét thø n¨m (V) lµ biÕn (string2+string1[0]) trong lÖnh add_to_dictionary(string2+ string1[0]). Input Codes: ‚ WED<256>E<260><261><257>B<260>T‛ Mét ®iÒu cÇn chó ý khi nÐn b»ng LZW: nã thªm phrase vµo tõ ®iÓn tr-íc khi toµn bé phrase nµy ®-îc nÐn, cô thÓ lµ ký tù cuèi cña phrase chØ ®-îc xö lý ë lÇn lÆp sau. NÕu v× mét lý do nµo ®ã mµ tr×nh nÐn sö dông ngay lËp tøc phrase nµy th× khi gi¶i nÐn sÏ cã vÊn ®Ò lµ gÆp ph¶i code cña mét phrase mµ phrase nµy l¹i ch-a xuÊt hiÖn trong tõ ®iÓn (phrase nµy cßn thiÕu mét ký tù cuèi lµ ký tù ®Çu cña x©u ®-îc gi¶i m· tiÕp theo. RÊt tiÕc lµ ®iÒu nµy cã thÓ x¶y ra. §iÒu nµy chØ x¶y ra khi trong d÷ liÖu vµo cã ®o¹n CHARACTER.STRING.CHARACTER.STRING.CHARACTER. Trong vÝ dô sau CHARACTER=’I’, STRING=’WOMBAT’. Gi° sö x©u 12 ‘IWOMBAT’ ®± cã trong tõ ®iÓn (m± l¯ 300) cßn ‘IWOMBATI’ th× ch­a cã. Nh­ vËy khi gÆp ®o¹n d÷ liÖu‘IWOMBATIWOMBATI’ tr×nh nÐn sÏ cho ra m± 300 v¯ thªm ‘IWOMBATI’ v¯o tõ ®iÓn(víi m± 400 ch¼ng h¹n). Vµ sau ®ã nã sö dông ngay m· 400 cho ®o¹n tiÕp theo, tøc lµ c¶ ®o¹n d÷ liÖu trªn sÏ cho ra m· <300><400>. B©y giê chóng ta h·y theo dâi qu¸ tr×nh gi¶i nÐn. Sau khi thay <300> b»ng ‘IWOMBAT’ th× tr×nh gi°i nÐn gÆp m± 400. Nh-ng khi ®ã trong tõ ®iÓn cña tr×nh gi¶i nÐn cßn ch-a cã phrase ‘IWOMBATI’ v× cßn thiÕu ch÷‘I’ ë cuèi. Cho nªn trong ®o¹n pseudocode trªn, lÖnh string1=dictionary_lookup(code) kh«ng ph¶i lóc nµo còng thµnh c«ng. Nh-ng nã còng chØ kh«ng thµnh c«ng trong tr-êng hîp gÆp ph¶i d÷ liÖu cã d¹ng nh- võa m« t¶, v× ®Ó t¹o thµnh pharase míi trong tõ ®iÓn chóng ta còng chØ thiÕu cã 1ký tù cuèi vµ ký tù nµy xuÊt hiÖn ë ngay ®Çu cña ®o¹n d÷ liÖu tiÕp theo. Cho nªn chóng ta cÇn ph¶i söa l¹i nh- sau: old_string[0]=input_bits(); old_string[1]=’\0’; putc(old_string[0], output); while ((new_code=input_bits())!=EOF) { new_string=dictionary_lookup(new_code); if (new_string==NULL) { strcpy(new_string, old_string); append_character_to_string(new_string, new_string[0]); } fputs(new_string, output); append_character_to_string(old_string, new_string[0]); add_to_dictionary(old_string); strcpy(old_string, new_string); } 13 Ch-¬ng tr×nh LZW15: /* LZW15V.C : realization of Lempel-Ziv*/ #include "bitio.c" void usage_exit(char *prog_name); void CompressFile(FILE input, BIT_FILE *output, int argc, char *argv[]); 14 void ExpandFile(BIT_FILE *input, FILE *output, int argc, char *argv[]); unsigned int decode_string(unsigned int count, unsigned int code); unsigned int find_child_node(int parent_code, int child_character); void InitializeStorage(void); void InitializeDictionary(void); char *CompressionName="LZW 15 Bit Variable Rate 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; 15 extension=strrchr(short_name,'.'); if (extension != NULL) *extension='\0'; printf("\nUsage : %s %s \n",short_name,Usage); exit(0); } /*===============================*/ #define BITS 15 #define MAX_CODE ((1<> 8)+1) #define END_OF_STREAM 256 #define BUMP_CODE 257 //M· d¸nh khi nµo th× t¨ng ®é dµi cña tõ m· #define FLUSH_CODE 258 #define FIRST_CODE 259 #define UNUSED -1 16 struct dictionary { int code_value; int parent_code; char character; } *dict[TABLE_BANKS]; #define DICT(i) dict[i>>8][i & 0xff] char decode_stack[TABLE_SIZE]; unsigned int next_code; int current_code_bits; unsigned int next_bump_code; void InitializeDictionary(void) { unsigned int i; for(i=0;iMAX_CODE) { OutputBits(output,(unsignedlong)FLUSH_CODE,current_code_bits); InitializeDictionary(); } else if (next_code > next_bump_code) { OutputBits(output,(unsigned long)BUMP_CODE,current_code_bits); current_code_bits++; next_bump_code <<= 1; next_bump_code |= 1; putc('B',stdout); } } 20 } OutputBits(output,(unsigned long)string_code,current_code_bits); OutputBits(output,(unsigned long)END_OF_STREAM,current_code_bits); while (argc-- >0) printf("Unknown argument :%s\n",*argv++); } /*======================*/ void ExpandFile(BIT_FILE *input,FILE *output,int argc,char *argv[]) { int new_code; int old_code; int character; unsigned int count; InitializeStorage(); while (argc-->0) Thùc hiÖn mét sè lÖnh khëi t¹o printf("Unknown argument:%s",*argv); for(;;) 21
- Xem thêm -