ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN

Vũ Văn Minh ĐỀ TÀI
ỨNG DỤNG PHƯƠNG PHÁP
MOVE-TO-FRONT TRONG NÉN DỮ LIỆU
Chuyên ngành: Bảo đảm toán học cho máy tính
và hệ thống tính toán
Mã số: 60.46.35

LUẬN VĂN THẠC SĨ KHOA HỌC

NGƯỜI HƯỚNG DẪN KHOA HỌC
GS.TSKH. Nguyễn Xuân Huy Hà Nội, năm 2011
Ứng dụng phương pháp Move to front trong nén dữ liệu
3

DANH MỤC HÌNH VẼ, BẢNG BIỂU 6
DANH MỤC CÁC TỪ VIẾT TẮT 7
Mở đầu 8
Chương 1. TỔNG QUAN VỀ NÉN DỮ LIỆU 9
1.1 Thông tin, dữ liệu và mã hóa 9
1.2 Dữ liệu ký hiệu 10
1.3 Sự thay đổi độ dài mã 11
1.3.1 Tính duy nhất để giải mã 11

2.4.2 Mã hóa 39
2.4.3 Giải mã 42
2.5 Phép biến đổi Move-To-Front (MTF) 45
2.5.1 Giới thiệu MTF 45
2.5.2 Mã hóa 45
2.5.3 Giải mã 47
2.6. Phân tích phương pháp MTF 48
2.6.1. Tổ chức dữ liệu 48
2.6.2. Thực hiện 49
2.7 Lược đồ nén dữ liệu ứng dụng phương pháp MTF 49
2.7.1 Lược đồ nén dữ liệu 49
Ứng dụng phương pháp Move to front trong nén dữ liệu
5
2.7.2 Nén dữ liệu 50
2.8 Một số cải tiến phương pháp MTF 51
2.8.1 Một số định nghĩa 51
2.8.2 Cơ sở MTF 52
2.8.3 Một số cải tiến MTF 53
Chương 3. KẾT QUẢ THỰC NGHIỆM 55
3.1. Môi trường thực nghiệm 55
3.2 Dữ liệu mẫu 55
3.3 Phân tích thực nghiệm kết quả 56
3.3.1 Áp dụng MTF với thuật toán nén Huffman 56
3.3.1 Áp dụng MTF với thuật toán nén số học 58
3.4. Kết luận 59
PHỤ LỤC 62
Ứng dụng phương pháp Move to front trong nén dữ liệu

Bảng 13. Số lần xuất hiện các ký hiệu sau khi sử dụng MTF 64

Ứng dụng phương pháp Move to front trong nén dữ liệu
7
DANH MỤC CÁC TỪ VIẾT TẮT
TT
Từ viết tắt
Viết đầy đủ
1
ASCII
American Standard Code for Information Interchange
2
BIT
BInary digiT
3
BMRH
BWT- MTF- RLE- Huffman
4
BRH
BWT - RLE- Huffman
5
BWCA
Burrow-Wheeler Compression Alogrithm
6
BWT
Burrow-Wheeler Transform
7
EC
Entropy Coding
8

