ĐẠI HỌC THÁI NGUN
TRƯỜNG ĐẠI HỌC CNTT & TRUYỀN THƠNG

HÀ DIỆU THÚY

NÉN DỮ LIỆU TIẾNG VIỆT SỬ DỤNG PHƯƠNG PHÁP
MÃ HĨA SỐ HỌC
Chun ngành: Khoa học máy tính
Mã số: 60 48 01

TĨM TẮT LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Có thể tìm hiểu luận văn tại:
- Trung tâm học liệu Đại học Thái Ngun
- Thư viện trường Đại học CNTT & Truyền thơng Thái Ngun
Số hóa bởi trung tâm học liệu /> 1

MỞ ĐẦU
1. Đặt vấn đề
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, truyền hình số, điện thoại, internet, các hệ thống lưu trữ, văn bản 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.
Tiếng Việt là một ngơn ngữ thuộc hệ thống chữ cái Latinh, sử dụng
nhiều dấu đi kèm với ngun âm, ngồi bảng chữ cái của tiếng Anh, tiếng
Việt còn có thêm các ký tự:
Sáu ngun âm a, e, i, o, u, y với 5 dấu thanh (sắc, huyền, hỏi, ngã,
nặng) tổ hợp thành 30 ký tự.
Sáu ngun âm ă, â, ê, ơ, ơ, ư với sáu dấu thanh (sắc, huyền, hỏi, ngã,
nặng, khơng dấu) tổ hợp thành 36 ký tự.
Một phụ âm đặc biệt đ.
Vậy cần thêm (30 + 36 +1) x 2 = 134 ký tự cho tiếng Việt.
Với bảng mã ASCII 8 bit sử dụng phổ biến trên máy tính, chúng ta có
thể mã hóa 256 ký tự. Tuy nhiên, các ký tự có mã từ 0 đến 127 đã được chuẩn
hóa và thuộc diện “cấm vi phạm” vì vậy chỉ còn 128 chỗ (mã từ 128 đến 255)
là được “tự do”. Vậy nếu xây dựng mỗi chứ ứng với một mã thì sử dụng hết
vùng tự do mà vẫn thiếu 134 – 128 = 6 chỗ.
Hiện nay chúng ta đang sử dụng chuẩn Unicode để lưu trữ các ký tự

- Khảo sát thực tế các phần mềm nén dữ liệu hiện nay đối với việc nén
các văn bản tiếng Việt.
- Phân tích, đánh giá các kỹ thuật (thuật tốn) nén dữ liệu.
- Cài đặt kỹ thuật nén Arithmetic Coding
- Triển khai thử nghiệm trên các loại dữ liệu văn bản tiếng Việt.
5. Ý nghĩa khoa học và ý nghĩa thực tiễn của đề tài
- Nghiên cứu hồn thiện các kỹ thuật nén bảo tồn dữ liệu cho các văn
bản tiếng Việt.
- Xây dựng ứng dụng nén dữ liệu cho các văn bản tiếng Việt.
Số hóa bởi trung tâm học liệu /> 4

Chương 1: TỔNG QUAN VỀ NÉN DỮ LIỆU
1.1. Tổng quan về nén dữ liệu
1.1.1. Sơ lược về nén dữ liệu
1.1.1.1 Khái niệm nén dữ liệu
Nén dữ liệu là q trình làm giảm lượng thơng tin “dư thừa” trong dữ
liệu gốc và do vậy, lượng thơng tin thu được sau nén thường nhỏ hơn so với
dữ liệu gốc rất nhiều.
1.1.1.2 Ngun tắc nén dữ liệu
Thơng thường, hầu hết các tập tin trong máy tính có rất nhiều thơng tin
dư thừa, việc thực hiện nén tập tin thực chất là mã hố lại các tập tin để loại
bỏ các thơng tin dư thừa.
Nhìn chung khơng thể có phương pháp nén tổng qt nào cho kết quả
tốt đối với tất cả các loại tập tin vì nếu khơng ta sẽ áp dụng n lần phương pháp
nén này để đạt được một tập tin nhỏ tuỳ ý. Kỹ thuật nén tập tin thường được
áp dụng cho các tập tin văn bản (Trong đó có một số kí tự nào đó có xác suất
xuất hiện nhiều hơn các kí tự khác), các tập tin ảnh bitmap (Mà có thể có
những mảng lớn đồng nhất), các tập tin dùng để biểu diễn âm thanh dưới dạng
số hố và các tín hiệu tương tự (analog signal) khác (Các tín hiệu này có thể
có các mẫu được lặp lại nhiều lần). Ðối với các tập tin nhị phân như tập tin

