http://www.ebook.edu.vn
Chu
.o
.ng 4
Cˆ
AY
4.1 Mo
.
˙’ d¯ˆa
`u
Cˆay l`a mˆo
.t trong nh˜u
.ng kh´ai niˆe
.m quan tro
.ng nhˆa
´t cu
˙’a l´y thuyˆe
´t d¯ˆo
`thi
., v`a thu
.`o
.ng xuˆa
´t
hiˆe
.n trong nh˜u
.ng l˜anh vu
.
.c ´ıt c´o liˆen quan d¯ˆe
´n d¯ˆo
`thi
..
Trong chu
.o.ng n`ay, tru
.´o
.c hˆe
´t s˜e nghiˆen c´u
.ucˆay Huffman v`a nh˜u
.ng ´u
.ng du
.ng cu
˙’a n´o
trong viˆe
.c n´en d˜u
.liˆe
.u. Kˆe
´tiˆe
´p ch´ung ta x´et tr`ınh b`ay c´ac thuˆa
.t to´an t`ım cˆay bao tr`um, cˆay
bao tr`um c´o tro
.ng lu
.o.
.ng nho
˙’ nhˆa
´t khi c´ac ca
.nh cu
˙’a d¯ˆo
`thi
.d¯u
.o.
.c gˇa
´n v´o.i c´ac chi ph´ı (tro
.ng
lu
.o.
.ng). Cˆay bao tr`um nho
˙’ nhˆa
´t cu
˙’a d¯ˆo
`thi
.c´o nhiˆe
`u ´u
.ng du
.ng trong nh˜u
.ng tru
.`o
.ng ho.
.p c´ac
d¯u
.`o
.ng dˆa
˜n (ˆo
´ng dˆa
˜n ga, dˆay dˆa
˜n trong ma
.ng d¯iˆe
.n, v.v) d¯u
.o.
.c su
.
˙’ du
.ng d¯ˆe
˙’ nˆo
´ind¯iˆe
˙’m v´o
.i
nhau theo c´ach tˆo
´t nhˆa
´t: tˆo
˙’ng khoa
˙’ng c´ach cu
˙’a c´ac d¯u
.`o
.ng dˆa
˜n l`a nho
˙’ nhˆa
´t. Nˆe
´und¯iˆe
˙’m
d¯u
.o.
.c nˆo
´i v´o
.i nhau trˆen mˆo
.t mˇa
.t phˇa
˙’ng, ta c´o thˆe
˙’ biˆe
˙’u diˆe
˜n bo.
˙’ i mˆo
.t d¯ˆo
`thi
.d¯ˆa
`y d¯u
˙’ trong d¯´o
c´ac chi ph´ı ca
.nh l`a khoa
˙’ng c´ach gi˜u
.a hai d¯iˆe
˙’m tu
.o.ng ´u
.ng. Khi d¯´o cˆay bao tr`um v´o
.i tro
.ng
lu
.o.
.ng nho
˙’ nhˆa
´t s˜e cho ma
.ng giao thˆong v´o
.i chi ph´ı ´ıt nhˆa
´t. Nˆe
´u c´o thˆe
˙’ nˆo
´i thˆem ngo`ai n
d¯iˆe
˙’m cho ph´ep, ta c´o thˆe
˙’ thˆa
.m ch´ı xˆay du
.
.ng d¯u
.o
.
.c ma
.ng v´o
.i ch´ı ph´ı re
˙’ ho.n v`a x´ac d¯i
.nh n´o
ch´ınh l`a gia
˙’i quyˆe
´t b`ai to´an Steiner. B`ai to´an sau n`ay s˜e d¯u
.o.
.c d¯ˆe
`cˆa
.p o.
˙’ phˆa
`n cuˆo
´i chu
.o.ng.
D
-i
.nh ngh˜ıa 4.1.1 C´ac d¯i
.nh ngh˜ıa sau cu
˙’acˆay (vˆo hu
.´o
.ng) l`a tu
.o.ng d¯u
.o.ng:
1. D
-ˆo
`thi
.liˆen thˆong c´o nd¯ı
˙’nh v`a (n−1) ca
.nh.
2. D
-ˆo
`thi
.liˆen thˆong khˆong c´o chu tr`ınh.
3. D
-ˆo
`thi
.m`a mo
.i cˇa
.p d¯ı
˙’nh d¯u
.o.
.c nˆo
´i v´o
.i nhau bo.
˙’ i mˆo
.t v`a chı
˙’ mˆo
.t dˆay chuyˆe
`n so.cˆa
´p.
4. D
-ˆo
`thi
.liˆen thˆong v`a khi b´o
.t mˆo
.t ca
.nh bˆa
´t k`y th`ı mˆa
´t t´ınh liˆen thˆong.
99
http://www.ebook.edu.vn
H`ınh 4.1 minh ho
.a cˆay c´o ba
˙’y d¯ı
˙’nh v`a s´au ca
.nh.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
v1
v2
v3
v4
v5
v6
v7
•
•
•
•
••
•
H`ınh 4.1: Mˆo
.t v´ı du
.vˆe
`cˆay.
Kh´ai niˆe
.m vˆe
`cˆay nhu
.mˆo
.t thu
.
.c thˆe
˙’ cu
˙’a to´an ho
.c d¯u
.o.
.c d¯u
.a ra lˆa
`n d¯ˆa
`u tiˆen bo.
˙’ i
Kirchhoff [37] khi liˆen hˆe
.v´o
.i d¯i
.nh ngh˜ıa c´ac ma
.ch co.ba
˙’n d¯u
.o.
.c su
.
˙’ du
.ng trong phˆan t´ıch c´ac
ma
.ng d¯iˆe
.n. Khoa
˙’ng 10 nˇam sau d¯´o, mˆo
.t c´ach d¯ˆo
.c lˆa
.p, Cayley [11] d¯˜a ph´at hiˆe
.n la
.i c´ac cˆay
v`a nh˜u
.ng t´ıch chˆa
´t cu
˙’a n´o khi nghiˆen c´u
.u c´ac t´ınh chˆa
´t ho´a ho
.c cu
˙’a c´ac chˆa
´t d¯ˆo
`ng phˆan
cu
˙’a hydrocarbon.
Cˆay c´o gˆo
´c(c`on go
.i l`a cˆay gia pha
˙’) d¯u
.o.
.c d¯i
.nh ngh˜ıa tu
.o.ng tu
.
.nhu
.sau:
D
-i
.nh ngh˜ıa 4.1.2 Cˆay c´o gˆo
´cTl`a d¯ˆo
`thi
.c´o hu
.´o
.ng khˆong ma
.ch m`a mo
.i d¯ı
˙’nh, ngoa
.i tr`u
.
mˆo
.t d¯ı
˙’nh (chˇa
˙’ng ha
.nv1),c´o bˆa
.c trong bˇa
`ng mˆo
.t: bˆa
.c trong cu
˙’a d¯ı
˙’nh v1(go
.i l`a gˆo
´ccu
˙’a cˆay)
bˇa
`ng khˆong; n´oi c´ach kh´ac, mo
.i d¯ı
˙’nh v∈Ttˆo
`n ta
.i duy nhˆa
´t mˆo
.t d¯u
.`o
.ng d¯i t`u
.gˆo
´c d¯ˆe
´nv.
H`ınh 4.2 minh ho
.a mˆo
.t d¯ˆo
`thi
.l`a cˆay c´o gˆo
´c v´o
.i d¯ı
˙’nh v1l`a gˆo
´c. T`u
.d¯i
.nh ngh˜ıa suy ra
rˇa
`ng cˆay c´o gˆo
´cnd¯ı
˙’nh c´o (n−1) cung v`a l`a d¯ˆo
`thi
.liˆen thˆong (khi bo
˙’ qua hu
.´o
.ng trˆen c´ac
cung).
Cˆa
`n ch´u ´y rˇa
`ng, c´o thˆe
˙’ d¯i
.nh hu
.´o
.ng trˆen mˆo
.t cˆay (vˆo hu
.´o
.ng) sao cho d¯ˆo
`thi
.thu d¯u
.o.
.c
l`a cˆay c´o gˆo
´c: Ta chı
˙’ cˆa
`n cho
.n mˆo
.t d¯ı
˙’nh tu`y ´y, chˇa
˙’ng ha
.nv1,l`am gˆo
´c v`a d¯i
.nh hu
.´o
.ng c´ac
cung theo dˆay chuyˆe
`n t`u
.v1d¯ˆe
´n c´ac d¯ı
˙’nh treo. Ngu
.o.
.c la
.i, nˆe
´u bo
˙’ qua c´ac hu
.´o
.ng trˆen cˆay
c´o gˆo
´c ta thu d¯u
.o.
.c mˆo
.t cˆay.
Cˆay gia pha
˙’ m`a trong d¯´o mˆo
˜i ngu
.`o
.i d¯`an ˆong biˆe
˙’u thi
.mˆo
.t d¯ı
˙’nh v`a c´ac cung d¯u
.o
.
.c v˜e
t`u
.c´ac cha d¯ˆe
´n c´ac con cu
˙’a ho
.l`a mˆo
.t v´ı du
.quen thuˆo
.c cu
˙’a cˆay c´o gˆo
´c, gˆo
´c cu
˙’a cˆay l`a ngu
.`o
.i
d¯ˆa
`u tiˆen trong d`ong ho
.m`a c´o thˆe
˙’ x´ac d¯i
.nh d¯u
.o.
.c.
100
http://www.ebook.edu.vn
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
v1
v2v3
v4v5
v6
v7
v8
v9
v10
v11
v12 v13
•
• •
• • • •
• •
• •
• •
H`ınh 4.2: Mˆo
.t v´ı du
.vˆe
`cˆay c´o gˆo
´c.
4.2 Cˆay Huffman
Tiˆe
´n tr`ınh g´an d˜ay c´ac bit cho c´ac k´y hiˆe
.u go
.i l`a m˜a ho´a. Trong phˆa
`n n`ay ch´ung ta mˆo
.t ta
˙’
mˆo
.t thuˆa
.t to´an m˜a ho´a rˆa
´t quen thuˆo
.c-thuˆa
.t to´an m˜a ho´a Huffman.
4.2.1 C´ac bˆo
.m˜a “tˆo
´t”
Khi ta n´oi vˆe
`m˜a ho´a c´o ngh˜ıa l`a g´an d˜ay c´ac bit cho c´ac phˆa
`n tu
.
˙’ cu
˙’a mˆo
.t ba
˙’ng ch˜u
.c´ai.
Tˆa
.p c´ac chuˆo
˜i nhi
.phˆan go
.i l`a bˆo
.m˜a v`a c´ac phˆa
`n tu
.
˙’ cu
˙’a ch´ung go
.i l`a t`u
.m˜a. Mˆo
.t ba
˙’ng
ch˜u
.c´ai l`a mˆo
.t tˆa
.p ho.
.p c´ac k´y hiˆe
.u, go
.i l`a c´ac k´y tu
.
.. Chˇa
˙’ng ha
.n, ba
˙’ng ch˜u
.c´ai su
.
˙’ du
.ng
trong hˆa
`u hˆe
´t c´ac s´ach (tiˆe
´ng Anh) gˆo
`m 26 k´y tu
.
.thu
.`o
.ng, 26 k´y tu
.
.hoa, v`a c´ac dˆa
´u ngˇa
´t cˆau
(nhu
.dˆa
´u phˆa
˙’y). M˜a ASCII (viˆe
´t tˇa
´t cu
˙’a c´ac ch˜u
.c´ai d¯ˆa
`u tiˆen cu
˙’a chuˆo
˜i American Standard
Code for Information Interchange cu
˙’a k´y tu
.
.Al`a 01000001,cu
˙’a k´y tu
.
.al`a 01100001 v`a k´y
tu
.
., l`a 0011010. Ch´u ´y rˇa
`ng trong m˜a ASCII sˆo
´c´ac bit su
.
˙’ du
.ng d¯ˆe
˙’ biˆe
˙’u diˆe
˜n c´ac k´y tu
.
.l`a
bˇa
`ng nhau. M˜a nhu
.vˆa
.y go
.i l`a m˜a c´o d¯ˆo
.d`ai cˆo
´d¯i
.nh. Nˆe
´u ta muˆo
´n gia
˙’m sˆo
´c´ac bit d¯`oi ho
˙’i
d¯ˆe
˙’ biˆe
˙’u diˆe
˜n c´ac thˆong b´ao kh´ac nhau, ta cˆa
`n c´ac chuˆo
˜i bit biˆe
˙’u diˆe
˜n k´y tu
.
.c´o d¯ˆo
.d`ai (n´oi
chung) khˆong bˇa
`ng nhau. Nˆe
´u biˆe
˙’u diˆe
˜n c´ac bit d`ai ho.n cho c´ac k´y tu
.
.thu
.`o
.ng xuyˆen xuˆa
´t
hiˆe
.n v`a ngu
.o.
.c la
.i, ch´ung ta c´o thˆe
˙’, vˆe
`trung b`ınh, gia
˙’m sˆo
´bit biˆe
˙’u diˆe
˜n c´ac k´y hiˆe
.u. Chˇa
˙’ng
ha
.n, m˜a Morse [31] su
.
˙’ du
.ng c´ac t`u
.m˜a ngˇa
´n ho.n cho c´ac k´y tu
.
.xuˆa
´t hiˆe
.n thu
.`o
.ng xuyˆen:
m˜a cu
˙’a cu
˙’aal`a ·−,cu
˙’ael`a ·,trong khi cu
˙’azl`a − − · · · · , q l`a − − ·−, j l`a · − − − .
Tuy nhiˆen d¯ˆo
.d`ai trung b`ınh cu
˙’a m˜a khˆong pha
˙’i l`a tiˆeu chuˆa
˙’n quan tro
.ng khi thiˆe
´t kˆe
´
101
http://www.ebook.edu.vn
mˆo
.t bˆo
.m˜a “tˆo
´t”. X´et v´ı du
.sau. Gia
˙’ su
.
˙’ ba
˙’ng ch˜u
.c´ai gˆo
`m bˆo
´n k´y tu
.
.a1, a2, a3, a4v´o
.i c´ac
x´ac suˆa
´t xuˆa
´t hiˆe
.n tu
.o.ng ´u
.ng l`a P(a1) = 1
2, P (a2) = 1
4, P (a3) = 1
8, P (a4) = 1
8.Entropy cu
˙’a
m˜a nguˆo
`n n`ay l`a 1.75 bit/k´y hiˆe
.u (xem [31] d¯ˆe
˙’ c´o kh´ai niˆe
.m vˆe
`entropy). X´et c´ac bˆo
.m˜a
trong nguˆo
`n n`ay cho bo.
˙’ i ba
˙’ng sau
C´ac k´y tu
.
.M˜a C1M˜a C2M˜a C3M˜a C4
a11 1 1 1
a21 0 01 10
a30 11 001 100
a401 00 000 1000
D
-ˆo
.d`ai trung b`ınh 1.125 1.125 1.75 1.875
D
-ˆo
.d`ai trung b`ınh lcu
˙’a mˆo
˜i m˜a x´ac d¯i
.nh bo.
˙’ i
l=
4
X
i=1
P(ai)n(ai) (bit/k´y hiˆe
.u),
trong d¯´o n(ai) l`a sˆo
´c´ac bit cu
˙’a t`u
.m˜a ai.
Du
.
.a trˆen d¯ˆo
.d`ai trung b`ınh, m˜a C1l`a tˆo
´t nhˆa
´t. Tuy nhiˆen, c´ac m˜a cˆa
`n pha
˙’i c´o kha
˙’
nˇang truyˆe
`n thˆong tin sao cho ngu
.`o
.i nhˆa
.n c´o thˆe
˙’ hiˆe
˙’u d¯u
.o.
.c r˜o r`ang. Hiˆe
˙’n nhiˆen m˜a C1
khˆong c´o t´ınh chˆa
´t n`ay: V`ı ca
˙’ hai k´y hiˆe
.ua1v`a a2d¯ˆe
`u d¯u
.o.
.c g´an l`a 1 nˆen khi nhˆa
.n d¯u
.o.
.c
thˆong tin l`a 1, ngu
.`o
.i nhˆa
.n khˆong thˆe
˙’ phˆan biˆe
.t d¯´o l`a k´y hiˆe
.ua1hay a2.Ch´ung ta muˆo
´n
mˆo
˜i k´y hiˆe
.u d¯u
.o.
.c g´an duy nhˆa
´t mˆo
.t t`u
.m˜a.
M˜a C2c´o c´ac k´y tu
.
.d¯u
.o.
.c g´an c´ac chuˆo
˜i bit kh´ac nhau cho c´ac k´y tu
.
.. Tuy nhiˆen, gia
˙’
su
.
˙’ m˜a ho´a d˜ay a2a1a1d¯u
.o.
.c 011 v`a gu
.
˙’ i d¯i chuˆo
˜i bit n`ay. Ngu
.`o
.i nhˆa
.n chuˆo
˜i 011 c´o mˆo
.t sˆo
´
c´ach gia
˙’i m˜a: a2a1a1hoˇa
.ca2a3.D
-iˆe
`u n`ay c´o ngh˜ıa l`a mˆo
.t d˜ay d¯u
.o.
.c m˜a ho´a v´o
.i bˆo
.m˜a C2
th`ı d˜ay n`ay c´o thˆe
˙’ d¯u
.o.
.c gia
˙’i m˜a khˆong tr`ung v´o
.i thˆong b´ao ban d¯ˆa
`u. N´oi chung, d¯ˆay khˆong
pha
˙’i l`a d¯iˆe
`u ch´ung ta mong muˆo
´n khi thiˆe
´t kˆe
´c´ac bˆo
.m˜a. Ch´ung ta muˆo
´n c´o t´ınh chˆa
´tgia
˙’i
m˜a duy nhˆa
´t; t´u
.c l`a mo
.i d˜ay c´ac t`u
.m˜a chı
˙’ c´o duy nhˆa
´t mˆo
.t c´ach gia
˙’i m˜a. C´o thˆe
˙’ ch´u
.ng
minh c´ac m˜a C3v`a C4thoa
˙’ m˜an t´ınh chˆa
´t n`ay.
Mˇa
.c d`u viˆe
.c kiˆe
˙’m tra t´ınh duy nhˆa
´t khi gia
˙’i m˜a l`a kh´o, ta c´o thˆe
˙’ ch´u
.ng minh t´ınh
chˆa
´t n`ay cho bˆo
.m˜a C3du
.
.a trˆen thuˆo
.c t´ınh cu
˙’a bˆo
.m˜a: khˆong c´o t`u
.m˜a n`ao trong m˜a C3
l`a “tiˆe
`n tˆo
´” cu
˙’a t`u
.m˜a kh´ac. Bˆo
.m˜a nhu
.vˆa
.y go
.i l`a m˜a tiˆe
`n tˆo
´.Mˆo
.t c´ach d¯o
.n gia
˙’n d¯ˆe
˙’ kiˆe
˙’m
tra mˆo
.t bˆo
.m˜a c´o pha
˙’i l`a tiˆe
`n tˆo
´hay khˆong ta v˜e cˆay nhi
.phˆan (mˆo
˜i d¯ı
˙’nh c´o bˆa
.c≤2) tu
.o.ng
´u
.ng v´o
.i bˆo
.m˜a. Cˆay d¯u
.o.
.c v˜e xuˆa
´t ph´at t`u
.mˆo
.t n´ut d¯o
.n (n´ut gˆo
´c) v`a mˆo
˜i n´ut trong c´o bˆa
.c
ngo`ai nho
˙’ ho.n hoˇa
.c bˇa
`ng hai. Mˆo
.t trong hai nh´anh con tu
.o
.ng ´u
.ng bit 1 v`a nh´anh c`on la
.i
102
http://www.ebook.edu.vn
tu
.o.ng ´u
.ng bit 0. D
-ˆe
˙’ thuˆa
.t tiˆe
.n, ta quy u
.´o
.c nh´anh con bˆen pha
˙’i tu
.o.ng ´u
.ng 0 v`a nh´anh con
bˆen tr´ai tu
.o.ng ´u
.ng 1. Theo c´ach n`ay, c´ac cˆay nhi
.phˆan tu
.o.ng ´u
.ng c´ac m˜a C2, C3v`a C4cho
trong H`ınh 4.3. (D
-ˆe
˙’ d¯o.n gia
˙’n, ta s˜e khˆong v˜e c´ac m˜ui tˆen trong c´ac cˆay nhi
.phˆan).
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1
1
0
0
a1a2
a3a4
•
•
•
•
•
M˜a C2
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1 0
1 0
1 0
•
•
•
•
•
•
•
a1
a2
a3a4
M˜a C3
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1
0
0
0
•
•
•
•
•
a1
a2
a3
a4
M˜a C4
H`ınh 4.3:
Ch´u ´y rˇa
`ng ngo`ai n´ut gˆo
´c, cˆay nhi
.phˆan c´o hai loa
.i n´ut: c´ac n´ut l´a c´o bˆa
.c ngo`ai bˇa
`ng
khˆong; v`a c´ac n´ut trong c´o bˆa
.c ngo`ai kh´ac khˆong. Trong bˆo
.m˜a tiˆe
`n tˆo
´, c´ac t`u
.m˜a chı
˙’ tu
.o.ng
´u
.ng c´ac n´ut l´a. M˜a C4khˆong pha
˙’i l`a m˜a tiˆe
`n tˆo
´do tˆo
`n ta
.i t`u
.m˜a tu
.o.ng ´u
.ng n´ut trong.
Duyˆe
.t cˆay t`u
.gˆo
´c d¯ˆe
´n c´ac n´ut l´a cho ta biˆe
˙’u diˆe
˜n chuˆo
˜i bit tu
.o.ng ´u
.ng k´y hiˆe
.u. Mˆo
˜i nh´anh
d¯´ong g´op mˆo
.t bit v`ao t`u
.m˜a cu
˙’a n´o: bit 1 cho nh´anh tr´ai v`a bit 0 cho nh´anh pha
˙’i.
M˜a tiˆe
`n tˆo
´luˆon luˆon d¯u
.o.
.c gia
˙’i m˜a duy nhˆa
´t nhu
.ng ngu
.o.
.c la
.i khˆong d¯´ung (chˇa
˙’ng ha
.n
m˜a C4).Tuy nhiˆen c´o thˆe
˙’ ch´u
.ng minh rˇa
`ng bˆo
.m˜a c´o thˆe
˙’ gia
˙’i m˜a duy nhˆa
´t tu
.o.ng d¯u
.o.ng
v´o.i m˜a tiˆe
`n tˆo
´theo ngh˜ıa: sˆo
´trung b`ınh c´ac bit biˆe
˙’u diˆe
˜n c´ac k´y hiˆe
.u bˇa
`ng nhau.
4.2.2 M˜a Huffman
M˜a Huffman l`a m˜a tiˆe
`n tˆo
´v`a tˆo
´i u
.u v´o
.i c´ac x´ac xuˆa
´t cho tru
.´o
.c. Phu
.o.ng ph´ap xˆay du
.
.ng
m˜a Huffman du
.
.a trˆen hai quan s´at sau:
1. Trong mˆo
.t bˆo
.m˜a tˆo
´t u
.u, c´ac k´y hiˆe
.u xuˆa
´t hiˆe
.n thu
.`o
.ng xuyˆen (c´o x´ac suˆa
´t hay tˆa
`n sˆo
´
xuˆa
´t hiˆe
.n l´o.n) s˜e c´o c´ac t`u
.m˜a ngˇa
´n ho.n c´ac k´y hiˆe
.u ´ıt xuˆa
´t hiˆe
.n.
2. Trong mˆo
.t bˆo
.m˜a tˆo
´t u
.u, hai k´y hiˆe
.u xuˆa
´t hiˆe
.n ´ıt nhˆa
´t s˜e c´o c´ac t`u
.m˜a c`ung d¯ˆo
.d`ai.
D
-ˆe
˙’ xˆay du
.
.ng m˜a Huffman, ch´ung ta c´o thˆe
˙’ biˆe
˙’u diˆe
˜n qua cˆay nhi
.phˆan m`a c´ac n´ut l´a
tu
.o.ng ´u
.ng c´ac k´y hiˆe
.u. Duyˆe
.t cˆay nhi
.phˆan s˜e cho ta c´ac t`u
.m˜a cu
˙’a bˆo
.m˜a: xuˆa
´t ph´at t`u
.
103