Bài tập mã hóa lempel-ziv chuỗi nhị phân năm 2024

Uploaded by

hương nguyễn

0% found this document useful (0 votes)

134 views

55 pages

dieucheso

Copyright

© © All Rights Reserved

Available Formats

PPT, PDF, TXT or read online from Scribd

Share this document

Did you find this document useful?

Is this content inappropriate?

0% found this document useful (0 votes)

134 views55 pages

CHUONG2

Uploaded by

hương nguyễn

dieucheso

Jump to Page

You are on page 1of 55

Search inside document

Reward Your Curiosity

Everything you want to read.

Anytime. Anywhere. Any device.

No Commitment. Cancel anytime.

DownloadVui lòng tải xuống để xem tài liệu đầy đủ

Nội dung Text: BÀI TẬP NHÓM MÔN LÝ THUYẾT THÔNG TIN - ĐỀ TÀI : “Lempel-ziv Encoding”

1. TRƯỜNG ĐẠI HỌC ĐIỆN LỰC Khoa Điện Tử Viễn Thông -- BÀI TẬP NHÓM MÔN LÝ THUYẾT THÔNG TIN ĐỀ TÀI : “Lempel-ziv Encoding” Giảng viên bộ môn: Vũ Ngọc Châm Nh óm Sinh Viên Thực Hiên: Nhóm 10 Sinh vi ên lớp: Đ5.ĐTVT1 Trường Đại Học Điện Lực Khoa Điện Tử Viễn Thông Nhóm 10
2. TRƯỜNG ĐAI HỌC ĐIỆN LỰC Khoa Điện Tử Viễn Thông Môn Lý THUYÊT thông tin LEMPEL-ZIV ENCODING Danh Sách Các Thành Viên Nhóm Số 10 1 : NGUYỄN QUỐC QUÂN 2: NGUYỄN VĂN HÙNG 3: NGUYỄN VĂN KHOÁI 4: HOÀNG VĂN LÂM 5: NGUYỄN VĂN TIẾN LÂM Hà nội ngày 11 tháng 9 năm 2012 Trường Đại Học Điện Lực Khoa Điện Tử Viễn Thông Nhóm 10
3. Mục Lục 1.Danh sách thành viên trong nhóm 10……………………….. 1 2.Lời giới thiệu………………………………………………....2 3.Tổng quan về nén giữ liệu …………………………………...4 4. Cơ sở một số phương pháp nén………..…………………….5 5. Tổng quan về Lempel-ziv coding …………………………...6 6.Từ điển mã hóa……………………………………………….7 7. Họ thuật toán Lempel-Ziv…………………………………..8 +Thuật toán LZ78……………………………………………...8 +Thuật toán LZW ……………………………………………..11 8.Kết Luận……………………………………………………..19 9.Tài liệu tham khảo……………………………………………21 2.Mục lục……………………………………………………….22 Trường Đại Học Điện Lực Khoa Điện Tử Viễn Thông Nhóm 10
4. Lời giới thiệu. Ngày nay thông tin là một phần gắn kết không thể thiếu của con người trong cuộc sống hiện đại. việc trao đổi thông tin là công việc thường xuyên và được coi như là bình thường của mỗi chúng ta.Có rất nhiều hình thức thể hiện khác nhau của thông tin như âm thanh, hình ảnh,tiếng nói,chữ viết và các loại ký tự……. Chính vì vậy mà cũng nảy sinh ra rất nhiều vấn đề bức thiết xung quanh việc chuyền tải thông tin từ người này tới người khác cũng như đến vấn đề lưu trữ bạn không thể bỏ 250 Gigabyte dung lượng ổ nhớ máy vi tính của bạn ra chỉ để lưu trữ và ghi nhớ một thông tin không quan trọng lắm, hoặc trong việc lưu trữ nó. Ví dụ như dung lượng tập tin mà quá lớn nó sẽ ảnh hưởng vân đề trao đổi thông tin bạn không thể chờ cả ngày để cập nhập một lượng tin quá lớn mà không cần thiết lắm cho cuộc sống của bạn.Chính vì vậy mà người ta mới nghĩ ra một thuật toán mà làm thế nào đó để có thể giảm dung lượng thông tin cần trao đổi đó xuống nhằm mục đích đơn giản và thuận tiện hơn trong việc trao đổi và lưu trữ thông tin. Để giải quyết vấn đề đó, các thuật toán nén đã được ra đời. Ban đầu với phương pháp mã hóa loạt dài RLC (Run Length Coding), phát hiện một loạt các bít lặp lại. Đây là phương pháp đơn giản nhất. Nguyên tắc cơ bản của phương pháp này là phát hiện một ký tự có số lần xuất hiện liên tiếp vượt qua một ngưỡng cố định nào đó. Trong trường hợp này dãy sẽ được thay thế bằng 3 ký tự: Ký tự thứ nhất là ký tự đặc biệt,thông báo dãy tiếp là dãy đặc biệt. Ký tự thứ hai chỉ số lần lặp. Ký tự thứ ba chỉ ký tự lặp.Như vậy tư tưởng của phương pháp này là thay thế một dãy bằng một dãy khác ngắn hơn tuân theo một ngưỡng nào đó, và thông thường ngưỡng có giá trị là 4.Kế đến là phương pháp Huffman, dựa vào mô hình thống kê, tính tần suất xuất hiện của các ký tự, rồi gán cho các ký tự có tần suất cao một từ mã ngắn, các ký tự tần suất thấp từ mã dài. Phương pháp này phải lưu giữ lại bảng mã gắn kèm cùng với dữ liệu nén. Một phương pháp nén hoàn toàn khác là thuật toán nén dữ liệu theo từ điển cơ sở: (Dictionary­based compression) Trường Đại Học Điện Lực Khoa Điện Tử Viễn Thông Nhóm 10
5. Có 2 loại: Mã hóa từ điển tĩnh (static dictionary coding) Mã hóa từ điển động (dynamic dictionary coding) Có rất nhiều thuật toán áp dụng kỹ thuật này như LZ77, LZR, LZSS, LZH… nhưng trong nội dung bài báo cáo này, chúng ta chỉ đề cập đến hai thuật toán chình là: +Thuât Toán LZ78 + Thuât toán LZW. Nhìn chung không có phương pháp nén tổng quát nào cho kết quả là tốt đối với tất cả các loại tập tin mà ta cần mã hóa cả.Năm 1983 Sperry nộp một bằng sáng chế cho một thuật toán phát triển bởi Terry Welch, một nhân viên tại Trung tâm nghiên cứu Sperry. Thuật toán này là biến thể trên một kỹ thuật nén dữ liệu lần đầu tiên được đề xuất bởi Jakob Ziv và Abraham Lempel năm 1978 của Welch. Kỹ thuật của Welch là cả hai đơn giản hơn và nhanh hơn. Ông đã xuất bản một bài báo trong vấn đề 1984 của Tạp chí máy tính IEEE mô tả kỹ thuật. Kỹ thuật này của Terry Welch trở nên rất phổ biến và được chấp nhận rộng rãi. Đó chính là thuật toán mã hóa mà ngày nay người ta gọi nó với cái tên là Lempel­Ziv­Welch. Hà nội ngày 11 tháng 9 năm 2012 Các thành viên nhóm 10 I: TỔNG QUAN VỀ NÉN GIỮ LIỆU I.1:Nén giữ liệu là gì?.  Nén giữ liệu được định nghĩa đơn giản như sau: Nén dữ liệu là quá trình làm giảm lượng thông tin “dư thừa” trong dữ liệu gốc và do vậy, thông tin thu được sau nén thường nhỏ hơn dữ liệu gốc rất nhiều. Ngoài thuật ngữ “nén dữ liệu”, do bản chất của kỹ thuật này nó còn có một số tên gọi khác như: giảm độ dư thừa, mã hóa ảnh gốc… Trường Đại Học Điện Lực Khoa Điện Tử Viễn Thông Nhóm 10
6. I.2:Tỷ Số Nén ( Compression rate )  Compression rate được định nghĩa như sau: Tỷ số nén là tỷ lệ giữa kích thướcfile đã nén và kích thước file khi mà chưa nén. + Công thức tỷ số nén như sau: Chú thích: + Compression rate: Tỷ số nén +Compressed Size: Kích cỡ file sau nén +Uncompressed Size :Kích cỡ file trước nén +Đơn vị thường ký hiệu là tỳ số ví dụ như 1/5 +Ví dụ ở đây ta có một file gốc kích thước 10M sau khi nén thì dung lượng giảm xuống còn 2M.Vậy rõ ràng Tỷ số nén ở đây là 2/10=1/5.Và thường được ký hiệu là tỷ lệ rõ ràng là 1/5. I.3: Khoảng Tiết Kiệm Không Gian (Space savings)  Space savings: được định nghĩa như sau nó là sự giảm kích thước tương đối so với kích thước không nén, đơn vị ở đây được dùng là đơn vị %. +Công thức tính như sau. Chú thích: +Space Savings : Khoảng tiết kiệm không gian +Compressed Size: Kích cỡ file sau nén +Uncompressed Size :Kích cỡ file trước nén +Đơn vị thường ký hiệu +Ví dụ Ta có tỷ lệ nén là 1/5 thì sẽ mang lại một khoảng tiết kiệm không gian là 1 - 1/5 = 0.8, vậy sau khi nén ta tiết kiệm được 80% không gian bộ nhớ so với trước khi nén.  Đối với các tín hiệu của kích thước không xác định, chẳng hạn như tuyến âm thanh và video, tỉ lệ nén được định nghĩa về tốc độ dữ liệu khi không nén và khi đã nén thay vì kích thước dữ liệu như tài liệu đã nêu ở trên. Và thay vì tiết kiệm không gian, người ta nói về tốc độ dữ liệu tiết kiệm, được định nghĩa là giảm tốc độ dữ liệu liên quan đến tốc độ dữ liệu không nén. + Công thức tính trong trường hợp này sẽ là: Trường Đại Học Điện Lực Khoa Điện Tử Viễn Thông Nhóm 10
7. Và Tỷ lệ tiết kiệm giữ liệu Data rate saving sẽ là: Chú thích: + Compression ratio : Tỷ số nén +Compressed Data Rate : Tốc độ nén giữ liệu +Uncompressed Size :Tốc độ khi chưa nén giữ liệu + Ví dụ, bài hát không nén ở định dạng CD có tốc độ dữ liệu 16 bit / kênh x 2 kênh x 44,1 kHz ≅ 1,4 Mbit / s, trong khi AAC các tập tin trên iPod thường được nén đến 128 kbit / s, tỷ lệ năng suất nén của 0,09 , một khoản tiết kiệm dữ liệu tốc độ 0,91, hoặc 91%. + Khi tỷ lệ dữ liệu không nén được biết, tỷ lệ nén có thể được suy ra từ tốc độ dữ liệu nén. II: CƠ SỞ CỦA MỘT SỐ PHƯƠNG PHÁP NÉN  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.  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.Người ta coi có 4 kiểu dư thừa giữ liệu và chính vì thế cũng có bốn phương pháp mã hóa cơ bản hiện nay đó là: II.1:Phương phap mã hoá Huffman. ́ Trong môt day ký tự, có môt số ký tự có tân suât xuât hiên nhiêu h ơn môt ̣ ̃ ̣ ̀ ́ ́ ̣ ̀ ̣ số day khac. Do vây, ta có thể mã hoá dữ liêu môt cach cô đong hơn. Cac ̃ ́ ̣ ̣ ̣ ́ ̣ ́ day ký tự có tân xuât cao được thay bởi môt từ mã nhị phân với số bit nho; ̃ ̀ ́ ̣ ́ ̉ Trường Đại Học Điện Lực Khoa Điện Tử Viễn Thông Nhóm 10
8. ngược lai cac day có tân xuât thâp sẽ được mã hoá bởi từ mã có nhiêu bit ̣ ́ ̃ ̀ ́ ́ ̀ ́ hơn. Đây chinh là ban chât cua phương phap mã hoá Huffman. ́ ̉ ́ ̉ ́ II.2: Phương phap mã hoá Run Length Coding. ́ Trong môt số tinh huông như trong anh, 1 ký hiêu (bit "0" hay bit "1") được lăp đi ̣ ̀ ́ ̉ ̣ ́ ́ ̣ lăp lai môt số lân. Kỹ thuât nen dung trong trường hợp nay là thay day lăp đó bởi ̣ ̣ ̣ ̀ ̣ ́ ̀ ̀ ̃ ̣ day mới gôm 2 thanh phân: số lân lăp và kí hiêu dung để ma. Phương phap mã hoá ̃ ̀ ̀ ̀ ̀ ̣ ̣ ̀ ̃ ́ kiêu nay có tên là mã hoá loat dai RLC (Run Length Coding). ̉ ̀ ̣ ̀ II.3:Phương pháp mã hóa Lempel-Ziv Welch. Có thể có day ký hiêu nao đó xuât hiên với tân suât tương đôi cao. Do ̃ ̣ ̀ ́ ̣ ̀ ́ ́ vây, có thể mã hoá bởi it bit hơn. Đây là cơ sở cua phương phap mã hoá ̣ ́ ́ ̉ ́ kiêu từ điên do Jacob Ziv và Abraham Lempel đề ra vao năm 1977-1978 và ̉ ̉ ̀ do đó có tên goi là phương phap nen LZ77, LZ78. Năm 1984, Terry Welch ̣ ́ ́ đã cai tiên hiêu quả hơn và đăt tên là LZW (Lempel-Ziv- Welch).Do đó kỹ ̉ ́ ̣ ̣ thuật được cải thiện hơn và nhanh hơn. II.4: Phương phap mã hoá dự đoan ́ ́ Do sự phụ thuôc lân nhau cua dữ liêu, đôi khi biêt được ký hiêu (giá tri) ̣ ̃ ̉ ̣ ́ ̣ ̣ xuât hiên tai môt vị tri, đông thời có thể đoan trước sự xuât hiên cua cac giá ́ ̣ ̣ ̣ ́ ̀ ́ ́ ̣ ̉ ́ trị ở cac vị trí khac nhau môt cach phù hợp.Chăng han, anh biêu diên trong ́ ́ ̣ ́ ̉ ̣ ̉ ̉ ̃ môt lưới hai chiêu, môt số điêm ở hang doc trong môt khôi dữ lêu lai xuât ̣ ̀ ̣ ̉ ̀ ̣ ̣ ́ ̣ ̣ ́ hiên trong cung vị trí ở cac hang khac nhau.Do vây, thay vì lưu trữ dữ liêu, ̣ ̀ ́ ̀ ́ ̣ ̣ ta chỉ cân lưu trữ vị trí hang và côt.Phương phap nen dựa trên sự dư thừa ̀ ̀ ̣ ́ ́ nay goi là phương phap mã hoá dự đoan ̀ ̣ ́ ́ III: TỔNG QUAN VỀ LEMPEL-ZIV CODING Jacob Ziv và Abraham Lempel đã mô tả kỹ thuật dựa trên từ điển bằng mã hóa LZ77 và LZ78. Ý tưởng dựa trên việc thay thế 1 cụm kí tự bằng một con trỏ, trỏ đến vị trí xuất hiện trước đó của cụm kí tự.LZW là mã hóa trong họ LZ, hoàn thiện hơn LZ77-LZ78 và đang được sử dụng phổ biến hiện nay. Trường Đại Học Điện Lực Khoa Điện Tử Viễn Thông Nhóm 10
9. III.1: Lempel-Ziv (LZ).  Thuật toán LZ (Lempel-Ziv): là thuật toán nén dữ liệu theo từ điển cơ sở (Dictionary-based compression).  Được tính bằng tỷ số giữa tổng số bit cần nén 1 từ hay 1 văn bản (vd:mã ascci-7bit) và số bít sử dụng để nén trong bộ từ điển đó.  Sử dụng một bảng chứa tất cả các chuỗi ký tự có thể xuất hiện trong văn bản và được chứa trên cả bộ mã hóa và giải mã.  Bộ mã hóa thay vì gửi các từ riêng lẻ, nó chỉ gửi chỉ số của từ được lưu trong bảng. Bộ giải mã sẽ truy cập vào bảng xử lý để tái tạo lại văn bản đó.  Như các thuật toán tĩnh khác, thuật toán LZ sử dụng 1 từ điển chung cho cả mã hóa và giải mã.  Một số gói xử lý từ có liên quan tới từ điển được sử dụng cho việc kiểm tra chính tả và nén văn bản. Thông thường trong khu vực gồm khoảng 25000 từ, do đó cần dùng15 bit để mã hóa. Vì vậy nếu dùng thuật toán LZ để nén từ “multimedia” ta sử dụng 15 bit . Thay vì khi sử dụng mã ASCII (mỗi từ mã dùng 7 bit) ta sẽ phải sử dụng 70 bit. → Compression ratio = 70/15 = 4.7:1  Những từ ngắn hơn sẽ có tỉ lệ nén nhỏ hơn so và những từ dài hơn sẽ có tỉ lệ nén lớn hơn.  Thuật toán LZ được phát triển, là sử dụng một bộ từ điển động được xây dựng trên cả bộ mã hóa và giải mã. Do đó kích thước của từ điển sẽ được tối ưu hơn so với từ điển tĩnh thông thường. III.2: Lempel-Ziv-Welch( LZW).  Phương pháp nén LZW được phát minh bởi Lempel - Zip và Welch. Nó hoạt động đựa trên một ý tưởng rất đơn giản là người mã hoá và người giải mã cùng xây dựng bản mã.  Đầu tiên, từ điển của cả bộ mã hóa và giải mã là tập hợp các từ ví dụ như bảng mã ASCII.  Sau đó từ điển động được xây dựng ở cả bộ mã hóa và giải mã từ các từ trong văn bản.  Chúng ta có thể thấy, các từ lưu trữ trong từ điển xuất hiện thường xuyên trong văn bản thì mức độ nén cao hơn. IV: TỪ ĐIỂN MÃ HÓA (DICTIONNARY CODING) Từ điển mã hóa( Dictionnary coding) gồm có hai loại là từ điển tĩnh (static dictionary coding) và từ điển động (dynamic dictionary coding) hai Trường Đại Học Điện Lực Khoa Điện Tử Viễn Thông Nhóm 10
10. loại từ điển này gộp chung lại và người ta gọi nó là từ điển cơ sở (Dictionary-based compression), hay hiểu một cách đơn giản từ điển cơ sở là loại từ điển mà bao gồm có hai phần kết hợp tạo thành là từ điển tĩnh và từ điển động. IV.1: Static coding : Dành cho các ứng dụng trong các văn bản biết được các đặc điểm của kí tự và tần suất xuất hiện của chúng. Thay vì sử dụng các từ mã có chiều dài cố định, ta sử dụng bộ từ mã tối ưu có chiều dài thay đổi. Từ mã ngắn nhất sử dụng để biểu diễn cho văn bản. IV.2: Dynamic hoặc adaptive coding : Dành cho các ứng dụng tổng quát hơn trong các văn bản có thể bị chuyển từ dạng này sang dạng khác và bộ từ mã tối ưu cũng thay đổi từ dạng này sang dạng khác. V:HỌ THUẬT TOÁN LEMPEL-ZIV. Có rất nhiều thuật toán áp dụng kỹ thuật này như LZ77, LZR, LZSS, LZH… được mô tả trong hình 1. Hình 1:Họ thuật toán Lempel-Ziv Trong bài báo cáo này chúng ta chỉ đề cập đến hai thuật toán chính và được ứng dụng nhiều trong thực tế hiện nay là: +Thuật Toán LZ78 + Thuật toán LZW V.1: Thuật Toán LZ78. Trường Đại Học Điện Lực Khoa Điện Tử Viễn Thông Nhóm 10
11. 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  Phương Pháp Nén: 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ứ. + Ví dụ: Giả sứ ta có đoạn văn bản :” 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 Bảng b1. Mô phỏng thuật toán LZ78  Bảng b1: Mô tả thuật toán LZ78 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: Thuật toán nén bao bồm 3 bước 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; Trường Đại Học Điện Lực Khoa Điện Tử Viễn Thông Nhóm 10
12. 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 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: Thuật toán giải nén cũng bao gồm 3 bước. 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 (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 Trường Đại Học Điện Lực Khoa Điện Tử Viễn Thông Nhóm 10
13. End Else Begin ww:=s; End; End; Bước 3: Dừng chương trình. V.2: Thuật Toán LZW. 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 phải chứa bảng mã. Nhược điểm của thuật toán này là tốn nhiều bộ nhớ, khó thực hiện dựa trên các mảng đơn giản (bé hơn 64KB) 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 dữ liệu. 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 , 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. 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- Trường Đại Học Điện Lực Khoa Điện Tử Viễn Thông Nhóm 10
14. 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. 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. Trường Đại Học Điện Lực Khoa Điện Tử Viễn Thông Nhóm 10
15. ► Nguyên Tắc Hoạt Động LZW. 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 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. Có bốn qui tắc để thực hiên việc nén dữ liệu theo thuật toán LZW là: Qui tắc 1: 256 dấu hiệu đầu tiên được dành cho các kí tự đơn (0 - 0ffh). Trường Đại Học Điện Lực Khoa Điện Tử Viễn Thông Nhóm 10
16. Qui tắc 2: Cố gắng so sánh với "từ điển" khi trong bộ đ ệm ch ứa đã có nhiều hơn hai kí tự. Qui tắc 3: Các kí tự ở đầu vào (Nhận từ tập tin s ẽ đ ược nén) đ ược b ổ sung vào bộ đệm chứa đến khi chuỗi kí tự trong bộ đệm chứa không có trong "từ điển". Qui tắc 4: Khi bộ đệm chứa có một chuỗi mà trong "t ừ đi ển" không có thì chuỗi trong bộ đệm chứa được đem vào "từ điển". Kí tự cuối cùng của chuỗi kí tự trong bộ đệm chứa phải ở lại trong bộ đệm chứa để tiếp t ục tạo thành chuỗi mới. ► Các bước thực hiện thuật toán.  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. Trường Đại Học Điện Lực Khoa Điện Tử Viễn Thông Nhóm 10
17.  Ví dụ 1: Các bước để mã hoá chuỗi "!BAN!BA!BAA!BAR!" như sau : - Bước 1: Kí tự thứ nhất ‘!’ được cất vào bộ đệm chứa để chuẩn bị tạo nên một chuỗi. - Bước 2: Kí tự thứ hai ‘B’ nối thêm vào sau kí tự !. Vì trong "t ừ đi ển" chưa có chuỗi "!B" nên chuỗi này được thêm vào "từ điển" và được gán dấu hiệu là 100h (Vì từ 000h đến 0ffh được dành riêng cho các kí t ự đ ơn: Qui tắc 1). ‘!’ được gửi ra còn ‘B’ phải ở lại trong bộ đệm chứa. - Bước 3: Kí tự thứ ba ‘A’ thêm vào sau ‘B’. Chuỗi "BA" cũng ch ưa có trong "từ điển" nên nó được thêm vào "từ điển" và gán dấu hiệu là 101h. ‘A’ ở lại trong bộ đệm chứa còn ‘B’ được gửi ra. - Bước 4: Kí tự thứ tư ‘N’ thêm vào sau ‘A’ tạo thành chuỗi "AN" cũng chưa có trong "từ điển" nên được thêm vào "từ điển" và có dâu hi ệu là 102h. ‘N’ ở lại trong bộ đệm chứa còn ‘A’ được gửi ra. - Bước 5: Kí tự thứ năm ‘!’ thêm vào sau ‘N’ để t ạo thành chu ỗi "N!", "N!" được thêm vào "từ điển" với dấu hiệu là 103h. ‘!’ ở lại còn ‘N’ được gửi ra. - Bước 6: Kí tự thứ sáu ‘B’ thêm vào sau ‘!’. Lần này thì chu ỗi "B!" đã có trong "từ điển" nên không có kí tự nào được gửi ra. "B!" ti ếp t ục ở lại trong "từ điển" để tạo ra chuỗi mới. - Bước 7: Kí tự thứ bảy ‘A’ thêm vào sau ‘B’ để tạo thành chuỗi "B!A", do "B!A" không có trong "từ điển" nên nó được thêm vào "t ừ đi ển" và gán dấu hiệu là 104h đồng thời dấu hiệu 100h được gửi ra thay cho "B!" (Qui tắc 4). A tiếp tục ở lại trong bộ đệm chứa để tạo thành chuỗi mới. Các bước trên cứ thế tiếp tục cho đến khi hết tập tin c ần nén. Vi ệc giảm kích thước chỉ thực sự bắt đầu tại bước 7 khi mà một dấu hiệu 12 bits là được gửi ra thay cho hai byte "B!". Các bước được mô tả rõ hơn trong bảng 5.1 dưới đây. Trường Đại Học Điện Lực Khoa Điện Tử Viễn Thông Nhóm 10
18. Bảng 5.1: Các bước thực hiện thuật toán LZW  Ví dụ 2: 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: Trường Đại Học Điện Lực Khoa Điện Tử Viễn Thông Nhóm 10
19. - 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 Coun W K wk symbo inde outpu t l x t 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 AB D ABC ABC 264 262 C D D 12 D Nll D 68 Bảng 5.2: Các bước thực hiện mã hoá chuỗi "ABCBCABCABCD" Chuỗi ra: 65- 66- 67- 259 -258- 67 (output) Trường Đại Học Điện Lực Khoa Điện Tử Viễn Thông Nhóm 10
20. • Đầ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 Trong thuật toán nén này, phần lớn thời gian khi bắt đầu nén ch ủ y ếu mất vào việc tạo "từ điển". Khi "từ điển" đủ lớn, xác suất gặp chuỗi ở bộ đệm chứa trong "từ điển" tăng lên và càng nén được nhiều hơn. Một điều cần chú ý ở đây là mỗi một dấu hiệu, ta ph ải lưu một chuỗi trong "từ điển" để so sánh. Vì dấu hiệu được biểu diễn bằng một số 12 bits nên "từ điển" sẽ có 4096 lối vào, khi tăng số bit dể biễu diễn d ấu hi ệu lên thì hiệu quả nén sẽ tốt hơn nhưng lại bị giới hạn bởi bộ nhớ của máy tính. Vì dụ, khi dùng 16 bits để biểu diễn một dấu hiệu thì "từ điển" phải có đến 65536 lối vào, nếu mỗi lối vào có khoảng 20 kí tự thì "t ừ đi ển" ph ải lớn khoảng 1,2 MB. Với một từ điển có dung lượng như vậy rất khó có thể thực hiện trên các máy tính PC hoạt động dưới hệ điều hành DOS vì giới hạn của một đoạn (Segment) là 64KB. Ưu điểm của ph ương pháp nén LZW là 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.  Quá trình giải nén LZW . Quá trình giải nén LZW cũng không có gì ph ức t ạp. Thêm vào đó nó có nhiều lợi thế hơn so với các phương thức nén tĩnh vì không cần một t ừ điển hay những thông tin tạp phí cần thiết cho quá trình thu ật gi ải nén. Một từ điển mới đồng nhất với từ điển gốc đã tạo trong khi nén đ ược tái tạo lại trong quá trình giải nén này.Quá trình mã hóa và giải mã cần ph ải sử dụng cùng 1 từ điển khởi đầu, trong trường hợp này là 256 kí tự của bảng mã ASCII Sau đây là cơ chế nó hoạt động. Bộ giải mã LZW trước hết đọc một chỉ mục (là 1 số nguyên), tìm chỉ mục đó trong từ đi ển, và cho ra chuỗi con gắn với chỉ mục đó. Kí tự đầu tiên của chu ỗi con này Trường Đại Học Điện Lực Khoa Điện Tử Viễn Thông Nhóm 10

172 tài liệu

823 lượt tải