chuỗi này có thể thay thế bằng (r,7,M) hay viết tắt là r7M. r với ý nghĩa ký
hiệu cho việc xuất hiện sự lặp lại (repeating) đòi hỏi chữ r khơng được xuất
hiện trong bảng chữ cái của đầu vào.
Cho chuỗi đầu vào là ABCDEFG (khơng xuất hiện sự lặp lại) chuỗi
này có thể thay thế bằng (n,7,ABCDEFGH), hay viết tắt là n7ABCDEFG. n
Số hóa bởi trung tâm học liệu /> 6

với ý nghĩa là ký hiệu cho việc khơng xuất hiện sự lặp lại (non-repeating), chữ
n khơng được xuất hiện trong bảng chữ cái đầu vào.
Thuật tốn này hiệu quả nếu như dữ liệu đầu vào gồm nhiều ký tự bị
lặp lại liên tiếp. Ký tự đầu vào có thể ở dạng chữ trong bảng chữ cái, có thể là
các bit 0, 1 nhị phân; các thơng số về màu của các điểm ảnh, cũng có thể là
các khối hợp thành của dữ liệu kiểu âm thanh. Trên thực tế, thuật tốn này
vẫn còn được áp dụng cho tới ngày nay: thuật tốn HDC (hardware data
compression), được sử dụng trong các ổ băng kết nối với hệ thống máy tính
IBM, và cả thuật tốn tương tự được dùng trong chuẩn SNA (System network
architecture) của IBM.
1.2.2 Mã hóa Huffman
1.2.2.1. Mã Huffman tĩnh
* Ngun lý:
Ngun lý của phương pháp Huffman là mã hố các bytes trong tệp
dữ liệu nguồn bằng biến nhị phân. Nó tạo mã độ dài biến thiên là một tập
hợp các bits. Đây cũng là một phương pháp nén kiểu thống kê, những ký
tự xuất hiện nhiều hơn sẽ có mã ngắn hơn.
Mã Huffman có một tính chất quan trọng: mã của một ký hiệu này
khơng thể là phần đầu của mã một ký hiệu khác.
Nếu như một ký hiệu được mã hố bằng tổ hợp nhị phân 101 thì tổ
hợp 10110 khơng thể là mã của một ký hiệu khác trong tệp nguồn. Do đó
khi giải mã cần phải đọc lần lượt các bit cho đến khi gặp mã của ký hiệu
nào đó.

Bước 2: Tạo cây phân nhánh ngược với q trình nhóm từ nhánh
trái có mã 0, nhánh phải mã 1.
0 1
0 1 0 1

0 1 e a o

0 1 i

u ơ

Số hóa bởi trung tâm học liệu /> 8

