1

ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
NGUYỄN THÀNH DƢƠNG

TÌM HIỂU MỘT SỐ THUẬT TOÁN MÃ HÓA VÀ NÉN DỮ
LIỆU, XÂY DỰNG ỨNG DỤNG ĐỂ NÉN DỮ LIỆU ẢNH
LUẬN VĂN THẠC SỸ KHOA HỌC


1.2. Nén dữ liệu
5
1.3. Entropy
5
1.4. Các kết quả cơ bản về nén dữ liệu
8
1.4.1. Phân loại nén dữ liệu
8
1.4.2. Các định lý về nén dữ liệu
9
1.5. Lý thuyết về hình ảnh
14
1.5.1. Giới thiệu về ảnh số và xử lý ảnh số
14
1.5.2. Mục đích và sự cần thiết của nén ảnh
15
1.5.3. Phân loại các phƣơng pháp nén ảnh
16
Chƣơng 2: MỘT SỐ THUẬT TOÁN MÃ HÓA VÀ NÉN DỮ LIỆU
19
2.1. Thuật toán HUFFMAN
19
2.1.1. Ý tƣởng của thuật toán
19
2.1.2. Thuật toán
19
2.2. Thuật toán tách đoạn (RLE – Runlength Coding)
22
2.2.1. Ý tƣởng của thuật toán
22

3.2.3. Thủ tục của chƣơng trình nén ảnh bằng thuật toán JPEG
62
3.3. Giao diện chính của chƣơng trình
64
3.4. Các bƣớc thực hiện chƣơng trình
66
3.5. So sánh kết quả thử nghiệm
68
KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN
72
TÀI LIỆU THAM KHẢO
74

4

PHẦN MỞ ĐẦU Nén dữ liệu hiện đang đƣợc sử dụng hầu nhƣ ở mọi nơi. Tất cả các hình ảnh
mà chúng ta xem hoặc sao chép đƣợc từ các trang web là các tệp hình ảnh đã đƣợc
nén, thông thƣờng trong định dạng JPEG hoặc GIF; đa số các modem đều sử dụng
tính năng nén dữ liệu; truyền hình độ phân giải cao (HDTV) sử dụng phƣơng pháp
nén theo chuẩn MPEG-2. Một số hệ thống quản lý tệp tin tự động nén các tệp tin
khi lƣu trữ và chúng ta cũng thƣờng sử dụng các chƣơng trình nén khác nhau để nén
tệp dữ liệu. Quá trình làm giảm kích thƣớc của một tệp dữ liệu đƣợc gọi một cách
phổ biến là nén dữ liệu (data compresion), còn tên gọi trong lý thuyết thông tin là
mã hóa nguồn (source coding). Trong khoa học máy tính và lý thuyết thông tin, nén
dữ liệu (hoặc mã hóa nguồn) là việc mã hóa thông tin bằng số ít bit hơn so với biểu
diễn ban đầu.
Có thể chia các phƣơng pháp nén ra hai lớp: nén không mất thông tin và nén

đó có nghĩa là sự mất mát một đại lƣợng nhƣ một thành phần tần số, hoặc nhiễu.
Chẳng hạn, ngƣời ta có thể nghĩ rằng nén văn bản có mất thông tin là không thể
chấp nhận đƣợc bởi vì họ nghĩ tới việc mất hoặc chuyển đổi các ký tự. Thay vì đó ta
có thể nghĩ tới một hệ thống các câu chuẩn, hoặc các từ thay thế bằng từ đồng
nghĩa, nhờ đó có thể nén tập tin tốt hơn. Về mặt kỹ thuật nén mất dữ liệu có thể gây
ra sự thay đổi của văn bản, nhƣng ý nghĩa và tính rõ ràng của văn bản vẫn có thể
đƣợc giữ nguyên hoặc thậm chí cải thiện.
Khi xét các thuật toán nén, điều quan trọng là cần phân biệt giữa hai thành
phần: mô hình và bộ mã hóa. Mô hình cho biết phân phối xác suất của các dãy tin
bằng cách nhận biết hoặc phát hiện cấu trúc của đầu vào. Bộ mã hóa tạo ra các dãy
mã dựa trên các xác suất tạo ra mô hình. Để có hiệu quả nén, bộ mã hóa thƣờng tạo
ra các dãy mã dài cho các dãy tin có xác suất thấp và gán dãy mã ngắn cho các dãy
tin có xác suất cao. Ví dụ, trong bảng chữ cái của một ngôn ngữ tự nhiên thƣờng có
một vài chữ cái xuất hiện trong các văn bản viết với xác suất cao hơn các chữ cái
khác, điều này còn rõ ràng hơn với các cặp chữ cái. Khi đó bộ mã hóa sẽ gán từ mã
có độ dài ngắn cho chữ cái xuất hiện với xác suất cao và ngƣợc lại. Thông thƣờng
6

