vumanhcuong_bn179
New Member
Chia sẻ miễn phí cho các bạn tài liệu: NGHIÊN CỨU CÁC THUẬT TOÁN NÉN DỮ L 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 Tuyển tập Báo cáo “Hội nghị Sinh viên Nghiên cứu Khoa học” lần thứ 6
Đại học Đà Nẵng - 2008
Báo cáo "Nghiên cứu các thuật toán nén dữ liệu thuật toán LZW"
TÓM TẮT
SVTH: PHẠM TUẤN ANH
Lớp: 05CCT2 Khoa Tin, Trường Đại học Sư Phạm
GVHD: ĐOÀN DUY BÌNH
Khoa Tin, Trường Đại học Sư Phạm
Có khá nhiều kỹ thuật nén dữ liệu như: dùng mã ký hiệu, mã đóng gói, mã theo độ dài, nén dữ liệu với mô hình nguồn, kỹ thuật từ điển... Trong số các kỹ thuật trên thì kỹ thuật từ điển là linh hoạt và hiệu quả hơn cả. Đặc biệt là dùng mã LZ với từ điển động, và phổ biến hơn hết là phương pháp nén LZW. Bài báo cáo này giới thiệu một số thuật toán nén dữ liệu và trình bày phương pháp nén LZW.
ABSTRACT
There are many method compress data, such as: use sysbol code, packed code, length code, compress data with source model and dictionary technonogy... In that, dictionary technonogy is activityer and effectiver. Special is method use LZ with dynamic dictionary, and popular is method LZW compress. This report introduce some algorithm of data compression and execute LZW compress method.
1. Mở đầu:
Trong các lĩnh vực của công nghệ thông tin – viễn thông hiện nay, việc truyền tải tin tức đã là một 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: 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 đã đượ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)
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, LZK, 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.
258
Tuyển tập Báo cáo “Hội nghị Sinh viên Nghiên cứu Khoa học” lần thứ 6 Đại học Đà Nẵng - 2008
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.
Vì điều kiện không cho phép nên bài báo cáo chỉ nêu ra một số thuật toán nén dữ liệu, nêu một số ưu – nhược điểm và so sánh làm nổi bật phương pháp nén bằng LZW.
2. Nội dung:
Phương pháp mã hóa Huffman
2.1.1. 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
2.1.2. 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.
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ì thực hiện bước một, ngược lại thì thực hiện bước 3.
Bước 3: Kết thúc thuật toán.
Một số những hạn chế của mã Hufman:
Mã Huffman chỉ thực hiện được khi biết được tần suất xuất hiện của các ký tự.
Mã Huffman chỉ giải quyết được độ dư thừa phân bố ký tự.
Huffman tĩnh đòi hỏi phải xây dựng cây nhị phân sẵn chứa các khả năng. Điều này
đòi hỏi thời gian không ít do ta không biết trước kiểu dữ liệu sẽ được thực hiện nén.
Quá trình giải nén phức tạp do chiều dài mã không biết trước cho đến khi ký tự đầu
tiên được tìm ra.
Phương pháp mã hóa 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ứ.
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 thành các đ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
259
Tuyển tập Báo cáo “Hội nghị Sinh viên Nghiên cứu Khoa học” lần thứ 6 Đại học Đà Nẵng - 2008
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
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 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; End;
Đọ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
ww:=s;
Ghi s ra tệp giải nén Thêm s vào từ điển
End
Else Begin
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
tốt đa.
Phương pháp mã hóa LZW
Thuật toán này là sự chuyển giao của thuật toán LZ78. Như chúng ta đã biết ở thuật toán LZ78, việc lưu trữ các ký tự theo sau mỗi đoạn thường gây lãng phí về bộ nhớ nên hiệu quả nén chưa cao. Thuật toán LZW quản lý bằng cách loại bỏ ký tự sau mỗi đoạn do đó đầu ra của mỗi đoạn chỉ chứa con trỏ mà thôi. Thuật toán này lưu trữ bằng việc chuẩn bị một danh sách các đoạn bao gồm rât nhiều ký tự trong đầu vào là một bảng chữ cái nào đó, nó thực hiện một quá trình mở rộng các bảng chữ cái hay nói cách khác là nó dùng ký tự bổ sung để biểu diễn lại các chuỗi của ký tự chính quy. Để nén LZW trên mã ASCII 8 bits ta cần mở rộng bảng chữ cái bằng cách dùng 9 bits hay nhiều hơn 256 ký tự bổ sung mà mã 9 bits cung cấp được dùng để lưu trữ các chuỗi mã được quyết định từ các chuỗi trong nguồn tin. Thuật toán sẽ không đạt hiệu quả nén cao nếu có những điều kiện sau:
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
Đại học Đà Nẵng - 2008
Báo cáo "Nghiên cứu các thuật toán nén dữ liệu thuật toán LZW"
TÓM TẮT
SVTH: PHẠM TUẤN ANH
Lớp: 05CCT2 Khoa Tin, Trường Đại học Sư Phạm
GVHD: ĐOÀN DUY BÌNH
Khoa Tin, Trường Đại học Sư Phạm
Có khá nhiều kỹ thuật nén dữ liệu như: dùng mã ký hiệu, mã đóng gói, mã theo độ dài, nén dữ liệu với mô hình nguồn, kỹ thuật từ điển... Trong số các kỹ thuật trên thì kỹ thuật từ điển là linh hoạt và hiệu quả hơn cả. Đặc biệt là dùng mã LZ với từ điển động, và phổ biến hơn hết là phương pháp nén LZW. Bài báo cáo này giới thiệu một số thuật toán nén dữ liệu và trình bày phương pháp nén LZW.
ABSTRACT
There are many method compress data, such as: use sysbol code, packed code, length code, compress data with source model and dictionary technonogy... In that, dictionary technonogy is activityer and effectiver. Special is method use LZ with dynamic dictionary, and popular is method LZW compress. This report introduce some algorithm of data compression and execute LZW compress method.
1. Mở đầu:
Trong các lĩnh vực của công nghệ thông tin – viễn thông hiện nay, việc truyền tải tin tức đã là một 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: 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 đã đượ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)
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, LZK, 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.
258
Tuyển tập Báo cáo “Hội nghị Sinh viên Nghiên cứu Khoa học” lần thứ 6 Đại học Đà Nẵng - 2008
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.
Vì điều kiện không cho phép nên bài báo cáo chỉ nêu ra một số thuật toán nén dữ liệu, nêu một số ưu – nhược điểm và so sánh làm nổi bật phương pháp nén bằng LZW.
2. Nội dung:
Phương pháp mã hóa Huffman
2.1.1. 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
2.1.2. 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.
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ì thực hiện bước một, ngược lại thì thực hiện bước 3.
Bước 3: Kết thúc thuật toán.
Một số những hạn chế của mã Hufman:
Mã Huffman chỉ thực hiện được khi biết được tần suất xuất hiện của các ký tự.
Mã Huffman chỉ giải quyết được độ dư thừa phân bố ký tự.
Huffman tĩnh đòi hỏi phải xây dựng cây nhị phân sẵn chứa các khả năng. Điều này
đòi hỏi thời gian không ít do ta không biết trước kiểu dữ liệu sẽ được thực hiện nén.
Quá trình giải nén phức tạp do chiều dài mã không biết trước cho đến khi ký tự đầu
tiên được tìm ra.
Phương pháp mã hóa 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ứ.
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 thành các đ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
259
Tuyển tập Báo cáo “Hội nghị Sinh viên Nghiên cứu Khoa học” lần thứ 6 Đại học Đà Nẵng - 2008
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
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 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; End;
Đọ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
ww:=s;
Ghi s ra tệp giải nén Thêm s vào từ điển
End
Else Begin
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
tốt đa.
Phương pháp mã hóa LZW
Thuật toán này là sự chuyển giao của thuật toán LZ78. Như chúng ta đã biết ở thuật toán LZ78, việc lưu trữ các ký tự theo sau mỗi đoạn thường gây lãng phí về bộ nhớ nên hiệu quả nén chưa cao. Thuật toán LZW quản lý bằng cách loại bỏ ký tự sau mỗi đoạn do đó đầu ra của mỗi đoạn chỉ chứa con trỏ mà thôi. Thuật toán này lưu trữ bằng việc chuẩn bị một danh sách các đoạn bao gồm rât nhiều ký tự trong đầu vào là một bảng chữ cái nào đó, nó thực hiện một quá trình mở rộng các bảng chữ cái hay nói cách khác là nó dùng ký tự bổ sung để biểu diễn lại các chuỗi của ký tự chính quy. Để nén LZW trên mã ASCII 8 bits ta cần mở rộng bảng chữ cái bằng cách dùng 9 bits hay nhiều hơn 256 ký tự bổ sung mà mã 9 bits cung cấp được dùng để lưu trữ các chuỗi mã được quyết định từ các chuỗi trong nguồn tin. Thuật toán sẽ không đạt hiệu quả nén cao nếu có những điều kiện sau:
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
You must be registered for see links
Tags: thuật toán nén lz78
Last edited by a moderator: