Nen du lieu

8/7/2019 Nen du lieu

http://slidepdf.com/reader/full/nen-du-lieu 1/14

oa n n ng : guy n n

SVTH: Nguyn Hu Hùng Trang 1

MC LC

MC LC .................................................................................................................... 1 MC TIÊU TÀI .................................................................................................... 2 Ý NGHA KHOA HC THC TIN ........................................................................ 3 PHM VI NGHIÊN CU ........................................................................................... 4 LI M U .............................................................................................................. 5

CHNG 1 : MÃ HÓA HUFFMAN.......................................................................... 7

1.1 GII THIU CHUNG V MÃ HÓA HUFFMAN. ...................................... 7

1.2 MÃ TIN T .................................................................................................. 7

CHNG 2 : GII THUT HUFFMAN VÀ ............................................................ 9 XÂY DNG CHNG TRÌNH ................................................................................. 9

2.1 GII THUT HUFFMAN. ............................................................................ 9

2.2 XÂY DNG CHNG TRÌNH .................................................................. 11

2.2.1 Thut toán nén: ...................................................................................... 11

2.2.2 Các vn trong vic xây dng chng trình ...................................... 11

KT LUN VÀ HNG PHÁT TRIN .......................Error! Bookmark not defined. TÀI LIU THAM KHO ......................................................................................... 13



oa n n ng : guy n n


MC TIÊU TÀI

Có khá nhiu k thut nén d liu nh: dùng mã ký hiu, mã óng gói, mã theo dài,

nén d liu vi mô hình ngun, k thut t in«.Trong tài này, chúng ta s nghiên

cu v k thut mã hóa ca Huff man.

hiu rõ h n v k thut này, chúng ta s i tng bc.

Gii thiu chung v mã Huff man.

Tìm hiu thut toán Huff man hiu rõ v cây Huff man và cách to cây.

Xây dng ch ng trình nén d liu dùng mã Huff man.

Gii quyt các vn phát sinh, t thc t rút ra nhng nhn xét v ch ng trình

nén dùng mã Huff man.



oa n n ng : guy n n


Ý NGHA KHOA HC THC TIN

Vài nm trc, cng 40 Mb ã c xem là khá r ng rãi cho c h iu hành,

ch ng trình son tho vn bn, ch ng trình to lp bng tính (k iu Lotus 123) và các

file d liu. Ngày nay, khi mi ch ng trình u cn vài Mb, thm chí hàng chc Mb

b nh thì 40Mb tr nên quá ít i. Chng hn ch r iêng MS-Windows ã cn khong

10Mb, thêm ch ng trình son tho nghiêm chnh - MS Wor d f or Windows chng hn,

li mt khong 8 Mb na.

Cách gii quyt thông th ng khi thiu b nh là b t ra a mm hoc gn thêm

a cng. Nhng còn ph ng pháp khá hiu qu là nén d liu. Vi ch ng trình nén

thích h p, có th s d dàng thm chí t ng - thu gn kích thc ca file. File vn

bn có th nén c tr ên 50%, file bng tính hoc d liu DBF tr ên 70%.

Nhu cu trao i d liu gia mi ng i ngày mt tng, d liu mà chúng ta

mun chia s, trao i ngày mt ln h n, phc tp h n và a dng h n. gii quyt

vn này bài toán nén d liu ã ra i, mc ích ca nó là làm gim kích thc ca

d liu gc nhm giúp cho vic x lý d liu nhanh h n (sao chép, di chuyn, ti lên,

ti xung,«). Có hai ph ng pháp nén d liu là nén d liu có hao ht (lossy

compr ession) và nén bo toàn (lossless compr ession). Thc t thì c hai ph ng pháp

nén u cho ra k t qu t ng t nhau. B i khi nén có hao ht ta th ng tìm nhng d



oa n n ng : guy n n


liu ít cn thit loi b nên bng mt th ng hu nh ta không nhn ra vic hao ht

ó. Thông th ng, hu ht các tp tinh trong máy tính có r t nhiu thông tin d tha,

vic thc hin nén tp tin thc cht là mã hoá li các tp tin loi b các thông tin d

tha.

Nhìn chung không th có ph ng phát nén tng quát nào cho k t qu tt i vi

tt c các loi tp tin vì nu không ta s áp dng n ln ph ng pháp nén này t

c mt tp tin nh tu ý! K thut nén tp tin th ng c áp dng cho các tp tin

vn bn (Trong ó có mt s kí t nào ó có xác sut xut hin nhiu h n các kí t

khác), các tp tin nh bitmap (Mà có th có nhng mng ln ng nht), các tp tin

dùng biu din âm thanh di dng s hoá và các tín hiu t ng t (analog signal)

khác (Các tín hiu này có th có các mu c lp li nhiu ln). Ði vi các tp tin

