ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
LÊ VĂN NINH
NÉN DỮ LIỆU THEO KỸ THUẬT MOVE – TO - FRONT
Chuyên ngành: KHOA HỌC MÁY TÍNH
Mã số: 60 48 01
LUẬN VĂN THẠC SỸ KHOA HỌC MÁY TÍNH
Thái Nguyên - 2011
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
Lêi c¶m ¬n!
Em xin chân thành cảm ơn các thầy giáo trong Viện công nghệ thông tin,
Viện khoa học và công nghệ Việt Nam; các thầy giáo, cô giáo trường Đại học
CNTT & TT - Đại học Thái Nguyên đã tạo điều kiện, giúp đỡ em hoàn thành
luận văn này.
Đặc biệt, em xin chân thành cảm ơn PGS.TSKH Nguyễn Xuân Huy,
thầy giáo đã giảng dạy và trực tiếp hướng dẫn trong suốt quá trình nghiên cứu
và hoàn thành luận văn.
Dù đã có nhiều cố gắng, nhưng chắc chắn luận văn sẽ không tránh khỏi
những thiếu sót và hạn chế. Vì vậy, rất mong được sự góp ý, chỉ dẫn của các
thầy, cô giáo, bạn bè và đồng nghiệp.
Trân trọng cảm ơn!
Thái Nguyên, tháng 11 năm 2011
Lê Văn Ninh
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
DANH MỤC TỪ VIẾT TẮT
Move – To – Front (Di chuyển lên phía trước)
MTF
Borrows – Wheeler Tranform (Chuyển đổi BW)
BWT
Run length (Mã hóa Run Length)
RUL
Inversion Frequencies (Sự đảo ngược tần số)
IF
Distance Coding (Mã hóa khoảng cách)
DC
Weighted Frequency Count (Đếm trọng số tần số)
WFC
Increased Frequency Count (Đếm gia tăng tần số)
IFC
Local to Global Transform (Chuyển đổi từ cục bộ đến tổng thể )
LGT
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
DANH MỤC HÌNH VẼ
PAGE
Hình 1.1: Máy nén và máy giải nén.
Hình 1.2: Bộ mã hóa và bộ giải mã
Hình 1.3: Những thuật toán nén không hao tổn
Hình 1.4: Các thuật toán nén tổn hao
Hình 1.5: Dữ liệu về nén
Hình 1.6: Dữ liệu về giải nén
Hình 1.7: Dữ liệu ký hiệu về nén
Hình 1.8: Mã và dữ liệu nguồn
Hình 1.9: Mã tiền tố
Hình 1.10: Đặc tính tiền tố và các cây nhị phân
Hình 1.11: Không phải mã tiền tố nhưng có thể giải mã duy nhất
Hình 1.12: Các điểm ảnh với các màu giống nhau
Hình 1.13: Một biểu đồ trong những khoảng xác đị nh
Hình 1.14: Một số dữ liệu ma trận được tập hợp dọc theo một dòng
Hình 1.15: Một dãy các frame hoạt hình
Hình 2.1(a) Mảng A chứa tất cả các phép quay của đầu vào mississippi
Hình 2.1(b) As thu được bằng cách sắp xếp A. Cột cuối của As (ký hiệu L) là
đầu ra của BWT
Hình 2.2 Mảng R được sử dụng để sắp xếp file mẫu mississippi
Hình 2.3 Mảng As với mississippi. F và L là các cột đầu và cuối tương ứng
Hình 2.4 Sử dụng thứ tự ký tự để thực hiện chuyển đổi ngược
Hình 2.5 Mảng (As) mặc nhiên được khôi phục để giải mã xâu pssmipissii
Hình 2.6 Các mảng phụ trợ V và W có thể được sử dụng để giải mã xâu mẫu
Hình 2.7 Một số văn bản được chuyển đổi sinh ra từ “Hamlet” của
Shakespeare.
Hình 2.8: Mã hóa Huffman
Hình 2.9: Mã hóa Huffman ngược
Hình 2.10: Xác suất và khoảng con khởi tạo của biểu tượng
Hình 2.11: Mã hóa số học
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
MỤC LỤC
PAGE
Lời cảm ơn!
Danh mục các ký hiệu, viết tắt
Danh mục các hình vẽ
Mục lục
MỞ ĐẦU
3
Chương I. TỔNG QUAN VỀ NÉN DỮ LIỆU
5
1.1. Giới thiệu
5
1.1.1. Một số vấn đề về Nén dữ liệu
6
1.1.2 Nén không tổn hao và nén tổn hao
9
1.1.2.1 Nén không tổn hao
9
1.1.2.2 Nén tổn hao
9
1.1.3 Đơn vị đo đặc tính nén
11
1.2. Mã hóa dữ liệu ký hiệu
13
1.2.1. Thông tin, dữ liệu và các mã
14
1.2.2 Dữ liệu ký hiệu
17
1.2.3 Mã chiều dài thay đổi
19
1.2.4 Cơ bản về lý thuyết thông tin
26
1.2.5 Sự dư thừa
27
Chương II. KỸ THUẬT NÉN DỮ LIỆU BURROWS WHEELER
31
2.1 Chuyển đổi Burrows-Wheeler (BWT)
31
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
2.1.1 Cách làm việc của chuyển đổi Burrows-Wheeler
33
2.1.1.1 Chuyển đổi Burrows – Wheeler thuận
33
2.1.1.2 Chuyển đổi Burrows – Wheeler nghịch
35
2.1.2 Các mã với chuyển đổi Burrows-Wheeler
41
2.1.2.1 Mã hóa Entropy
42
2.1.2.2 Mã hóa Huffman
42
2.1.2.3 Mã hóa số học
43
2.1.2.4 Mã hóa khoảng cách
46
2.1.2.5 Mã hóa run length
47
2.1.2.6 Các phương pháp đếm tần số
48
2.2 Mã hóa Move – To – Front
49
2.2.1 Mã hóa MTF với các biểu tượng là tập hợp các số nguyên
52
2.2.2 Hiệu suất mã hóa MTF
54
Chương III. GIẢI THUẬT MOVE – TO – FRONT VÀ DEMO
60
3.1. Thuật toán nén dữ liệu Move – To - Front
60
3.1.1. Thuật toán mã hóa
61
3.1.2. Thuật toán giải mã
62
3.2. Thực hiện giải thuật bằng ngôn ngữ C
62
KẾT LUẬN
72
TÀI LIỆU THAM KHẢO
73
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
MỞ ĐẦU
1. Lý do chọn đề tài
Trong các lĩnh vực của công nghệ thông tin và viễn thông hiện nay,
việc truyền tải tin tức là công việc xảy ra thường xuyên. Tuy nhiên, thông tin
được truyền tải đi thường rất lớn, điều này gây khó khăn cho công việc truyền
tải như: gây tốn kém tài nguyên mạng, tiêu phí khả năng của hệ thống,.. Để
giải quyết vấn đề đó, các thuật toán nén dữ liệu đã được ra đời.
Các kỹ thuật nén được nhúng ngày càng nhiều trong phần mềm và đã
trở thành yêu cầu chung cho hầu hết phần mềm ứng dụng như một lĩnh vực
nghiên cứu quan trọng và tích cực trong khoa học máy tính.
Trong kỹ thuật truyền tin nối tiếp, do các bit dữ liệu được truyền đi
nối tiếp, lại bị giới hạn về dải thông của kênh truyền và giới hạn về các chuẩn
ghép nối... nên tốc độ truyền tin tương đối chậm. Nén dữ liệu trước khi truyền
đi là một trong các phương pháp nhằm tăng tốc độ truyền dữ liệu. Nguyên tắc
của nén dữ liệu là quá trình mã hóa thông tin dùng ít bit 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 các phương pháp nào đó.
Dựa theo nguyên tắc này giúp tránh các hiện tượng kênh truyền bị quá tải và
việc truyền tin trở nên kinh tế hơn.
Mặc dù các chương trình nén dữ liệu thường sử dụng kết hợp nhiều
thuật toán có độ phức tạp khác nhau nhằm đạt được hiệu quả cao nhất cho dữ
liệu được nén để đáp ứng yêu cầu đặt ra. Nhưng nhìn chung không thể có
phương pháp nén tổng quát nào cho kết quả tốt đối với tất cả các loại tập tin.
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 đồng nhất), các tập tin dùng để
biểu diễn âm thanh dưới dạng số hoá và các tín hiệu tương tự 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 chương trình thì sau khi nén cũng không tiết kiệm được
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
1
nhiều. Ngoài ra, trong một số trường hợp để nâng cao hệ số nén người ta có
thể bỏ bớt một số thông tin của tập tin (Ví dụ như kỹ thật nén ảnh JPEG).
Nén dữ liệu theo kỹ thuật Move-To-Front (MTF) là một trong những
kỹ thuật nén dữ liệu được thiết kế để cải tiến hiệu quả của kỹ thuật nén mã
hóa entropy. Nó được sử dụng sau kỹ thuật chuyển đổi Burrows -Wheeler để
xếp hạng các biểu tượng theo tần số tương quan của chúng. Mục đích là để
đạt được một hiệu suất nén tốt hơn cho mã hóa entropy.
Xuất phát từ ý tưởng đó, tôi đã lựa chọn đề tài ―Nén dữ liệu theo kỹ
thuật Move – To – Front‖.
2. Đối tượng nghiên cứu:
- Kỹ thuật nén dữ liệu Move-To-Front
3. Phạm vi nghiên cứu:
- Tìm hiểu tổng quan về nén dữ liệu
- Nén dữ liệu Burrows-Wheeler
- Nén dữ liệu theo kỹ thuật Move – to – front
4. Mục tiêu nghiên cứu
Luận văn tập trung nghiên cứu, đánh giá về nén dữ liệu theo kỹ thuật
Move-To-Front. Vận dụng nén dữ liệu trong một số lĩnh vực đặc thù.
5. Ý nghĩa khoa học của đề tài
- Giúp tìm hiểu, đánh giá khái quát về nén dữ liệu theo kỹ thuật MTF.
- Vận dụng được phương pháp nén dữ liệu theo kỹ thuật MTF trong
một số lĩnh vực đặc thù.
6. Phương pháp nghiên cứu
Sử dụng các phương pháp nghiên cứu chính sau:
- Phương pháp nghiên cứu lý thuyết
- Phương pháp thực nghiệm
- Phương pháp thống kê
- Phương pháp trao đổi khoa học, lấy ý kiến chuyên gia.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
2
Chương I. TỔNG QUAN VỀ NÉN DỮ LIỆU
1.1. Giới tiệu
Nén dữ liệu trong ngữ cảnh khoa học máy tính là
khoa học để biểu
diễn thông tin dưới dạng thu gọn . Nói cách khác nén dữ liệu là việc thực hiện
thu gọn kích thước các tập tin hoặc làm cho thông tin lưu trữ chiếm không
gian lưu trữ ít nhất. Có nhiều cách để thực hiện điều này tùy vào từng đối
tượng cụ thể.
Nén dữ liệu đã trở thành yêu cầu chung cho hầu hết phần mềm ứng
dụng như một lĩnh vực nghiên cứu quan trọng và tích cực trong khoa học máy
tính. Nếu không có các kỹ thuật nén, Internet sẽ không bao giờ phát triển, TV
kỹ thuật số , các kỹ thuật tru yền thông di động hoặc truyền thông video đã
được phát triển trên thực tế.
Các lĩnh vực ứng dụng có liên quan và được thúc đẩy bởi nén dữ liệu
gồm có:
Các hệ thống truyền thông cá nhân: Fax, thư thoại (voice mail)
và điện thoại.
Các hệ thống máy tính: Cấu trúc bộ nhớ, đĩa và băng.
Tính toán di động.
Các hệ thống máy tính phân tán.
Mạng máy tính, đặc biệt là Internet.
Sự phát triển đa phương tiện, hình ảnh, xử lý tín hiệu.
Lưu trữ hình ảnh và hội nghị truyền hình.
Ti vi kỹ thuật số và truyền hình vệ tinh.
...
Nhiều vấn đề trên thực tế đã thúc đẩy nhiều nghiên cứu khác nhau về
nén dữ liệu. Tương tự , nghiên cứu về nén dữ liệu cũng đã dựa trên hay được
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
3
kích thích bởi các lĩ nh vực mới khác. Một phần do phạm vi ứng dụng rộng rãi
của nó, nén dữ liệu bao trùm nhiều ngành khoa học và có thể được tìm thấy
trong nhiều lĩnh vực khác nhau như: Lý thuyết thông tin; Lý thuyết mã hóa;
Mạng máy tính và viễn thông; Xử lý tín hiệu kỹ thuật số; Xử lý ảnh; Đa
phương tiện; Bảo mật máy tính...
Trong nén dữ liệu, từ dữ liệu có nghĩa là thông tin ở dạng kỹ thuật số
mà những chương trình máy tính hoạt động và nén, có nghĩa là quá trình loại
bỏ dư thừa trong dữ liệu. Cụm từ ―nén dữ liệu‖, có nghĩa là đưa ra các kỹ
thuật hay cụ thể hơn là thiết kế những thuật toán hiệu quả nhằm để:
Biểu diễn dữ liệu theo dạng mà chứa ít dư thừa.
Loại bỏ dư thừa trong dữ liệu.
Cài đặt thuật toán nén và giải nén.
1.1.1. Một số vấn đề về Nén dữ liệu
Một vấn đề nén liên quan đến việc tìm một thuật toán hiệu quả để loại
bỏ dư thừa khác nhau từ một kiểu dữ liệu nhất định. Ví dụ cho một xâu s, câu
hỏi là dãy các biểu tượng có thể thay thế mà chiếm ít không gian lưu trữ là
dãy nào? Giải pháp cho vấn đề nén là thuật toán nén nhằm đưa ra dãy các
biểu tượng chứa í t số lượng bit hơn , cộng với các thuật toán giải nén để phục
hồi xâu gốc.
Vậy số lượng bit í t hơn là bao nhiêu ? Điều đó phụ thuộc vào những
thuật toán nhưng nó cũng phụ thuộc vào sự dư thừa có thể chiết ra từ dữ liệu
gốc là bao nhiêu. Dữ liệu khác nhau có thể yêu cầu những kỹ thuật khác nhau
để xác định dư thừa và loại bỏ dư thừa trong dữ liệu.
Không có giải pháp nào phù hợp cho tất cả vấn đề nén dữ liệu . Theo
các nghiên cứu về nén dữ liệu , ta chủ yếu phải phân tích những đặc tính của
dữ liệu đã được nén và hy vọng đưa ra một
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
số mô hì nh để đạt được sự biểu
http://www.lrc-tnu.edu.vn
4
diễn ngắn gọn . Điều này làm gia tăng sự đa dạng của mô hình dữ liệu và
những kỹ thuật biểu diễn, đó là điểm quan trọng của kỹ thuật nén.
1.1.1.1 Vấn đề về nén
Nén dữ liệu có thể được xem như một phương tiện truyền thông biểu
diễn hiệu quả nguồn dữ liệu kỹ thuật số như văn bản , hình ảnh, âm thanh hay
bất kỳ sự kết hợp của các kiểu dữ liệu đó như video. Mục đích của nén dữ liệu
là biểu diễn dữ liệu nguồn theo dạng kỹ thuật số với càng ít bit càng tốt đáp
ứng yêu cầu tối thiểu hóa khi khôi phục lại dữ liệu gốc.
Khi làm việc về những vấn đề nén , ta phải xem xét khía cạnh hiệu quả
của các thuật toán cũng như hiệu quả nén. Bằng trực quan, tính chất của thuật
toán nén sẽ phụ thuộc vào dữ liệu và cấu trúc bên trong của nó. Việc dư thừa
càng nhiều của dữ liệu nguồn, càng làm cho một thuật toán nén có thể hiệu
quả hơn.
1.1.1.2 Vấn đề về giải nén
Bất kỳ thuật toán nén sẽ không làm việc trừ khi một phương tiện giải
nén được cung cấp do bản chất của dữ liệu nén. Từ nén ngụ ý là ngữ cảnh của
cả nén và giải nén.
Trong luận văn này, đôi khi không đề cập những thuật toán giải nén
khi quá trình giải nén là hiển nhiên hay có thể dễ dàng được suy ra từ quá
trình nén.
Trong nhiều trường hợp thực tiễn, hiệu quả của thuật toán giải nén
được quan tâm hơn thuật toán nén . Ví dụ như dữ liệu phim ảnh , hình ảnh, và
âm thanh thường được nén một lần bởi người lập trì nh và sau đó cùng phiên
bản với những file đã nén được giải nén nhiều lần bởi hàng triệu người xem
hoặc nghe.
Ngoài ra, đôi khi hiệu quả của các thuật toán nén quan trọng hơn . Ví
dụ, dữ liệu ghi âm thanh hay video từ một số chương trình thời gian thực có
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
5
thể được ghi trực tiếp vào bộ lưu trữ máy tính có giới hạn
, hay được truyền
đến đí ch từ xa thông qua kênh tín hiệu thu hẹp.
Phụ thuộc vào những vấn đề cụ thể , đôi khi ta xem xét vấn đề nén và
giải nén như hai quá trình đồng bộ và không đồng bộ riêng biệt.
Hình 1.1 Cho thấy một mô hình dựa trên mối quan hệ giữa các thuật
toán nén và giải nén.
Hình 1.1: Máy nén và máy giải nén.
Một thuật toán nén thường được gọi là máy nén và thuật toán giải nén
được gọi là máy giải nén.
Máy nén và máy giải nén có thể được đặt tại
nguồn và đí ch của một
kênh truyền thông. Trong trường hợp này, máy nén tại nguồn thường được
gọi là bộ mã hóa và máy giải nén tại đích của thông điệp được gọi là bộ giải
mã. Hình 1.2 cho thấy một mô hình dựa trên quan hệ giữa bộ mã hóa và bộ
giải mã được kết nối bởi một kênh truyền dẫn.
Hình 1.2: Bộ mã hóa và bộ giải mã
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
6
1.1.2 Nén không tổn hao và nén tổn hao
Có hai hệ thống kỹ thuật nén chủ yếu khi xem xét khả năng khôi phục
chính xác dữ liệu nguồn ban đầu . Chúng được gọi là nén không tổn hao và
nén tổn hao.
1.1.2.1 Nén không tổn hao
Một phương pháp nén là không tổn hao nếu và chỉ nếu nó có thể khôi
phục chính xác dữ liệu gốc từ phiên bản đã được nén. Đó là không mất bất kỳ
thông tin nào trong suốt quá trình nén.
Ví dụ, trong Hình 1.3, xâu đầu vào AABBBA được khôi phục lại sau
khi thực hiện thuật toán nén và được theo sau bởi thuật toán giải nén.
Nén không tổn hao được gọi là nén thuận nghịch vì dữ liệu gốc có thể
được phục hồi hoàn toàn bởi quá trì nh giải nén.
Hình 1.3: Những thuật toán nén không hao tổn
Những kỹ thuật nén không tổn hao được sử dụng khi dữ liệu gốc của
nguồn là rất quan trọng mà ta không thể để mất bất kỳ chi tiết nào . Các ví dụ
về dữ liệu nguồn như các hình ảnh y tế , văn bản và các hình ảnh được bảo vệ
vì lý do pháp lý, một số file khả thi của máy tính, …
1.1.2.2 Nén tổn hao
Một phương pháp nén tổn hao nếu nó không thể khôi phục bản gốc
chính xác từ các phiên bản đã được nén. Có một vài chi tiết không quan trọng
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
7
có thể bị mất trong quá trình nén . Từ không quan trọng ở đây hàm ý là những
yêu cầu nhất định về đặc tính của dữ liệu được khôi phục.
Hình 1.4 cho thấy một ví dụ số thập phân dài trở thành phép xấp xỉ
ngắn hơn sau quá trình nén – giải nén.
Hình 1.4: Các thuật toán nén tổn hao
Nén tổn hao được gọi là nén không thuận nghịch vì nó không thể khôi
phục dữ liệu gốc chính xác bởi quá trì nh giải nén.
Khôi phục xấp xỉ có thể là một sự mong muốn vì nó có thể đưa đến
hiệu quả nén nhiều hơn. Tuy nhiên, nó thường yêu cầu sự cân bằng tốt giữa
khả năng trực quan và độ phức tạp trong tính toán.
Dữ liệu như hình ảnh, video và âm thanh đa phương tiện được nén dễ
dàng hơn bởi kỹ thuật nén tổn hao vì cách thức mà các hệ thống thị giác và
thính giác của con người làm việc.
Khi xem xét ảnh hưởng của nén tổn hao , có hai dạng bài toán nén cổ
điển:
Bài toán tỷ lệ biến dạng : Cho một ràng buộc về tỷ lệ dữ l
iệu được
truyền hoặc dung lượng lưu trữ , bài toán là nén file nguồn bằng hoặc thấp hơn
tỷ lệ này nhưng sự chính xác cao nhất có thể.
Nén trong các lĩnh vực thư thoại , radio di động chia ô kỹ thuật số và
hội nghị truyền hình là các ví dụ cho các bài toán tỷ lệ biến dạng.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
8
Bài toán biến dạng tỷ lệ : Cho yêu cầu để đạt được sự chí nh xác được
xác định trước nào đó , bài toán là đáp ứng yêu cầu với ít bit trên giây có thể .
Nén trong các lĩnh vực âm thanh chất lượng CD và video chất lượng hình ảnh
chuyển động là các ví dụ cho các bài toán biến dạng tỷ lệ.
1.1.3 Đơn vị đo đặc tính nén
Việc thực hiện một thuật toán nén có thể được đo bằng các tiêu chuẩn
khác nhau phụ thuộc vào tí nh chất của ứng dụng . Khi hiệu quả về thời gian
không phải là một vấn đề (mặc dù nó quan trọng như nhau), mối quan tâm
chính của ta sẽ là hiệu quả về không gian, tức là hiệu quả một thuật toán nén
dữ liệu có thể tiết kiệm được không gian lưu trữ là bao nhiêu? Ví dụ, đo tỷ lệ
phần trăm của hiệu giữa kích thước của file đầu vào trước khi nén và kích
thước của file đầu ra sau khi nén sẽ cung cấp một dấu hiệu tốt về hiệu quả
nén.
Nhìn chung rất khó để đo hiệu suất của một thuật toán nén vì tính chất
nén của nó phụ thuộc rất nhiều vào dữ liệu chứa dư thừa mà thuật toán tìm
kiếm. Tính chất nén cũng phụ thuộc vào việc ta cho phép dữ liệu được khôi
phục giống với dữ liệu nguồn. Do đó ta sẽ thảo luận đơn vị đo theo hai trường
hợp cụ thể là nén không tổn hao và nén tổn hao.
Nén không tổn hao:
Đối với các thuật toán nén không tổn hao , ta đo hiệu quả nén bằng số
lượng hao hụt của file nguồn so với kích thước của phiên bản đã được nén.
Tỉ lệ nén: Đơn giản là tỉ lệ đầu ra với kích thước file đầu vào của một
thuật toán nén, tức là kích thước file được nén sau khi nén với kích thước file
nguồn trước khi nén.
Hệ số nén: Ngược với tỉ lệ nén.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
9
Tỷ lệ phần trăm tiết kiệm được: Điều này cho thấy hao hụt bằng tỷ lệ
phần trăm.
Ngoài ra, hiệu quả của một thuật toán chỉ là một khía cạnh về đơn vi
đo của thuật toán. Trong thực tế, tiêu chuẩn sau đây thường là mối quan tâm
với các lập trình viên:
Độ phức tạp trong tính toán: Điều này có thể được thông qua từ các
kỹ thuật phân tích thuật toán đã có từ lâu. Ví dụ, sử dụng ký hiệu O[CLRS01]
với yêu cầu hiệu quả thời gian và lưu trữ . Tuy nhiên, hoạt động của các thuật
toán nén có thể không nhất quán . Vì thế nó có thể sử dụng các kết quả thực
nghiệm trước đây.
Thời gian nén: Ta thường xem xét thời gian mã hóa và
giải mã tách
biệt nhau. Trong một số ứng dụng, thời gian giải mã quan trọng hơn thời gian
mã hóa. Trong các ứng dụng khác, chúng quan trọng như nhau.
Entropy: Nếu thuật toán nén dựa trên các kết quả thống kê, thì entropy
có thể được sử dụng như một ràng buộc lý thuyết với dữ liệu ngu ồn để giúp
thực hiện sự phán đoán đại lượng hữu ích . Vì vậy nó cung cấp sự hướng dẫn
lý thuyết để xem nén có thể đạt được bao nhiêu.
Sự dư thừa: Trong các lĩnh vực nén nhất định , sự khác biệt giữa chiều
dài mã trung bình và entropy của dữ liệu nguồn có thể được xem như là sự dư
thừa. Trong một vài lĩnh vực khác, sự khác nhau giữa phân phối xác suất
chuẩn và phân phối xác suất đều được xác định bằng sự dư thừa.
Độ phức tạp: Đơn vị đo lường này làm việc tốt để ch
ứng minh lý
thuyết hơn với các cài đặt thực tế . Độ phức tạp của dữ liệu nguồn trong một
file có thể được đo bằng chiều dài chương trình ngắn nhất để tạo ra dữ liệu.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
10
Kiểm tra cài đặt: Kiểm tra hiệu suất của thuật toán nén bằng cách cài
đặt thuật toán và chạy các chương trình với nhiều định dạng dữ liệu kiểm tra.
Canterbury Corpus cung cấp thử nghiệm tốt để kiểm tra các chương trình
nén. Xem http://corpus.canterbury.ac.nz để biết thêm chi tiết.
Chi phí phụ: Đơn vị đo này thường được sử dụng bởi ngành công
nghiệp công nghệ thông tin . Chi phí phụ là số lượng dữ liệu bổ sung được
thêm vào phiên bản đã được nén của dữ liệu để giải nén sau này . Chi phí phụ
đôi khi có thể lớn hơn mặc dù nó nhỏ hơn nhiều không gian được lưu trữ bằng
cách nén.
Nén tổn hao:
Đối với nén tổn hao, ta phải đo đặc tính của dữ liệu đã được giải nén
cũng như hiệu quả nén. Từ độ tin cậy thường được sử dụng để mô tả độ chí nh
xác giữa file dữ liệu nguồn và file được giải nén. Sự khác biệt giữa dữ liệu
nguồn trước khi nén và file sau khi giải nén, được gọi là độ biến dạng.
Thường độ biến dạng xấp xỉ được sử dụng trong thực tế.
Tóm lại: Nén dữ liệu là một lĩnh vực nghiên cứu tích cực và đang
được quan tâm. Có nhiều lý do thú vị để nghiên cứu những thuật toán nén .
Những thuật toán nén có thể được phân loại theo hai lớp đại cương như sau :
Nén tổn hao và không tổn hao. Đặc tính nén có thể được đo bằng nhiều cách
khác nhau.
1.2. Mã hóa dữ liệu ký hiệu
Nén dữ liệu là khoa học về biểu diễ n thông tin theo một hình thức thu
gọn. Tuy nhiên , thông tin là gì ? Thông tin được biểu diễn theo một dạng
―chuẩn‖ như thế nào, tức là dạng bất kỳ trước khi nén ? Ta muốn nói gì về dữ
liệu nguồn ? Làm thế nào để biết nếu có bất kỳ dư thừa nào trong dữ liệ
u
nguồn?
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
11
Để trả lời các câu hỏi đó, trước hết ta cần làm rõ ý nghĩa của các thuật
ngữ như: thông tin, dữ liệu, các mã và mã hóa.
1.2.1. Thông tin, dữ liệu và các mã
Thông tin là cái gì đó mà làm tăng thêm kiến thức của con người. Đó
là những gì góp phần giảm bớt sự không chắc chắn trong tâm trí con người
hay trạng thái của một hệ thống. Mọi người cảm nhận được sự tồn tại của
thông tin, xem xét phương tiện truyền th ông mang thông tin và tác động trở
lại theo thông tin chắc chắn.
Thông tin không hiện hữu nếu không tồn tại một số phương tiện
truyền thông sóng mang. Dữ liệu là phương tiện truyền thông logic thường
được mang bởi một số phương tiện truyền thông vật lý như CD hay kênh
truyền thông. Vì vậy dữ liệu có thể được xem như dạng cơ bản của một số
thông tin xác thực . Điều này được phân biệt từ các dạng tương phản của
thông tin như : văn bản, đồ họa, âm thanh và hình ảnh . Một số lượng lớn dữ
liệu có thể sau đó được tổ chức và được lưu trữ trong những thông điệp ngắn
hay những file dài.
Từ dữ liệu trong ngữ cảnh của nén dữ liệu bao gồm bất kỳ dạng kỹ
thuật số nào của thông tin xác thực được xử lý bởi chương trình máy tính . Dữ
liệu trước bất kỳ quá trình nén nào được gọi là dữ liệu nguồn, hay nói ngắn
gọn là nguồn.
Các ví dụ về thông tin xác thực có thể được phân loại rộng rãi như:
văn bản, âm thanh, hình ảnh và video. Nhiều chương trình ứng dụng chấp
nhận kiểu thông tin như kiểu file dữ liệu của chúng cho thuận tiện. Do đó dữ
liệu có thể được phân loại như: văn bản, âm thanh, hình ảnh và video trong
khi định dạng dữ liệu kỹ thuật số thực chứa các số 0 và 1 theo định dạng nhị
phân.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
12
Dữ liệu văn bản thường được biểu diễn bởi 8 bit mã ASCII mở rộng.
Chúng xuất hiện trong các file với phần mở rộng .txt hay .tex (hay các file hệ
thống mã hóa có thể đọc được khác như .doc) sử dụng một trình soạn thảo.
Các ví dụ của các file văn bản điển hình là các bản thảo, các chương trình
trong các ngôn ngữ bậc cao khác nhau (được gọi là các mã nguồn) hay các
email văn bản.
Dữ liệu nhị phân gồm các file cơ sở dữ liệu, dữ liệu bảng tính, các file
thực thi, và các mã chương trình. Các file đó thường có phần mở rộng là .bin.
Dữ liệu hình ảnh thường được biểu diễn bằng mảng hai chiều của
những điểm ảnh mà mỗi điểm ảnh được kết hợp với mã màu của nó . Phần mở
rộng .bmp biểu diễn một kiểu file ảnh bitmap trong Windows và .psd với định
dạng file riêng của Adobe Photoshop.
Dữ liệu đồ họa được biểu diễn theo dạng các vectơ hay các phương
trình toán học. Một ví dụ của định dạng dữ liệu là .png, đây là chuẩn với
Portable Network Graphics.
Dữ liệu âm thanh được biểu diễn bởi một hàm sóng (tuần hoàn). Một
ví dụ phổ biến là các file âm thanh theo định dạng .wav.
Ba kiểu cơ bản của dữ liệu nguồn trong máy tính là văn bản, hình ảnh
(kỹ thuật số) và âm thanh. Trong các lĩnh vực ứng dụng, dữ liệu nguồn được
nén gọi là đa phương tiện và có thể là hỗn hợp của định dạng phương tiện
truyền thông tĩnh như: văn bản, hình ảnh và đồ họa, và phương tiện truyền
thông động như âm thanh và video . Hình 1.5 giải thích các giai đoạn liên
quan đến dữ liệu nguồn trong file được mã hóa thành file nhị phân nguồn
trước khi nén . Hình 1.6 cho thấy quá trình ngược lại , trong đó dữ liệu nhị
phân được khôi phục sau khi giải nén phải được giải mã thành dữ liệu của
một loại nào đó trước khi được nhận ra trong bất kỳ ứng dụng nào.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
13
Hình 1.5: Dữ liệu về nén
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
14
- Xem thêm -