Burrow-Wheeler transform [9] được giới thiệu lần đầu tiên vào năm 1994 bởi hai
tác giả là Burrow và Wheeler, BWT biến đổi vị trí các ký hiệu sao cho các ký hiệu
giống nhau sẽ đứng cạnh nhau, bước tiếp theo của thuật toán này là phương pháp
MTF, phương pháp này xử lý dữ liệu đầu ra của phương pháp BWT để được dữ liệu
có khả năng nén cao hơn với mã nén Entropy (một cách khác của thuật toán BWCA
có thêm bước mã nén theo độ dài – Run-Length Encoding (RLE)). Ngày nay,
phương pháp BWT kết hợp MTF được ứng dụng để nén với nhiều loại dữ liệu khác
nhau như văn bản, hình ảnh, âm thanh hoặc phim. Luận văn này tập trung nghiên
cứu phương pháp MTF và một số cải tiến của phương pháp này trong nén văn bản
để đạt được hiệu quả cao hơn.
Ứng dụng phương pháp Move to front trong nén dữ liệu
9
Chương 1. TỔNG QUAN VỀ NÉN DỮ LIỆU
1.1 Thông tin, dữ liệu và mã hóa
Thông tin là một thể hiện về kiến thức và tư duy của con người hiểu biết về
các trạng thái của hệ thống – đó là các thông tin không chắc chắn. Con người cảm
nhận được sự tồn tại của thông tin, nhận biết được sự đa dạng các phương tiện mang
thông tin và bất cứ lúc nào cũng nhận thấy sự tác động ngược trở lại của thông tin
đối với con người – đó là các thông tin chắc chắn.
Thông tin không hiện hữu như các thiết bị vật lý, nó tồn tại như một dữ liệu
logic được chứa trong các phương tiện vật lý như đĩa CD hay các kênh truyền thông
tin. Vì thế dữ liệu được xem như dạng cơ bản của một số thông tin thực. Điều này
tạo nên sự khác biệt giữa các thông tin với nhau như văn bản, đồ họa, âm thanh,
hình ảnh… Một lượng lớn thông tin cần phải được tổ chức, lưu trữ dưới dạng các
tệp tin hoặc các thông điệp.
Ví dụ với dữ liệu “-30
0