sự tách biệt giữa mô hình và thành phần mã hóa không phải luôn luôn đƣợc xác
định một cách rõ ràng.
Lý thuyết thông tin là lĩnh vực có thể gắn mô hình với thành phần mã hóa.
Nó cho lý thuyết rất tốt sự liên quan giữa xác suất và độ dài từ mã. Lý thuyết này
phù hợp với thực tế gần nhƣ hoàn hảo, và chúng ta có thể đạt đƣợc độ dài mã gần
nhƣ giống hệt với những gì lý thuyết dự đoán.
Trong trƣờng hợp mã hóa có mất thông tin, ta có thể lấy tiêu chuẩn đánh giá
là thời gian nén, thời gian để tái tạo lại dãy tin ban đầu (giải mã) kích thƣớc của tệp
nén. Trong trƣờng hợp nén có mất thông tin, các tiêu chuẩn thƣờng là phức tạp hơn,
chẳng hạn xấp xỉ dãy tin ban đầu nhƣ thế nào đƣợc gọi là chấp nhận đƣợc. Thông
thƣờng cần dung hòa giữa kích thƣớc nén, thời gian chạy, và chất lƣợng dãy tin
đƣợc giải mã.

1
,a
2
, ,a
n
}, X là một bản tin trên bảng
chữ cái A. Ta gọi bản tin Y trên bảng chữ cái B = {b
1
,b
2
,…,b
m
} là bản mã của bản
tin X nếu tồn tại ánh xạ f sao cho Y = f(X). Khi đó f đƣợc gọi là phép mã hóa.
Cách ghi mã: Có nhiều cách ghi mã, giả sử mã văn bản ngƣời ta hay sử dụng
những nhóm ký hiệu đƣợc phân cách bởi một dấu Space, cách mã nhƣ vậy gọi là mã
bằng phƣơng pháp từ. Mã chỉ sử dụng hai ký tự "0" và "1" để biểu diễn gọi là mã
nhị phân. Loại mã dùng ký hiệu bằng một nhóm ký tự có độ dài nhất định cho mỗi
từ mã là mã có độ dài cố định. Loại mã này ta luôn giải mã đƣợc. Nhƣng nếu lƣu trữ
nhƣ vậy sẽ rất tốn kém, nên ngƣời ta thƣờng dựa vào tần suất xuất hiện các chữ cái
để mã, với tần suất càng nhiều mã càng ngắn. Mã nhƣ vậy gọi là mã có độ dài thay
đổi. Tuy nhiên nếu độ dài của từ mã thay đổi thì không phải với ánh xạ mã nào cũng
có thể giải mã đƣợc.
Xét ví dụ ánh xạ mã: a  100; b  1000; c  0
Mã của "ac" và "b" đều là dãy bit "1000". Nhƣ vậy khi nhận đƣợc chuỗi bit
1000 chúng ta không thể biết đƣợc rằng văn bản ban đầu là "b" hay là "ac". Cho nên
khi mã hoá sử dụng mã có độ dài thay đổi cần có tính chất là giải mã đƣợc, đó là
tính phân tách. Tính phân tách đƣợc đƣa ra dƣới đây sẽ đảm bảo cho tính giải đƣợc
của mã.
8

thuật toán.
1.3. Entropy
* Độ đo Logarit của thông tin: Giả sử có hai biến ngẫu nhiên X và Y; X có thể
nhận các giá trị trong tập {x
1
,x
2
, ,x
n
} và Y có thể nhận giá trị trong tập
{y
1
,y
2
,…,y
m
}. Chúng ta cần xác định về mặt định lƣợng thông tin của sự kiện X = x
i

