Mã hóa Shanon fano-huffman
PHẦN 1
GIỚI THIỆU ĐỀ TÀI
I.1.
GIỚI THIỆU
Công nghệ thông tin (CNTT-IT) được mệnh danh là ngành của mọi ngành. Thực
vậy, ta có thể thấy hầu hết mọi ngành, nghề đều ít nhiều có ứng dụng CNTT vào công
việc của nó.
Bảo mật thông tin, nén dữ liệu là công việc cần thiết trong ngành CNTT. Từ thời xa
xưa, con người đã biết gìn giữ thông tin trong quân sự, trong chiến tranh nhằm làm cho
thông tin được an toàn, không lọt vào tay đối phương. Muốn vậy, con người có nhiều
cách để làm cho thông tin truyền đi được gọn nhẹ và an toàn khi lưu thông. Để thông
tin đến tay người nhận một cách bí mật, gọn gàng nhất thì họ phải nén thông tin lại hay
dùng các ký hiệu đặc biệt có qui ước trước.
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 qui 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 chẽ với nhau. Một trong những tiêu chí giúp ngành CNTT phát triển là
sử dụng công nghệ bảo mật, nén dữ liệu, thông tin trong lưu trữ và truyền thông.
Trong kỹ thuật truyền số liệu, bảo mật và nén dữ liệu (nguồn tin) truyền đi là 2 vấn
đề quan trọng, nhiều cơ sở lý thuyết về mã hóa nguồn cho ta thấy tầm quan trọng của
việc mã hóa và nén dữ liệu. Các thuật toán nén dữ liệu đã ra đời từ rất lâu như mã nén
Shannon-Fano, Huffman hay Lempel Ziv Welch (LZW) được cho là kinh điển của
công nghệ nén dữ liệu.
Trong bài luận văn này, em sẽ trình bày đôi nét về các thuật toán nén dữ liệu thông
dụng hiện nay và so sánh tính hiệu quả của việc nén một số loại dữ liệu khác nhau giữa
2 loại mã nén Shannon-Fano và Huffman. Phần mô phỏng tính hiệu quả của 2 loại mã
Trang 1
nén thông dụng này em sẽ trình bày bằng chương trình được viết trên nền tảng ngôn
ngữ lập trình C và C++.
I.2.
MỤC ĐÍCH VÀ PHẠM VI CỦA ĐỀ TÀI
Đồ án này tập trung vào các vấn đề xoay quanh thuật toán Shannon-Fano và
Huffman, phân tích các ưu, nhược điểm của thuật toán này so với thuật toán kia bằng
hình thức mô phỏng tỉ lệ nén của nó. Các phần sẽ thực hiện trong đồ án này gồm :
1. Tìm hiểu lý thuyết nén dữ liệu, tổng hợp các kết quả trên thế giới về nén dữ
liệu. Tổng quan về các phương pháp mã hóa nguồn, nguyên tắc làm việc của các
phương pháp, tốc độ và tỷ lệ nén.
2. Phân loại và ứng dụng. Nhiệm vụ đặt ra là đưa ra được nội dung của các
thuật toán mã hóa nguồn .
3. Nội dung thuật toán Shannon-Fano và Huffman . Trong phần này sẽ đi sâu
phân tích các ưu nhược điểm của từng thuật toán, lựa chọn thuật toán Shannon-Fano
và Huffman – là các thuật toán nén dữ liệu kinh điển để 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.
4. Khái quát về chương trình, kết quả của thuật toán. Trong phần này sẽ nêu cấu
trúc của chương trình và các vấn đề khi xây dựng chương trình. Nhiệm vụ quan trọng
là phải mô phỏng được thuật toán, xây dựng lưu đồ thuật toán và coding.
I.3.
PHUƠNG PHÁP NGHIÊN CỨU
- Đưa ra được cơ sở lý thuyết
- Tiến hành nghiên cứu thuật toán của các loại mã nén Shannon-Fano và Huffman.
- Đưa ra nguyên tắc mã hóa và bài toán mã hóa.
- Chạy chương trình và kiểm thử
- Đánh giá ưu điểm và nhược điểm
PHẦN 2
Trang 2
NỘI DUNG
CHƯƠNG 1
SƠ LƯỢC VỀ NÉN DỮ LIỆU
II.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 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ủa các phương pháp nào đó. Dựa theo nguyên tắc này giúptrá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. Nén dữ liệu giúp tiết kiệm các
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 có thể đò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.
II.1.2 TỔNG QUAN CÁC LOẠI MÃ NÉN
II.1.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 có 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.
II.1.2.2.
Tốc độ và tỷ lệ nén
Trang 3
Ngay cả khi tất cả các chương trình nén file đều dùng chung một thuật toán thì hoạt
động của chúng cũng khác nhau. Mỗi hãng triển khai thuật toán một kiểu để dung hòa
hai vấn đề: thời gian và tỷ lệ nén. Chương trình PKZIP thường trội hơn các chương
trình nén khác về mặt tốc độ, về mặt tỷ lệ nén, nhiều khi nó cũng khá hơn. Tính ổn
định của các chương trình nén cũng là điều cần quan tâm. Các file nén nói chung rất ít
khi bị hỏng. Cũng cần lưu ý là các loại file nén không tương thích với nhau, tức là nếu
gửi file nén cho người khác thì người đó cần phải có chương trình thích hợp mới giải
nén ra được. Tuy nhiên để giải quyết vấn đề này, cả 3 chương trình ARC + PLUS,
LHA và PKZIP đều cho phép tạo file nén tự bung - tức file nén ở dạng chương trình
thực hiện, khi chạy sẽ tự động bung ra, trên thị trường cũng bắt đầu xuất hiện chương
trình chuyển đổi từ dạng file nén này sang dạng file nén khác, ví dụ chương trình
D'Compress for Windows chuyển các file PKZIP, ARC, LHA sang dạng ARJ.
Các chương trình nén giá không cao (PKZIP: 47USD, LHA cung cấp miễn phí)
nên được dùng khá rộng rãi. Hạn chế hiện nay của chúng là giao diện người dùng
không thuận tiện, thường phải gõ lệnh với nhiều tham số ở dấu nhắc của DOS để thực
hiện một công việc nào đó. Cải tiến theo hướng này đang được thực hiện: ARC +
PLUS có giao diện kiểu menu, PKZIP cũng đã có phần bổ sung là PKZIP menu.
Nhiều chương trình quản lý file trong DOS và trong Windows đã bắt đầu dùng kỹ
thuật nén. Chương trình Magellan của hãng Lotus dùng PKZIP từ năm 1990, chương
trình Xtree Gold đưa PKZIP vào công cụ quản lý file năm 1991.
Thư mục nén rời sau đó lại phải bung ra để dùng của các chương trình 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ư 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 trên
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.
Trang 4
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ể gây 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 nó 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
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ó chức năng loại bỏ. Đối
với các chương trình khác cần tóm các file ẩn của chương trình nén và xóa bỏ chúng đi.
Có khi phải format lại ổ cứng.
Tóm lại, dù một số hạn chế, nén dữ liệu là cách thức kinh tế nhất để mở rộng dung
lượng ổ cứng. Ngoài ra còn tiết kiệm được khá nhiều thời gian và kinh phí khi nén dữ
liệu trước khi truyền đi
Tỷ lệ nén là một trong các đặc trưng quan trọng nhất của mọi phương pháp nén.
Tuy nhiên, về cách đánh giá và các kết quả công bố trong các tài liệu cũng cần được
quan tầm xem xét. Nhìn chung, người ta định nghĩa tỷ lệ nén như sau :
Tỷ lệ nén = 1/ r x %
Với r là tỷ số nén được định nghĩa : r = kích thước dữ liệu gốc / kích thước dữ liệu
thu được sau nén. Như vậy hiệu suất của nén là : ( 1 - tỷ lệ nén) x %
Trang 5
Trong các trình bày sau khi nói đến kết quả nén, chúng ta dùng tỷ số nén, thí dụ như
10 trên 1 có nghĩa là dữ liệu gốc là 10 sau khi nén chỉ có 1 phần.
Tuy nhiên, cũng phải thấy rằng những số đo của một phương pháp nén chỉ có giá trị
với chính sự nén đó, vì rằng hiệu quả của nén còn phụ thuộc vào kiểu dữ liệu định nén.
nhiều khi tỷ lệ nén cao cũng chưa thể nói rằng phương pháp đó là hiệu quả hơn các
phương pháp khác, vì còn các chi phí khác như thời gian, không gian và thậm chí cả độ
phức tạp tính toán nữa. Thí dụ như nén phục vị trong truyền dữ liệu : vấn đề đặt ra là
hiệu quả nén có tương hợp với đường truyền không.
II.1.2.3
Các loại dư thừa dữ liệu.
Như trên đã nói, nén nhằm mục đích giảm kích thước dữ liệu bằng cách loại bỏ dư
thừa dữ liệu. việc xác định bản chất các kiểu dư thừa dữ liệu rất có ích cho việc xây
dựng các phương pháp nén dữ liệu khác nhau. Nói một cách khác, các phương pháp
nén dữ liệu khác nhau là do sử dụng các kiểu dư thừa dữ liệu khác nhau. Có 4 kiểu dư
thừa chính được trình bày ở các mục sau đây.
II..2.3.1.1.
Sự phân bố ký tự.
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ã hoá dữ liệu một cách cô đọng hơn. Các ký tự có tần xuất
xuất hiện cao hơn được thay thế bởi một từ mã nhị phân với số bít nhỏ; ngược lại các
dãy có tần xuất xuất hiện thấp sẽ được mã hóa bởi từ mã có nhiều bít hơn. Đây chính là
bản chất của phương pháp mã hoá Huffman hay Shannon-Fano.
II.1.2.3.2.
Sự lặp lại của các ký tự
Trong một số tình huống như trong ảnh, 1 ký hiệu (bít "0" hay bít "1") được lặp đi
lặp lại một số lần. Kỹ thuật nén dùng trong trường hợp này là thay dãy lặp đó bởi dãy
mới gồm 2 thành phần: số lần lặp và kí hiệu dùng để mã hóa. Phương pháp mã hoá
kiểu này có tên là mã hóa loạt dài RLC (Run Length Coding).
II.1.2.3.3.
Những mẫu sử dụng tần suất
Trang 6
Có thể có 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ã hoá bởi ít bít hơn. Đây là cơ sở của phương pháp mã hoá kiểu từ điển do LempelZiv đưa ra và có cải tiến vào năm 1977, 1978 và 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ữ liệu dựa 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 Shannon-Fano và Huffman.
II..2.3.4.1
Độ dư thừa vị trí
Do sự phụ thuộc lẫn nhau của dữ liệu, đôi khi biết được 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ị ở các 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 trong một khối dữ lệu lại xuất hiện trong cùng vị trí ở các hàng khác
nhau. Do vậy, thay vì 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ã hoá dự đoán.
Cách đánh giá độ dư thừa như trên hoàn toàn mang tính trực quan nhằm biểu thị
một cái gì đó xuất hiện nhiều lần. Đối với dữ liệu ảnh, ngoài đặc thù chung đó, nó còn
có những đặc thù riêng. Thí dụ như có ứng dụng không cần toàn bộ dữ liệu thô của ảnh
mà chỉ cần các thông tin đặc trưng biểu diễn ảnh như biên ảnh hay vùng đồng nhất. Do
vậy, có những phương pháp nén riêng cho ảnh dựa vào biến đổi ảnh hay dựa vào biểu
diễn ảnh.
II.2.2 PHÂN LOẠI VÀ ỨNG DỤNG
II.1.3.11
Dựa vào nguyên lý nén:
Theo cách này người ta phân thành 2 họ:
II..3.1.11 Các thuật toán nén không tổn hao:
Trong phương pháp nén không tổn hao, dữ liệu được nén sau khi giải nén sẽ giống
y như ban đầu. Trong đó thông dụng nhất là thuật toán Lempel-Ziv (LZ). DEFLATE,
là một biến thể của thuật toán LZ, được tối ưu hóa nhằm tăng tốc độ giải nén và tỉ lệ
nén, bù lại thuật toán này có tốc độ của quá trình nén chậm. DEFLATE được dùng
Trang 7
trong PKZIP, GZIP, và PNG. LZW (Lemple-Zip-Welch) được dùng trong định dạng
file GIF. Hai biến thể của thuật toán LZ cũng đáng chú ý là thuật toán LZX dùng trong
định dạng file CAB của Microsoft (Microsoft còn dùng thuật toán nén này trong file
CHM, các file office 2007) và thuật toán LZMA dùng trong chương trình 7-ZIP.
Các thuật toán nén không tổn hao được dùng để nén các file như file thực thi, file
văn bản, word, excel, v.v… Các loại dữ liệu này không thể sai lệch dù chỉ một bit, nhất
là các file chương trình.
Các thuật toán nén không tổn hao cơ bản:
1. Run-length encoding (RLE).
2. Dictionary coders.
3. LZ-77 & LZ-78.
4. LZW.
5. Burrows and Wheeler transform (BWT).
6. Prediction by partial matching (PPM).
7. Context mixing (CM).
8. Entropy encoding.
9. Huffman coding (huffman động thường 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. Arithematic.
12. Shannon-Fano coding.
13. Range coding.
II..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
Trang 8
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 đệ qui 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 toán nén không tổn hao
được biết, trong khi vẫn đảm bảo được chất lượng. Nén tổn hao thường được sử dụng
để nén ảnh, âm thanh, video. Âm thanh có thể nén với tỉ lệ 10:1 mà hầu như không
giảm chất lượng. Video có thể nén với tỉ lệ 300:1 với chất lượng giảm ít.
II.1.3.2 Dựa vào cách thức thực hiện nén
• Theo cách này, người ta cũng phân thành hai họ:
• Phương pháp không gian (Spatial Data Compression): các phương pháp thuộc
họ này thực hiện nén bằng cách tác động trực tiếp lên việc lấy mẫu của ảnh trong miền
không gian.
• Phương pháp sử dụng biến đổi (Transform Coding): Gồm các phương pháp tác
động lên sự biến đổi của ảnh gốc mà không tác động trực tiếp như họ trên.
CHUƠNG 2
CÁC PHƯƠNG PHÁP NÉN DỮ LIỆU
Trang 9
II.2.1 PHUƠNG PHÁP NÉN KHÔNG TỔN HAO
II.2.1.1.
Mô hình thống kê
II.2.1.1.1.1
Thuật toán Shannon-Fano:
Các bước thực hiện mã hoá theo thuật toán Shanon-Fano:
-
Bước 1: Sắp xếp các ký tự theo thứ tự giảm dần.
Bước 2: Tính xác suất
- Bước 3: Đệ quy làm hai phần, mỗi phần có tổng xác suất gần bằng nhau.
Mã hoá phần trên bằng bit 0 (hoặc bit 1), phần dưới bằng bit 1(hoặc bit 0).
-
Bước 4: Vẽ sơ đồ cây.
- Bước 5: Tính Entropy, số bits mã hoá trung bình và số bit mã hoá thông
thường.
Ví dụ mô tả thuật toán
Thống kê lượng tin:
Ký hiệu
A
B
C
D
E
Số lần xuất hiện
15
7
6
5
6
Mã hóa lượng tin:
Ký hiệu Đếm
Pi
Log2(1/pi)
Mã
A
15
15/39
1.38
0
0
30
B
7
7/39
2.48
0
1
14
C
6
6/39
2.7
1
0
12
E
6
6/39
2.7
1
1
0
18
D
5
5/39
2.96
1
1
1
15
Số bits sử dụng trung bình: (tổng bits/ số lần xuất hiện).
Trang 10
Tổng bits
R = (30+14+12+18+15) / 39 = 2.29 bits
II.2.1.1.2
Thuật toán Huffman
Thuật toán Huffman có ưu điểm là hệ số nén tương đối cao, phương pháp thực hiện
tương đối đơn giản, đòi hỏi ít bộ nhớ, có thể xây dựng dựa trên các mảng bé hơn
64KB. Nhược điểm của nó là phải chứa cả bảng mã vào tập tin nén thì phía nhận mới
có thể giải mã được do đó hiệu suất nén chỉ cao khi ta thực hiện nén các tập tin lớn.
• Nguyên lý:
Nguyên lý của phương pháp Huffman là mã hóa 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 là
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
(gần giống Shannon-Fano).
• Thuật toán:
• 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 trọ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 cùng và tạo cây nhị phân với quy ước bên trái
mã 0, bên phải mã 1.
Xét ví dụ.
Thống kê lượng tin:
Ký hiệu
A
B
C
D
E
Số lần xuất hiện
15
7
6
5
6
Trang 11
Mã hóa lượng tin:
Ký hiệu Xác suất
Tổng bit
1
15
0
000
21
1 24/39 0
001
18
010
18
011
15
1
A
15/39
B
7/39
0
1
C
6/39
0
E
6/39
D
5/39
01
-
Mã
13/39
11/39
Số bit trung bình: 87/39 =2.23 (<2.28) Hiệu quả hơn Shannon – Fano.
• 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.
II.2.1.1.31
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
Trang 12
Chuỗi này có thể được mã hoá một cách cô đọng hơn bằng cách thay thế chuỗi kí
tự lặp lại bằng một thể hiện duy nhất của kí tự lặp lại cùng với một biến đếm số lần kí
tự đó được lặp lại. Ta muốn nói rằng chuỗi này gồm bốn chữ A theo sau bởi ba chữ B
rồi lại theo sau bởi hai chữ A, rồi lại theo sau bởi năm chữ B... Việc nén một chuỗi theo
phương pháp này được gọi là mã hoá độ dài loạt. Khi có những loạt dài, việc tiết kiệm
có thể là đáng kể. Có nhiều cách để thực hiện ý tưởng này, tuỳ thuộc vào các đặc trưng
của ứng dụng (các loạt chạy có khuynh hướng tương đối dài hay không ? Có bao nhiêu
bit được dùng để mã hoá các kí tự đang được mã ?).
Nếu ta biết rằng chuỗi của chúng ta chỉ chứa các chữ cái, thì ta có thể mã hoá biến
đếm một cách đơn giản bằng cách xen kẻ các con số với các chữ cái. Vì vậy chuỗi kí tự
trên được mã hoá lại như sau: 4A3BAA5B8CDABCB3A4B3CD
Ở đây "4A" có nghĩa là "bốn chữ A"... Chú ý là không đáng để mã hoá các loạt
chạy có độ dài 1 hoặc 2 vì cần đến hai kí tự để mã hoá.
Ðối với các tập tin nhị phân một phiên bản được tinh chế của phương pháp này
được dùng để thu được sự tiết kiệm đáng kể. Ý tưởng ở đây là lưu lại các độ dài loạt,
tận dụng sự kiện các loạt chạy thay đổi giữa 0 và 1 để tránh phải lưu chính các số 0 và
1 đó. Ðiều này giả định rằng có một vài loạt chạy ngắn (Ta tiết kiệm các bit trên một
loạt chạy chỉ khi độ dài của đường chạy là lớn hơn số bit cần để biễu diễn chính nó
trong dạng nhị phân), nhưng khó có phương pháp mã hoá độ dài loạt nào hoạt động
thật tốt trừ phi hầu hết các loạt chạy đều dài.
Việc mã hoá độ dài loạt cần đến các biễu diễn riêng biệt cho tập tin và cho bản đã
được mã hoá của nó, vì vậy nó không thể dùng cho mọi tập tin, điều này có thể hoàn
toàn bất lợi, ví dụ, phương pháp nén tập tin kí tự đã được đề nghị ở trên sẽ không dùng
được đối với các chuỗi kí tự có chứa số. Nếu những kí tự khác được sử dụng để mã hoá
các số đếm, thì nó sẽ không làm việc với các chuỗi chứa các kí tự đó. Giả sử ta phải mã
hoá 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 hoạ, giả sử ta phải mã hoá 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.
Trang 13
Ðể 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ã hoá, 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ã hoá 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ã hoá bất kì một loạt chạy nào.
Trong trường hợp bản thân kí tự "Escape" xuất hiện trong dãy kí tự cần mã hoá 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ã hoá bằng nhiều dãy Escape, ví dụ, một
loạt chạy gồm 51 chữ A sẽ được mã hoá như QZAQYA bằng cách dùng trên.
Phương pháp mã hoá độ dài loạt thường được áp dụng cho các tập tin đồ hoạ
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 trong các tập tin .PCX,
.RLE.
II.2.1.2.
Mô hình từ điển
II.2.1.2.11
Thuật toán LZ78
Thay vì thông báo vị trí đoạn văn lặp lại trong quá khứ, mã LZ78 đánh số tất cả
các đoạn văn sao cho mỗi đoạn ghi nhận số hiệu đoạn văn lặp lại trong quá khứ cộng
với một ký tự mà nó làm cho đoạn đó khác với đoạn trong quá khứ. Như vậy mỗi đoạn
mới là một đoạn ký tự trong quá khứ cộng với một ký tự trong quá khứ. Chính vì thế
đoạn mới khác với đoạn cũ trong quá khứ.
Trang 14
Ví dụ: Giả sứ ta có đoạn văn bản sau:” aaabbabaabaaabab”
Theo thuật toán LZ78 thì chúng được phân đoạn như sau:
Input
A
Aa
b
Ba
baa
baaa
bab
Đoạn
1
2
3
4
5
6
7
output
0+a
1+a
0+b
3+a
4+a
5+a
4+b
Như vậy bản nén của chúng ta là: (0,a); (1,a); (0,b); (3,a); (4,a); (5,a); (4,b)
Thuật toán nén:
Bước 1: Đọc một ký tự -> ch, đoạn được gán bằng 1, kết nạp ký tự đó vào từ điển,
w=ch;
Bước 2: While not eof(f) do
Begin
Đọc tiếp ký tự tiếp theo w:= ww+ch;
If w thuộc từ điển then ww:=w;
Else begin
Trang 15
Code(w,j);
Ghi j và ch vào tệp nén.
Thêm w vào từ điển.
End;
End;
Bước 3: Dừng chương trình.
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.
Trang 16
Đá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.
II.2.1.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 hiện cao
trong ảnh. Từ điển là tập hợp những cặp từ vựng và nghĩa của nó. Trong đó, từ vựng sẽ
là các từ mã được sắp xếp theo thứ tự nhất định. Nghĩa là một chuỗi con trong dữ liệu
ảnh. Từ điển được xây dựng đồng thời với quá trình đọc dữ liệu. Sự có mặt của một
chuỗi con trong từ điển khẳng định rằng chuỗi đó đã từng xuất hiện trong phần dữ liệu
đã đọc. Thuật toán liên tục “tra cứu” và cập nhật từ điển sau mỗi lần đọc một ký tự dữ
liệu đầu vào.
Do kích thước bộ nhớ không phải vô hạn và để đảm bảo tốc độ tìm kiếm, từ điển
chỉ giới hạn 4096 ở phần tử dùng để lưu lớn nhất là 4096 giá trị của các từ mã. Như
vậy độ dài lớn nhất của từ mã là 12 bits (4096 = 212 ). Cấu trúc từ điển như sau.
0
0
…
…
255
255
256
256| Clear Code
257
257| End of Information
258
Chuỗi mới
…
…
4095
Chuỗi mới
256:Mã xoá CC để khắc phục tình
trạng mẫu lặp lớn hơn 4096, nếu 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.
Trang 17
- 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 mã đặc biệt là “mã xoá” (CC- Clear Code). Mục
đích việc dùng mã xoá 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ã xoá để 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ã xoá 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ó chứa nhiều
ảnh.Mỗi một ảnh sẽ được mã hoá riêng.Chương trình giải mã sẽ lặp lại thao tác giải mã
từng ảnh cho đến khi gặp mã kết thúc thông tin thì dừng lại.
Các từ mã còn lại (từ 258 đến 4095) chứa các mẫu thường lặp lại trong
ảnh. 512 phần tử đầu tiên của từ điển biểu diễn bằng 9 bit. Các từ mã từ 512 đến 1023
biểu diễn bởi 10 bit, từ 1024 đến 2047 biểu diễn bởi 11 bit và từ 2048 đến 4095 biểu
diễn bởi 12 bit.
Nguyên tắc hoạt động của nó như sau:
- Một xâu kí tự là một tập hợp từ hai kí tự trở lên.
- Nhớ tất cả các xâu kí tự đã gặp và gán cho nó một dấu hiệu (token) riêng.
-
Nếu lần sau gặp lại xâu kí tự đó, xâu kí tự sẽ được thay thế bằng dấu hiệu của
nó.
Phần quan trọng nhất của phương pháp nén này là phải tạo một mảng rất lớn
dùng để lưu giữ các xâu kí tự đã gặp (Mảng này được gọi là "Từ điển"). Khi các byte
dữ liệu cần nén được đem đến, chúng liền được giữ lại trong một bộ đệm chứa
(Accumulator) và đem so sánh với các chuỗi đã có trong "từ điển". Nếu chuỗi dữ liệu
trong bộ đệm chứa không có trong "từ điển" thì nó được bổ sung thêm vào "từ điển" và
chỉ số của chuỗi ở trong "từ điển" chính là dấu hiệu của chuỗi. Nếu chuỗi trong bộ đệm
Trang 18
chứa đã có trong "từ điển" thì dấu hiệu của chuỗi được đem ra thay cho chuỗi ở dòng
dữ liệu ra.
• Quá trình nén:
LZW bắt đầu bởi 1 từ điển 256 kí tự (trong trường hợp sử dụng bảng mã 8 bits) và
sử dụng chúng như tập kí tự chuẩn. Sau đó mỗi lần đọc nó đọc 8 bits (ví dụ 't', 'r', ...) và
mã hóa thành con số tương ứng với chỉ mục của kí tự đó 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 1 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 (2 ^ 12 = 4096). Cần thiết phải lập mã dài hơn số
bits của một kí tự (12 vs 8 bits), do đo 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.
Ví dụ: Các bước để mã hoá chuỗi "ABCBCABCABCD" như sau:
•
Các bước thực hiện.
- Bươc 1: w = NIL;
- Bước 2: Trong khi đọc được ký tự thứ k trong chuỗi:
- Bước 3: Nếu wk đã tồn tại trong từ điển thì w=wk
- Bước 4: Còn không thì thêm wk vào trong từ điển, mã hoá ngõ ra cho
w,w=k
- k=k+1
Trang 19
Count
W
K
wk
symbol
index
output
0
Nil
A
A
1
A
B
AB
AB
258
65
2
B
C
BC
BC
259
66
3
C
B
CB
CB
260
67
4
B
C
BC
5
BC
A
BCA
BCA
261
259
6
A
B
AB
7
AB
C
ABC
ABC
262
258
8
C
A
CA
CA
263
67
9
A
B
AB
10
AB
C
ABC
11
ABC
D
ABCD
ABCD
264
262
12
D
NIL
D
Chuỗi ra: 65- 66- 67- 259 -258- 67 (output)
• Đầu vào kích thước: 12 x 8 = 96 bits.
• Đầu ra kích thước là: 5 x 8 + 3 x 9 = 67 bits
• Tỉ lệ nén là: 96 /67 =1.43
Trang 20
68
- Xem thêm -