ở dạng này biểu diễn bằng 8 BIT nhị phân 0 và 1.
1.2 Dữ liệu ký hiệu
Các ký hiệu hoặc ký tự sử dụng ở đầu vào của thuật toán nén dữ liệu là cách
thể hiện phù hợp cho thuật toán nén mà trong đề tài đề cập đến. Văn bản, hình ảnh,
âm thanh hay phim được xem xét như một khối dữ liệu bao gồm mảng một chiều
các ký tự được xét đến trong thuật toán.
Khối dữ liệu nguồn S=(s
1
, s
2
, s
3
, …. , s
n
) được coi là một chuỗi các ký tự s
1
,
s
2
, s
3
, …. , s
n
. Thể hiện dưới dạng số hóa của tập các ký tự trong S là C=(c
1
, c
2
, c
3
,

1.3.1 Tính duy nhất để giải mã
Thay đổi độ dài từ mã là rất tốt cho việc nén dữ liệu. Tuy nhiên thay đổi độ
dài từ mã sẽ là vô ích nếu như không xác định tính duy nhất các từ mã trong thông
điệp cần mã hóa. Nghĩa là các ký hiệu phải có từ mã duy nhất.
Xét các từ mã (0, 10, 010, 101) tương ứng với các ký tự (a, b, c, d). Một đoạn
mã hóa thông điệp là “0100101010” sẽ được giải mã với nhiều kết quả khác nhau
như “0 10 010 101 0” là abcda hoặc “010 0 101 010” là cadc.
Một mã có tính duy nhất để giải mã nếu chỉ có một cách duy nhất để giải mã
thông điệp đã mã hóa. Tất nhiên cũng có những cách khác để làm việc này, ví dụ
như thêm dấu “/” để phân cách các từ mã “0/10/010/101/0”, nhưng điều này sẽ phản
tác dụng khi ta nén dữ liệu, làm tăng dung lượng dữ liệu nén và khó khăn trong thao
tác nén và giải nén. Tuy nhiên điều này cho ta ý tưởng tự phân cách các ký tự trong
thông điệp giải mã bằng cách tổ chức dưới dạng cây nhị phân.
Tính chất tự phân cách được thể hiện rõ khi ta biểu diễn dưới dạng cây nhị
phân trong Hình 1. Mỗi nhánh con bên trái được ký hiệu là 0 và nhánh con bên phải
Ứng dụng phương pháp Move to front trong nén dữ liệu
12
được ký hiệu là 1. Trong suốt quá trình giải mã, mỗi từ mã thu được bằng cách đọc
lần lượt các bit 0 hoặc 1 từ nút gốc đến nút lá, đọc tới nút lá ta coi như hết từ mã và
giá trị của nút là chính là ký hiệu cần giải mã.

Hình 1. Cây nhị phân trong mã Huffman
1.3.2 Mã tiền tố và cây nhị phân
Tiền tố là số các bit liên tiếp đứng trước từ mã. Khi có hai từ mã có độ dài
mã khác nhau, có thể từ mã ngắn lại chính là phần đứng trước của từ mã dài. Trong
trường hợp này từ mã ngắn được gọi là tiền tố của từ mã dài.
Ví dụ xét từ mã c
1
= 010 (độ dài mã là 3) và c
2

Ứng dụng phương pháp Move to front trong nén dữ liệu
13
mã tương ứng với nút con phải của cây nhị phân (Hình 2). Nếu trên đường đi tới các
nút lá là các từ mã thì đó là mã tiền tố.

Hình 2. Mã tiền tố

1.4 Cơ bản về lý thuyết thông tin
Lý thuyết thông tin là một ngành khoa học nghiên cứu về thông tin nhằm tạo
ra cơ sở hạ tầng tốt cho việc truyền thông chính xác, nhanh chóng và an toàn; lưu
trữ có hiệu quả. Các lĩnh vực nghiên cứu của lý thuyết thông tin là truyền thông,
nén dữ liệu và bảo mật thông tin. Điểm quan trọng trong lĩnh vực lý thuyết thông tin
là entropy được C.E.Shannon giới thiệu vào năm 1948 [4].
1.4.1 Entropy
Trong lý thuyết thông tin, Entropy mô tả mức độ hỗn loạn trong một tín hiệu
lấy từ một sự kiện ngẫu nhiên. Nói cách khác, entropy cũng chỉ ra có bao nhiêu
thông tin trong tín hiệu, với thông tin là các phần không hỗn loạn ngẫu nhiên của tín
hiệu.
Ví dụ, nhìn vào một dòng chữ tiếng Việt, được mã hóa bởi các chữ cái,
khoảng cách, và dấu câu, tổng quát là các ký tự. Dòng chữ có ý nghĩa sẽ không hiện
ra một cách hoàn toàn hỗn loạn ngẫu nhiên; ví dụ như tần số xuất hiện của chữ cái x
sẽ không giống với tần số xuất hiện của chữ cái phổ biến hơn là t. Đồng thời, nếu
Ứng dụng phương pháp Move to front trong nén dữ liệu
14
dòng chữ vẫn đang được viết hay đang được truyền tải, khó có thể đoán trước được
ký tự tiếp theo sẽ là gì, do đó nó có mức độ ngẫu nhiên nhất định. Entropy thông tin
là một thang đo mức độ ngẫu nhiên này.
Claude E. Shannon đã xây dựng định nghĩa về entropy để thoả mãn các giả
định sau:
• Entropy phải tỷ lệ thuận liên tục với các xác suất xuất hiện của các phần tử

, …, p
n
) thì ta có thể tính
độ dài trung bình của từ mã là và entropy được tính là H(P) =
.
Vì entropy cung cấp một giới hạn lý thuyết của số tối thiểu các bit thông tin.
Sự khác nhau giữa độ dài trung bình của một mã và entropy tương ứng với lượng
dư thừa trong từ mã.
Tính tỉ lệ phân trăm của entropy của dữ liệu nguồn với độ dài từ mã trung
bình:

Lý thuyết thông tin khẳng định rằng một lược đồ nén dữ liệu không mất mát
thông tin mã hóa nguồn dữ liệu với số lượng bit trung bình lớn hơn hoặc bằng
entropy của dữ liệu nguồn tức là E(P, L) nhỏ hơn hoặc bằng 100%. Khi khoảng
cách giữa entropy và độ dài trung bình mã lớn hơn thì giá trị E(P, L) nhỏ hơn.
Một mã được gọi là tối ưu nếu hiệu quả mã đạt 100%, nói cách khác một mã
gọi là mã tối ưu nếu độ dài trung bình các từ mã bằng entropy của dữ liệu nguồn.
1.5 Sự dư thừa dữ liệu
Công việc đầu tiên của nén dữ liệu là tìm ra sự dư thừa trong dữ liệu nguồn.
Thuật ngữ dư thừa là có nghĩa chung, có thể là một số thông tin lồng nhau, các dữ
liệu cơ sở chung, các định danh riêng biệt được lưu trữ ở bộ nhớ ngoài. Ta xem xét
cụ thể qua các ví dụ sau.
Ví dụ 1: Một chuỗi ký tự lặp lại liên tiếp nhau là “BAAAAAAAC”. Sự dư
thừa ở đây là 7 ký tự A có thể thay thế bằng chuỗi ngắn hơn như r
7
A
Ứng dụng phương pháp Move to front trong nén dữ liệu
16
Ví dụ 2: Một chuỗi ký tự không lặp lại liên tiếp “ABACAA” nhưng ta lại
thấy ký tự “A” là tiền tố của các từ khác. Có những ký tự xuất hiện thường xuyên

