Bài tập & Hướng dẫn Các giải thuật nén file

Chia sẻ: Lit Ga | Ngày: | Loại File: PDF | Số trang:5

Thêm vào BST

Báo xấu

328
lượt xem 61
download

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

Tham số truyền vào là tên của file nén và tên file kết quả giải nén. Kết quả trả về 0 nếu không thành công; 1 nếu thành công. - Destructor: giải phóng các dữ liệu Yêu cầu: thư viện được xây dựng...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài tập & Hướng dẫn Các giải thuật nén file

CTDL 2 CÁC GIẢI THUẬT NÉN ---oOo--- Bài 1. Nén RLE Viết lớp RLE với các chức năng cơ bản để nén và giải nén tập tin, sử dụng thu ật toán nén PCX RLE. Các chức năng yêu cầu như sau: - Contructor: khởi tạo các thành phần d ữ liệu cần thiết cho việc nén và giải nén - Compress: tiến hành nén 1 file cho trước thành 1 tập tin nén. Tham số truyền vào là tên củ a file cần nén và tên file kết qu ả nén. Kết quả trả về 0 nếu không thành công; 1 nếu thành công, trong trường hợp này, trả về hiệu suất của phép nén. - De-Compress: giải nén 1 file cho trước (đ ã được nén bằng chức năng Compress của class). Tham số truyền vào là tên củ a file nén và tên file kết qu ả giải nén. Kết qu ả trả về 0 nếu không thành công; 1 nếu thành công. - Destructor: giải phóng các d ữ liệu Yêu cầu: thư viện được xây dựng thành 2 file - File .H chứa mô tả class - File .CPP chứa cài đặt các phương thức của class Bài 3. Nén Huffman tĩnh Viết lớp STATIC_HUFFMAN với các chức năng cơ b ản đ ể nén và giải nén tập tin. Các chức năng yêu cầu như sau: - Contructor: khởi tạo các thành phần d ữ liệu cần thiết cho việc nén và giải nén - Compress: tiến hành nén 1 file cho trước thành 1 tập tin nén. Tham số truyền vào là tên củ a file cần nén và tên file kết qu ả nén. Kết quả trả về 0 nếu không thành công; 1 nếu thành công, trong trường hợp này, trả về hiệu suất của phép nén. File nén lưu bảng thố ng kê số lần xuất hiện củ a các ký tự với mô tả chi tiết Header như sau: o 4 b ytes: số b yte (kích thước) của file gốc o 2 b ytes: chiều dài Header (kể cả bảng thống kê số lần xuất hiện củ a các ký tự) = 6 + 5*n o Bảng thống kê số lần xu ất hiện của mỗi ký tự (5*n bytes) - De-Compress: giải nén 1 file cho trước (đ ã được nén bằng chức năng Compress của class). Tham số truyền vào là tên củ a file nén và tên file kết qu ả giải nén. Kết qu ả trả về 0 nếu không thành công; 1 nếu thành công. - Print-Tree: in cây Huffman - Print-Code-Table: In bảng mã bit củ a từng ký tự. Theo thứ tự tăng d ần của mã ASCII - Destructor: giải phóng các d ữ liệu 1/5
Hướng dẫn tóm tắt ý chính Bài 3: Mô tả cây Huffman: // số nút max trong cây #define MAX_TREE_NODES 511 // số p hần tử max trong #define MAX_CODETABLE_ITEMS 256 bảng mã bit // c.dài max của mã bit 256 bits # 32 bytes #define MAX_BIT_LEN 256 // Cấu tạo 1 phần tử trong cây struct HUFF_TREE_NODE { // Ký tự đại diện Node char c; // Trọng số của node unsigned long nFreq; // 1: Đã xử lý – 0 : Chưa xử lý (dùng lúc tạo cây) char nUsed; // Con trỏ nút con trái, phải (-1 nếu không có nút con) int nLeft, nRight; } // Cấu tạo 1 phần tử trong bảng mã bit struct CODE_TABLE_ITEM { // Mã bit của ký tự char Bits[MAX_BIT_LEN/8]; // số b it thật sự sử dụ ng unsigned char nBitLen; } // Mả ng lưu trữ cây struct HUFF_TREE_NODE HuffTree[MAX_TREE_NODES]; // Bảng mã bit của các ký tự. Mã bit của ký tự a là HuffCodeTable[a] struct CODE_TABLE_ITEM HuffCodeTable[MAX_CODETABLE_ITEMS]; // Các hàm chính q uan trọ ng void initTree(); void initCodeTable(); int demKytu(char *fn); int tim2PhantuMin(int &i, int &j); int taoCay(); void taoBangMaBit(int nRoot); void duyetCay(int nCurrNode, char *BitCode, int BitCodeLen); int maHoa1KyTu(char c, FILE *f, int nFinish=0); // ----------------------------------------------------------------------------------------------- // Hàm initTree(…) // + Khởi tạo cây (HuffTree), 511 phần tử. Trong đó, 256 phần tử đầu tiên là 256 nút lá của cây. // Phần tử thứ i: - c = ký tự thứ i (dùng cho 256 phần tử đầu tiên) // - nFreq = 0; nUsed = 0; (dùng cho 511 phần tử) // - nLeft = nRight = -1; (dùng cho 511 phần tử) // // ----------------------------------------------------------------------------------------------- void initTree() { … } 2/5
// ----------------------------------------------------------------------------------------------- // Hàm initCodeTable(…) // + Khởi tạo b ảng mã bit (HuffCodeTable) 256 phần tử // - nBitLen = 0 // ----------------------------------------------------------------------------------------------- void initCodeTable() { … } // ----------------------------------------------------------------------------------------------- // Hàm demKytu(…) // + Duyệt file fn, đếm số ký tự mỗi lo ại và cập nhật vào b ảng thố ng kê (256 phần tử đầu tiên củ a cây) // // + Hàm trả về số lo ại ký tự trong file // ----------------------------------------------------------------------------------------------- int demKytu(char *fn) { … } // ----------------------------------------------------------------------------------------------- // Hàm taoCay(…) // + Dựa trêh b ảng thố ng kê (256 phần tử đầu tiên của cây), tạo các nút mới // + Thêm các nút mới vào cuố i mảng HuffTree (từ phần từ 257  511) // + Hàm trả về chỉ số củ a phần tử chứa nút gố c củ a cây // ----------------------------------------------------------------------------------------------- int taoCay() { int n = 256; // Nút mới bắt đ ầu từ p hần tử thứ 257 trong mảng while (1) { // Tìm 2 phần tử có trọ ng số nhỏ nhất Kq = tim2PhantuMin(i, j); // phần tử i nhỏ hơn phần tử j // Không tìm thấy  đ ã tạo cây xong, if (Kq==0) break; // nút gốc nằm tại vị trí (n-1) // Nếu tìm đ ược 2 phần tử nhỏ nhất (i, j)  tạo 1 phần tử mới với 2 con là i, j …. n++; // Đánh d ấu 2 phần tử i, j đ ã xử lý xong …. } return (n – 1); } // ----------------------------------------------------------------------------------------------- // Hàm tim2PhantuMin(…) // + Tìm 2 phần tử có trọ ng số nhỏ nhất trong bảng (chỉ xét trên những phần tử chưa xử lý) (có cờ nUsed = 0 và nFreq > 0) // // + Hàm trả về 0 nếu không tìm đ ược 2 phần tử (chỉ còn 1 phần tử duy nhất)  đ ã xây dựng cây xong // // + Hàm trả về 1 nếu tìm được 2 phần tử. Lúc đó, i và j là chỉ số củ a 2 phần tử tìm được. 3/5
- Qui ước phần tử i luôn nhỏ hơn phần tử j (nhỏ hơn về trọng số ; // nếu trọ ng số b ằng nhau, nhỏ hơn về mã ASCII) //  p hần tử i sẽ trở thành nút con bên trái; phần tử j sẽ trở thành nút con bên // phải // ----------------------------------------------------------------------------------------------- int tim2PhantuMin(int &i, int &j) { } // ----------------------------------------------------------------------------------------------- // Hàm taoBangMaBit(…) // + Duyệt cây HuffTree và xác định bảng mã bit cho mỗ i ký tự. // + Kết quả lưu vào bảng HuffCodeTable // + nRoot là chỉ số củ a phần tử gố c trong cây (trả về từ hàm taoCay) // + Gọ i hàm d uyetCay với nút đầu tiên được xét là nút gố c // ----------------------------------------------------------------------------------------------- void taoBangMaBit(int nRoot) { … } // ----------------------------------------------------------------------------------------------- // Hàm duyetCay(…) // + Hàm đệ qui duyệt cây Huffman (HuffTree) và tạo lập b ảng mã bit cho các ký tự // + nCurrNode: chỉ số của nút hiện đang được duyệt // + BitCode: chu ỗi bit được ghi nhận hiện tại (ứng với nút nCurrNode) // + BitCodeLen: chiều dài dãy bit (số b it thực sự trong dãy BitCode) // ----------------------------------------------------------------------------------------------- void duyetCay(int nCurrNode, char *BitCode, int BitCodeLen) { if (nCurrNode== -1) return; if (Nếu nút hiện tại là nút lá) { // thì thêm mã bit củ a nó vào bảng HuffCodeTable … return; } // Thêm 1 bit 0 vào dãy BitCode, tại vị trí BitCodeLen … duyetCay(HuffTree[nCurrNode].nLeft, BitCode, BitCodeLen+1); // Duyệt trái // Thêm 1 bit 1 vào dãy BitCode, tại vị trí BitCodeLen … duyetCay(HuffTree[nCurrNode].nRight, BitCode, BitCodeLen+1); // Duyệt phải } // ----------------------------------------------------------------------------------------------- // Hàm maHoa1KyTu(…) // + Hàm mã hóa 1 ký tự c thành chuỗ i bit tương ứng và ghi vào file f // + c: ký tự cần mã hóa // + f: file output để ghi chuỗ i bit được mã hóa // + finish: cờ cho biết có kết thúc quá trình mã hóa hay không (khi finish=1, quá trình kết thúc, // hàm sẽ ghi các bit dư vào file f, lúc này không cần quan tâm ký tự c). Khi đó, hàm trả về // số bit có ý nghĩa đ ã ghi lên file. // ----------------------------------------------------------------------------------------------- 4/5
int maHoa1KyTu(char c, FILE *f, int nFinish=0) { // dựa vào HuffCodeTable, xác định được chuỗ i bit của ký tự c // byte sẽ được ghi trực tiếp lên file f. Khai static để lần gọi sau static char out = 0; có // thể giữ được những bit thừa của lần gọi trước static char SoBit = 0; // số b it đang thực sự đ ược lưu trong b yte out // Nếu finish = 1 và SoBit > 0 (lúc này byte out lưu những bit thừa) thì ghi byte out vào file // f và thoát khỏi hàm, trả về SoBit // Duyệt qua từng bit trong chu ỗi bit mã hóa, với mỗi bit: // +Thêm bit vào byte out +Nếu byte out đủ 8 bit, ghi byte out vào file f và đặt lại out=0, SoBit=0 // // Lưu ý: các bit cao được lấy trước, bit thấp được lấ y sau } Một số thao tác xử lý bit : //lay bit thu j cua N BIT = (N >> j) & 1; //Gan 1 bit 0 vao BitCode tai vi tri j temp = 1