{{{{u, ơ}, 1}, e}, {a, o}}
0 1
{{{u, ơ}, i}, e} {a, o}
0 10 1
{{{ u, ơ}, i}, e a o
0 1
{u, ơ} i
0 1
u ơ
Vậy mã của ký tự là: u -> 0000; e -> 01
ơ -> 0001; a -> 10
i -> 001; o -> 11
Thuật tốn nén:
Bước 1: Tìm hai ký tự có trọng số nhỏ nhất ghép lại làm một, trọng số của ký

Khái niệm cửa sổ χ:
Cửa sổ χ là một số lượng rất lớn các ký tự được thêm vào cây nhị phân
Huffman trong q trình nén văn bản.
Trong q trình nén dữ liệu, ta tiến hành thống kê các ký tự. Nhờ việc thống
kê này mà sinh ra bộ nén.
Thuật tốn nén:
Bước 1: Khởi tạo bảng mã Huffman(front tree) với ký tự đặc biệt, có số đếm
bằng 1.
Bước 2: Tạo mã thứ tự theo ngun tắc cân bằng.
Bước 3: While not eof(f) do
Begin
Getchar-> ch
If ch thuộc bảng mã thứ tự then
Begin
Ghi mã 0/1 của ký tự đó và ký tự đặc biệt ra tệp đích
Xóa ký tự đó ở bảng mã thứ tự, thêm ký tự đó vào bảng mã Huffman
(trong cây front tree) với số đếm bằng 1.
End Else
Begin
Số hóa bởi trung tâm học liệu /> 10

If ch thuộc bảng mã Huffman then
Begin
Tăng số đếm của ký tự đó lên một đơn vị
If số đếm của ký tự đó lớn hơn số đếm của ký tự ngay trên nó then
Begin
Đổi chỗ hai ký tự đó
End;
Ghi mã 0/1 của ký tự đó và ký tự đặc biệt ra tệp đích
End;

Lấy ra lần lượt từng ký tự và gán chuỗi ư cho đến khi gặp ký tự đặc
biệt.
If ký tự đặc biệt đó chỉ tới bảng mã thứ tự then
Begin
Tra trong bảng mã thứ tự và ghi ký tự đó ra tệp đích.
Thêm ký tự đó vào bảng mã Huffman với số đếm bằng 1.
End;
If ký tự đặc biệt đó chỉ tới bảng mã Huffman then
Begin
Tra trong bảng mã Huffman và ghi ký tự đó ra tệp đích.
Tăng số đếm của ký tự lên 1 đơn vị.
If số đếm của ký tự đó lớn hơn số đếm của ký tự trên nó then
Begin
Đổi chỗ.
End;
End;
If số lượng ký tự trong bảng mã Huffman>=χ then
Begin
Tìm ký tự nào đó giảm đi 1 đơn vị.
If số đếm của ký tự đó < số đếm của ký tự đứng trước nó then
Begin
If bên dưới nó là ký tự đặc biệt then
Giảm số đếm của ký tự đặc biệt đó đi 1.
Đổi chỗ hai ký tự đó.
End;
If số đếm của ký tự đó sau khi giảm đi 1 bằng khơng then
Begin
Số hóa bởi trung tâm học liệu /> 12

Tăng số lượng ký tự ở cây thứ tự lên một.

Số hóa bởi trung tâm học liệu /> 13

đọc ký tự đầu tiên -> w
Bước 2: While not eof(f) do
Begin
Đọc một ký tự -> ch
if t=false then w:=w+ch
else
begin
w:=ww+ch;t:=false;
end;
TIMCHU(w,tl);
If tl=false then
Begin
Code(ư,j);
Ghi j ra tệp nén.
Thêm w vào từ điển.
w:=ch;
end else
begin
ww:=w;
t:=true;
end;end;
Bước 3: Code(ch), Dừng chương trình.

Thuật tốn giải nén:
Bước 1: Đọc thơng tin từ điển ở trong tệp nén, đọc byte tiếp theo và giải
nén gán vào w, t=false;
Bước 2: While not eof(f) do
Begin

chương trình nhanh nếu chúng ta sử dụng cấu trúc cây( nhị phân, tam phân).
Một trong những ưu điểm nữa là thuật tốn có hiệu quả nén cao.
1.2.4. Phương pháp mã hóa số học (Arithmetic Coding)
Phương pháp này giống với mã hóa Huffman ở chỗ nó cũng dựa trên
bảng chữ cái và tần số xuất hiện của từng chữ, nó cũng có thể áp dụng dạng
động hoặc dạng tĩnh dựa vào việc thay đổi các khoảng tần số trong q trình
mã hóa.
Số hóa bởi trung tâm học liệu /> 15Mục đích của phương pháp là tìm ra một khoảng duy nhất thể hiện một
chuỗi ký tự có độ dài cố định, tiếp theo cần chọn trong khoảng này một số
thập phân thích hợp, và coi đấy là mã biểu diễn cho chuỗi ký tự trên. Q
trình mã hóa được khởi tạo với khoảng ban đầu là [0, 1).
Ví dụ:
Cho tần số xuất hiện ký tự A là 1/4 và tần số xuất hiện ký tự B là 3/4.
Xét việc mã hóa trong trường hợp chuỗi mã hóa là những ký tự đơn.
Chia [0, 1) thành hai nửa, nửa [0, 1 4) biểu diễn cho A và nửa [1 4 , 1)
biểu diễn cho B. Có thể chọn mã hóa cho A là 0, và cho B là 0.5.

0 1
0 A 1/4 B 1
Cho tần số xuất hiện ký tự A là 1/4 và tần số xuất hiện ký tự B là 3/4.
Xét việc mã hóa trong trường hợp chuỗi mã hóa là hợp thành của 2 ký tự một
p
A
=1/4, p

= 9/16 0 1

A B AB BA BB
Số hóa bởi trung tâm học liệu /> 16

Sau khi đã chia được các khoảng cho mỗi ký tự đơn, tiếp tục chia các
khoảng của bước trước cho 2 ký tự ghép. Cụ thể là khoảng [0, 1/ 4) của A
được chia thành hai khoảng cho AA, AB dựa vào tần số xuất hiện của chúng.
Thực hiện chia khoảng cho BA, BB dựa vào khoảng chia cho B tương tự.
Thuật tốn tổng qt:
Cho bảng chữ cái S = (s
1
, s
2
, … , s
n
) và tần số xuất hiện từng ký tự là
P = (p
1
, p
2
, … , p
n
). Dựa vào tần số xuất hiện để chia khoảng [0,1) thành n

đó Ω là tập các đoạn bit 0/1. Việc nén sẽ tối ưu khi chúng ta phân được
đoạn văn bản có độ dài lớn nhất mà sao cho khi đi tìm trong q khứ thì
chúng ta được đoạn 0/1 trong Ω là nhỏ nhất.
Trong kỹ thuật từ điển, tương tự như kỹ thuật thống kê, ta cũng có
hai phương án sau:
+ Mã tĩnh (từ điển tĩnh).
+ Mã động (từ điển động).
1.2.5.1. Từ điển tĩnh
Mã có từ điển cố định được gọi là mã tĩnh hay nói cách khác là từ
điển tĩnh.
Một số những nhược điểm của từ điển tĩnh:
+ Kích thước của từ điển tĩnh khơng thể mở rộng ra, để cập nhật các
thơng tin mới so với các loại dữ liệu khác.
+ Q trình nghiên cứu thiết kế từ điển đòi hỏi nhiều cơng sức.
+ Các thuật tốn sử dụng từ điển tĩnh chạy tương đối chậm.
+ Tốn khơng gian lưu trữ dữ liệu.
Số hóa bởi trung tâm học liệu /> 18

Tuy nhiên bên cạnh những nhược điểm này thì từ điển tĩnh cũng có ưu
điểm là: Thiết kế các thuật tốn áp dụng cho việc tìm kiếm trên từ điển
tĩnh đơn giản tốn ít thời gian.
Do những đặc tính hạn chế của từ điển tĩnh, kết hợp với những đặc
điểm nổi bật của thuật tốn nén là "sự cứng nhắc" đã làm cho người dùng
chương trình để tiết kiệm bộ nhớ nhàm chán khơng thích sử dụng các
chương trình nén nữa. Vậy phải có cách để khắc phục những hạn chế đó
và làm cho chương trình nén dữ liệu trở nên mềm dẻo hơn. Chính vì vậy
những thuật tốn nén chỉ đạt hiệu quả cao nếu chúng ta xử lý tốt "từ điển"
được sử dụng trong các thuật tốn nói chung.
1.2.5.2. Từ điển động
Để khắc phục những hạn chế của từ điển tĩnh, biện pháp được xét

+ Sử dụng loại mã có chiều dài thay đổi:
Phương án này nảy sinh một vấn đễ là chiều dài mã là bao nhiêu
hay nói cách khác đó là kích thước của mảng làm từ điển có phạm vi bao
nhiêu là phù hợp?. Nếu kích thước của từ điển nhỏ thì có ưu điểm trong
việc tìm kiếm trên từ điển vì vậy thuật tốn chạy nhanh khắc phục được
một hạn chế của thuật tốn nén là thời gian. Ngược lại nếu chúng ta sử
dụng một từ điển có kích thước lớn thì làm cho thuật tốn chạy chậm. Do
vậy chúng ta phải tìm ra kích thước của từ điển sao cho phù hợp để đảm
bảo thời gian thực hiện chương trình khơng q lâu mà vẫn đạt hiệu quả
nén cao. Để đạt được những u cầu trên người ta sử dụng loại mã có
chiều dài thay đổi từ 8 đến 13 bit. Có nghĩa là khi bộ nén dùng hết mã 8
bits thì nó sẽ dùng mã 9 bits, 10 bits, Tuy nhiên nếu dùng hết số bits cho
phép mà nguồn thơng tin vẫn còn thì chúng ta lại có cách giải quyết sau:
* Dừng q trình thêm các đoạn mới vào từ điển, tiến hành xố từ
điển hiện tại và bắt đầu xây dựng lại từ điển cho dữ liệu mới. Theo cách
Số hóa bởi trung tâm học liệu /> 20

nói trên thì phương pháp nén khá mềm dẻo nhưng hiệu quả nén lại khơng
cao do chúng ta khơng tận dụng được thơng tin trên từ điển cũ.
Tóm lại, mã có từ điển cố định được gọi là mã tĩnh và ngược lại nếu
từ điển biến đổi thì ta gọi đó là mã động.
Để tiến hành nén theo kỹ thuật từ điển ta có thuật tốn phân đoạn.
Đây chính là tiền đề cho hệ thống mã thuộc họ LZ. Thuật tốn phân đoạn
bao gồm 3 giai đoạn sau:
+ Bước 1: Phân đoạn văn bản theo một ngun lý nào đó.
+ Bước 2: Mã hố các đoạn văn bản đó.
+ Bước 3: Sử dụng một tập phân tích để nén.
Khơng thể có một cơ sở lý luận chắc chắn nào cho phép tìm thuật
tốn phân đoạn tốt nhất. Chúng ta cho rằng nếu xuất phát từ việc tìm lại
sự tương tự trong q khứ thì nén tìm sự tương tự nào gần giống nhất.

Plane - SMP), được dùng chủ yếu cho các loại chữ viết cổ, ví dụ Egyptian
hieroglyph (chưa được mã hóa), nhưng cũng còn được dùng cho các ký hiệu
Số hóa bởi trung tâm học liệu /> 22