1.6.2 Nén có mất thông tin và nén không mất thông tin
Có rất nhiều phương pháp nén và giải nén dữ liệu, nhưng thường được phân
lại thành hai nhóm chủ yếu là nén dữ liệu có mất thông tin và nén dữ liệu không mất
thông tin.
Nén dữ liệu không mất thông tin là phương pháp nén dữ liệu mà khi khôi
phục dữ liệu ban đầu thì thông tin không bị mất, tức là không có thông tin nào bị
mất trong quá trình nén. Hình 3 minh họa nén dữ liệu không mất thông tin.

Hình 3. Nén dữ liệu không mất thông tin
Kỹ thuật nén dữ liệu không mất thông tin được sử dụng khi dữ liệu gốc là
quan trọng và không thể bỏ đi một chi tiết nào về dữ liệu. Ví dụ như các hình ảnh
chẩn đoán bệnh trong y học, các tệp tin thi hành trong máy tính, các văn bản và hình
ảnh vì lý do pháp luật nào đó.
Nén dữ liệu có mất thông tin là phương pháp nén mà không lấy lại được dữ
liệu nguyên bản khi giải nén. Một số chi tiết không quan trọng sẽ bị mất khi thực
hiện nén, các chi tiết không quan trọng khi bỏ đi không làm giảm đáng kể chất
lượng của dữ liệu nguồn. Hình 4 nén dữ liệu sẽ bỏ đi các số phần lẻ không cần thiết
để được một số ngắn hơn.
Nén dữ liệu
ABAAB
1000110110111
Giải nén
Ứng dụng phương pháp Move to front trong nén dữ liệu
18

Hình 4. Nén dữ liệu có mất thông tin
Nén dữ liệu có mất thông tin được áp dụng cho những dữ liệu mà khi quan
sát hoặc các dữ liệu tính toán phức tạp, sẽ loại bỏ đi các thông tin ít quan trọng hơn,
không cần độ chính xác cao. Các dữ liệu đa phương tiện như hình ảnh, âm thanh,
phim thường được áp dụng kỹ thuật nén có mất thông tin bởi vì liên quan đến tổ

bit nhị phân này, ông đề xuất cách tổ chức ký hiệu trên cây nhị phân dựa vào tần
suất xuất hiện các ký hiệu. Xét chuỗi ký hiệu “BURROW WHEELER” được nói
chi tiết hơn trong phần 2.2.2 của luận văn này; Bảng sau đây mô tả về từ mã và độ
dài từ mã tương ứng với mỗi ký hiệu xuất hiện trong chuỗi “BURROW
WHEELER”
Ký hiệu
B
U
L
O
H
W
E
R
Số lần xuất hiện
1
1
1
1
1
2
3
3
Từ mã
1100
1101
0010
0011
000
111

phương pháp biến đổi dữ liệu đầu vào là phép biến đổi Burrow-Wheeler và Move to
front.
2.1 Thuật toán mã hóa độ dài (RLE)
2.1.1 Giới thiệu RLE
RLE (Run Length Encoding) là phương pháp mã hóa độ dài ký hiệu. Thuật
toán này nhận biết các ký hiệu xuất hiện thường xuyên liên tục và ghi nhận độ dài
của các ký hiệu này.
RLE rất có hiệu quả trong nén dữ liệu đối với dữ liệu xuất hiện liên tiếp các
ký hiệu như hình ảnh; Trong hình ảnh, ví dụ như màu nền của một bức tranh có rất
nhiều màu trùng nhau đứng cạnh nhau. Còn trong văn bản thì rất ít xuất hiện liên
tiếp ký hiệu. Vì vậy thuật toán RLE được sử dụng ngay sau phương pháp BWT. Bởi
vì phương pháp BWT tạo ra rất nhiều các ký hiệu lặp lại liên tiếp.
Ý tưởng chính của phương pháp RLE rất đơn giản, nếu có ‘aaaaaaa’ thì ta
kết xuất ra ‘aa’ và số lần xuất hiện ký hiệu này.

