Download miễn phí Mã hóa LZW (Lempel-Ziv-Wech)
Thuật toán nén LZW có các ưu điểm là hệ số nén tương đối cao, trong tập tin nén không cần chứa bảng mã.
- Bên nhận có thể tự xây dựng bảng mã mà không cần bên gửi phải gửi kèm theo bản tin nén.
- Thuật toán LZW đã khắc phục được sự lãng phí về bộ nhớ mà các thuật toán trước không tận dụng được hết. Đồng thời khắc phục được sự cứng nhắc của thuật toán nén, góp phần làm thuật toán nén trở nên mềm dẻo hơn, có sức hấp dẫn hơn đối với người sử dụng

http://s1.luanvan.co/qYjQuXJz1boKCeiU9qAb3in9SJBEGxos/swf/2013/06/26/ma_hoa_lzw_lempelzivwech.udOsQFiFl6.swf luanvanco /luan-van/de-tai-ung-dung-tren-liketly-30500/
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí

Tóm tắt nội dung tài liệu:

ã. Phương pháp mã hoá kiểu này có tên là mã hoá loạt dài RLC (Run Length Coding). Phương pháp mã hoá RLC.
Những mẫu sử dụng tần suất
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 Lempel-Ziv đư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)
Độ 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.
1.2. Phân loại và ứng dụng
1.2.1 Dựa vào nguyên lý nén
Theo cách này người ta phân thành 2 họ:
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 Lemple-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 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.
Các thuật toán nén không tổn hao cơ bản là:
Shannon-Fano
Run-length coding
LZ77 , LZ78, LZW
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 đệ qui nhiều lần. Mã hóa suy hao thực hiện theo 2 kiểu chính:
- 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 hay mã hóa số học
- Các mẫu hình ảnh âm thanh trước được sử dụng để đoán các mẫu tiếp theo. Sai số giữa dữ liệu đ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.
Trong các phần trình bày dưới đây, ta sẽ theo cách phân loại này.
1.2.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.
Theo cách của Jain, các phương pháp nén gồm 4 họ chính:
Phương pháp điểm.
Phương pháp dự đoán.
Phương pháp dựa vào biến đổi.
Chương 2: NỘI DUNG CÁC THUẬT TOÁN
2.1. Phương pháp nén không tổn hao
2.1.1. Mô hình thống kê
2.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 (hay bit 1), phần dưới bằng bit 1(hay 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
Ký hiệu
A
B
C
D
E
Số lần xuất hiện
15
7
6
5
6
Ký hiệu
Đếm
Pi
Log2(1/pi)
Mã
Tổng bits
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
Bảng 2.1: Mô tả thuật toán Shannon-Fano
Số bits sử dụng trung bình: (tổng bits/ số lần xuất hiện.
R = (30+14+12+18+15) / 39 = 2.29 bits
Ưu nhược điểm.
Nhược điểm:
Thuật toán Shanon có hệ số nén khá thấp và yêu cầu khá phức tạp nên hiếm khi được sử dụng.
Ưu điểm:
Đơn giản, dễ thực hiện.
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
Thuật toán:
a) 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ụ.
Ký hiệu
A
B
C
D
E
Số lần xuất hiện ...

---