Website: http://www.docs.vn Email :
[email protected] 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 a0
®-îc 0abababaaababb tõ ®iÓn
®o¹n copy míi aabababaaababb
B-íc 2 aabababaaababb
thay a0
®-îc 00bababaaababb
tõ ®iÓn
®o¹n copy míi aabababaaababb
B-íc 3 00bababaaababb
thay b1
®-îc 001ababaaababb
tõ ®iÓn
®o¹n copy míi aabababaaababb
B-íc 4 001ababaaababb
thay ab3
5
®-îc 0013abaaababb
tõ ®iÓn
®o¹n copy míi aabababaaababb
aabababaaababb
B-íc 5 0013abaaababb
thay aba5
®-î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 aa2
®-î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 ba4
®-î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× cha
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
.PDF 
31 
80 
79 