nh phân nh tp tin ch ng trình thì sau khi nén cng không tit k im c nhiu.

PHM VI NGHIÊN CU

Nghiên cu thut toán Huff man.

Thut toán tng quát.

Cách xây dng cây Huff man.

Ph ng pháp nén dùng thut toán Huff man.

Kim tra thc t và a ra k t lun v ph ng pháp nén này.



oa n n ng : guy n n


LI M U

Trong th i i công ngh thông tin ngày nay, nén d liu là quá trình mã hóa

thông tin dùng ít bit h n so vi thông tin cha c mã hóa bng cách dùng mt hoc

k t h p ca các ph ng pháp nào ó. Da theo nguyên tc này giúp tránh các hin

t ng k ênh tr uyn b quá ti và vic tr uyn tin tr nên k inh t h n .

Nén d liu, n gin, ngôn ng, c i din vi ti thiu là tín hiu k thut

s. vai tr ò ca nó là: nhanh chóng tr uyn tín hiu khác nhau, nh Fax, Modem

tr uyn thông, trong các dòng thông tin liên lc hin có ng th i m thêm các dch v

a ph ng tin, chng hn nh k inh doanh giá tr gia tng; cr unch kh nng lu tr d

liu, chng hn nh CD-ROM, VCD và DVD vv; máy phát in nng thp h n, mà i

vi h thng thông tin di ng a ph ng tin c bit quan tr ng. T th i gian này,

tr uyn thông,, bng thông tr uyn ti, không gian lu tr và nng l ng phát thi thm

chí, có th tr thành i t ng d liu nén.

Nén d liu giúp tit k im các tài nguyên nh dung l ng b nh, bng thông,

th i gian. Ng c li, d liu ã c nén cn phi c gii nén c (thc thi, nghe,

xem v.v«), quá trình này cng òi hi các tài nguyên nht nh.

Nén d liu trc khi tr uyn i cng là mt trong các ph ng pháp nhm tng tc

tr uyn d liu. Trong các modem hin i, vic thc hin nén d liu trc khi tr uyn

i có th c thc hin ngay trong modem theo các giao thc V42bis, MNP5. Ph ng



oa n n ng : guy n n


pháp này òi hi hai modem phi có cùng mt giao thc nén d liu, iu này nhiu

khi khó thoã mãn.

Có mt ph ng pháp khác là thc hin nén các tp tin ngay ti các máy vi tính

trc khi tr uyn i, ti các máy tính nhn, các tp tin li c gii nén phc hi li

dng ban u. Ph ng pháp này có u im là bên phát và bên thu ch cn có chung

phn mm nén và gii nén, ngoài ra còn có th áp dng c tr uyn d liu qua các

modem không h tr nén d liu hoc tr uyn d liu tr c tip qua cng COM ca máy

tính.

Nén c thc hin bng cách s dng thut toán nén (công thc) mà sp xp

li và t chc li d liu thông tin nó có th c lu tr nhiu h n v k inh t. Bng

cách mã hóa thông tin, d liu có th c lu tr bng cách s dng các bit ít h n.Này

c thc hin bng cách s dng mt nén gii nén ch ng trình làm thay i

cu trúc ca các d liu tm th i. Nén làm gim thông tin bng cách s dng nhng

cách khác nhau và hiu qu h n ca i din các thông tin. Các ph ng pháp có th

bao gm n gin loi b các không gian, s dng hai ký t i din cho mt chui

ký t lp i lp li hoc thay th các chui bit ln h n b i nhng cái nh h n. Mt s

thut toán nén i xa nh xóa thông tin hoàn toàn t c kích thc file nhh n. Tùy thuc vào thut toán c s dng, các tp tin có th c y liên quan

n gim kích thc ban u ca h.

tài này nghiên cu v mt thut toán nén k inh in, ó là thut toán nén s

dng k thut mã hóa Huff man. làm rõ tài nay, chúng ta s gii quyt các vn

trong phn ni dung.

Em xin gi l i cm n ti thy giáo Nguyn Vn Th - ng i ã giúp em hoàn

thành án chuyên ngành.

à Nng, tháng 10 nm 2010

SVTH



oa n n ng : guy n n


NGUYN H U HÙNG

CHNG 1 : MÃ HÓA HUFFMAN

1.1 GII THIU CHUNG V MÃ HÓA HUFFMAN.

Thut toán c xut b i David A.Huff man (9/8/1925 ± 7/10/1999), khi ông

còn là sinh viên ti MIT, và công b nm 1952 trong bài báo "A Method f or the

Constr uction of Minimum-Redundancy Codes". Sau này Huff man ã tr thành mt

