Thuật toán nén LZW

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” . 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. 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 0 a 1 b B­íc 1 aabababaaababb thay a®0 ®­îc 0abababaaababb tõ ®iÓn ®o¹n copy míi aabababaaababb 0 a 1 b 2 aa 0+a B­íc 2 aabababaaababb thay a®0 ®­îc 00bababaaababb tõ ®iÓn 0 a 1 b 2 aa 0+a 3 ab 0+b ®o¹n copy míi aabababaaababb B­íc 3 00bababaaababb thay b®1 ®­îc 001ababaaababb tõ ®iÓn 0 a 1 b 2 aa 0+a 3 ab 0+b 4 ba 1+a 5 aba 3+a ®o¹n copy míi aabababaaababb B­íc 4 001ababaaababb thay ab®3 ®­îc 0013abaaababb tõ ®iÓn ®o¹n copy míi aabababaaababb aabababaaababb 0 a 1 b 2 aa 0+a 3 ab 0+b 4 ba 1+a 5 aba 3+a 6 abaa 5+a B­íc 5 0013abaaababb thay aba®5 ®­îc 00135aababb tõ ®iÓn ®o¹n copy míi aabababaaababb 0 a 1 b 2 aa 0+a 3 ab 0+b 4 ba 1+a 5 aba 3+a 6 abaa 5+a 7 aab 2+b B­íc 6 00135aababb thay aa®2 ®­îc 001352babb tõ ®iÓn ®o¹n copy míi aabababaaababb 0 a 1 b 2 aa 0+a 3 ab 0+b 4 ba 1+a 5 aba 3+a 6 abaa 5+a 7 aab 2+b 8 bab 4+b B­íc 7 001352babb thay ba®4 ®­îc 0013524bb 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Î. 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. 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); b¾t ®Çu mét x©u míi b»ng ký tù võa ®äc vµo. Pseudocode nÐn cña LZW: 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). 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);} 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); 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: “ WEDEBT” 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 ‘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· . B©y giê chóng ta h·y theo dâi qu¸ tr×nh gi¶i nÐn. Sau khi thay 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); } 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[]); 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; 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<<BITS)-1) #define TABLE_SIZE 35023L #define TABLE_BANKS ((TABLE_SIZE >> 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 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;i<TABLE_SIZE;i++) DICT(i).code_value=UNUSED; next_code=FIRST_CODE; putc('F',stdout); //B¸o hiÖu khëi ®Çu hay khëi ®Çu l¹i tõ ®iÓn. current_code_bits=9; //M· hiÖn t¹i. next_bump_code=511; } /*===============================*/ void InitializeStorage(void) //Thñ tôc cÊp ph¸t bé nhí. { int i; for(i=0;i<TABLE_BANKS;i++) { dict[i]=(struct dictionary *) calloc(256,sizeof(struct dictionary)); if (dict[i]==NULL) fatal_error("Error allocating dictionary space"); } } /*==============================*/ void CompressFile(FILE *input,BIT_FILE *output,int argc,char *argv[]) { int character; int string_code; unsigned int index; InitializeStorage(); InitializeDictionary(); //ký tù ®Çu tiªn ®­îc ®äc vµo. if ((string_code=getc(input))==EOF) string_code=END_OF_STREAM; while((character=getc(input))!=EOF) //B¾t ®Çu vßng lÆp. { index=find_child_node(string_code,character); if(DICT(index).code_value!=-1) string_code=DICT(index).code_value; else { T¹o thªm 1 ®Ønh øng víi phrase míi trong tõ ®iÓn vµ g¸n c¸c gi¸ trÞ cÇn thiÕt. Ghi string_code võa t×m ®­îc ra tÖp vµ b¾t ®Çu viÖc t×m míi PhÇn xö lý khëi ®Çu l¹i tõ ®iÓn. PhÇn thay ®æi ®é dµi tõ m· DICT(index).code_value=next_code++; DICT(index).parent_code=string_code; DICT(index).character=(char)character; OutputBits(output,(unsigned long)string_code,current_code_bits); string_code=character; if(next_code >MAX_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); } } } 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; Thùc hiÖn mét sè lÖnh khëi t¹o InitializeStorage(); while (argc-->0) printf("Unknown argument:%s",*argv); for(;;) { InitializeDictionary(); old_code=(unsigned int)InputBits(input,current_code_bits); if (old_code==END_OF_STREAM) return; character=old_code; putc(old_code,output); for(;;) { new_code=(unsigned int)InputBits(input,current_code_bits); if (new_code==END_OF_STREAM) return; //NÕu (new_code==END_OF_STREAM) th× gäi intializeDictionnary() ®Ó g¸n l¹i tõ ®iÓn. if (new_code==FLUSH_CODE) break; if (new_code==BUMP_CODE) //NÕu (new_code==BUMP_CODE) th×®é dµi tõ m· ®­îc t¨ng b»ng lÖnh: current_code_bits++ { current_code_bits++; putc('B',stdout); continue; } //NÕu gÆp ph¶i m· ch­a xuÊt hiÖn trong tõ ®iÓn th× xö lý nh­ sau: if (new_code >= next_code) { decode_stack[0]=(char)character; //Trong tr­êng hîp cßn l¹i chóng ta gäi code_string() ®Ó xö lý. 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); DICT(next_code).parent_code=old_code; DICT(next_code).character=(char)character; next_code++; old_code=new_code; } } } /*==============================*/ unsigned int find_child_node(int parent_code,int child_character) { unsigned int index; int offset; index=(child_character << (BITS-8)) ^ parent_code; if (index==0) offset=1; else offset=TABLE_SIZE-index; for (;;) { if (DICT(index).code_value==UNUSED) return((unsigned int)index); if (DICT(index).parent_code==parent_code && DICT(index).character==(char)child_character) return(index); if (index >= offset) index-=offset; else index+=TABLE_SIZE-offset; } } /*=========================================*/ unsigned int decode_string(unsigned int count,unsigned int code) //Thñ tôc tr¶ l¹i sè ký tù cña phrase. { while(code>255) { decode_stack[count++]=DICT(code).character; code=DICT(code).parent_code; } decode_stack[count++]=(char)code; return(count); } /*===================*/ Chóng ta t¨ng kÝch th­íc cña tõ ®iÓn lªn tíi 15 bit. Nh­ng kh«ng ph¶i mäi code ®Òu dïng15 bit ®Ó m·. Chóng ta sö dông 9 bit cho 512 phrase ®Çu (tõ 0 ®Õn 511), 10 bit cho c¸c phrase tõ 512 ®Õn 1023, vµ cø thÕ tiÕp tôc. Nh­ vËy cÇn thªm mét ký tù ®Æc biÖt lµ BUMP_CODE ®Ó ®¸nh dÊu khi nµo th× t¨ng ®é dµi cña tõ m·. BiÕn unsigned int next_bump_code ®­îc sö dông ®Ó theo dâi viÖc nµy. §é dµi tõ code ë biÕn current_code_bits. Mét c¶i tiÕn thø hai chóng ta ®­a vµo ®Ó xö lý khi tõ ®iÓn ®· lín hÕt cì. Trong tr­êng hîp nµy chóng ta cho ra mét ký tù ®Æc biÖt lµ FLUSH_CODE. Khi ®ã sÏ x©y dùng tõ ®iÓn l¹i tõ ®Çu. Trong ch­¬ng tr×nh nµy, chóng ta chia tõ ®iÓn ra TABLE_BANKS kho¶ng, mçi kho¶ng cã 256 phrase vµ sö dông macro #define DICT(i) dict[i>>8][i & 0xff] ®Ó xö lý index. Thñ tôc void InitializeDictionary(void) gåm c¸c lÖnh: for(i=0;i<TABLE_SIZE;i++) DICT(i).code_value=UNUSED; next_code=FIRST_CODE; putc('F',stdout); // b¸o hiÖu khëi ®Çu hay khëi ®Çu l¹i tõ ®iÓn current_code_bits=9; next_bump_code=511; Thñ tôc void InitializeStorage(void) ®Ó cÊp ph¸t bé nhí: for(i=0;i<TABLE_BANKS;i++) { dict[i]=(struct dictionary *) calloc(256,sizeof(struct dictionary)); if (dict[i]==NULL) fatal_error("Error allocating dictionary space"); } Thñ tôc void CompressFile(FILE *input,BIT_FILE *output,int argc,char *argv[]) gièng nh­ ë ch­¬ng tr×nh LZW12, nh­ng cã thªm phÇn xö lý khëi ®Çu l¹i tõ ®iÓn: if(n ext_code >MAX_CODE) { OutputBits(output,(unsigned long)FLUSH_CODE,current_code_bits); InitializeDictionary(); } vµ phÇn thay ®æi ®é dµi tõ m·: 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); } Thñ tôc void ExpandFile(BIT_FILE *input,FILE *output,int argc,char *argv[]) gièng nh­ trong ch­¬ng tr×nh LZW12 nh­ng còng cã 2 thay ®æi. NÕu (new_code == FLUSH_CODE) th× sÏ gäi InitializeDictionary() ®Ó g¸n l¹i tõ ®iÓn. Thø hai lµ nÕu (new_ code == BUMP_CODE) th× ®é dµi tõ m· ®­îc t¨ng lªn b»ng lÖnh current_code_bits++. C¸c thñ tôc unsigned int find_child_node(int parent_code,int child_character) vµ unsigned int decode_string(unsigned int count,unsigned int code) gièng nh­ ë LZW12. while(code>255) { decode_stack[count++]=dict[code].character; code=dict[code].parent_code; } decode_stack[count++]=(char)code; return(count); S¬ ®å phô thuéc cña c¸c thñ tôc trong LZW15 CompressFile InitializeDictionary decoding_string ExpandFile InitializeStorage find_child_node VÝ dô tr×nh nÐn Lzw /* Tcc –mh LZW15VCO.C */ /* LZW15VCO.C: to compress file by Lempel-Ziv-Welch 15 bit*/ #include "lzw15v.c" int main(int argc,char *argv[]) { BIT_FILE *output; FILE *input; setbuf(stdout,NULL); if (argc < 3) usage_exit(argv[0]); input=fopen(argv[1],"rb"); if (input==NULL) fatal_error("Error opening %s for input\n",argv[1]); output=OpenOutputBitFile(argv[2]); if (output==NULL) fatal_error("Error opening %s for output\n",argv[2]); printf("\nCompressing %s to %s\n",argv[1],argv[2]); printf("Using %s\n",CompressionName); argc-=3; argv+=3; CompressFile(input,output,argc,argv); CloseOutputBitFile(output); fclose(input); argv-=3; print_ratios(argv[1],argv[2]); return(0); } VÝ dô tr×nh tëi nÐn Lzw /* Tcc –mh LZW15VEX.C */ /*LZW15VEX.C */ #include "lzw15v.c" int main(int argc,char *argv[]) { FILE *output; BIT_FILE *input; setbuf(stdout,NULL); if (argc < 3) usage_exit(argv[0]); input=OpenInputBitFile(argv[1]); if (input==NULL) fatal_error("Error opening %s for input\n",argv[1]); output=fopen(argv[2],"wb"); if (output==NULL) fatal_error("Error opening %s for output\n",argv[2]); printf("\nExpanding %s to %s\n",argv[1],argv[2]); printf("Using %s\n",CompressionName); argc-=3; argv+=3; ExpandFile(input,output,argc,argv); CloseInputBitFile(input); fclose(output); putc('\n',stdout); return(0); }