Luận văn tốt nghiệp Nén và xử lý dữ liệu
Chương I
PHẦN MỞ ĐẦU
1.1 - TẠI SAO PHẢI NÉN DỮ LIỆU
1.1.1 Khái niệm về dữ liệu
Trong một bài toán, dữ liệu bao gồm một tập các phần tử cơ sở mà ta
gọi là dữ liệu nguyên tử (atoms). Nó có thể là một chữ số, một ký tự... nhưng
cũng có thể là một con số, hay một từ..., điều đó tuỳ thuộc vào từng bài toán.
1.1.2. Mục đích của việc nén dữ liệu
Một trong những chức năng chính của máy tính là xử lý dữ liệu và lưu
trữ. Bên cạnh việc xử lý nhanh, người ta còn quan tâm đến việc lưu trữ được
nhiều dữ liệu nhưng lại tiết kiệm được vùng nhớ và giảm chi phí lưu trữ. Về
mặt lý thuyết thì các thiết bị lưu trữ là không có giới hạn nhưng ngày nay do
nhu cầu xử lý nhiều tập tin, nhiều loại dữ liệu trong cùng một tệp do vậy mà
kích thước tệp trở nên khá lớn.
Trong nhiều năm gần đây, mạng máy tính đã trở nên phổ biến trên thế
giới. Sự ra đời của mạng đã thực hiện được ước mơ chinh phục khoảng cách
giữa con người. Những lợi ích mà mạng cung cấp rất đa dạng và phong phú
trên các lĩnh vực khác nhau của xã hội như cung cấp, trao đổi thông tin giữa
các máy tính, giữa máy tính với server hoặc giữa các server với nhau. Điều
này dẫn đến phải làm như thế nào để giảm thiểu thời gian, chi phí sử dụng để
trao đổi dữ liệu trên mạng. Nó cũng đồng nghĩa với việc bên cạnh nâng cao
chất lượng của các thiết bị truyền dữ liệu trên mạng thì mặt khác chúng ta
phải nghĩ ra một phương pháp nào không để sao cho việc truyền dữ liệu có
hiệu quả hơn.
Tất cả những vấn đề trên nảy sinh ra khái niệm nén dữ liệu. Một trong
những hình thức nén dữ liệu đầu tiên là hệ chữ Braille, là một hệ chữ dùng
phương pháp mã hoá ký hiệu cho người mù có thể đọc và viết. Ngày nay, nén
dữ liệu mang lại rất nhiều lợi ích khác nhau mà điển hình là :
1
Luận văn tốt nghiệp Nén và xử lý dữ liệu

một phần tử Yi ∈ Y.
2
Luận văn tốt nghiệp Nén và xử lý dữ liệu
1.3 - NÉN KHÔNG BẢO TOÀN
Trong kỹ thuật nén, bên cạnh nén bảo toàn thì người ta còn đưa ra khái
niệm nén không bảo toàn. Nén không bảo toàn là mô hình nén dữ liệu mà
tính bảo toàn của dữ liệu không được coi trọng. Nó có nghĩa là nếu ta có tập
dữ liệu D, tập nén D' thì sau khi giải nén ta thu được tập D'' khác tập D ban
đầu. Kỹ thuật này thường áp dụng cho việc nén dữ liệu là các loại tệp ảnh vì
nói chung nó cũng không ảnh hưởng gì nhiều đến hình dạng ảnh. Nếu biểu
diễn bằng toán học, chúng có mô hình sau:
F(x) → { y
1
, y
2
, ...}
1.4 - QUÁ TRÌNH NÉN VÀ GIẢI NÉN
Quá trình nén dữ liệu là một quá trình gồm 2 công đoạn:
1) Công đoạn nén.
2) Công đoạn giải nén.
Chúng ta có thể minh hoạ như sau:
a) Công đoạn nén:
Dữ liệu → Mã hoá → Đóng gói → Dữ liệu nén.
b) Công đoạn giải nén:
Dữ liệu nén → Giải mã → Mã hoá → Dữ liệu gốc.
Hai công đoạn trên là 2 điển hình trái ngược nhau. Đối với tiến trình
nén thì module mã hoá thực hiện việc cắt văn bản nguồn thành các đoạn và
gán cho chúng ký hiệu để xác định chúng. Ngược lại đối với tiến trình giải
nén thì module giải mã sẽ dựa vào các mã mà module mã hoá ở tiến trình nén
sinh ra để tìm đoạn tương ứng. Quá trình tìm đoạn tương ứng đó được thực