ging viên MIT và sau ó khoa K hoa hc máy tính ca ai hc Calif or nia, Santa Cr uz, Tr ng K ngh Bask in. Mã Huff man là mt thut toán mã hóa dùng nén d

liu. Nó da tr ên bng tn sut xut hin các kí t cn mã hóa xây dng mt b mã

nh phân cho các kí t ó sao cho dung l ng (s bít) sau khi mã hóa là nh nht.

1.2 MÃ TIN T

- mã hóa các kí hiu (kí t, ch s, ...) ta thay chúng bng các xâu nh phân, c

gi là t mã ca kí hiu ó. Chng hn b mã ASCII, mã hóa cho 256 kí hiu là biu

din nh phân ca các s t 0 n 255, mi t mã gm 8 bít. Trong ASCII t mã ca kí t "a" là 1100001, ca kí t "A" là 1000001. Trong cách mã hóa này các t mã ca tt

c 256 kí hiu có dài bng nhau (mi t mã 8 bít). Nó c gi là mã hóa vi dài

không i.



oa n n ng : guy n n


- K hi mã hóa mt tài liu có th không s dng n tt c 256 kí hiu. H n na trong

tài liu ch cái "a" ch có th xut hin 1000000 ln còn ch cái "A" có th ch xut

hin 2, 3 ln. Nh vy ta có th không cn dùng 8 bít mã hóa cho mt ký hiu,

h n na dài (s bít) dành cho mi kí hiu có th khác nhau, kí hiu nào xut hin

nhiu ln thì nên dùng s bít ít, ký hiu nào xut hin ít thì có th mã hóa bng t mã

dài h n. Nh vy ta có vic mã hóa vi dài thay i. Tuy nhiên, nu mã hóa vi

dài thay i, khi gii mã ta làm th nào phân bit c xâu bít nào là mã hóa ca ký

hiu nào. Mt trong các gii pháp là dùng các du phy (",") hoc mt kí hiu quy c

nào ó tách t mã ca các kí t ng cnh nhau. Nhng nh th s các du phy s

chim mt không gian áng k trong bn mã. Mt cách gii quyt khác dn n khái

nim mã tin t- Mã tin t là b các t mã ca mt tp h p các kí hiu sao cho t mã ca mi ký hiu

không là tin t (phn u) ca t mã mt ký hiu khác trong b mã y.

- ng nhiên mã hóa vi dài không i là mã tin t.

- Ví d: Gi s mã hóa t "LILEE", tp các ký hiu cn mã hóa gm 3 ch cái

"L","I","E".

Nu mã hóa bng các t mã có dài bng nhau ta dùng ít nht 2 bit cho mt

ch cái chng hn "L"=00, "E"=01, "I"=10. K hi ó mã hóa ca c t là 0010000101. gii mã ta c hai bit mt và i chiu vi bng mã.

Nu mã hóa "L"=0, "E"=01, "I"=11 thì b t mã này không là mã tin t ví t

mã ca "A" là tin t ca t mã ca "R". mã hóa c t LILEE phi t du ngn

cách vào gia các t mã 0.11.0.01.01

Nu mã hóa "L"=0, "E"=10, "I"=11 thì b mã này là mã tin t. Vi b mã tin

t này khi mã hóa xâu "LILEE" ta có 01101010.

Hoc

Ví d, mun mã hóa t "PETE", vi 3 ký t ³E´, ³P´, ³T´. Ta có:

- Nu mã hóa bng các t mã có dài bng nhau, ta dùng ít nht 2 bit cho mt ký t.

Chng hn ³E´=00, ³P´=01, ³T´=10. K hi ó mã hóa ca c t là 0001010010.





oa n n ng : guy n n


Ð gii mã thông ip này, ch n gin là c ra 5 bits tng th i im và

chuyn i nó t ng ng vi vic mã hoá nh phân ã c nh ngha tr ên. Trong

mã chun này, ch D xut hin ch mt ln s cn s l ng bit ging ch A xut hin

nhiu ln.

Ta có th gán các chui bit ngn nht cho các kí t c dùng ph bin nht, gi

s ta gán: A là 0, B là 1, R là 01, C là 10 và D là 11 thì chui tr ên c biu din nh

sau:

0 1 01 0 10 0 11 0 1 01 0

Ví d này ch dùng 15 bits so vi 55 bits nh tr ên, nhng nó không thc s là

mt mã vì phi l thuc vào khong tr ng phân cách các kí t. Nu không có du

phân cách thì ta không th gii mã c thông ip này. Ta cng có th chn các t mã sao cho thông ip có th c gii mã mà không cn du phân cách, ví d nh: A là

11, B là 00, C là 010, D là 10 và R là 011, các t mã này gi là các t mã có tính pr efix

(K hông có t mã nào là tin t ca t mã khác). Vi các t mã này ta có th mã hoá