Hình 5. Phương pháp nén RLE (1)
Ở đây byte thứ ba trong dữ liệu nén là ký hiệu có số thứ tự trong bảng mã là
6. Nghĩa là ta coi số lần ký hiệu lặp là một byte nếu số lần lặp nhỏ hơn 256. Nếu số
lần lặp là lớn hơn 256 thì ta kết xuất ký hiệu gốc và số lần lặp là 255, sau đó phải
ghi nhận số lần lặp mới với ký hiệu gốc này. Điều này minh họa như sau:
RLE
a
a
6
Ứng dụng phương pháp Move to front trong nén dữ liệu
21

Hình 6. Phương pháp nén RLE (2)
Vấn đề nảy sinh đối với các ký hiệu không lặp lại thì ta không nên nén
chúng. Sau đây là bảng mô tả chi tiết với các trường hợp xuất hiện ký hiệu khác

a
4
Ứng dụng phương pháp Move to front trong nén dữ liệu
22
o Cập nhật con trỏ tới file nguồn
o Quay lại bước lặp.
Các ký hiệu sử dụng trong thuật toán:
in: tệp nguồn
out: tệp đích
c: ký hiệu đọc được từ tệp nguồn
prev: ký hiệu đứng trước ký hiệu c
rle_cnt: số lần lặp
Đoạn mã nguồn như sau:
if ((c=getc(in)) != EOF) {
putc((unsigned char) c, out);
prev = c;
}
else return;
while ((c=getc(in)) != EOF) {
if (c != prev) {
/* if there's a run, encode it. */
if (rle_cnt) {
putc((unsigned char) prev, out);
putc((unsigned char) rle_cnt-1, out);
rle_cnt = 0;
}
/* then encode the new byte. */
putc((unsigned char) c, out);
prev = c;
}

o Quay lại bước lặp.
Nếu không đúng
o Kết xuất byte Y
o Gán Y vào X.
o Quay lại bước lặp.
Ứng dụng phương pháp Move to front trong nén dữ liệu
24
Đoạn mã nguồn như sau:
if ((c=getc(in)) != EOF) {
prev = c;
putc((unsigned char) c, out);
}
else return;
while ((c=getc(in)) != EOF) {
if (c == prev) {
putc((unsigned char) prev, out);
// output the next "run" of bytes, as
// stored in the rle_cnt variable.
if ((rle_cnt = getc(in)) != EOF) {
while(rle_cnt ) {
putc((unsigned char) prev, out);
}
}
else break;
}
else {
putc((unsigned char) c, out);
prev = c;
}
}

3
1
Sau đó sắp xếp các ký tự theo tần số xuất hiện
B
U
L
O
H
W
E
R
1
1
1
1
1
2
3
3
Ta có bảng ký tự của dữ liệu nguồn là (B, U, L, O, H, W, E, R) với số lần
xuất hiện tương ứng là (1, 1, 1, 1, 1, 2, 3, 3). Khi đó ta xây dựng bảng ký tự có độ
dài mã thay đổi.
Dữ liệu vào của thuật toán Huffman là chuỗi ký tự. Dữ liệu ra là chuỗi các
bit nhị phân tương ứng với chuỗi ký tự vào. Để giải quyết vấn đề này ta xét ba vấn
đề nhỏ sau:
1. Đọc dữ liệu vào.
2. Mã hóa mỗi ký tự vào.
3. Kết xuất từ mã cho mỗi ký tự vào (nén).
Để giải quyết vấn đề 1 ta cần tổ chức dữ liệu vào sao cho có thể đọc được
từng ký tự ở chuỗi dữ liệu vào, trong luận văn này tác giả định dạng tệp tin dưới