4
Luận văn tốt nghiệp Nén và xử lý dữ liệu
cuốn truyện nào đó, nếu từ nào trong đoạn ta cảm thấy không thích thì ta có
thể tìm một từ hay hơn thay thế và rõ ràng sự thay đổi này không làm ảnh
hưởng đến nội dung cốt truyện mà nó chỉ ảnh hưởng tới một vài câu gần đó
mà thôi.
2.3. MÔ HÌNH PHỤ THUỘC XA
Một chương trình máy tính được viết bằng một ngôn ngữ lập trình nào
đó là một ví dụ về phụ thuộc xa. Với ngôn ngữ Pascal câu lệnh đầu tiên
"begin" và câu lệnh cuối "End" có mối liên quan trực tiếp đến nhau.
2.4. MÔ HÌNH PHÂN CẤP
Để minh hoạ cho mô hình này, chúng ta có thể thấy trong các kinh bản
của phim. Sự vận động của các nhân vật tuân thủ theo các quy luật về không
gian, thời gian, tâm lý, nhân quả... là một khái niệm phụ thuộc gần theo kiểu
nào đó và cũng chỉ là mục đích thể hiện 1 ý tưởng nào đó của tác giả. Ý
tưởng của các lập trình viên cũng là một ví dụ về mô hình phân cấp.
Định nghĩa mô hình nguồn.
Một bảng mã M được gọi là mô hình nguồn nếu nó thoả mãn các điều
kiện sau :
+ Nó phải là 1 hệ thống tín hiệu.
+ Phải tồn tại các quy tắc sinh tin.
+ Phải có quy tắc khởi đầu và kết thúc.
Hay nói cách khác 1 mô hình nguồn là tập hợp của 4 thành phần sau <
∑, ∆, I, R > trong đó : ∑, ∆ ≠ Φ ; ∑, ∆ không giao nhau.
+ Tập ∑ được gọi là từ điển cơ bản, mỗi phần tử của nó là phần tử kết
thúc.
+ Tập ∆ được gọi là từ điển hỗ trợ.
+ Ký hiệu I ∈ ∆ được gọi là ký hiệu ban đầu
+ R là tập các quy tắc sinh tin.
Trong kỹ thuật nén dữ liệu nếu chúng ta biết được mô hình nguồn sinh

Uses { các unit sử dụng }
Var { khai báo biến và thủ tục }
6
Luận văn tốt nghiệp Nén và xử lý dữ liệu
Begin { chương trình chính }
...............
End. { kết thúc chương trình }
2.5.3. Mô hình state : Do A.A.Markov (1856-1922) đưa ra.
* Định nghĩa :
Mô hình state là một đồ thị định hướng mà mỗi một cạnh có một nhãn
và một trọng số là xác suất chuyển trạng thái đọc theo hướng đó, tổng các xác
suất chuyển trạng thái để ra khỏi một đỉnh bất kỳ của đồ thị luôn luôn = 1.
Ví dụ:
a 0.5 a 0.2
a 0.2
b 0.3 d 0.3
c 0.5 a 0.2
c 0.8
Với mô hình trên, ta có thể có các chuỗi văn bản khác nhau như vậy với
một chuỗi văn bản bất kỳ thì luồng thông tin sinh ra từ mô hình trên đó là một
chu trình nào đó.
Mô hình state được gọi là xác định nếu có một số nguyên B đủ lớn sao
cho mọi dãy tên các cạnh do mô hình state sinh ra có độ dài lớn hơn B xác
định duy nhất một dãy các đỉnh các cạnh mà nó đi qua. Như thế luồng tin đủ
dài sẽ tương ứng với một chu trình nào đó đi qua dọc các đỉnh và các cạnh.
Entropy của luồng tin khi đó được định nghĩa thông qua entropy của chu
trình.
Vậy entropy là gì ? Chúng ta tiếp tục xem xét khái niệm về entropy.
Định nghĩa entropy:
Entropy là độ khó trung bình để đoán nhận 1 thông tin trạng thái được