thông ip tr ên nh sau:

1100011110101110110001111

Vi chui ã mã hoá này ta hoàn toàn có th gii mã c mà không cn du

phân cách. Nhng bng cách nào tìm ra bng mã mt cách tt nht? Vào nm 1952,D.Huff man ã phát minh ra mt cách tng quát tìm ra bng mã này mt cách tt

nht.

- Bc u tiên trong vic xây dng mã Huff man là m s ln xut hin ca mi kí t

trong tp tin s c mã hoá.

- Bc tip theo là xây dng mt cây nh phân vi các tn s c cha trong các nút.

Hai nút có tn s bé nht c tìm thy và mt nút mi c to ra vi hai nút con là

các nút ó vi giá tr tn s ca nút mi bng tng tn sut ca hai nút con. Tip theo

hai nút mi vi tn s nh nht li c tìm thy và mt nút mi na li c to ra

theo cách tr ên. Lp li nh vy cho n khi tt c các nút c t h p thành mt cây

duy nht.



oa n n ng : guy n n


- Sau khi có cây nh phân, bng mã Huff man c phát sinh bng cách thay th các tn

s nút áy bng các kí t t ng ng.

2.2 XÂY DNG CHNG TRÌNH

Thut toán này vn da tr ên ý t ng ca Huff man là s dng mt vài bit (bit

code) biu din mt kí t.

dài ³mã bit´ cho các kí t không ging nhau:

K í t xut hin nhiu lnbiu din bng mã ngn.

K í t xut hin ít biu din bng mã dài.

To sn mt cây ³ti thiu´ ban u, d liu nén s c cp nht dn vào cây.

2.2.1 Thut toán nén:

Bc 1: Tìm hai ký t có tr ng s nh nht ghép li thành mt, tr ng s ca ký t

mi bng tng tr ng s ca hai ký t em ghép.

Bc 2: Trong khi s l ng ký t trong danh sách còn ln h n mt thì thc hin

bc mt, nu không thì thc hin bc ba.

Bc 3: Tách ký t cui cùng và to cây nh phân vi quy c bên trái mã 0, bênphi mã 1.

2.2.2 Các vn trong vic xây dng chng trình

2.2.2.1 Các cu trúc d liu s dng trong chng trình:

typedef str uct node



oa n n ng : guy n n


{ char Data ;// K í t alpha

int TSuat ;// Tn sut kí t alpha

node * Lef t ;// Con tr trái

node * Right ;// Con tr phi

};

typedef node * HTr ee ;

str uct list

{ char alpha ;// K í t alpha

int ts ;// Tn sut

char code[max] ;// Mng lu tr mã nh phân

};- Kiu d liu ca mng node[] dùng cài t cây Huff man. Các node t ng ng

vi ký t (node.alph nu có). node.Lef t, node.Right, t ng ng là ch s ca nút

con trái, con phi, Node.TSuat cha tng tn s các nút lá thuc nhánh ca nó.

2.2.2.2 Lp b ký t (a[i].alph) và tn s tng ng (a[i].ts) t mt xâu ký t

(s):

- c ký tu tiên ca xâu cho vào a[0].alpha t ng ng là a[0].ts bng 1.

- Duyt tng ký t còn li ca xâu, nu gp ký t nào ã có trong mng a[i].alph thì tng a[i].ts lên 1, nu cha có ký tó thì thêm phn t mi vào mng và cho

tn s t ng ng bng 1.

2.2.2.3 C ài t cây Huffman và tn s (cha trong mng a[]).

- Sp xp li các a .

- K h i to các node, node.alph và node.TSuat t ng ng vi a.alph và a.ts sau khi

ã sp xp. Các thành phn còn li có giá tr là NULL (cha xác nh).

- To cây Huff man bng cách chèn thêm nút mi ng th i sp xp li theo th t tn

s tng dn.

2.2.2.4 Mã hóa:

- c tng ký t ca chui (hoc file), gp phn t nào thì hin th xâu mã hóa t ng

ng hoc ghi thêm xâu mã hóa t ng ng ca ký t ó vào file ã mã hóa (fileout).



oa n n ng : guy n n


2.2.2.5 Gii mã:

- Duyt cây Huff man t tr ên xung, gp 0 thì nhy xung con trái, gp 1 thì nhy

xung con phi, cho ti khi gp node có thành phn alph khác NULL.

- Nu gp node có thành phn alph khác NULL thì hin th ký t ca node ó và nhy

v gc

HÌNH 3.1 : Lu thut toán

TÀI LIU THAM KHO



oa n n ng : guy n n


[1] http://vi.wik ipedia.or g

[2] http://dhti.tk

[3] http://my.opera.com

[4] http://www.data-compr ession.com

Documents

Nen du lieu