âm nhạc. Mặt phẳng 2, (Supplementary Ideographic Plane - SIP), được dùng
cho khoảng 40000 chữ Trung Quốc ít gặp mà đa số là các ký hiệu cổ, ngồi ra
cũng có một số ký hiệu hiện đại. Mặt phẳng 14 hiện chứa một số các ký tự thẻ
ngơn ngữ khơng được khuyến khích và một số ký hiệu lựa chọn biến thể. Mặt
phẳng 15 và Mặt phẳng 16 được mở cho các sử dụng cá nhân.
Vẫn còn nhiều tranh luận giữa các chun gia về ngơn ngữ CJK (Hoa-
Nhật-Hàn), đặc biệt là các chun gia người Nhật, về nhu cầu và lợi ích kỹ
thuật của việc "thống nhất chữ Hoa", tức là việc chuyển những bộ chữ Hoa và
chữ Nhật vào trong một bộ chữ hợp nhất. (Xem thêm mã hóa chữ Hoa)
Kho ≈220 điểm mã bảo đảm sự tương thích với bộ mã UTF-16. Việc
mới chỉ dùng hết có 10% kho chữ cho thấy rằng kho chữ cỡ ≈20 bit này khó
bị đầy trong một tương lai gần.
2.1.1.2. Bảng mã
Unicode là một cách để đánh số duy nhất cho tất cả các ký tự được
dùng bởi con người trong ngơn ngữ viết. Nhưng những con số đó được ghi
trong các hệ thống xử lý văn bản lại là những vấn đề khác; những vấn đề đó là
hậu quả của việc phần lớn các phần mềm ở phương Tây chỉ biết tới các hệ
thống mã hóa 8-bit, và việc đưa Unicode vào các phần mềm chỉ mới diễn ra
chậm chạp trong những năm gần đây.
Các chương trình 8-bit cũ chỉ nhận biết các ký tự 8 bit, và khơng thể
dùng nhiều hơn 256 điểm mã nếu khơng có những cách giải quyết đặc biệt.
Do đó người ta phải đề ra nhiều cơ chế để dùng Unicode; tùy thuộc vào khả
năng lưu trữ, sự tương thích với chương trình nguồn và sự tương tác với các
hệ thống khác mà mỗi người chọn một cơ chế.
UTF-32
Số hóa bởi trung tâm học liệu /> 23