75
49
)719()12730(
12730
=
++++
++
;
a
21
=
)719()12730(
719
++++
+
=
75
26
a
12
=
26
26
= 1 ; a
22
= 0
8
Luận văn tốt nghiệp Nén và xử lý dữ liệu
P =






λ−
λ−
0
75
26
1
75
49
= 0
Khai triển ra ta có phương trình sau :
0
75
26
75
49
2
=−λ−λ
nghiệm là :
λ
1
= 1 ; λ
2
= -
75
26
9

x
x
075/26
175/49
2
1
trong đó X
1
và X
2
là xác suất xuất hiện của trạng thái 1
và 2 nên λ ≥ 0 do đó ta chọn λ = λ
1
=1.
Giải hệ phương trình trên với λ = 1 do X
1
+ X
2
= 1 =>
có No: X
1
=
100
75
; X
2
=
101
26
Bước 4 : Tính entropy cả từng trạng thái.

26
2612730
log
2612730
26
2
+++
+++
= 1.80096
- Trạng thái 2 :
E
2
=
7
719
log
719
7
19
719
log
719
19
22
+
+
+
+
+
= 0.84036

A- Mã ký hiệu:
Định nghĩa : Đó là một hệ thống quy ước các mã được sử dụng để nhận
ra 1 chuỗi các sự kiện khác nhau thì được gọi là ký hiệu. Mã ký hiệu là 1 hình
thức của phương pháp nén dữ liệu.
Mã ký hiệu xuất hiện hàng ngày xung quanh chúng ta.
Ví dụ : Trong văn bản Nhà nước thường có cụm từ :
CV → công văn ; QĐ → quyết định
TTCP → Thủ tướng Chính phủ ...
Với các nước phát triển, hệ thống chuẩn hoá ký hiệu cho phép dùng
chúng một cách dễ dàng và tiết kiệm như trong lĩnh vực điện tín, telex, thư
11
Luận văn tốt nghiệp Nén và xử lý dữ liệu
điện tử, ... Xét về các mặt khác nhau mà mã ký hiệu được áp dụng thì mã ký
hiệu cung cấp thông tin cho chúng ta đầy đủ hơn, nó dễ dàng gợi nhớ trí nhớ
của mọi người do vậy lưọng thông tin từ mã ký hiệu sinh ra là rất lớn.
Một số đặc điểm của mã ký hiệu:
+ Tiết kiệm bộ nhớ, tiết kiệm thời gian.
+ Tính nguyên thủy của mã.
+ Tính tương đối của hệ thống mã.
Nhờ những đặc điểm trên mà mã ký hiệu được sử dụng nhiều trong lĩnh
vực như quản lý dữ liệu, quản lý dân sự, quản lý việc mua bán hàng hoá...
* Tính nguyên thuỷ của mã được xem xét như sau:
Một trong những lĩnh vực sử dụng mã ký hiệu nhiều nhất là quản trị dữ
liệu. Dữ liệu là đặc tính của đối tượng quản lý và được chia ra làm 2 đặc tính
sau:
* Quản lý sự vật:
Sự vật là các chủ thể mà chúng ta gọi nó là các thực thể.
* Quản lý sự việc :
Sự việc các hoạt động biên nhận ghi lại sự tương tác của các sự vật
được gọi là các form.

a b c d u
100 10001 01 001 0010111010011010101
Trong hình thức này chúng ta có các kỹ thuật đóng gói khác nhau
nhưng phổ biến vẫn là kỹ thuật đóng gói định lượng.
+ Khái niệm đóng gói định lượng:
Đóng gói định lượng là cách thức chúng ta qui định số byte dành
cho các ký tự được ghi trong tệp nén.
Đặc điểm của mã đóng gói định lượng:
+ Phương pháp nén không mềm dẻo.
+ Hiệu quả nén chưa cao.
13
Luận văn tốt nghiệp Nén và xử lý dữ liệu
+ Thời gian chạy nhanh.
Ví dụ:
Chúng ta xét đầu ra của thuật toán L778 của 1 xâu ký tự
"aaabbabaabaaabab" là:
(0+a) (10 + b) (3 + a) (4 + a) (5 + a) (4 + b).
Nếu ta ghi mỗi ký tự là 1 byte thì sẽ dẫn tới kích thước của tệp nén
có thể to hơn kích thước cuả tệp trước khi nén đồng thời chúng ta cũng sẽ
gặp một số khó khăn trong việc giải nén. Vì vậy đóng gối cũng là một
khâu quan trọng trong việc nén dữ liệu.
Trong phương pháp định lượng chúng ta phải có một số qui ước
nhất định để đóng gói các ký tự đó sao cho tốn ít bộ nhớ nhất. Như ở ví dụ
trên nếu chúng ta đóng gói các con số nằm trong khoảng 1- 2 byte và các
ký tự chúng ta cố định rất nhiều do vậy mà hiệu quả nén cao. Với qui
nước trên, chúng ta có đầu ra là: 0a1a3a4a5a4b.
Bên cạnh khái niệm đóng gói định lượng thì ta cũng có khái niệm
đóng gói tự động.
*Định nghĩa:
Đóng gói tự động là hình thức chương trình tự tạo ra các byte theo

+Ví dụ:
Dãy nguồn: ..SSOOOOONNNLLLLLLAAANNN..
Dãy nhận được sau khi nén:
.... HH CS S O NNN CS 6L AAAN...
Tuy nhiên phương pháp này cũng có nhiều khuyết điểm. Trước hết
là ký tự đặc biệt không được phép xuất hiện trong tệp dữ liệu nguồn. Nếu
ký tự đó xuất hiện với tư cách là dữ liệu thì khi gỡ nén nó sẽ dẫn đến tình
trạng nhập nhằng.
Ngoài ra người ta còn chú ý đến chỉ số lặp. Nếu chỉ số lặp được lưu
trữ trên 1 byte thì số lần lặp của một ký tự không vượt qua 255.
Khi số lần lặp của một ký tự vượt quá 255 thì chỉ số lặp sẽ được lưu
trữ trên 2 byte. Trong trường hợp này, chỉ số lặp tối đa sẽ được nâng lên
15
Luận văn tốt nghiệp Nén và xử lý dữ liệu
thành 65535. Tuy nhiên trong thực tế sẽ số lần lặp của một ký tự thường ≤
255 -> quá trình nén sẽ chiếm 1 byte vô ích.
Dựa vào những đặc điểm trên ta thấy phương pháp mã hoá theo độ
dài không được lợi nhiều trong việc nén tệp văn bản.
Nhưng đối với những tệp hình ảnh thì phương pháp này lại có hiệu
quả cao vì ảnh đen trắng là dãy các số 0 (điểm đen) và các số 1 (điểm
trắng) đan xen nhau. Trong trường hợp này việc đếm số lần xuất hiện liên
tiếp của các số 0 và số 1 tương đối dễ dàng và khi mã hoá không cần ký tự
đặc biệt cũng như không cần phải chỉ rõ ký tự lặp là ký tự nào mà chỉ cần
ghi số lần xen kẽ.
+ Ví dụ:
Nguồn: 0000000000 11111111 00000 111111
=> sẽ có mã: 10 8 5 6
N... với hình ảnh mà điểm đầu tiên không phải là điểm đen như ví
dụ trên thì phải bắt đầu dãy mã bằng 1 số 0.
+ Ví dụ : Nguồn: ... 00 .. 0 11111100 ...

In dem;
In ktlap;
End;end;
for |:= 1 to dem do
In ktlap
End;
Dem: = 1
ktlap := kt
End;
* Giải nén:
Tệp nén: f
Ký tự đặc biệt: db
Số lần lặp: dem
17
Luận văn tốt nghiệp Nén và xử lý dữ liệu
db = 255
While not eof (f) do
begin
Đọc ký tự trong f là kt;
If kt:=db then
begin
Đọc ký tự tiếp - dem;
Đọc ký tự tiếp - ktlap;
for | = 1 to dem do
In ktlap
else
Đọc ký tự tiếp;
end;
End ;
Trong phương pháp này, người ta sử dụng ký tự đặc biệt với tư cách

2 phương pháp sau:
- Mô hình tĩnh: Đó là mô hình tìm được thông qua nghiên cứu các
đặc trưng thống kê của văn bản rồi sau đó sử dụng chúng.
- Mô hình thích ứng: Mô hình thích ứng có xuất phát điểm là một
mô hình tổng quát nào đó sau đó hiệu chỉnh dần.
- Đặc điểm của mô hình thích ứng:
+ Mô hình thích ứng dựa vào thống kê của một số rất lớn các văn
bản cùng loại và áp dụng cho văn bản mới. Ưu điểm của phương pháp này
là trình nén dãn chạy nhanh.
+ Dựa vào mô hình nén giả định để chúng ta tính giá trị các trọng
tải và tiến hành nén.
3.3.1. Nén dữ liệu có mô hình nguồn
Một trong những đặc điểm của việc nén dữ liệu này là cả người nén
cùng biết nguồn sinh ra tin. Những thuật toán nén dữ liệu đặc trưng cho
việc nén dữ liệu có mô hình nguồn này là:
19
Luận văn tốt nghiệp Nén và xử lý dữ liệu
+ Thuật toán Fano - Shannon
+ Thuật toán Huffman.
3.3.2. Nén dữ liệu chưa có mô hình nguồn
Một trong những ví dụ điển hình về nén chưa có mô hình nguồn là
ngôn ngữ tự nhiên. Chúng ta luôn rơi vào tình trạng có văn bản mà không
có mô hình nguồn. Để tìm ra một thuật toán nén tốt nhất thì chúng ta phải
tìm ra qui luật của chúng. Qua nghiên cứu có thể rút ra được hai cách tiếp
cận sau:
a. Cách tiếp cận tổng thể:
Cách tiếp cận này còn được gọi là phương pháp thống kê. Cách này
dựa vào nhận xét tinh tế, đó là những gì đã xảy ra trong quá khứ thì sẽ xảy
ra trong tương lai. Điều này cũng đã được thừa nhận trên thực tế mà đặc
trưng là những câu tục ngữ của cha ông chúng ta được đúc kết từ nhiều

hiện tuy rất nhỏ nhưng vẫn phải lớn hơn 0".
Điểm mấu chốt này được gọi là “zero - frequency problem”. Vấn đề
này cho đến nay vẫn đang được tìm hiểu và chưa được chứng minh.
- Thuật toán nén động
1. Thống kê các ký tự có trong văn bản để tạo mô hình mới.
2. Nén mô hình mới vừa xây dựng ở bước một.
3. Lặp lại bước một và bước hai cho đến hết.
Tóm lại, trên thực tế những kỹ thuật tiếp cận tổng thể (kỹ thuật
thống kê) được áp dụng rất ít do các thuật toán chạy chậm vì các chương
trình viết theo kỹ thuật trên phải thực hiện một số lượng lớn các phép tính
toán và mặt khác hiệu quả nén lại không cao.
b. Cách tiếp cận đi từ chi tiết:
Cách tiếp cận này dựa vào những nhận xét phụ thuộc ở thời điểm
hiện tại cũng tương tự một thời điểm nào đó trong quá khứ. Nói theo một
cách khác thì cách tiếp cận này dựa vào những qui luật nhất định. Các qui
luật gộp lại thành từ điển nên ta có thể gọi cách tiếp cận này là phương
pháp từ điển mà chúng ta có thể xem xét kỹ hơn ở phần sau.
21
Luận văn tốt nghiệp Nén và xử lý dữ liệu
3.4. KỸ THUẬT TỪ ĐIỂN
Kỹ thuật này đã được 1 bài báo xuất bản vào năm 1967 khẳng định:
"Phương pháp nén tốt nhất có thể đạt được đó là việc thay thế các xâu ký
tự thường xuyên lặp đi, lặp lại nhiều lần bằng chỉ số mà nó đã xảy ra
trong quá khứ". Phương pháp thay một đoạn ký tự bằng vị trí một đoạn
giống hệt nó trong quá khứ được gọi là Ziv - Lempel do 2 nhà bác học
Jacob Zib và Abraham Lempel phát triển năm 1977. Như vậy ta có:
Kỹ thuật từ điển là kỹ thuật sử dụng phương pháp phân đoạn văn
bản thành các đoạn nhỏ hơn sao cho nó đạt được độ dài nhất có thể được
mà nó đã xuất hiện ở trong quá khứ.
Định nghĩa (phân đoạn văn bản)

được sử dụng trong các thuật toán nói chung.
3.4.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
đến là:
Chúng ta không thiết kế một từ điển sẵn mà " từ điển" đó được xây
dựng trong quá trình chạy chương trình. Một từ điển như vậy người ta gọi
là từ điển động.
Những đặc điểm chính của từ điển động:
+ Kích thước của từ điển có thể thay đổi tuỳ theo kích thước của tập
tin.
+ Không tốn thời gian lưu trữ từ điển.
+ Thời gian thực hiên quá trình nén nhanh.
+ Từ điển không phụ thuộc vào kiểu dữ liệu.
+ Thời gian thực hiện quá trình giải nén chậm.
23
Luận văn tốt nghiệp Nén và xử lý dữ liệu
Với từ điển động thì không những làm cho thuật toán nén đạt hiệu
quả cao hơn, khắc phục được sự cứng nhắc của thuật toán nén, góp phần
làm cho thuật toán trở nên mềm dẻo hơn. Nhưng kích thước cảu từ điển
tăng lên rất nhanh khi các tập tin đem nén mà độ dư thừa của chúng không
cao. Vậy để tăng kích thước của từ điển và không làm cho chúng lớn quá
mức bộ nhớ mà máy tính có thì chúng ta phải thực hiện xử lý từ điển sao
cho lượng thông tin mà từ điển đó đem lại nén đạt hiệu quả cao và cải
thiện sự cứng nhắc của thuật toán nén. Như chúng ta đều biết, việc nén dữ
liệu chẳng qua là việc mã các thông tin thương xuyên xuất hiện bằng một
từ mã ngắn và thông tin ít xuất hiện bằng từ mã dài và được lưu trữ trong
một từ điển. Vậy chúng ta có một số phương án sau:
+ Sử dụng loại mã có chiều dài cố định:
Trong phương án này, số bits cần nén dữ liệu cần được quyết định
trước khi tiến hành nén. Nén sử dụng số bits ít thì từ điển sẽ nhanh chóng

Không thể có một cơ sở lý luận chắc chắn nào cho phép tìm thuật
toá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 quá khứ thì nén tìm sự tương tự nào gần giống nhất.
Chính vì thế mà các khúc khi phần ra từ văn bản nguồn nên được tính
toán sao cho chúng là các phần dài nhất có thể lặp lại được trong quá khứ.
Nguyên lý như trên được gọi là nguyên lý kinh nghiệm.
3.4.3. Mã LZ với từ điển tĩnh
Trước hết chúng ta định nghĩa lại khái niệm từ điển tĩnh.
Định nghĩa từ điển tĩnh:
Từ điển tĩnh là từ điển đã được xây dựng từ trước, nó là kết quả của
việc nghiên cứu rất lớn các văn bản.
Định lý LZ:
Giả sử ta có từ điển S gồm n chuỗi ký tự và một luồng thông tin Z
có cùng phân số. Giả sử l là độ dài xâu lớn nhất mà có thể lấy được từ
25

Trích đoạn Thuật toán LZ78: Thuật toán LZW:

---