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ộtTuyể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
259
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
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 tr
Dành riêng cho anh em Ket-noi, bác nào cần
download miễn phí bản đầy đủ thì trả lời topic này, Nhóm Mods sẽ gửi tài liệu cho bạn qua hòm tin nhắn nhé.
- Bạn nào có tài liệu gì hay thì up lên đây chia sẻ cùng anh em.
- Ai cần tài liệu gì mà không tìm thấy ở forum, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
source: content/getpagecontent?id=373644&pageNumber=2&documentKindID=1