khi đã biết Y = y
j
. Rõ ràng là nếu X và Y là hai biến độc lập thì việc biết trƣớc
Y = y
j
thì không cho lƣợng thông tin nào về việc xảy ra X = x
i
. Mặt khác nếu X và
Y phụ thuộc nhau đầy đủ thì khi Y = y
j
xác định đƣợc X = x

) và p(X=x
i
) = p(x
i
)
Trong đó: I(x
i
,y
j
) số đo thông tin liên quan giữa x
i
và y
j
.
Đơn vị của I(x
i
,y
j
) đƣợc xác định bởi cơ số của Logarit ngƣời ta thƣờng lấy là
2 hoặc e, nếu cơ số là 2 ta gọi đơn vị của I là bit, nếu là e ta gọi là đơn vị tự nhiên.
Công thức chuyển đổi giữa các đơn vị là :
lna = ln2log
2
a = 0,69315log
2
a

Trƣờng hợp X và Y là hai biến độc lập thì p(x
i
|y

)
Công thức 1.3 chính là thông tin của sự kiện X = x
i
, có thể viết công thức 1.3
ở dạng:
I(x
i
) = - log p(x
i
)
Cần chú ý rằng từ 1.4 suy ra sự kiện có xác suất càng cao thì lƣợng thông tin
mang lại ít hơn sự kiện có xác suất thấp. Rõ ràng với sự kiện x bất kỳ mà p(x) = 1
thì I(x) = 0, nghĩa là việc xảy ra sự kiện x không mang lại lƣợng thông tin nào.
Xét ví dụ sau: Giả sử có nguồn rời rạc phát đi các bit 0, 1 với xác suất bằng
nhau bằng 1/2 trong t giây thông tin đƣa ra từ nguồn là:
I(x
i
) = - log
2
1/2 = 1 bit, ở đây x
i
= 0 hoặc x
i
= 1
Hoặc ví dụ khác: Giả sử xét mô hình thống kê độc lập. Xét dãy k bít của nguồn
phát đi, rõ ràng có tất cả M = 2
k
dãy k bit khác nhau do vậy các dãy này có xác suất
xuất hiện bằng nhau và bằng 1/2
k

),(),(),(
1 1
ji
n
i
m
j
ji
yxIyxPYXI

 

)()(
),(
1 1
),(),(
ji
ji
ypxp
yxP
n
i
m
j
ji
yxPYXI

 

Bây giờ chúng ta chú ý tới đẳng thức sau:

)/p(y
j
)
Từ đây suy ra: I(x
i
,y
j
) = I(y
j
,x
i
)
Nhƣ vậy thông tin về sự kiện X = x
i
khi xảy ra sự kiện Y = y
j
đã xảy ra bằng
thông tin về sự kiện Y = y
j
khi sự kiện X = x
i
đã xảy ra.
Ngoài ra từ định nghĩa thông tin phụ thuộc lẫn nhau (Mutual Information) và
thông tin độc lập (Self Information) đƣợc dùng để xác định thông tin có điều kiện
(Condition self - Information)
I(x
i
|y
j
) = log [1/ p(x
Hay :

Ta thấy I(X,Y) = 0 khi X và Y độc lập, vậy một đặc trƣng quan trọng của
I(X,Y) là I(X,Y)  0. Tƣơng tự nhƣ vậy chúng ta định nghĩa thông tin trung bình: Khi X là bảng chữ cái bao gồm các kí tự sinh ra nguồn, khi đó H(X) là trung
bình thông tin trên các kí tự.
1.5
1.6
1.7
1.8
1.9
1.10
11

)(log)()(
1
i
n
i
i
xPxPXH



Giả sử có không gian xác suất X = {x
1

log
1
()( 

Nói chung H(X)  logn cho tập nguồn gồm các chữ cái. Nói một cách khác
Entropy của nguồn rời rạc là cực đại khi các kí tự trong bảng chữ cái có xác xuất
bằng nhau.
1.4. Các kết quả cơ bản về nén dữ liệu
1.4.1. Phân loại nén dữ liệu
Kỹ thuật nén dữ liệu có thể đƣợc phân theo 2 hƣớng chính: Nén dữ liệu không
mất thông tin, nén dữ liệu có mất thông tin.
1.4.1.1. Nén dữ liệu không mất thông tin
Nén dữ liệu không mất thông tin đƣợc dùng với bản tin dạng văn bản. Do tính
chất quan trọng của dữ liệu, sau khôi phục dữ liệu phải giống hoàn toàn với dữ liệu
gốc. Ta định nghĩa nhƣ sau:
Gọi X là tệp dữ liệu gốc, Y là tệp dữ liệu đƣợc nén qua phép mã f với
L
f
(Y)  L(X). Nếu tồn tại một ánh xạ f
-1
sao cho X= f
-1
(Y) thì phép mã f gọi là nén
không mất thông tin.
1.4.1.2. Nén dữ liệu có mất thông tin
Nén dữ liệu có mất thông tin thƣờng sử dụng cho các bản tin là hình ảnh, âm
thanh hay video. Trong các bản tin này ngƣời ta thực hiện mã bằng cách loại bỏ đi
các yếu tố mà con ngƣời không thể nhận biết. Sau khi khôi phục, dữ liệu thu đƣợc
khác dữ liệu gốc, nhƣng sự sai khác đó có thể chấp nhận đƣợc.
1.11

m
} vớ i xá c suấ t xuấ t hiệ n củ a cá c chƣ̃ cá i
tƣơng ƣ́ ng là p
1
= p(a
1
), p
2
= p(a
2
), , p
m
= p(a
m
).
Nế u văn bả n  =

1

2


n
đƣợ c sinh ra tƣ̀ việ c chọ n ngẫ u nhiên cá c chƣ̃ cá i
thì sẽ có xác suất xuất hiện là p() = p(

1
)p(

2


m
i
i
i
p
p
1
2
1
log
bit là 2. Mộ t qui trình né n nhƣ vậ y thì chỉ có thể dù ng để nén 2 văn bả n mà thôi đế n
văn bả n thƣ́ 3 là nội dung của file nén sẽ bị trùng lặp . Vậ y thì không thể né n mộ t
văn bả n nhỏ tù y ý đƣợ c . Giớ i hạ n né n củ a mộ t văn bả n là bao nhiêu ? Shannon là
ngƣờ i đầ u tiên chƣ́ ng minh đƣợ c sƣ̣ tồ n tạ i mộ t giớ i hạ n né n cho mỗ i văn bả n . Mộ t
văn bả n thƣ̣ c ra chỉ có thể né n đế n mộ t giớ i hạ n nhấ t đị nh , giớ i hạ n ấ y gọ i là lƣợ ng
tin củ a văn bả n. Lƣợ ng tin chỉ phụ thuộ c và o bả n thân văn bả n chƣ́ không phụ thuộ c
vào thuật toán nào. Mọi thuật toán đều không thể nén một văn bản đế n mộ t file nhỏ
hơn lƣợ ng tin mà văn bả n có . Lƣợ ng tin cò n đƣợ c gọ i là Entropy.
Đối với văn bản đƣợc sinh ra từ mô hình rời rạ c thì :
Entropy =
i
m
i
i
p
p
1
log
2

i
m
i
i
p
p
1
log
2
1


.
(b) Vớ i hầ u hế t cá c văn bả n bit trung bình (cho mộ t chƣ̃ cá i ) của văn bản không
nhỏ hơn


m
1i
i
2i
p
1
logp
.
2. Tồ n tạ i mã nhị phân cho tƣ̀ ng khố i k chƣ̃ cá i có tí nh phân tá ch sao cho bit
trung bì nh (cho mộ t chƣ̃ cá i) của nó nằm giữa và

Nhƣ vậ y, định lý khẳ ng định rằ ng “ entropy đú ng là giớ i hạ n nhỏ nhấ t có thể mà
bít trung bì nh củ a mộ t mã né n nhị phân có th  đt đưc ” cho dù mã đƣợ c tạ o ra

26
101
26
log
101
26
101
30
log
101
30
(
2222

= 1.98
Tuy nhiên, văn bả n do con ngƣờ i tạ o ra không phải các chữ cái xuất hiện một
cách ngẫ u nhiên , đƣơng nhiên là phụ thuộ c lẫ n nhau tuân thủ theo cá c qui tắ c tạ o
tƣ̀ , tạo câu,
1.4.2.2. Mã Huffman
 Định nghĩ a
Cho bảng chữ cái A = {a
1
, a
2
, , a
m
} với xác suất xuất hiện tương ứng là
p
1


(p
1
p
2
 p
m
>0). Nhƣ vậ y chƣ̃ cá i ở cuố i bả ng là chữ cái có xác suất xuất
hiệ n nhỏ nhấ t.
 Ghép 2 chƣ̃ cá i vớ i xá c suấ t nhỏ nhấ t lạ i thà nh mộ t chƣ̃ cá i ké p vớ i xá c
suấ t xuấ t hiệ n là tổ ng củ a hai xá c suấ t ấ y . Nhƣ vậ y trong bả ng chƣ̃ cá i
mớ i 2 chƣ̃ cá i nà y bị loạ i nhƣng chƣ̃ cá i ké p đƣợ c thêm và o.
 Tạo mã Huffman cho bảng chữ cái mới này (có m - 1 chƣ̃ ).
 Tạo 2 tƣ̀ mã mớ i bằ ng cá ch thêm "0" và thêm "1" vào mã của chữ cái kép.
Gán 2 mã này cho 2 chƣ̃ cá i bị ghé p lạ i.
Ví d 1: Với không gian xá c suấ t cá c sƣ̣ kiệ n {e, a, i, o, u, ô} các xác suất tƣơng
ứng là (e,0.3) (a,0.2) (o,0.2) (i,0.1) (u,0.1) (ô,0.1) thì ta cần ghép 5 lầ n nhƣ sau:
15

e  0.3
e  0.3
e  0.3
{a,o}  0.4
{{{u,ô},i,
e}  0.6
{{{{u,ô},i},e,
{a,o}}  1.0
a  0.2
a  0.2
{{u,ô},i}0.3
e  0.3
 Định lý :
o Mã Huffman là mã tối ưu.
o Đối với mã tối ƣu thì


m
1i
i
2i
p
1
logp



m
i
ii
p
1

 1+


m

u
Bảng mã của các
chữ cái.
u0000
ô0001
i001
e01
a10
o11

Việc gán mã đƣợc thực hiện nhƣ sau:
16

kk
k
f















m
f
m
2
51
log
2




m
i
ii
i
m
i
i
p
p
p
11
2
1
log

i
i
p


đầu tiên còn lại là các số của dãy Fibonaci.
Công thức tổng quát là f
k
= f
k-1
+ f
k-2
. Ta đã biết
Tổng các tần xuất là f
m+2
. Trong quá trình đệ quy thì từ kép bao giờ cũng đứng ở vị
trí áp chót. Cần m bƣớc đệ quy nên từ mã ứng với xác suất dài m + 1. Đối
với mã Shannon thì độ dài từ mã xấp xỉ - log
2
f
m+2
. Nhƣ vậy, độ dài từ mã của chữ
cái này trong mã Huffman dài gấp lần độ dài từ mã của nó trong mã

Shannon (do tỷ số tiến tới < 1 khi m  ).
Nhƣ vậy không nhất thiết từ mã cho các chữ cái của mã tối ƣu luôn phải
ngắn nhất có thể. Thậm chí cũng không thể coi độ dài từ mã, ngay cả khi là mã tối
ƣu, là thƣớc đo lƣợng tin của phần tử.
Chú ý:
Mặc dù chúng ta đã biết đƣợc rằng với mọi mã giải đƣợc thì
Thế nhƣng đối với từng ký tự thì không có bất đẳng thức .
Ta có thể lấy ví dụ nhƣ sau: bảng chữ cái gồm 3 chữ “a”, “b”, “c” với xác
suất là 1/3, 1/3 và 1/3 thì mã hóa Huffman của chúng ta là “a”  “0”, “b”  “10”,
“c”  “11”. Nhƣ vậy, đối với chữ cái “a”, ta có tức là Nhƣng
đối với mã Shannon thì ta có .

1.5.1.2. Xử lý ảnh số
Xử lý ảnh là một khoa học mặc dù còn tƣơng đối mới so với nhiều ngành
khoa học khác, nhất là trên quy mô công nghiệp. Xử lý ảnh số có rất nhiều ứng
Pixel or
PEL
o
r

P
E
L
Độ sáng trung bình trong mỗi hình
chữ nhật = giá trị một điểm ảnh.
Hình 1.1: Biu diễn một mức xám của ảnh số.
18

dụng nhƣ làm nổi các ảnh trong y học, khôi phục lại ảnh do tác động của khí quyển
trong thiên văn học, tăng cƣờng độ phân giải của ảnh truyền hình mà không cần
thay đổi cấu trúc bên trong của hệ thống chuyển tải, nén ảnh trong khi truyền đi xa
hoặc lƣu trữ. Các giai đoạn chính trong xử lý ảnh có thể đƣợc mô tả trong hình sau:

Camera
SENSO
Thu nhËn
¶nh
Sè
L-u
tr÷
Ph©n tÝch
¶nh
L-u
HÖ quyÕt
®Þnh
NhËn
d¹ng
Hình 1.2: Các giai đon chính trong xử lý ảnh.
19

 Ảnh màu RGB (24 bit/điểm ảnh) cùng độ phân giải nhƣ vậy cần hơn 10 triệu
bit để lƣu trữ và 20 phút để truyền.
 Một phim âm bản có kích thƣớc 24x36 mm (35 mm) chia bằng các khoảng
cách nhau 12 âm, vào khoảng 3000x2000 điểm, 8 bit/pixel, yêu cầu 48 triệu
bit cho lƣu giữ ảnh và 83 phút để truyền.

con số, một từ, điều đó phụ thuộc vào từng bài toán.
 Tỷ lệ nén
Tỷ lệ nén là một trong các đặc trƣng quan trọng của mọi phƣơng pháp nén. Tỷ
lệ nén đƣợc định nghĩa nhƣ sau:
Tỷ lệ nén = (1/r)*%
với r là tỷ số nén đƣợc định nghĩa:
r = kích thước dữ liệu gốc/kích thước dữ liệu nén.
Nhƣ vậy hiệu suất nén = (1- tỷ lệ nén)*100%.
+ Đối với ảnh tĩnh, kích thƣớc chính là số bit biểu diễn toàn bộ bức ảnh.
+ Đối với ảnh video, kích thƣớc chính là số bit để biểu diễn một khung hình
video (video frame).
1.5.3.2. Phân loi dựa vào nguyên lý nén
Nén bảo toàn thông tin (losses compression): bao gồm các phƣơng pháp nén
mà sau khi giải nén sẽ thu đƣợc chính xác dữ liệu gốc. Tuy nhiên nén bảo toàn
thông tin chỉ đạt hiệu quả nhỏ so với phƣơng pháp nén không bảo toàn thông tin.
Nén không bảo toàn thông tin (lossy compression): bao gồm các phƣơng
pháp nén sau khi giải nén sẽ không thu đƣợc dữ liệu nhƣ bản gốc. Các phƣơng pháp
này đƣợc gọi là “tâm lý thị giác” đó là lợi dụng tính chất của mắt ngƣời chấp nhận
một số vặn xoắn trong ảnh khi khôi phục lại. Phƣơng pháp này luôn đem lại hiệu
quả cao do loại bỏ đi những thông tin dƣ thừa không cần thiết.
1.5.3.3. Phân loi dựa vào cách thức thực hiện nén
Phƣơng pháp không gian (Spatial Data Compression): các phƣơng pháp này
thực hiện nén bằng cách tác động trực tiếp lên việc lấy mẫu của ảnh trong miền
không gian.
21

Phƣơng pháp sử dụng biến đổi (Transform Coding): gồm các phƣơng pháp
tác động lên sự biến đổi của ảnh gốc chứ không tác động trực tiếp.
1.5.3.4. Phân loi dựa vào lý thuyết mã hóa
Các phương pháp nén thế hệ thứ nhất: gồm các phƣơng pháp có mức độ tính

Ngƣời ta tính tần suất xuất hiện của các ký tự bằng cách duyệt tuần tự từ đầu tệp
gốc đến cuối tệp. Việc xử lý ở đây tính theo bit. Trong phƣơng pháp này các ký tự
có tần suất cao thì đƣợc gán một từ mã ngắn, các ký tự có tần suất thấp thì đƣợc gán
một từ mã dài. Nhƣ vậy với cách thức này ta đã làm giảm chiều dài trung bình của
từ mã hoá bằng cách dùng các từ mã có độ dài khác nhau.
2.1.2. Thuật toán
 Thuật toán HUFFMAN gồm 2 bƣớc chính:
- Bước một:
Tính tần suất của các ký tự trong dữ liệu gốc bằng cách duyệt tệp gốc một
cách tuần tự từ đầu đến cuối để xây dựng bảng mã và tính toán tần suất. Tiếp theo
sau là sắp xếp lại bảng mã theo thứ tự tần suất giảm dần.
- Bước hai:
Duyệt bảng tần suất từ cuối lên đầu để thực hiện ghép hai phần tử có tần suất
thấp thành một phần tử duy nhất có tần suất bằng tổng hai tần suất thành phần. Cập
nhật phần tử này vào vị trí phù hợp trong bảng và loại bỏ hai phần tử đã xét. Thực
hiện cho đến khi bảng chỉ có một phần tử. Đây là quá trình tạo cây nhị phân
HUFFMAN, phần tử có tần suất thấp ở bên phải, phần tử kia ở bên trái. Sau khi cây
đã tạo xong ngƣời ta tiến hành gán mã cho các nút lá. Việc mã hoá thực hiện theo
quy định: mỗi lần xuống bên phải ta thêm một bit „1‟ vào từ mã, mỗi lần xuống bên
trái ta thêm một bit „0‟ vào từ mã.
Quá trình giải nén cũng khá đơn giản đƣợc tiến hành theo chiều ngƣợc lại.
Ngƣời ta cũng phải dựa vào bảng mã tạo ra trong giai đoạn nén (bảng này đƣợc lƣu
23

trữ trong cấu trúc đầu của tệp nén cùng với dữ liệu nén).
Ví d: Một tệp bất kỳ có tần suất xuất hiện của các kí tự số nhƣ bảng sau:

Ký tự
Tần suất
0

0.0982
2
0.0824
4
0.0577
1
0.0388
8
0.0286
7
0.0235
9
0.0222

24 0
0.3906
0.3906
0.3906
0.3906
0.3906
0.3906
0.3906
0.3906
0.6100
6
0.1535
0.1535

0.0824
0.0982
0.1034
0.1051
4
0.0577
0.0577
0.0674
0.0824
0.0982

1
0.0388
0.0457
0.0577
0.0674 8
0.0286
0.0388

bỏ đi 2 tần suất thành phần tạo thành nó. Sau khi đƣa giá trị mới vào bảng ta phải
tiến hành sắp xếp lại toàn bộ bảng, lúc này số lƣợng tần suất chỉ còn là (n – 1) nếu
ban đầu số lƣợng tần suất là n. Tiếp tục thực hiện lần lƣợt theo thứ tự nhƣ trên cho
đến khi nào số lƣợng tần suất chỉ còn lại duy nhất 1 giá trị.
 Việc tạo cây nhị phân đƣợc thực hiện theo một thuật toán sau:
1. Tất cả những ký tự ban đầu đƣợc xem nhƣ là những ký tự giao điểm tự do.
2. Hai nút tự do với tần số xuất hiện thấp nhất đƣợc phân công tới một nút
gốc với giá trị bằng với tổng của hai nút con tự do.
3. Hai nút con đƣợc chuyển khỏi danh sách nút tự do. Chuyển nút gốc mới
tạo thành công vào danh sách.
4. Bƣớc hai sang bƣớc ba đƣợc lặp cho đến khi chỉ có 1 nút tự do về phía
trái. Nút tự do này là gốc của cây.
Trong thuật toán mã HUFFMAN, mã của ký tự là duy nhất và không mã nào
là phần bắt đầu của mã trƣớc. Vì vậy khi đọc theo từng bit từ đầu đến cuối tệp nén
ta có thể duyệt cây mã cho đến một lá, tức là ký tự đã đƣợc giải mã. Việc giải mã
chắc chắn phải sử dụng cây nhị phân giống nhƣ trong mã hoá. Để đọc, giải mã đƣợc
yêu cầu phải sử dụng theo đúng tiêu chuẩn nhất định. 25

Ƣu điểm: của thuật toán mã hoá HUFFMAN là đạt đƣợc hệ số nén cao (Hệ
số nén tuỳ thuộc vào cấu trúc của các tập tin).
Nhƣợc điểm: bên nhận muốn giải mã đƣợc thông điệp thì phải có một bảng