Mục tiêu của đề tài: Tìm hiểu ngôn ngữ VC ++ , Nghiên cứu và cài đặt một số thuật toán nén và giải nén tập tin văn bản | §å ¸N TèT NGHIÖP §Ò Tµi: T×M HIÓU NG¤N NG÷ VC++ Vµ øng dông trong viÖc nÐn vµ gi¶i nÐn tËp tin v¨n b¶n GVHD: Huúnh Thanh B×nh SVTH:NguyÔn §øc NghÜa MSSV:98S1049 Líp 40TH Nha Trang 10/2003 Lêi C¶m ¥n Em xin ®îc nãi lªn lêi c¶m ¬n ®Êng sinh thµnh vµ ThÇy, C« ®· nu«i, d¹y em lín kh«n. Yªu cÇu cña ®Ò tµi T×m hiÓu ng«n ng÷ VC ++ Nghiªn cøu vµ cµi ®Æt mét sè thuËt to¸n nÐn vµ gi¶i nÐn tËp tin v¨n b¶n Những khái niệm cơ bản và mục đích của việc nén dữ liệu. Một số phương pháp nén Thực hiện chương trình Kết luận. Nh÷ng kh¸i niÖm c¬ b¶n vµ môc ®Ých cña viÖc nÐn d÷ liÖu *Khái niệm dữ liệu Là bao gồm các phần tử cơ sở mà ta gọi là dữ liệu nguyên tử. *Mục đích của việc nén dữ liệu Lưu trữ dữ liệu được nhiều hơn. Tiết kiệm được vùng nhớ. Giảm chi phí lưu trữ. Mang lại hiệu quả cho việc truyền dữ liệu trên mạng. *Dạng nén Có hai dạng nén bảo toàn và nén không bảo toàn. *Quá trình nén và giải nén Công đoạn nén: Dữ liệu Mã hoá Đóng gói Dữ liệu nén Công đoạn giải nén: Giải mã Mã hoá Dữ liệu nén Dữ liệu gốc MỘT SỐ PHƯƠNG PHÁP NÉN *Định nghĩa nén dữ liệu Là để ghi lại dòng dữ liệu sao cho tốn ít bộ nhớ hơn mà có thể cho phép chúng ta khôi phục lại dữ liệu ban đầu. *Một số loại mã Mã ký hiệu:Quy ước các mã được sử dụng để nhận ra một chuỗi các sự kiện khác nhau. Mã đóng gói:Trong phương pháp mã bao giờ cũng có một khâu đóng gói. Mã theo độ dài: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 đó. *Mô hình nén Nén dữ liệu có mô hình nguồn Những thuật toán nén dữ liệu đặt trưng cho mô hình nguồn điển hình là: Thuật toán Huffman. Thuật toán Fano-Shannon Nén dữ liệu chưa có mô hình nguồn Một trong những đặt điểm nén dữ liệu chưa có mô hình nguồn là ngôn ngữ tự nhiên. *Kỹ thuật từ điển Sử dụng phương pháp phân đoạn văn bản thành các đoạn nhỏ hơn sao cho nó đạt được độ dài nhất có thể được mà nó đã xuất hiện trong quá khứ. Định nghĩa về phân đoạn văn bản: Phân đoạn văn bản A là chia nó ra thành các đoạn nhỏ hơn, mỗi đoạn được gọi là một phân đoạn. Có hai loại từ điển: Tù điển tĩnh: Mã có từ điển cố định được gọi là mã tĩnh hay nói cách khác là từ điển tĩnh. Từ điển động: Được xây dựng trong quá trình chạy chương trình. THỰC HIỆN CHƯƠNG TRÌNH *Chương trình đã cài đặt được các thuật toán nén theo kỹ thuật từ điển sau: Thuật toán LZSS Thuật toán LZARI Thuật toán LZW *Thuật toán LZSS Thuật toán nén: Đặt vị trí mã hoá nơi bắt đầu của dòng đầu vào Tìm sự phù hợp tối đa trong cửa sổ cho vùng đệm P :=con trỏ tới sự phù hợp L:= chiều dài của sự phù hợp 3. If L>=MIN_LENGTH then -Đầu ra P và di chuyển vị trí mã hoá một ký tự ở trước. else Đầu ra là ký tự đầu tiên của vùng đệm và chuyển vị trí mã hoá một ký tự ở trước. có nhiều ký tự trong luồng đầu vào thì trở về bước 2. Thuật toán giải nén: Ngược lại quá trình nén. Ví dụ thuật toán nén lzss *Thuật toán LZW Thuật toán nén lzw: String=lấy ký tự vào While vẫn còn ký tự vào Do begin ch:=lấy ký tự vào if String +ch là trong bảng chuỗi then String = String+ch else begin Đầu ra Code của String Thêm String + ch tới bảng chuỗi String String=ch end; End; Thuật toán giải nén LZW Read Old_code While Vẫn còn ký tự đầu vào Do begin read New_code String=sự chuyển đổi của New_code Output String ch= ch đầu tiên trong String Thêm Old_code + ch để chuyển đổi bảng old_code=New_code end *Thuật toán LZW Ví dụ thực hiện nén: Ví dụ thực hiện giải nén: *So sánh giữa các thuật toán KẾT LUẬN *Đánh giá chương trình Đã cài đặt được một số thuật toán nén theo kỹ thuật từ điển như: LZSS, LZARI,LZW. Do hạn chế về tài liệu tham khảo nên một số thuật toán nén khác chưa cài đặt được. *Hướng phát triễn Có thể mở rộng chương trình để thực hiện trong việc nén tập tin hình ảnh.
