đồ án tốt nghiệp Đề Tài: tìm hiểu ngôn ngữ vc++ 6.0 Và ứng dụng trong việc nén và giải nén tập tin văn bản
Mục tiêu của đề tài: Tìm hiểu ngôn ngữ VC ++ 6.0, 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++ 6.0 Vµ øng dông t rong
viÖc nÐn vµ gi¶i nÐn t Ëp t in v¨n b¶n
GVHD: T h.s H uúnh T hanh
B×nh
SVTH:N guyÔn §øc N ghÜ a
MSSV:98S1049
Líp 40TH
Nha Tr ang 10/2003
L êi C¶ m ¥n
Em xi n ®-îc nãi l ªn l êi c¶ m ¬n
®Êng si nh 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 ++ 6.0
Nghiªn cøu vµ cµi ®Æt mét sè
t huËt t o¸n nÐn vµ gi¶i nÐn t Ëp
t in b¶n
v¨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
*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:
Dữ liệu nén Giải mã Mã hoá Dữ liệu
gốc
MỘT SỐ PHƯƠNG PHÁP
NÉN nén dữ liệu
*Định nghĩa
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:
1. Đặt vị trí mã hoá nơi bắt đầu của dòng đầu vào
2. 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.
4.Nếu 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:
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
*Ví dụậtựtoán n nén:
Thu LZW
th c hiệ
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.