LỜI CẢM ƠN
Em xin chân thành cảm ơn Ban chủ nhiệm khoa Công nghệ thông tin,
các thầy cô giáo, gia đình và bạn bè đã động viên và giúp đỡ em rất nhiều
trong quá trình hoàn thành khóa luận này. Đặc biệt em xin bày tỏ lòng cảm ơn
sâu sắc tới thầy giáo hướng dẫn Th.s Trần Tuấn Vinh đã tận tình và tận tâm
hướng dẫn em từ những ý tưởng ban đầu cho đến lúc hoàn thành khóa luận
quan trọng này.
Em rất mong đón nhận sự đánh giá, bổ sung và những lời chỉ bảo của
các thầy cô, giúp em có thể tiếp tục nghiên cứu kĩ hơn về lĩnh vực này.
Em xin chân thành cảm ơn!
Hà Nội, tháng 5 năm 2013
Sinh viên
Nguyễn Công Thành
1
LỜI CAM ĐOAN
Tên em là: Nguyễn Công Thành
Sinh viên: K35 – CNTT, trường Đại học Sư phạm Hà Nội 2.
Em xin cam đoan:
1. Đề tài “Tìm hiểu các thuật toán nén dữ liệu và xây dựng chương
trình ứng dụng” là kết quả tìm hiểu và nghiên cứu của riêng em dưới
sự hướng dẫn của Th.s Trần Tuấn Vinh.
2. Khóa luận hoàn toàn không sao chép từ các tài liệu có sẵn đã được
công bố khác.
3. Kết quả không trùng với các tác giả khác.
Nếu sai em xin hoàn toàn chịu trách nhiệm.
Hà Nội, tháng 05 năm 2013
Sinh viên
2.1. Phương pháp nén không tổn hao......................................................... 16
2.1.1. Mô hình thống kê ............................................................................ 16
2.1.2. Mô hình từ điển .............................................................................. 20
2.2. Phương pháp nén tổn hao ................................................................... 27
CHƯƠNG 3 ................................................................................................ 42
XÂY DỰNG CHƯƠNG TRÌNH NÉN DỮ LIỆU ..................................... 42
BẰNG MÃ HUFFMAN VÀ RUN-LENGTH ........................................... 42
3.1. Đặc điểm của các thuật toán nén dữ liệu ............................................. 42
3.2. Phân tích thuật toán ............................................................................ 43
3.2.3.1. Biến thể vào Run-length Encoding ............................................... 46
4
3.2.3.2.Gói Replication dọc ...................................................................... 48
CHƯƠNG 4 ................................................................................................ 50
HÌNH ẢNH MINH HỌA CÁC CHƯƠNG TRÌNH SỬ DỤNG THUẬT
TOÁN HUFFMAN VÀ RUN-LENGTH ................................................... 50
TÀI LIỆU THAM KHẢO.......................................................................... 54
5
MỞ ĐẦU
Ngày nay với sự tiến bộ của khoa học kĩ thuật, CNTT được nâng lên
một tầm cao mới. Mọi ngành, nghề đều phải ứng dụng CNTT một cách triệt
để để phát triển một cách tốt nhất. Ngay như cả cụm từ “ Chính phủ điện tử”
mà ta thường nghe cho ta thấy tầm quan trọng của việc đưa CNTT vào cuộc
sống. Không nằm ngoài sự phát triển có tính quy luật chung của xã hội,
CNTT đã và đang làm hết sức mình để phát triển ngày một tốt hơn, nhanh
hơn, nhẹ hơn, gọn hơn.... CNTT và Viễn thông có mối liên hệ tương đối chặt
Run-length và Huffman để so sánh tính hiệu quả của từng loại với một số loại
dữ liệu khác nhau.
- Hình ảnh minh họa của các chương trình sử dụng 2 thuật toán
Huffman và Run-length.
7
CHƯƠNG 1
SƠ LƯỢC NÉN DỮ LIỆU
1.1. Tổng quan về nén dữ liệu
Trong khoa học máy tính và lí thuyết thông tin, nén dữ liệu là quá trình
mã hóa thông tin dùng ít bít hơn so với thông tin chưa được mã hóa bằng cách
dùng một hoặc kết hợp phương pháp nào đó. Dựa theo nguyên tắc này giúp
tránh hiện tượng kênh truyền bị quá tải và truyền tin trở nên kinh tế hơn. Nén
dữ liệu giúp tiết kiệm tài nguyên như dung lượng bộ nhớ, băng thông, thời
gian. Ngược lại, dữ liệu đã được nén cần phải được giải nén để đọc (thực thi,
nghe, xem, v.v…), quá trình này cũng đòi hỏi các tài nguyên nhất định. Một
ví dụ điển hình là việc nén video đòi hỏi phần cứng đắt tiền để quá trình giải
nén đủ nhanh để ta có thể xem được. Do đó việc thiết kế một chương trình
nén dữ liệu phụ thuộc nhiều yếu tố như mức độ nén, độ méo (đối với nén có
tổn hao), tài nguyên hệ thống dùng để thực hiện quá trình nén và giải nén dữ
liệu.
1.2. Tổng quan các loại mã nén
1.2.1. Các chương trình nén hoạt động như thế nào?
Nguyên tắc của các chương trình nén nói chung giống nhau: Tận dụng
sự lặp lại của dữ liệu, các chuỗi dữ liệu lặp lại được thay thế bởi con trỏ
chung có độ dài bé hơn. Kỹ thuật này rất hiệu quả đối với dữ liệu dạng text,
bảng tính, hoặc file DBF (nén trên 70%), vì tính lặp lại của dữ liệu loại này
cao: File chương trình (.EXE hoặc .COM) nén được ít hơn.
nén file khá rườm rà, chính bởi lí do này mà các chương trình nén đĩa như
9
Stacker hoặc Super Store được sử dụng tương đối rộng rãi. Các chương trình
nén đĩa cũng hoạt động nguyên tắc giống như nén file, chỉ khác là chúng tự
động nén và bung mà người dùng không phải quan tâm đến. Thời gian và tỷ
lệ nén của các chương trình nén loại này khác nhau. Để bung 3,5 MB dữ liệu,
chương trình này hết 12 giây, chương trình khác 40 giây. Tỷ số nén đối với
file văn bản cũng khác: từ 2:1 đến 3:1. Tóm lại khi dùng chương trình nén đĩa,
người dùng yên tâm là dung lượng trống của ổ cứng dường như tăng khoảng 2
lần.
Việc bung và nén khi làm việc với file sẽ làm công việc chậm lại đôi
chút. Đối với các file dữ liệu lớn, điều này thể hiện khá rõ. Khi làm việc, các
chương trình nén đĩa hoạt động ở dạng thường trú, bởi thế một mặt nó chiếm
dụng bộ nhớ RAM, một mặt có thể xung đột với các chương trình thường trú
khác. Các chương trình nén file khi có sự cố chỉ hỏng một vài file, còn
chương trình nén đĩa làm hỏng cả ổ đĩa. Tuy điều này rất ít khi xảy ra nhưng
cũng làm cho nhiều người e ngại không dám dùng.
Để cài đặt chương trình nén đĩa cần phân chia lại ổ cứng vì máy tính
cần được khởi động bằng đĩa nén trước khi chương trình nén hoạt động. Nếu
dùng Windows thì phần mềm không nén cần khá lớn (thông thường cần dành
10 Mb cho vùng không nén, chỉ nén vùng đĩa còn lại).
Một điều có thể làm người dùng đau đầu là phải quyết định tỷ lệ nén là
bao nhiêu. Với tỷ lệ nén 10:1 chẳng hạn, chương trình nén sẽ dành nhiều “con
trỏ” để trỏ đến các dữ liệu, mỗi con trỏ chiếm 2 byte, khi đó dễ xảy ra trường
hợp không đủ con trỏ, chương trình báo đĩa đầy mà thực ra không phải như
vậy.
Cuối cùng, việc loại bỏ chương trình nén đĩa khi đã cài đặt cũng là một
vấn đề hơi phiền toái. Nhiều chương trình – chẳng hạn Double Density có
Trong một dãy kí tự, có một số kí tự có tần suất xuất hiện nhiều hơn
một số dãy khác. Do vậy, ta có thể mã hóa dữ liệu một cách cô đọng hơn. Các
kí tự có tần suất xuất hiện cao hơn được thay thế bởi một từ mã nhị phân với
số bit nhỏ. Ngược lại các dãy có tần suất xuất hiện thấp được mã hóa bởi từ
mã có nhiều bit hơn. Đây chính là bản chất của phương pháp mã hóa Huffman
hay Shanon – Fano.
1.2.3.2. Sự lặp lại của các kí tự
Trong một số tình huống, 1 kí hiệu (bit “0” hay bit “1”) được lặp lại
một số lần. Kĩ thuật nén trong trường hợp này là thay thế dãy lặp đó bằng dãy
lặp mới gồm hai thành phần: số lần lặp và kí hiệu dùng để mã hóa. Phương
pháp mã hóa này gọi là mã hóa loạt dài RLE (Run-length Encoding).
1.2.3.3. Những mẫu sử dụng tần suất
Có thể dãy kí hiệu nào đó xuất hiện với tần suất tương đối cao. Do vậy
có thể mã hóa bởi ít bit hơn. Đó là cơ sở của phương pháp mã hóa theo kiểu
từ điển do Lempel – Ziv đưa ra và có cải tiến vào năm 1977, 1978 do đó có
tên gọi là phương pháp nén LZ77, LZ78. Năm 1984, Terry Welch đã cải tiến
hiệu quả hơn và đặt tên là LZW (Lempel – Ziv – Welch). Thuật toán nén dữ
12
liệu vào mẫu sử dụng tần suất hiệu quả phải kể đến phương pháp nén dữ liệu
của Shanon – Fano và Huffman.
1.2.3.4. Độ dư thừa vị trí
Do sự phụ thuộc lẫn nhau của dữ liệu, đôi khi biết được 1 kí hiệu (giá
trị) xuất hiện tại một vị trí, đồng thời có thể đoán trước sự xuất hiện của các
giá trị ở vị trí khác nhau một cách phù hợp. Chẳng hạn, ảnh biểu diễn trong
một lưới hai chiều, một số điểm ở hàng dọc của khối dữ liệu lại xuất hiện
trong cùng một vị trí ở các hàng khác nhau. Do vậy lưu trữ dữ liệu ta chỉ cần
lưu trữ vị trí hàng và cột. Phương pháp nén dựa trên sự dư thừa này gọi là
phương pháp mã hóa dự đoán.
6. Prudition by partial matching (PPM)
7. Context mixing (CM)
8. Entropy encoding
9. Huffman coding (Huffman động được dùng ở bước cuối cùng của quá
trình nén file gồm nhiều bước)
10. Adaptive Huffman
11. Arithmetic
12. Shannon-Fano coding.
13. Range coding.
14
1.3.1.2. Các thuật toán nén tổn hao
Trong các phương pháp nén tổn hao thì dữ liệu được nén khi giải nén ra
sẽ không giống với dữ liệu gốc, tuy nhiên phải đảm bảo dữ liệu sau khi nén
vẫn còn hữu ích. Đối với hình ảnh, âm thanh, video, do giới hạn của mắt và
tai người nên một lượng lớn dung lượng có thể được tiết kiệm bằng cách loại
bỏ các phần dư thừa, trong khi chất lượng hầu như không thay đổi.
Trong thực tế, các file hình ảnh, âm thanh hay là video được lưu trữ
trên máy tính đều đã được nén có tổn hao để tiết kiệm dung lượng và băng
thông. Đối lập với nén không tổn hao các phương pháp nén có tổn hao thường
gây giảm chất lượng rất nhanh khi thực hiện nén và giải nén đệ quy nhiều lần.
Các mẫu hình ảnh âm thanh sẽ được chia thành các phần nhỏ và được biến
đổi qua miền khác. Các hệ số biến đổi này sẽ được lượng tử hóa sau đó được
mã hóa bằng mã Huffman hoặc mã hóa số học.
Các mẫu hình ảnh âm thanh trước được sử dụng để dự đoán các mẫu
tiếp theo. Sai số giữa dữ liệu dự đoán và dữ liệu thực sẽ được lượng tử hóa rồi
mã hóa. Ưu điểm của nén tổn hao so với nén không tổn hao đó là nén tổn hao
trong nhiều trường hợp cho tỷ lệ nén cao hơn rất nhiều so với bất cứ thuật
Thuật toán nén:
- Bước 1: Tìm hai ký tự có trọng số nhỏ nhất ghép lại thành một, trọng
số của ký tự mới bằng tổng số của hai ký tự đem ghép.
- Bước 2: Trong khi số lượng ký tự trong danh sách còn lớn hơn một thì
thực hiện bước một, nếu không thì thực hiện bước ba.
- Bước 3: Tách ký tự cuối và tạo cây nhị phân với quy ước bên trái mã 0,
bên phải mã 1.
16
Số bit trung bình: 87/39 = 2.23 (< 2.28)
Thuật toán giải nén:
- Bước 1: Đọc lần lượt từng bit trong tập tin nén và duyệt cây nhị phân
đã được xác định cho đến khi hết một lá. Lấy kí tự ở lá đó ghi ra tệp
giải nén.
- Bước 2: Trong khi chưa hết tập tin nén thì quay lại thực hiện bước một,
ngược lại thì thực hiện bước tiếp theo.
- Bước 3: Khi hết tập tin, kết thúc thuật toán.
17
2.1.1.2. Thuật toán Run-length
Loại dư thừa đơn giản nhất trong một tập tin là các đường chạy dài
gồm các kí tự lặp lại, điều này thường thấy trong các tập tin đồ họa bitmap,
các vùng dữ liệu hằng của các tập tin chương trình, một số tập tin văn bản...
Ví dụ, xét chuỗi sau:
AAAABBBAABBBBBCCCCCCCCDABCBAAABBBBCCCD
Chuỗi này có thể được mã hóa một cách cô đọng hơn bằng cách thay
làm việc với các chuỗi chứa các kí tự đó. Giả sử ta phải mã hóa bất kì kí tự
nào từ một bảng chữ cái cố định bằng cách chỉ dùng các kí tự từ bảng chữ cái
đó. Để minh họa, giả sử ta phải mã hóa bất kì một chuỗi nào từ một chữ cái
đó, ta sẽ giả định rằng ta chỉ có 26 chữ cái trong bảng chữ cái (và cả khoảng
trống) để làm việc.
Để có thể dùng vài chữ cái để biểu diễn các số và các kí tự khác biểu
diễn các phần tử của chuỗi sẽ được mã hóa, ta phải chọn một kí tự được gọi là
kí tự “Escape”. Mỗi một sự xuất hiện của kí tự đó báo hiệu rằng hai chữ cái
tiếp theo sẽ tạo thành một cặp (số đếm, kí tự) với các số đếm được biểu diễn
bằng cách dùng kí tự thứ i của bảng chữ cái để biểu diễn số i. Vì vậy, chuỗi ví
dụ của chúng ta sẽ được biểu diễn như sau với Q được xem là các kí tự
Escape “QDABBBAABQHCDABCBAAAQDBCCCD”
Tổ hợp của kí tự “Escape”, số đếm và một kí tự lặp lại được gọi là một
dãy Escape. Chú ý rằng không đáng để mã hóa các đường chạy có chiều dài ít
hơn bốn kí tự, vì ít nhất là cần đến ba kí tự để mã hóa bất kì một loạt chạy
nào.
19
Trong trường hợp bản thân kí tự “Escape” xuất hiện trong dãy kí tự cần
mã hóa ta sử dụng một dãy “Escape” với số đếm là 0 (kí tự space) để biểu
diễn kí tự “Escape”. Như vậy trong trường hợp kí tự “Escape” xuất hiện nhiều
thì có thể làm cho tập tin nén phình to hơn trước.
Các loạt chạy dài có thể được cắt ra để mã hóa bằng nhiều dãy Escape,
ví dụ một loạt chạy gồm 51 chữ A sẽ được mã hóa như QZAQYA bằng cách
dùng trên.
Phương pháp mã hóa độ dài loạt thường được áp dụng cho các tập tin
đồ họa bitmap vì ở đó thường có các mảng lớn cùng màu được biểu diễn dưới
dạng bitmap là các chuỗi bit có đường chạy dài. Trên thực tế, nó được dùng
Bước 3: Dừng chương trình
21
Thuật toán giải nén
Bước 1: Đọc thông tin về từ điển đã được lưu trong tệp nén, tl:=false;
Bước 2: while not eof(f) do
Begin
Đọc byte tiếp theo ->b
Decode(b,s,t);
If tl=false then w:=w+s
Else w:=ww+s;
TIMCHU(w,t);
If t=false then
Begin
Ghi s ra tệp giải nén Thêm s vào từ điển
End;
Else Begin
ww:=s;
End;
End.
Bước 3: Dừng chương trình.
Đánh giá: Nói chung thuật toán LZ78 là một thuật toán nén văn bản
khá tốt, có thời gian chạy chương trình tương đối nhanh tuy nhiên khả năng
tiết kiệm chưa được khai thác.
22
2.1.2.2. Thuật toán LZW
Giải thuật nén LZW xây dựng một từ điển lưu các mẫu có tần suất xuất
258
Chuỗi mới
…
…
4095
Chuỗi mới
256: Mã xóa CC để khắc phục tình trạng mẫu lặp lớn hơn
4096 thì gửi CC để xây dựng từ điển cho phần tiếp theo.
Eoi: Báo hiệu hết một phần nén.
23
- 256 từ mã đầu tiên theo thứ tự từ 0...255 chứa các số nguyên từ 0...255.
Đây là mã của 256 ký tự cơ bản trong bảng mã ASCII.
- Từ mã thứ 256 chứa một kí tự đặc biệt là “mã xóa” (CC- Clear Code).
Mục đích việc dùng mã xóa nhằm khắc phục tình trạng số mẫu lặp trong ảnh
lớn hơn 4096. Khi đó một ảnh được quan niệm là nhiều mảnh ảnh và từ điển
là một bộ từ điển gồm nhiều từ điển con. Cứ hết một mảnh ảnh người ta lại
gửi một mã xóa để báo hiệu kết thúc mảnh ảnh cũ, bắt đầu mảnh ảnh mới
đồng thời khởi tạo lại từ điển cho mảnh ảnh mới. Mã xóa có giá trị là 256.
- Từ mã thứ 257 chứa mã kết thúc thông tin (EOI – End of information).
Mã này có giá trị là 257. Như chúng ta đã biết, một file ảnh GIF có thể có
trong từ điển.
Mỗi khi LZW đi qua 1 chuỗi con mới (giả sử “tr”) thì nó thêm chuỗi
con đó vào từ điển.
Mỗi khi nó đi qua 1 chuỗi con mà nó đã thấy trước đó, nó chỉ đọc thêm
1 kí tự mới nữa và cộng với chuỗi con đã biết để tạo ra một chuỗi con mới.
Lần tiếp theo LZW bắt gặp một chuỗi con đã có, nó chỉ có việc sử dụng số chỉ
mục tương ứng trong từ điển.
Thường thì người ta sẽ định sẵn số lượng lớn nhất các từ trong từ điển
(giả sử 4096), vì thế việc nén LZW không làm tiêu tốn hết toàn bộ bộ nhớ. Vì
vậy mã của các chuỗi con trong ví dụ này là 12 bits ( 212=4096). Cần thiết
phải lập mã dài hơn số bits của một kí tự (12 với 8 bits), do đó khi rất nhiều
chuỗi con lặp lại sẽ được thay thế bởi một mã duy nhất thì việc nén được thực
hiện.
25
Copyright: Tài liệu đại học ©