Kỹ thuật mã hóa Huffman với mô hình từ điển
CHƯƠNG 0. GIỚI THIỆU 3 CHƯƠNG i. LÝ THUYẾT TỔNG QUAN VỀ NÉN DỮ LIỆU 5 I. Khái niệm về nén dữ liệu 5 II. Một số khái niệm cơ bản 5 II.1. Tỉ lệ nén (compression ratio) 5 II.2. Độ dư thừa số liệu 6 a. Sự lặp lại của những kí tự 6 b. Sự phân bố các kí tự 6 c. Độ dư thừa vị trí 6 d. Những mẫu sử dụng mật độ cao 6 II.3. Độ dài trung bình từ mã 7 II.4. Nén tổn hao và nén không tổn hao 7 a. Nén tổn hao (lossy compression) 7 b. Nén không tổn hao (lossless compression) 7 II.5. Nén số liệu = Mô hình hóa + Mã hóa 7 III. Lý thuyết về mã hÓa 8 III.1. Định nghĩa mã hóa 8 III.2. Một số khái niệm cơ bản 8 a. Chiều dài từ mã 8 b. Trọng lượng từ mã 9 c. Khoảng cách mã 9 III.3. Phân loại mã 9 III.4. Một số phương pháp biểu diễn mã thông dụng 9 a. Phương pháp liệt kê 9 b. Phương pháp đồ hình kết cấu 10 c. Phương pháp cây 10 III.5. Điều kiện để mã phân tách được 11 III.6. Mã có tính tiền tố (prefix) 12 III.7. Định lý về độ dài trung bình từ mã 12 IV. Mã thống kê tối ưu 14 IV.1. Mã Shannon-Fano 14 IV.2. Mã số học 16 IV.3. Mã Huffman 18 V. Mô hình hóa nguồn số liệu 18 V.1. Mô hình thống kê 18 V.2. Mô hình từ điển 20 CHƯƠNG ii. Phương pháp mã hóa Huffman VỚI MÔ HÌNH THỐNG KÊ 21 I. Phương pháp mã hóa Huffman 21 I.1. Mã Huffman tĩnh 21 a. Cở sở nén số liệu của phương pháp mã hóa Huffman tĩnh 21 b. Phương pháp tạo mã Huffman tĩnh 21 c. Phương pháp giải mã Huffman tĩnh 26 d. Ưu và nhược điểm của phương pháp mã hóa Huffman tĩnh với mô hình thống kê 27 CHƯƠNG iii. CÁC PHƯƠNG PHÁP NÉN THEO MÔ HÌNH TỪ ĐIỂN 28 I. Mô hình từ điển tĩnh và mô hình từ điển động 29 II. Các phương pháp nén Lempel và Ziv 31 II.1. Phương pháp nén LZ77 31 II.2. Phương pháp nén LZ78 34 CHƯƠNG iv. KỸ THUẬT MÃ HÓA HUFFMAN ĐỘNG VỚI MÔ HÌNH TỪ ĐIỂN THÍCH ỨNG 38 I. MÃ HÓA HUFFMAN ĐỘNG 38 II. MÔ HÌNH TỪ ĐIỂN THÍCH ỨNG 38 II.1. Kỹ thuật nén với một cửa sổ hạn chế 39 II.2. Các cấu trúc dữ liệu hỗ trợ 39 a. Bộ đệm quay vòng 39 b. Bảng băm (Hash table) 40 III. Tiến trình nén 42 III.1. Quá trình mô hình hóa 42 III.2. Quá trình mã hóa 43 a. Cấu trúc dữ liệu mô tả cây mã Huffman động 43 b. Thủ tục mã hóa 45 IV. Tiến trình giải nén 46 IV.1. Quá trình giải mã theo cây mã Huffman động 46 a. Khởi tạo cây mã đầu tiên 46 b. Thủ tục giải mã 46 IV.2. Quá trình giải nén 47 V. Nhận xét 48 CHƯƠNG V. THỰC NGHIỆM 49 I. So sánh tỉ số nén 49 I.1. Bảng so sánh tỉ số nén 50 I.2. Biểu đồ so sánh tỉ số nén 50 I.3. Nhận xét 51 II. So sánh tốc độ nén 51 II.1. Bảng so sánh tốc độ nén 51 II.2. Biểu đồ so sánh tốc độ nén 51 II.3. Nhận xét 52 III. So sánh tốc độ giải nén 52 III.1. Bảng so sánh tốc độ giải nén 52 III.2. Biểu đồ so sánh tốc độ giải nén 53 III.3. Nhận xét 53 IV. Kết luận 53 CHƯƠNG vi. KẾT LUẬN 54 CHƯƠNG 0 I. GIỚI THIỆU Ngày nay, máy tính đã thâm nhập vào hầu hết các lĩnh vực của đời sống- xã hội. Nói đến máy tính tức là nói đến hai vấn đề lớn : lưu trữ và xử lý thông tin. Với sự bùng nổ thông tin như hiện nay, việc lưu trữ và trao đổi thông tin đã và đang đặt ra nhiều vấn đề cần phải giải quyết, đó là làm sao để lưu trữ một cách tiết kiệm, hiệu quả và trao đổi thông tin một cách nhanh chóng nhất. Một giải pháp là tăng dung lượng của các thiết bị lưu trữ. Tuy nhiên, điều này đòi hỏi cao về mặt kỹ thuật phần cứng và chi phí khá tốn kém. Như vậy, giải pháp này là không kinh tế. Một giải pháp khác nhiều triển vọng hơn và mang tính khả thi đã được đặt ra, đó là nén dữ liệu. Vậy nén dữ liệu là gì ? Có thể hiểu một cách nôm na rằng, nén dữ liệu là quá trình làm giảm dung lượng lưu trữ của dữ liệu mà vẫn bảo toàn được nội dung thông tin trước đó. Như vậy, việc nén dữ liệu sẽ đem lại nhiều lợi ích thiết thực. Đó là : · Tiết kiệm được không gian lưu trữ. · Tăng tốc độ và giảm chi phí truyền dẫn trên mạng. · Bảo mật được thông tin. Mặc dù dung lượng của các thiết bị lưu trữ ngày nay đã tăng đến tốc độ chóng mặt, có thể lên đến hàng chục Gigabytes, nhưng với những lợi ích như đã nêu trên, giải pháp nén dữ liệu trước khi lưu trữ, cũng như truyền dẫn qua mạng là điều khiến chúng ta không thể không xét đến. Nói chung, nén dữ liệu là quá trình biến đổi một luồng các kí hiệu thành một luồng các mã có kích thước nhỏ hơn ban đầu. Thông thường, một quá trình nén được tiến hành qua hai giai đoạn: (1) Mô hình hóa, là giai đoạn tiên đoán về tần suất xuất hiện của các kí tự và / hoặc chuỗi kí tự của văn bản cần nén. (2) Mã hóa, là giai đoạn dựa trên mô hình với tần suất vừa được xác định để tạo ra từ mã tương ứng. Cùng với sự phát triển mạnh mẽ của lý thuyết thông tin, có khá nhiều phương pháp mã hóa và mô hình hóa đã ra đời. Trong các phương pháp mã hóa, đáng chú ý nhất là mã hóa Huffman và mã hóa số học. Phương pháp mã hóa Huffman được D.A Huffman công bố vào năm 1952. Phương pháp mã hóa này đơn giản, dễ xây dựng và cho thời gian mã hóa ngắn. Phương pháp mã hóa số học ra đời vào cuối những năm 70. Phương pháp này hướng đến việc tối ưu độ dài từ mã nên tương đối phức tạp hơn và vì vậy thời gian mã hóa chậm hơn. Kỹ thuật nén xử lý từng kí tự một của luồng kí hiệu đầu vào được gọi là nén với mô hình thống kê (Statistical model). Ngược lại, kỹ thuật nén xem xét mỗi lúc một chuỗi các kí tự từ luồng nhập gọi là nén với mô hình từ điển (Dictionary-based model). Do đặc thù của mô hình từ điển và thực tế cũng cho thấy, với cùng một phương pháp mã hóa thì việc áp dụng mô hình từ điển sẽ cho hiệu quả nén cao hơn nhiều so với mô hình thống kê. Hầu hết các chương trình nén thương mại hiện hành đều sử dụng mô hình từ điển mà điển hình là các chương trình nén nổi tiếng như NCZip, PKZip và WinZip. Trong một thời gian ngắn, việc nghiên cứu tất cả các kỹ thuật nén dữ liệu là điều không khả thi, do vậy, trong cuốn luận văn tốt nghiệp này, tác giả chỉ đi sâu nghiên cứu về phương pháp nén dữ liệu không tổn hao dựa trên kỹ thuật mã hóa Huffman (chủ yếu là mã Huffman động) và mô hình từ điển. Do năng lực bản thân và thời gian có hạn nên Đồ án còn khá nhiều thiếu sót. Xin nhận được những lời phê bình, góp ý quý báu của các thầy cô và bạn đọc để đề tài có thể hoàn thiện hơn trong tương lai. Cấu trúc Đồ án Đồ án bao gồm 6 chương và chương trình Demo trên đĩa. Nội dung như sau : Chương 0 : Giới thiệu đề tài, vai trò và ý nghĩa của nó. Chương I : Trình bày tổng quan về lý thuyết nén và giải nén dữ liệu, làm nền tảng cho việc giải quyết vấn đề đã đặt ra trong Đồ án. Chương II : Trình bày phương pháp nén dữ liệu áp dụng kỹ thuật mã hóa Huffman dựa trên mô hình thống kê. Chương III: Tìm hiểu một số phương pháp nén dựa trên mô hình từ điển. Chương IV : Đi sâu nghiên cứu phương pháp nén dữ liệu áp dụng kỹ thuật mã hóa Huffman động, dựa trên mô hình từ điển thích ứng, làm nền tảng cho việc phát triển chương trình. Chương V : Trình bày kết quả thực nghiệm kiểm tra tính đúng đắn, chính xác của chương trình và so sánh với một số chương trình thương mại có cùng chức năng. Trên cơ sở đó, đánh giá ưu điểm và hạn chế của phương pháp nén được sử dụng. Chương VI : Kết luận, đánh giá những gì đã làm được, những gì chưa đạt được và nêu hướng phát triển của đề tài.
Bạn đang xem trước 20 trang tài liệu Kỹ thuật mã hóa Huffman với mô hình từ điển, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
öu, coï thãø chæïa tæì 10 âãún 100 kê tæû. Thuáût toaïn luän luän tiãún haình so khåïp (match) näüi dung cuía bäü âãûm “nhçn tháúy træåïc” våïi mäüt chuäùi naìo âoï trong tæì âiãøn. Mäüt vê duû âån giaín thãø hiãûn nhæ hçnh dæåïi âáy:
for ( i=0 ; i<MAX -1 ; i++ )\r for ( j = i+1 ; j<MAX ; j++ )\r
Thán cuía cæía säø træåüt
Bäü âãûm
Mäüt cæía säø træåüt âæåüc sæí duûng
Cæía säø træåüt trong LZ77
Hçnh 9.
Hçnh veî trãn laì mäüt âoaûn maî nguäön C âæåüc âem neïn. Cæía säø træåüt coï âäü daìi täøng cäüng laì 64 bytes, våïi 16 bytes trong âoï âæåüc sæí duûng båíi bäü âãûm. Mäùi theí baìi gäöm coï ba haûng muûc dæî liãûu duìng âãø xaïc âënh mäüt cuûm tæì våïi âäü daìi thay âäøi chæïa trong bäü âãûm hiãûn taûi. Âoï laì:
Vë trê cuía cuûm tæì trong cæía säø.
Chiãöu daìi cuûm tæì.
Kê tæû âáöu tiãn åí bäü âãûm theo sau cuûm tæì âoï.
ÅÍ vê duû trãn, bäü âãûm bao gäöm cuûm kê tæû “.
Chæång trçnh neïn thæûc hiãûn thuáût toaïn LZ77 phaït ra theí baìi âáöu tiãn, sau âoï dëch chuyãøn (træåüt) cæía säø sang phaíi nàm kê tæû ( laì âäü daìi cuûm tæì væìa âæåüc maî hoïa, kãø caí kê tæû theo sau ). Nàm kê tæû måïi âæåüc âoüc vaìo bäü âãûm, vaì quaï trçnh làûp laûi nhæ trãn.
i=0 ; i<MAX -1 ; i++ )\r for ( j = i+1 ; j<MAX ; j++ )\r a[i]
Thán cuía cæía säø træåüt
Bäü âãûm
Cæía säø sau khi maî hoïa
Hçnh 10.
Theí baìi tiãúp theo âæåüc phaït ra båíi thuáût toaïn neïn seî maî hoïa cuûm kê tæû “;j+” (bao gäöm caí kê tæû theo sau) thaình . Cuï phaïp cuía theí baìi naìy cho pheïp maî hoïa caí nhæîng cuûm tæì khäng xuáút hiãûn trong cæía säø. Nãúu bäü âãûm chè ra sæû khäng so khåïp (vê duû, noï coï thãø maî hoïa mäüt kê tæû âån leí khäng coï màût trong cæía säø taûi mäüt thåìi âiãøm nhæ laì cuûm tæì coï âäü daìi zero: ) thç phæång phaïp naìy khäng hiãûu quaí, båíi vç âãø maî hoïa mäüt kê tæû phaíi cáön âãún ba loaûi thäng tin. Tuy nhiãn, phaíi tháúy ràòng, thuáût toaïn coï thãø maî hoïa moüi chuäùi kê tæû.
Giaíi thuáût maî hoïa cuía LZ77 laì tæång âäúi âån giaín. Noï cho pheïp xem xeït xuyãn suäút toaìn bäü cæía säø træåüt våïi sæû so khåïp täúi âa, maî hoïa vaì sau âoï chuyãøn âäøi.
Thuáût toaïn giaíi neïn cuîng khaï âån giaín, båíi vç noï khäng thæûc hiãûn nhæîng viãûc so saïnh. Noï âoüc vaìo mäüt theí baìi, xuáút ra cuûm tæì xaïc âënh, âæa ra kê tæû theo sau, dëch chuyãøn vaì làûp laûi. Noï duy trç cæía säø, nhæng khäng laìm viãûc so saïnh chuäùi.
Mäüt hiãûu æïng phuû têch cæûc cuía phæång phaïp giaíi neïn laì noï coï thãø sæí duûng cuûm tæì chæa âæåüc maî hoïa âãø maî hoïa cuûm tæì âaî coï. Trong mäüt nguäön tin coï 100 kê tæû “A” liãn tiãúp, vê duû, chuïng ta coï thãø maî hoïa kê tæû “A” âáöu tiãn laì . Luïc naìy, cæía säø seî nhæ hçnh dæåïi:
...................................................................AAAAAAAAAAA
Maî hoïa cho 100 kê tæû ‘A’ liãn tiãúp nhau
Hçnh 11.
Chuïng ta coï thãø maî hoïa chên kê tæû “A” kãú tiãúp laì (giaí sæí kêch thæåïc cuía cæía säø træåüt laì 38). Âiãöu âoï coï veí nhæ laì sæí duûng mäüt cuûm tæì coï chên kê tæû. Màûc duì chuïng ta coï thãø tháúy taïm kê tæû trong cuûm tæì laì coï màût åí bäü âãûm. Khi bäü pháûn giaíi maî nháûn âæåüc theí baìi , bäü âãûm seî nhæ hçnh dæåïi:
...................................................................A
Vë trê so khåïp bäü âãûm
Bäü âãûm khi bäü pháûn giaíi maî nháûn âæåüc theí baìi
Hçnh 12.
Nhæng nãúu xem xeït thuáût toaïn giaíi neïn, ta seî tháúy caïch thæïc noï tiãún haình thuí thuáût naìy. Sau khi kê tæû âáöu tiãn âæåüc sao cheïp, bäü âãûm seî nhæ sau:
...................................................................AA
Vë trê so khåïp + i bäü âãûm + i
Bäü âãûm sau khi sao cheïp kê tæû âáöu tiãn
Hçnh 13.
Qua voìng làûp kãú tiãúp, chên kê tæû “A” seî âæåüc sao cheïp, màûc duì chuïng khäng coï màût trong cæía säø khi bàõt âáöu tiãún haình giaíi maî. Sau khi hoaìn táút viãûc sao cheïp, kê tæû âån tiãúp theo seî âæåüc âoüc vaìo, vaì bäü âãûm sàôn saìng chuyãøn dëch nhæ hçnh sau:
...................................................................AAAAAAAAAAA
Vë trê so khåïp + i bäü âãûm + i
Bäü âãûm khi sàôn saìng chuyãøn dëch
Hçnh 14.
Vê duû naìy cho tháúy âiãøm maûnh cuía phæång phaïp neïn LZ77: thêch æïng nhanh choïng våïi säú liãûu âáöu vaìo. ÅÍ vê duû trãn, noï maî hoïa mäüt loaût mæåìi kê tæû khi maì tæì âiãøn cuía noï chè chæïa mäüt kê tæû âån.
Mäüt váún âãö låïn xuáút hiãûn bãn trong LZ77. Âoï laì, khi maî hoïa noï phaíi so saïnh chuäùi kê tæû trong bäü âãûm våïi táút caí caïc vë trê cuía cæía säø træåüt. Nãúu sæí duûng mäüt cæía säø nhoí âãø læu træî caïc chuäùi âaî âæåüc xem xeït træåïc âoï, thuáût toaïn seî liãn tuûc boí qua nhæîng thay âäøi åí ngoî vaìo cuía tæì âiãøn, båíi vç noï træåüt nhanh qua pháön tæì âiãøn. Nhæ váûy, âãø tàng tyí säú neïn, ta phaíi tàng kêch thæåïc cuía cæía säø træåüt. Âiãöu naìy seî dáùn âãún hai báút låüi chênh. Thæï nháút, chuïng ta seî täún mäüt säú bit nhiãöu hån âãø maî hoïa cho mäüt theí baìi. Chàóng haûn, khi tàng kêch cåî cuía cæía säø tæì 4KB lãn 64KB, chuïng ta seî cáön 16 bits thay vç 12 bits âãø maî hoïa vë trê trong cæía säø, vaì cáön 10 bits thay vç 4 bits âãø maî hoïa cho âäü daìi cuûm tæì trong bäü âãûm nãúu kêch thæåïc bäü âãûm tàng tæì 16 bytes lãn 1KB. Nhæ váûy, ta cáön âãún 26 bits thay cho 16 bits âãø maî hoïa mäüt cuûm tæì. Thæï hai, viãûc tàng thäng säú trãn seî laìm cho thåìi gian neïn trong CPU tàng lãn âaïng kãø. Våïi LZ77, nãúu tàng kêch thæåïc cæía säø træåüt tæì 4KB lãn 64KB thç thåìi gian tçm kiãúm chuäùi seî tàng lãn 16 láön, vç moüi chuäùi trong cæía säø âãöu âæåüc so saïnh våïi bäü âãûm. Tçnh thãú báút låüi chè thæûc sæû phaït sinh khi tàng kêch cåî bäü âãûm, båíi vç thåìi gian chaûy seî tàng tè lãû våïi chiãöu daìi bäü âãûm. Chæång trçnh seî chaûy cháûm âi khoaíng 64 láön nãúu tàng dung læåüng cuía bäü âãûm tæì 16 bytes lãn 1024 bytes.
Tuy nhiãn, màût têch cæûc laì quaï trçnh giaíi maî seî khäng chëu háûu quaí cuía viãûc tàng kêch thæåïc cæía säø træåüt láùn bäü âãûm. Quaï trçnh giaíi maî chè tiãún haình sao cheïp laûi nhæîng cuûm tæì, khäng thæûc hiãûn viãûc tçm kiãúm chuäùi nãn täúc âäü thæûc hiãûn nhanh hån.
Mäüt váún âãö næîa laì khi cuûm tæì / kê tæû åí bäü âãûm khäng tçm tháúy trong tæì âiãøn. Khi âoï, chæång trçnh neïn váùn sæí duûng âuïng ba loaûi thäng tin liãn hãû chè âãø maî hoïa mäüt kê tæû. Âãø tháúy âæåüc sæû laîng phê naìy, giaí thiãút ràòng kêch thæåïc cæía säø træåüt laì 4KB vaì bäü âãûm laì 16 bytes, nhæ váûy cáön 12 bits âãø maî hoïa vë trê trong cæía säø, 4 bits âãø maî hoïa cho chiãöu daìi chuäùi. Nghéa laì khi maî hoïa theí baìi daûng phaíi cáön âãún 24 bits maì táút caí chè âãø maî hoïa cho mäüt kê tæû 8 bit. Âoï laì mäüt caïi giaï quaï låïn phaíi traí.
Vç nhæîng haûn chãú noïi trãn, hai taïc giaí Lempel vaì Ziv âaî caíi tiãún LZ77 vaì âæa ra phæång phaïp neïn LZ78.
II.2. Phæång phaïp neïn LZ78
LZ78 tæì boí khaïi niãûm vãö mäüt cæía säø træåüt. Trong LZ77, tæì âiãøn âæåüc âënh nghéa laì mäüt cæía säø coï kêch thæåïc cäú âënh cuía nhæîng âoaûn vàn baín âæåüc âoüc vaìo træåïc âoï. Nhæng våïi LZ78, tæì âiãøn laì mäüt danh saïch khäng coï giåïi haûn cuía nhæîng cuûm tæì âaî âæåüc xem xeït træåïc âoï.
LZ78 cuîng coï mäüt vaìi âiãøm tæång âäöng våïi LZ77. LZ77 xuáút ra mäüt loaût caïc theí baìi, mäùi theí baìi gäöm coï ba thaình pháön: . LZ78 cuîng xuáút ra mäüt loaût caïc theí baìi våïi yï nghéa tæång tæû. Mäùi theí baìi cuía LZ78 bao gäöm: . Khäng giäúng nhæ LZ77, chiãöu daìi cuía chuäùi âæåüc choün khäng âæåüc chuyãøn âi vç bäü giaíi maî biãút âæåüc âiãöu âoï.
Mäüt âiãøm khaïc biãût næîa so våïi LZ77 laì LZ78 khäng coï mäüt cæía säø âáöy nhæîng chuäùi âæåüc âoüc sàôn âãø sæí duûng nhæ mäüt tæì âiãøn. Thay vaìo âoï, LZ78 taûo ra mäüt cuûm tæì måïi taûi mäùi thåìi âiãøm mäüt theí baìi âæåüc xuáút ra vaì cáûp nháût cuûm tæì âoï vaìo tæì âiãøn. Sau khi cuûm tæì âaî âæåüc cáûp nháût, noï coï thãø seî âæåüc bäü maî hoïa sæí duûng taûi mäüt thåìi âiãøm báút kyì trong tæång lai chæï khäng chè åí vaìi ngaìn kê tæû kãú tiãúp.
Khi sæí duûng thuáût toaïn LZ78, caí bäü maî hoïa vaì giaíi maî âãöu khåíi âäüng våïi mäüt tæì âiãøn gáön nhæ träúng räùng. Theo âënh nghéa, tæì âiãøn chè coï mäüt xáu âaî âæåüc maî hoïa, âoï laì xáu räùng. Mäùi khi mäüt kê tæû âæåüc âoüc vaìo, noï seî âæåüc thãm vaìo chuäùi hiãûn taûi. Chæìng naìo maì chuäùi hiãûn haình coìn so khåïp våïi mäüt cuûm tæì naìo âoï trong tæì âiãøn, quaï trçnh naìy váùn tiãúp tuûc.
Nhæng cuäúi cuìng seî âãún luïc chuäùi hiãûn haình khäng khåïp våïi xáu âaî coï trong tæì âiãøn. Âáy laì luïc LZ78 xuáút ra mäüt theí baìi vaì mäüt kê tæû. Cáön nhåï ràòng, chuäùi âaî coï mäüt sæû so khåïp trong tæì âiãøn cho âãún khi kê tæû cuäúi cuìng âæåüc vaìo. Vç váûy, chuäùi hiãûn taûi âæåüc xem nhæ laì sæû so khåïp cuäúi cuìng cho âãún khi mäüt kê tæû måïi âaî âæåüc thãm vaìo. Âáy laì luïc LZ78 seî âæa ra: chè säú cuía muûc tæì væìa âæåüc so khåïp trong tæì âiãøn vaì kê tæû thãm vaìo maì gáy ra sæû khäng so khåïp.
Nhæng khäng dæìng taûi âáy, LZ78 coìn thæûc hiãûn thãm mäüt bæåïc, chuäùi måïi bao gäöm chuäùi so khåïp trong tæì âiãøn vaì kê tæû måïi, seî âæåüc thãm vaìo tæì âiãøn. Sau naìy, khi chuäùi âoï xuáút hiãûn noï coï thãø âæåüc sæí duûng âãø xáy dæûng chuäùi daìi hån.
Theo âënh nghéa, chuäùi räùng seî luän so khåïp våïi xáu 0, âoï laì nuït räùng trong tæì âiãøn. Do âoï, khi chuïng ta gàûp mäüt kê tæû láön âáöu tiãn, noï seî âæåüc maî hoïa nhæ laì mäüt xáu 0 cäüng våïi kê tæû âoï. Sau naìy, nãúu kê tæû âoï laûi xuáút hiãûn, noï seî âæåüc maî hoïa nhæ mäüt pháön cuía xáu.
Dæåïi âáy laì mäüt vê duû vãö âáöu ra cuía bäü maî hoïa:
Chuäùi vàn baín vaìo: “DAD DADA DADDY DADO...”
Quaï trçnh maî hoïa LZ78 bàõt âáöu maì khäng coï xáu naìo trong tæì âiãøn; vç váûy, kê tæû âáöu tiãn âoüc âæåüc tæì luäöng nháûp, “D”, taûo ra mäüt chuäùi chæa coï trong tæì âiãøn. Bäü maî hoïa seî xuáút ra mäüt càûp , trong træåìng håüp naìy laì 0 vaì “D”. Læu yï ràòng, tæì âiãøn âæåüc khåíi taûo våïi giaï trë 0 nhæ laì mäüt cuûm tæì räùng.
Hai kê tæû âáöu tiãn âi qua bäü maî hoïa, “D” vaì “A”, chæa âæåüc tháúy træåïc âoï. Mäùi mäüt trong säú chuïng seî âæåüc maî hoïa nhæ laì mäüt càûp 0 cäüng våïi kê tæû. “D” âæåüc cáûp nháût vaìo tæì âiãøn nhæ laì cuûm tæì 1, “A” âæåüc cáûp nháût vaìo tæì âiãøn nhæ laì cuûm tæì 2.
Khi kê tæû thæï 3 laì “D” âæåüc âoüc vaìo, noï so khåïp våïi mäüt xáu coï trong tæì âiãøn. Kê tæû tràõng “ “ âæåüc âoüc tiãúp vaìo seî taûo ra xáu “D “ chæa coï trong tæì âiãøn. LZ78 seî xuáút ra maî 1 cho chuäùi træåïc (chuäùi “D”) vaì tiãúp theo laì kê tæû tràõng “ “.
Maî xuáút
Kê tæû xuáút
Chuäùi âæåüc maî hoïa
Chè säú cuía cuûm tæì trong tæì âiãøn
0
‘D’
“D”
1
0
‘A’
“A”
2
1
‘ ‘
“D “
3
1
‘A’
“DA”
4
4
‘ ‘
“DA “
5
4
‘D’
“DAD”
6
1
‘Y’
“DY”
7
0
‘ ‘
“ “
8
6
‘O’
“DADO”
9
Khi tiãúp tuûc maî hoïa, tæì âiãøn nhanh choïng xáy dæûng âæåüc nhæîng xáu daìi. Sau khi 19 kê tæû âaî âæåüc âoüc vaìo hãút vaì âæåüc maî hoïa, ta coï tæì âiãøn nhæ sau:
0
“ “
1
“D”
2
“A”
3
“D “
4
“DA”
5
“DA “
6
“DAD”
7
“DY”
8
“ “
9
“DADO”
Cuîng nhæ LZ77, LZ78 coï thãø tuìy yï thiãút láûp kêch thæåïc cuía xáu trong tæì âiãøn. Tuy nhiãn, chuïng ta cáön læu yï âãún sæû taïc âäüng cuía noï trong hai træåìng håüp. Mäüt laì, cáön læu yï âãún säú bêt cung cáúp cho theí baìi xuáút ra âäúi våïi mäùi tæì maî. Hai laì, quan troüng hån, cáön phaíi xeït xem CPU máút bao nhiãu thåìi gian âãø quaín lyï tæì âiãøn.
Theo lyï thuyãút, LZ78 coï thãø neïn täút hån nãúu ta tàng kêch thæåïc cuía tæì âiãøn. Nhæng âiãöu âoï chè âuïng khi kêch thæåïc cuía nguäön säú liãûu vaìo tæång âäúi låïn. Mäüt khoï khàn thæûc sæû våïi LZ78 laì viãûc quaín lyï tæì âiãøn. Nãúu sæí duûng maî 16 bits âãø maî hoïa chè säú cuía xáu trong tæì âiãøn, chuïng ta coï thãø coï 65.536 xáu khaïc nhau, bao gäöm caí maî räùng. Vaì mäùi xáu coï thãø khaï daìi.
Caïc xáu âoï coï thãø âæåüc læu træî trong mäüt cáy nhiãöu nhaïnh. Cáy naìy coï nuït gäúc mang maî 0 (xáu räùng). Mäùi kê tæû âæåüc thãm vaìo xáu räùng laì mäüt nhaïnh måïi cuía cáy vaì mäùi xáu âæåüc taûo ra theo caïch naìy seî âæåüc gaïn cho mäüt säú æïng våïi mäüt nuït måïi. Våïi vê duû trãn, ta coï cáy tæì âiãøn nhæ sau:
Mäüt cáy tæì âiãøn LZ78
“O“
9
“D“
6
“ “
5
“Y“
7
“A“
4
“ “
3
“D“
1
“A“
2
“ “
8
Hçnh 15.
CHÆÅNG IV
KYÎ THUÁÛT MAÎ HOÏA HUFFMAN ÂÄÜNG VÅÏI MÄ HÇNH TÆÌ ÂIÃØN THÊCH ÆÏNG
Chæång naìy, chuïng ta âi tçm hiãøu vãö phæång phaïp maî hoïa Huffman âäüng (coìn goüi laì maî hoïa Huffman thêch æïng). Âáy laì phæång phaïp maî hoïa âæåüc sæí duûng trong chæång trçnh minh hoüa cho âäö aïn cuìng våïi mä hçnh tæì âiãøn.
I. MAÎ HOÏA Huffman ÂÄÜNG
Phæång phaïp maî hoïa Huffman ténh cho tháúy mäüt nhæåüc âiãøm cuía noï laì bãn phaït (bãn maî hoïa) phaíi truyãön âi cáúu truïc cuía cáy maî (hoàûc täúi thiãøu laì baíng thäúng kã táön suáút cuía caïc kê hiãûu) cuìng våïi dæî liãûu âaî âæåüc maî hoïa âãø cho bãn thu (bãn giaíi maî) coï thãø khäi phuûc laûi chênh xaïc dæî liãûu gäúc. Quaï trçnh neïn vaì giaíi neïn âãöu dæûa vaìo mäüt cáy maî Huffman duy nháút, nghéa laì dæûa vaìo mäüt bäü tæì maî duy nháút, trãn cå såí thäúng kã toaìn bäü nguäön säú liãûu ngay tæì luïc âáöu.
Âãø khàõc phuûc nhæîng haûn chãú âoï, ngæåìi ta âaî âæa ra maî Huffman âäüng.
Cå chãú laìm viãûc cuía maî Huffman âäüng laì caí bãn phaït vaì bãn thu âãöu phaíi tæû xáy dæûng vaì cáûp nháût cáy maî trong suäút mäùi quaï trçnh neïn vaì giaíi neïn. Nghéa laì, cáúu truïc cuía cáy maî vaì do âoï hçnh daïng cáy maî luän luän thay âäøi trong mäùi quaï trçnh âoï. Mäüt æu âiãøm cuía maî Huffman âäüng laì viãûc xáy dæûng cáy maî khäng cáön phaíi thäúng kã toaìn bäü nguäön säú liãûu ngay tæì luïc âáöu. Quaï trçnh xáy dæûng cáy maî trong khi maî hoïa/giaíi maî âæåüc tiãún haình theo caïc bæåïc sau:
Bæåïc 1. Khåíi âäüng cáy maî räùng âáöu tiãn.
Bæåïc 2. Âäúi våïi bãn phaït : Nháûn mäüt kê hiãûu cáön maî hoïa vaì maî hoïa theo cáy maî hiãûn haình.
Âäúi våïi bãn thu : Láúy mäüt tæì maî tæì file neïn vaì giaíi maî theo cáy maî hiãûn haình.
Bæåïc 3. Cáûp nháût laûi cáy maî vaì quay vãö laûi bæåïc 2.
MÄ HÇNH TÆÌ ÂIÃØN THÊCH ÆÏNG
Nhæ âaî noïi, caïc phæång phaïp mä hçnh hoïa xæí lyï mäùi luïc mäüt chuäùi kê hiãûu tæì luäöng nháûp âæåüc goüi chung laì mä hçnh tæì âiãøn. Tuy nhiãn, coï nhæîng mä hçnh laì mä hçnh tæì âiãøn nhæng kyî thuáût maì chuïng sæí duûng laûi ráút khaïc nhau. Chàóng haûn, caïc kyî thuáût mä hçnh hoïa cuía LZ77, LZ78 hay LZW. Kyî thuáût mä hçnh hoïa âæåüc caìi âàût cho âäö aïn khaï giäúng våïi kyî thuáût âæåüc sæí duûngåí LZ77, noï âæåüc goüi laì “kyî thuáût neïn sæí duûng cæía säø haûn chãú” (Finite window compression).
Phæång phaïp maî hoïa âæåüc sæí duûng cuìng våïi mä hçnh trãn laì phæång phaïp maî hoïa Huffman âäüng.
Kyî thuáût neïn våïi mäüt cæía säø haûn chãú
YÏ tæåíng cå baín cuía thuáût toaïn laì duy trç mäüt tæì âiãøn, goüi laì “cæía säø haûn chãú” (Finite window), chæïa sàôn khoaíng vaìi ngaìn kê tæû âæåüc âoüc vaìo gáön thåìi âiãøm hiãûn taûi vaì tiãún haình tçm kiãúm åí âoï chuäùi kê tæû daìi nháút so khåïp (matching) våïi âoaûn vàn baín bàõt âáöu taûi vë trê âang xeït. Nãúu coï mäüt chuäùi nhæ thãú âæåüc tçm tháúy vaì nãúu noï phuì håüp hoàûc væåüt quaï mäüt âäü daìi täúi thiãøu thç viãûc neïn seî âæåüc thæûc hiãûn bàòng caïch maî hoïa pháön âæåüc so khåïp cuía âoaûn vàn baín âoï bàòng mäüt theí baìi coï khuän daûng .
maî hoïa Huffman
maî hoïa Huffman
, chuïng ta âi tçm hiãøu vãö phæång phaïp âäüng (coìn goüi laì thêch æïng)
Vë trê âang xeït
Vë trê bàõt âáöu xaíy ra sæû
so khåïp täút nháút
chiãöu daìi âoaûn
so khåïp âæåüc
Khoaíng caïch seî
âæåüc maî hoïa
Minh hoüa sæû so khåïp våïi mäüt pháön cuía bäü âãûm âæåüc trêch
Vê duû :
Hçnh 16.
Nãúu chiãöu daìi chuäùi âæåüc so khåïp khäng væåüt quaï mäüt âäü daìi täúi thiãøu cho træåïc hoàûc täön taûi mäüt sæû so khåïp täút hån taûi vë trê kãú tiãúp thç kê tæû taûi vë trê âang xeït (goüi laì kê tæû hiãûn haình) seî âæåüc chuyãøn âi nguyãn daûng sang bäü maî hoïa vaì thuáût toaïn seî tiãúp tuûc xæí lyï taûi vë trê kãú tiãúp trong cæía säø.
Thuáût toaïn “cæía säø haûn chãú” naìy seî laìm phaït sinh hai daûng maî, âoï laì daûng maî cuía kê tæû âæåüc chuyãøn âi nguyãn veûn sang bäü maî hoïa vaì daûng maî cuía chuäùi so khåïp âæåüc bao gäöm âäü daìi vaì giaï trë khoaíng caïch. Âãø tiãút kiãûm säú bit maî hoïa, khoaíng caïch giæîa hai chuäùi so khåïp âæåüc seî âæåüc tênh tæì kê tæû cuäúi cuìng cuía chuäùi so khåïp tçm tháúy âãún vë trê âang xeït, thay vç tênh tæì kê tæû âáöu tiãn. Caïc giaï trë khoaíng caïch khaïc nhau seî âæåüc maî hoïa bàòng nhæîng säú bit khaïc nhau (cuû thãø laì duìng mäüt säú bit væìa âuí) nhàòm cæûc tiãøu hoïa âäü daìi cuía maî khoaíng caïch.
Caïc cáúu truïc dæî liãûu häù tråü
Bäü âãûm quay voìng
Váún âãö âáöu tiãn laì laìm thãú naìo læu træî bäü âãûm chæïa âoaûn vàn baín væìa måïi xuáút hiãûn. Nãúu duy trç mäüt haìng âåüi (queue) bàòng caïch sæí duûng danh saïch liãn kãút (linked list) thç seî laìm phæïc taûp quaï trçnh tçm kiãúm chuäùi. Viãûc dëch chuyãøn näüi dung cuía caí mäüt maíng âãø thãm vaìo mäüt kê tæû måïi laì mäüt cäng viãûc âoìi hoíi quaï nhiãöu thåìi gian.
Kyî thuáût âãûm âæåüc sæí duûng trong chæång trçnh âãø læu træî vàn baín trong mäüt bäü âãûm tæû quay voìng. Chuïng ta sæí duûng mäüt biãún âãø âaïnh dáúu vë trê cuäúi cuía vàn baín væìa âæåüc âoüc vaìo bäü âãûm. Khi biãún âoï âaût âãún vë trê cuäúi maíng (cuäúi bäü âãûm), noï seî âæåüc âàût laûi âãø troí vaìo âáöu maíng vaì khi âoï, vàn baín cuî seî bë ghi âeì. Chuïng ta khäng cáön sæí duûng mäüt cáúu truïc dæî liãûu phæïc taûp khaïc âãø laìm bäü âãûm båíi vç cáúu truïc maíng tæû quay voìng chè chiãúm mäüt khäng gian nhåï täúi thiãøu.
Baíng bàm (Hash table)
Mäüt váún âãö låïn cuía thuáût toaïn “cæía säø haûn chãú” laì âi tçm kiãúm chuäùi kê tæû daìi nháút so khåïp våïi âoaûn vàn baín hiãûn haình (âoaûn vàn baín bàõt âáöu tæì vë trê âang xeït) trong mäüt khäúi låïn dæî liãûu. Mäüt sæû tçm kiãúm thä thiãøn (nhæ laì giaíi thuáût “brute-force”) seî cho täúc âäü thæûc hiãûn ráút cháûm. Mäüt vaìi thuáût toaïn khaïc âaî âæåüc thæí nghiãûm, bao gäöm cáy nhë phán tçm kiãúm (binary search tree), baíng tçm kiãúm træûc tiãúp (direct lookup table), vaì caïc kyî thuáût tçm kiãúm chuäùi nhanh. Våïi chæång trçnh cuía âäö aïn, phæång phaïp tæång âäúi täút âæåüc tçm tháúy laì sæí duûng baíng bàm (hash table) våïi khoïa bàm âæåüc dáùn xuáút tæì ba kê tæû âáöu tiãn taûi vë trê âang xeït trong bäü âãûm.
Baíng bàm coï cáúu taûo nhæ sau: Mäùi âiãøm vaìo (entry) cuía baíng bàm laì mäüt danh saïch liãn kãút keïp (Doubly linked list) chæïa táút caí caïc vë trê coï cuìng khoïa bàm trong bäü âãûm. Mäùi chè säú vë trê âæåüc chæïa trong mäüt nuït. Mäùi nuït coï hai con troí, mäüt con troí (goüi laì pred) troí âãún nuït kãú træåïc trong danh saïch vaì con troí kia (goüi laì succ) troí âãún nuït kãú sau trong danh saïch.
Mäùi danh saïch cuîng âæåüc quaín lyï båíi hai con troí: mäüt con troí troí âãún nuït âáöu tiãn vaì con troí kia troí âãún nuït cuäúi cuìng trong danh saïch. Khi mäüt nuït âæåüc thãm vaìo danh saïch thç noï seî âæåüc thãm vaìo âáöu danh saïch âoï vaì khi xoïa mäüt nuït thç xoïa nuït cuäúi cuía danh saïch.
Lyï do ta phaíi sæí duûng danh saïch liãn kãút keïp laì vç: Våïi danh saïch liãn kãút âån, viãûc xoïa nuït cuäúi cuìng seî máút nhiãöu thåìi gian, båíi vç toaìn bäü danh saïch phaíi âæåüc duyãût âãø tçm ra pháön tæí cuäúi cuìng.
Bäü âãûm âæåüc xæí lyï âãún vë trê naìo thç chè säú cuía vë trê æïng våïi vë trê âoï seî âæåüc thãm vaìo âáöu danh saïch tæång æïng. Vaì khi bäü âãûm âaî âáöy thç biãún giæî vë trê seî âæåüc reset vãö âáöu bäü âãûm, nuït cuî æïng våïi vë trê âoï seî âæåüc xoïa taûi âuäi cuía danh saïch liãn kãút tæång æïng.
Quaï trçnh so khåïp chuäùi luän âæåüc bàõt âáöu taûi vë trê æïng våïi nuït âáöu tiãn cuía danh saïch coï giaï trë khoïa bàm bàòng våïi giaï trë khoïa bàm taûi vë trê âang xeït. Caïch thæûc hiãûn naìy laìm cho chuäùi so khåïp täút nháút våïi chuäùi hiãûn haình luän åí gáön vë trê âang xeït. Kãút quaí laì khoaíng caïch giæîa hai chuäùi khaï beï vaì do váûy, giaï trë khoaíng caïch seî âæåüc maî hoïa chè trong vaìi bit.
Baíng bàm seî coï daûng nhæ sau:
Danh saïch liãn kãút keïp 1
Nuït âáöu tiãn cuía DSLK 1
Danh saïch liãn kãút keïp n
Cáúu taûo cuía baíng bàm
entry 1 (æïng våïi giaï trë khoïa key1)
...
...
...
...
entry 2 (æïng våïi giaï trë khoïa key2)
i
j
k
...
...
...
...
...
...
entry n (æïng våïi giaï trë khoïa keyn)
...
...
...
...
Hçnh 17.
Theo hçnh veî trãn thç caïc vë trê i, j, k trong bäü âãûm seî coï cuìng mäüt khoïa bàm laì key2; vaì kêch thæåïc cuía baíng bàm laì n.
Nguyãn tàõc sæí duûng baíng bàm
Giaí sæí coï hai vë trê khaïc nhau n1 vaì n2 thuäüc bäü âãûm, trong âoï n1 laì vë trê âang xeït, cuìng laìm phaït sinh mäüt khoïa bàm (nghéa laì, giaï trë haìm bàm æïng våïi n1 bàòng våïi giaï trë haìm bàm æïng våïi n2). Khi âoï, seî coï hai træåìng håüp xaíy ra:
Chuäùi gäöm ba kê tæû bàõt âáöu taûi vë trê n1 so khåïp våïi chuäùi gäöm ba kê tæû bàõt âáöu taûi vë trê n2.
Xaíy ra sæû âuûng âäü ( (1) khäng xaíy ra).
Màûc duì haìm bàm âaî âæåüc choün sao cho êt xaíy ra âuûng âäü nháút nhæng trong quaï trçnh tçm kiãúm chuäùi dæûa vaìo khoïa bàm, sæû so khåïp phaíi âæåüc thæûc hiãûn taûi vë trê bàõt âáöu cuía mäùi chuäùi (chàóng haûn nhæ taûi n1 vaì n2).
Vê duû:
Tçm kiãúm chuäùi trong bäü âãûm nhåì sæí duûng pheïp bàm
chiãöu daìi âoaûn
so khåïp âæåüc
Khoaíng caïch seî
âæåüc maî hoïa
Vë trê n2 (coï cuìng
khoïa bàm nhæ n1)
Vë trê âang xeït n1
, chuïng ta âi tçm hiãøu vãö phæång phaïp maî hoïa Huffman âäüng (coìn goüi laì maî hoïa Huffman thêch æïng)
î
î
Hçnh 18.
Nhæ åí hçnh trãn, khi maì hai vë trê n1 vaì n2 coï cuìng khoïa bàm, thæûc tãú cho tháúy chuäùi gäöm ba kê tæû bàõt âáöu taûi n1 bàòng våïi chuäùi gäöm ba kê tæû bàõt âáöu taûi n2. Tuy nhiãn, trong khi sæí duûng pheïp bàm chuïng ta chæa thãø biãút chàõc âæåüc âiãöu âoï. Vç váûy, quaï trçnh so khåïp phaíi âæåüc bàõt âáöu taûi n1 vaì n2.
Roî raìng, nhåì sæí duûng baíng bàm, thåìi gian tçm kiãúm chuäùi trong bäü âãûm giaím âi âaïng kãø. Ta tháúy ràòng, trong mäüt láön bàm, nãúu khäng xaíy ra âuûng âäü thç ta coï âæåüc mäüt sæû so khåïp våïi âäü daìi täúi thiãøu laì ba. Âiãöu quan troüng laì phaíi xáy dæûng âæåüc mäüt haìm bàm âån giaín nhæng êt va chaûm âãø tàng xaïc suáút tçm tháúy chuäùi.
Haìm bàm âaî âæåüc sæí duûng trong chæång trçnh laì:
(buffer[n] ^ (buffer[ (n + 1) % maxsize ] << 4) ^ (buffer[ (n + 2) % maxsize ] << 8) ) & HASHMASK
Trong âoï:
n : vë trê cáön bàm trong bäü âãûm
maxsize : kêch thæåïc cuía bäü âãûm
HASHMASK : hàòng säú coï giaï trë bàòng (16384 - 1)
buffer[k] : kê tæû taûi vë trê thæï k cuía bäü âãûm
Ta nháûn tháúy ràòng, haìm bàm trãn khäng quaï phæïc taûp vaì chi phê vãö thåìi gian tênh toaïn tæång âäúi tháúp, båíi vç, noï chuí yãúu chè duìng nhæîng pheïp toaïn xæí lyï åí mæïc bit laì AND, XOR, Dëch traïi vaì Dëch phaíi (&, ^, > ).
Tiãún trçnh neïn
Chæång trçnh cho âäö aïn âæåüc caìi âàût trãn ngän ngæî C, do âoï, khi cáön minh hoüa cho mäüt quaï trçnh naìo âoï ta qui æåïc seî duìng ngän ngæî giaí C âãø minh hoüa.
Quaï trçnh mä hçnh hoïa
Quaï trçnh mä hçnh hoïa coï thãø âæåüc minh hoüa bàòng âoaûn ngän ngæî giaí sau âáy :
khåíi taûo caïc biãún vaì cáúu truïc dæî liãûu( );
for (i=0; i < MINCOPY; i++ ) { /*MINCOPY laì hàòng âäü daìi täúi thiãøu cuía chuäùi so khåïp*/
c = âoüc kê tæû kãú tiãúp tæì file cáön neïn( );
if ( c == EOF ) { /* hãút file */
maî hoïa( giaï trë EOF ); /* goüi bäü pháûn maî hoïa */
kãút thuïc xæí lyï( );
}
maî hoïa( giaï trë maî ASCII cuía kê tæû c );
thãm kê tæû c vaìo bäü âãûm( ) ; /* thãm c vaìo tæì âiãøn */
}
âoüc MAXCOPY kê tæû tiãúp theo tæì file cáön neïn vaìo bäü âãûm( );
/*MAXCOPY laì hàòng âäü daìi täúi âa cuía chuäùi so khåïp*/
while ( chæa hãút file cáön neïn ) {
if ( bäü âãûm âáöy )
xoïa nuït cuî æïng våïi vë trê 0 cuía bäü âãûm ra khoíi danh saïch liãn kãút thuäüc baíng bàm( );
thãm mäüt nuït måïi vaìo danh saïch liãn kãút tæång æïng thuäüc baíng bàm( );
n = vë trê âang xæí lyï trong bäü âãûm( );
next_len = âäü daìi cuía chuäùi so khåïp âæåüc taûi vë trê n + 1 trong bäü âãûm( );
len = âäü daìi cuía chuäùi so khåïp âæåüc taûi vë trê n trong bäü âãûm( );
distance = khoaíng caïch chuäùi so khåïp âæåüc taûi vë trê n trong bäü âãûm( );
if ( len >= MINCOPY vaì len >= next_len ) {
temp = biãún âäøi âäü daìi len thaình giaï trë trung gian låïn hån 256( );
maî hoïa( giaï trë temp ); /* goüi bäü pháûn maî hoïa */
k = tçm säú bit täúi thiãøu âãø biãøu diãùn giaï trë distance( );
xuáút k bit ra file neïn( );
} else
/*chuäùi so khåïp khäng âuí daìi hoàûc täön taûi mäüt chuäùi so khåïp täút hån taûi vë trê kãú tiãúp*/
maî hoïa( giaï trë maî ASCII cuía kê tæû taûi vë trê n );
}
if ( bäü âãûm âáöy )
cáûp nháût vë trê xæí lyï vãö âáöu bäü âãûm( );
if ( c != EOF )
c = âoüc kê tæû kãú tiãúp tæì file cáön neïn( );
if ( c != EOF ) /* hãút file */
thãm kê tæû c vaìo bäü âãûm( ) ; /* thãm c vaìo tæì âiãøn */
} /* hãút voìng làûp while */
maî hoïa ( giaï trë EOF );
kãút thuïc xæí lyï( );
Quaï trçnh maî hoïa
Nhæ âaî trçnh baìy, âáöu ra cuía bäü pháûn mä hçnh hoïa bao gäöm caïc kê tæû åí nguyãn daûng (chæa maî hoïa) vaì caïc theí baìi daûng . Báy giåì, chuïng ta seî sæí duûng maî Huffman âäüng âãø maî hoïa caïc kê tæû nguyãn daûng âoï vaì chiãöu daìi chuäùi âaî so khåïp âæåüc. Coìn caïc giaï trë khoaíng caïch (thæåìng laì caïc giaï trë ngáùu nhiãn, khäng phuì håüp våïi maî hoïa Huffman) seî âæåüc xuáút træûc tiãúp ra file neïn våïi säú bit âæåüc tênh væìa âuí (vê duû: Nãúu giaï trë khoaíng caïch laì 13 thç ta chè cáön täúi thiãøu 4 bit âãø biãøu diãùn vaì seî xuáút daîy gäöm 4 bit 1101 ra file neïn).
Tuy nhiãn, âãø caïc kê tæû vaì caïc giaï trë âäü daìi phán biãût âæåüc våïi nhau, giaï trë âäü daìi seî âæåüc biãún âäøi theo mäüt quy tàõc nháút âënh thaình mäüt giaï trë trung gian låïn hån 256 (caïc giaï trë tæì 0..255 daình cho maî ASCII cuía caïc kê tæû, giaï trë 256 daình cho maî End_Of_File) træåïc khi chuyãøn cho bäü maî hoïa. Tæì mäüt giaï trë trung gian, ta hoaìn toaìn coï thãø khäi phuûc laûi chênh xaïc giaï trë âäü daìi tæång æïng.
Cáúu truïc dæî liãûu mä taí cáy maî Huffman âäüng
Træåïc khi âi xáy dæûng cáy maî, chuïng ta cáön hiãøu âæåüc yï nghéa cuía caïc hàòng säú coï liãn quan âæåüc sæí duûng trong chæång trçnh:
Hàòng säú
Giaï trë
YÏ nghéa
MAXFREQ
2000
Ngæåîng troüng læåüng daình cho nuït gäúc cáy maî
MINCOPY
3
Âäü daìi täúi thiãøu cuía chuäùi so khåïp
MAXCOPY
64
Âäü daìi täúi âa cuía chuäùi so khåïp
COPYRANGES
6
Säú khoaíng bit duìng âãø maî khoaíng caïch
CODESPERRANGE
MAXCOPY - MINCOPY + 1
TERMINATE
256
Maî cho kê hiãûu EOF
FIRSTCODE
257
Giaï trë trung gian nhoí nháút cuía maî âäü daìi
MAXCHAR
FIRSTCODE + COPYRANGES*
CODESPERRANGE - 1
Giaï trë trung gian låïn nháút cuía maî âäü daìi
SUCCMAX
MAXCHAR + 1
TWICEMAX
2 * MAXCHAR + 1
ROOT
1
Nuït gäúc cuía cáy maî
Cáy maî Huffman maì ta seî xáy dæûng laì mäüt cáy nhë phán cán bàòng. Noï âæåüc biãøu diãùn trong bäü nhåï bàòng bäún maíng thaình pháön nhæ sau:
int left[ MAXCHAR + 1 ], right[ MAXCHAR + 1 ] ;
int up[ TWICEMAX + 1 ], freq[ TWICEMAX + 1 ] ;
Nuït gäúc cuía cáy laì nuït coï chè säú 1 (ROOT).
Hai maíng left[ ], right[ ] âãöu coï (MAXCHAR + 1) pháön tæí, nhæng ta chè sæí duûng MAXCHAR pháön tæí coï chè säú tæì 1..MAXCHAR (pháön tæí 0 khäng sæí duûng). Caïc pháön tæí up[0], up[1], freq[0], freq[1] cuîng khäng âæåüc sæí duûng.
Maíng left[ ] : chæïa chè säú cuía táút caí caïc nuït con traïi trong cáy maî.
Maíng right[ ] : chæïa chè säú cuía táút caí caïc nuït con phaíi trong cáy maî.
Maíng up[ ]: chæïa chè säú cuía táút caí caïc nuït cha trong cáy maî.
Maíng freq[ ]: chæïa troüng læåüng cuía táút caí caïc nuït trong cáy maî.
Maíng up[ ] coï säú pháön tæí bàòng täøng säú pháön tæí cuía hai maíng left[ ], rigth[ ] båíi vç mäùi nuït cha coï hai nuït con tæång æïng.
Ta qui æåïc ràòng:
left[ i ] = = j : nghéa laì nuït con traïi cuía nuït coï chè säú i laì nuït coï chè säú j, hay coï thãø noïi mäüt caïch ngàõn goün hån, nuït con traïi cuía nuït i laì nuït j.
right[ i ] = = j : nuït con phaíi cuía nuït i laì nuït j.
up[ i ] = = j : nuït cha cuía nuït i laì nuït j, hay nuït j laì nuït con cuía nuït i.
freq[ i ] = = j : troüng læåüng cuía nuït i bàòng j.
Cáy maî Huffman trong træåìng håüp biãøu diãùn nhæ trãn âæåüc goüi laì cáy måí räüng (Splay Tree).
Æu âiãøm cuía caïch biãøu diãùn cáy maî nhæ trãn laì cáúu truïc dæî liãûu âån giaín, truy xuáút nhanh, dãù sæí duûng nhæng coï haûn chãú laì cáy maî khaï træìu tæåüng, laîng phê bäü nhåï nãúu nhæ caïc pháön tæí cuía maíng khäng âæåüc sæí duûng hãút.
Nhæ váûy, cáy maî Huffman âæåüc biãøu diãùn nhæ trãn seî coï:
Nuït gäúc laì nuït coï chè säú 1 (ROOT).
Caïc nuït nhaïnh coï chè säú tæì 2..MAXCHAR.
Caïc nuït laï coï chè säú tæì (MAXCHAR + 1)..TWICEMAX, tæång æïng våïi (MAXCHAR+1) giaï trë cáön maî hoïa (bao gäöm maî ASCII cuía 256 kê tæû, kê hiãûu EOF vaì (MAXCHAR - FIRSTCODE + 1) giaï trë trung gian cuía maî âäü daìi).
Giaï trë cáön maî hoïa k (nàòm trong khoaíng tæì 0..MAXCHAR) seî tæång æïng våïi nuït laï coï chè säú (k+SUCCMAX).
Khåíi taûo cáy maî âáöu tiãn:
for (i = 1; i <= MAXCHAR; i++ ) {
left[ i ] = 2*i;
right[ i ] = 2*i + 1;
}
for (i = 2; i <= TWICEMAX; i++ ) {
up[ i ] = i / 2;
freq[ i ] = 1;
}
Nuït laï coï chè säú SUCCMAX
(æïng våïi giaï trë 0)
4
5
6
7
ROOT
2
0
1
3
0
1
1
0
1
.......... .......... .......... ........ .......
......... .......... .......... ........
0
1
0
1
0
1
0
1
...... ...... ...... ....... ....... ......
Nuït laï
Cáy maî Huffman âäüng sau khi khåíi taûo
Sau khi khåíi taûo, cáy maî seî coï daûng nhæ sau:
Hçnh 19.
Ta coï: left[ 2 ] == 4: nuït 4 laì con traïi cuía nuït 2
up[7] == 3: nuït 3 laì nuït cha cuía nuït 7.
Thuí tuûc maî hoïa
Khi bäü pháûn maî hoïa nháûn âæåüc mäüt giaï trë cáön maî hoïa tæì bäü pháûn mä hçnh hoïa chuyãøn sang, noï seî tiãún haình maî hoïa giaï trë âoï theo cáy maî hiãûn thåìi. Tæì maî cuía giaï trë âoï seî âæåüc xaïc âënh bàòng caïch: duyãût tæì nuït laï tæång æïng våïi giaï trë âoï âãún nuït gäúc cuía cáy maî; trãn âæåìng âi, têch luîy laûi giaï trë cuía nhaïnh phaíi âi qua (0 / 1), cuäúi cuìng, âaío ngæåüc daîy bit âaî têch luîy âæåüc ta coï tæì maî cáön xaïc âënh.
Sau khi maî hoïa xong mäüt giaï trë, bäü pháûn maî hoïa seî tiãún haình cáûp nháût laûi cáy maî. Sau âoï, quaï trçnh laûi âæåüc tiãúp tuûc våïi giaï trë kãú tiãúp cáön maî hoïa tæì bäü pháûn mä hçnh hoïa chuyãøn sang.
¨ Thuí tuûc cáûp nháût cáy maî Huffman âäüng
Thuí tuûc cáûp nháût cáy maî seî âæåüc thæûc hiãûn tuáön tæû theo caïc bæåïc sau:
Bæåïc 1. Tàng troüng læåüng cuía nuït laï æïng våïi giaï trë væìa âæåüc maî hoïa lãn mäüt âån vë.
Bæåïc 2. Cáûp nháût troüng læåüng cho táút caí caïc nuït nhaïnh (kãø caí nuït gäc) nàòm trãn âæåìng âi tæì nuït laï væìa tàng troüng læåüng âãún nuït gäúc, theo hæåïng tæì dæåïi lãn, theo nguyãn tàõc: troüng læåüng cuía nuït cha bàòng täøng troüng læåüng hai nuït con.
Bæåïc 3. Kiãøm tra tênh cháút Sibling: Viãûc cáûp nháût troüng læåüng coï thãø seî laìm cho mäüt nuït naìo âoï coï troüng læåüng låïn hån mäüt nuït khaïc nàòm åí vë trê cao hån trong cáy maî (vi phaûm tênh cháút Sibling). Træåìng håüp naìy, chuïng ta phaíi traïo âäøi nuït âoï våïi mäüt nuït nàòm åí vë trê cao hån trong cáy. Coï thãø coï nhiãöu nuït coï troüng læåüng bàòng våïi nuït nàòm åí vë trê cao hån âoï, do váûy nuït cáön choün traïo âäøi chênh laì nuït cuäúi cuìng trong loaût caïc nuït coï cuìng troüng læåüng âoï. Sau khi traïo âäøi, ta cuîng phaíi cáûp nháût troüng læåüng cho caïc nuït coï liãn quan tæång tæû nhæ åí bæåïc 2.
Bæåïc 4. Kiãøm tra bäü âãúm troüng læåüng åí nuït gäúc: Nãúu troüng læåüng cuía nuït gäúc âaût âãún mäüt giaï trë ngæåîng âaî âënh træåïc, âãø traïnh hiãûn tæåüng traìn, troüng læåüng cuía táút caí caïc nuït trong cáy seî âæåüc qui giaím âi 1/2 vaì laìm troìn. Âiãöu naìy cuîng taûo ra mäüt sæû thêch æïng cuûc bäü âäúi våïi dæî liãûu âáöu vaìo vaì nhæ váûy, hiãûu quaí neïn seî täút hån.
Tiãún trçnh giaíi neïn
Quaï trçnh giaíi maî theo cáy maî Huffman âäüng
Khåíi taûo cáy maî âáöu tiãn
Træåïc hãút, chæång trçnh giaíi maî cuîng khåíi taûo mäüt cáy maî giäúng hãût nhæ bãn bäü pháûn maî hoïa âaî laìm :
for (i = 1; i <= MAXCHAR; i++ ) {
left[ i ] = 2*i;
right[ i ] = 2*i + 1;
}
for (i = 2; i <= TWICEMAX; i++ ) {
up[ i ] = i / 2;
freq[ i ] = 1;
}
Thuí tuûc giaíi maî
Sau khi cáy maî âæåüc khåíi taûo xong, thuí tuûc giaíi maî seî nháûn âiãöu khiãøn tæì chæång trçnh. Thuí tuûc giaíi maî seî âoüc tæìng tæì maî tæì file cáön giaíi neïn vaì tiãún haình giaíi maî theo cáy maî hiãûn thåìi. Khi âæåüc goüi, noï seî âæïng taûi nuït gäúc cuía cáy maî, nháûn tæìng bit mäüt tæì luäöng tæì maî âãø xæí lyï: Nãúu bit nháûn âæåüc laì 0, noï seî reî xuäúng theo nhaïnh traïi; ngæåüc laûi, bit nháûn âæåüc laì 1, noï reî sang nhaïnh phaíi cuía cáy. Noï cæï tiãúp tuûc nhæ thãú cho âãún khi bàõt gàûp mäüt nuït laï. Taûi thåìi âiãøm naìy, thuí tuûc cáûp nháût cáy maî cho giaï trë æïng våïi nuït laï væìa âæåüc bàõt gàûp seî âæåüc goüi. Âãún âáy, xem nhæ mäüt tæì maî âaî âæåüc xæí lyï xong. Thuí tuûc giaíi maî seî quay vãö âæïng taûi nuït gäúc âãø chåì xæí lyï tæì maî tiãúp theo vaì âäöng thåìi, giaï trë tæång æïng våïi nuït laï trãn seî âæåüc chuyãøn cho bäü pháûn mä hçnh hoïa xæí lyï tiãúp.
Thuí tuûc cáûp nháût cáy maî trong quaï trçnh giaíi maî laì hoaìn toaìn giäúng nhæ trong quaï trçnh maî hoïa.
Thuáût toaïn giaíi maî mäüt tæì maî:
int a = ROOT; /* xuáút phaït tæì gäúc cuía cáy */
do {
Láúy mäüt bit maî tæì file neïn( );
if (bit maî laì 1) a = right[ a ]; /*reî sang nhaïnh phaíi*/
else a = left[ a ]; /*reî sang nhaïnh traïi*/
} while ( a <= MAXCHAR );
cáûp nháût cáy maî cho giaï trë ( a - SUCCMAX ) ;
return ( a - SUCCMAX ) ;
Båíi vç MAXCHAR laì giåïi haûn chè säú cuía caïc nuït nhaïnh, do âoï, khi duyãût qua hãút caïc nuït coï chè säú <= MAXCHAR (laì caïc nuït nhaïnh) trãn mäüt âæåìng âi xuáút phaït tæì nuït gäúc thç ta luän gàûp âæåüc mäüt nuït laï.
Quaï trçnh giaíi neïn
Quaï trçnh giaíi neïn âæåüc tiãún haình nhæ sau:
khåíi taûo cáy maî âáöu tiãn( ) ;
while (1) {
code = giaíi maî mäüt tæì maî tæì file neïn( ) ; // goüi thuí tuûc giaíi maî mäüt tæì maî.
if (code == TERMINATE) // maî EOF
kãút thuïc quaï trçnh giaíi neïn( );
if (code < 256) { // maî ASCII cuía kê tæû bçnh thæåìng
xuáút kê tæû coï maî code vaìo file giaíi neïn( );
cáûp nháût kê tæû coï maî code vaìo bäü âãûm( ); // thãm kê tæû vaìo tæì âiãøn
} else { // giaï trë trung gian cuía maî âäü daìi chuäùi so khåïp
phuûc häöi âäü daìi length cuía chuäùi âaî so khåïp( );
phuûc häöi säú bit k âaî duìng âãø maî hoïa khoaíng caïch( );
distance = âoüc k bit tiãúp theo tæì file neïn( ); // khäi phuûc giaï trë khoaíng caïch
n = vë trê âang xæí lyï trong bäü âãûm( );
i = n - ( distance + length );
sao cheïp length kê tæû bàõt âáöu taûi vë trê i cuía bäü âãûm vaìo file giaíi neïn( );
sao cheïp length kê tæû bàõt âáöu taûi vë trê i vaìo vë trê n cuía bäü âãûm( );
n += length; // cáûp nháût vë trê xæí lyï måïi trong bäü âãûm.
}
}
Vê duû minh hoüa:
Giaí sæí taûi mäüt thåìi âiãøm naìo âoï trong quaï trçnh giaíi neïn, sau khi caïc giaï trë length vaì distance âæåüc khäi phuûc, bäü âãûm coï daûng nhæ sau:
Bäü âãûm træåïc khi sao cheïp length kê tæû taûi i vaìo vë trê n
length
distance
Vë trê i = n - (distance + length)
Vë trê n âang xæí lyï
, chuïng ta âi tçm hiãøu vãö phæång phaïp maî hoïa Huffman âäüng (coìn goüi laì
Hçnh 20.
Sau khi length kê tæû taûi vë trê i âæåüc sao cheïp vaìo vë trê n, bäü âãûm seî nhæ sau:
, chuïng ta âi tm hiãøu vãö phæång phaïp maî hoïa Huffman âäüng (coìn goüi laì maî hoïa Huffman
Vë trê n
Vë trê i = n - (distance + length)
distance
length
Bäü âãûm sau khi sao cheïp length kê tæû taûi i vaìo vë trê n
Vë trê xæí lyï måïi (n+length)
Hçnh 21.
Nháûn xeït
Våïi caïc cáúu truïc dæî liãûu nhæ âaî trçnh baìy åí trãn (bao gäöm caïc maíng cho cáy maî Huffman, bäü âãûm quay voìng, baíng bàm, danh saïch liãn kãút keïp,...) thç læåüng bäü nhåï maì chæång trçnh chiãúm duûng khi caìi âàût thæûc tãú laì tæång âäúi beï (khoaíng vaìi tràm KB khi neïn vaì vaìi chuûc KB khi giaíi neïn, båíi vç khi giaíi neïn ta khäng cáön âãún baíng bàm vaì caïc danh saïch liãn kãút keïp). Thuáût toaïn âæåüc sæí duûng laì khäng quaï phæïc taûp.
Ta nháûn tháúy ràòng, täúc âäü neïn cuía chæång trçnh phuû thuäüc ráút nhiãöu vaìo thåìi gian tçm kiãúm chuäùi trong tæì âiãøn. Thåìi gian tçm kiãúm chuäùi seî tè lãû våïi kêch thæåïc cuía tæì âiãøn (bäü âãûm) vaì âäü sáu tçm kiãúm (âäü daìi chuäùi so khåïp låïn nháút). Mäüt haìm bàm täút seî tàng xaïc suáút tçm tháúy chuäùi vaì do váûy, cuîng laìm giaím thåìi gian tçm kiãúm.
Tuy nhiãn, coï thãø tháúy ràòng, täúc âäü giaíi neïn cuía chæång trçnh laì khäng chëu aính hæåíng cuía caïc yãúu täú trãn. Båíi vç, quaï trçnh giaíi neïn chè âån giaín laì giaíi maî caïc kê hiãûu vaì thæûc hiãûn sao cheïp chuäùi, chæï khäng tiãún haình viãûc tçm kiãúm chuäùi. Thæûc tãú cho tháúy, täúc âäü giaíi neïn cuía chæång trçnh laì khaï nhanh. Âoï cuîng laì æu âiãøm chung cuía caïc chæång trçnh neïn dæûa trãn mä hçnh tæì âiãøn.
Mäüt váún âãö næîa laì khi chuïng ta tàng âäü sáu tçm kiãúm chuäùi, xaïc suáút tçm tháúy nhæîng chuäùi so khåïp daìi hån seî tàng lãn vaì tè lãû neïn cuîng tàng lãn. Tuy nhiãn, caïi giaï phaíi traí laì täúc âäü neïn seî giaím âi. Do âoï, tuìy vaìo tæìng yãu cáöu cuû thãø (tè lãû neïn hay täúc âäü neïn) maì ta thay âäøi caïc thäng säú cuía chæång trçnh cho phuì håüp.
CHÆÅNG V
THÆÛC NGHIÃÛM
Chæång naìy nhàòm trçnh baìy kãút quaí pháön thæûc nghiãûm so saïnh hiãûu quaí cuía chæång trçnh neïn âæåüc caìi âàût cho Âäö aïn (viãút bàòng ngän ngæî C, biãn dëch trãn mäi træåìng Borland C++ 3.1) våïi mäüt säú chæång trçnh neïn thæång maûi âang âæåüc sæí duûng phäø biãún hiãûn nay. Caïc chæång trçnh neïn âæåüc choün so saïnh laì :
NCZip (NC 5.0): chæång trçnh neïn chaûy trong mäi træåìng 16-bit MS-DOS.
WinZip 7.0: chæång trçnh neïn chaûy trãn Hãû âiãöu haình 32-bit Windows 9x.
Ngoaìi ra, ta choün thãm mäüt chæång trçnh neïn næîa âãø so saïnh. Âoï laì chæång trçnh neïn sæí duûng cuìng phæång phaïp maî hoïa Huffman âäüng nhæng dæûa trãn mä hçnh thäúng kã (báûc mäüt), âæåüc caìi âàût cho mäüt âäö aïn khaïc. Âãø thuáûn låüi cho viãûc so saïnh, ta quy æåïc goüi tãn chæång trçnh naìy laì DHuffO1 (maî hoïa Huffman âäüng, mä hçnh thäúng kã báûc 1) vaì chæång trçnh caìi âàût cho âäö aïn naìy laì DhuffDic (maî hoïa Huffman âäüng, mä hçnh tæì âiãøn thêch æïng).
Dæî liãûu thê nghiãûm âæåüc choün ngáùu nhiãn theo tæìng loaûi, chuí yãúu laì loaûi file vàn baín (tiãúng Anh vaì tiãúng Viãût) âæåüc soaûn thaío dæåïi hai mäi træåìng MS-DOS vaì Windows 9x, bao gäöm:
Caïc file vàn baín thuáön tuïy (*.TXT, *.PAS, *.CPP,...)
Caïc file vàn baín coï âënh daûng (*.DOC, *.RTF,...)
Caïc file thæûc thi (*.EXE)
Caïc file cå såí dæî liãûu (*.MDB, *.MDE,...)
Nguyãn tàõc thê nghiãûm
Thê nghiãûm âæåüc tiãún haình trãn maïy PC Pentium, 100 MHz, 16 MB RAM, Hãû âiãöu haình Windows 98.
Mäùi âåüt thê nghiãûm âæåüc thæûc hiãûn ba láön, caïc thäng säú âæåüc âo laì: tè säú neïn, thåìi gian neïn vaì thåìi gian giaíi neïn. Våïi mäùi thäng säú, kãút quaí âæåüc láúy trung bçnh cäüng. Caïc láön âo âæåüc tiãún haình caïch biãût nhau.
Coï thæûc hiãûn viãûc “laìm saûch” bäü nhåï giæîa caïc láön thê nghiãûm (traïnh cå chãú “âãûm âéa” cuía Hãû âiãöu haình,...)
Trãn cå såí caïc thäng säú âo âæåüc trong quaï trçnh thê nghiãûm, chuïng ta seî tiãún haình veî caïc biãøu âäö so saïnh vãö tè säú neïn, täúc âäü neïn vaì thåìi gian giaíi neïn cuía caïc chæång trçnh.
I. So saïnh tè säú neïn
Coï nhiãöu caïch tênh tè säú neïn khaïc nhau. ÅÍ âáy, ta tênh tè säú neïn theo cäng thæïc sau:
%
100
)
âáöu
ban
file
c
kêch thæåï
neïn
âaî
file
c
kêch thæåï
-
(1
=
neïn
säú
Tè
x
I.1. Baíng so saïnh tè säú neïn
Loaûi dæî liãûu
Chæång trçnh neïn
File vàn baín thuáön tuïy (*.TXT,...)
File vàn baín âënh daûng (*.DOC)
File cå såí dæî liãûu
(*.MDB, *.MDE)
File thæûc thi
(*.EXE)
DhuffDic
Vaìo:
20MB
76%
Vaìo:
10MB
66%
Vaìo:
10MB
73%
Vaìo:
10MB
60%
Ra:
4.89MB
Ra:
3.43MB
Ra:
2.71MB
Ra:
4.06MB
NCZip (NC 5.0)
Vaìo:
20MB
75%
Vaìo:
10MB
67%
Vaìo:
10MB
73%
Vaìo:
10MB
60%
Ra:
4.94MB
Ra:
3.28MB
Ra:
2.68MB
Ra:
3.99MB
WinZip 7.0
Vaìo:
20MB
77%
Vaìo:
10MB
68%
Vaìo:
10MB
74%
Vaìo:
10MB
60%
Ra:
4.60MB
Ra:
3.24MB
Ra:
2.56MB
Ra:
3.97MB
DHuffO1
Vaìo:
20MB
52%
Vaìo:
10MB
46%
Vaìo:
10MB
51%
Vaìo:
10MB
42%
Ra:
9.52MB
Ra:
5.50MB
Ra:
4.96MB
Ra:
5.77MB
I.2. Biãøu âäö so saïnh tè säú neïn
Loaûi dæî liãûu âæåüc choün thê nghiãûm âãø xáy dæûng biãøu âäö dæåïi âáy laì loaûi vàn baín thuáön tuïy. Truûc hoaình cuía biãøu âäö chæïa thäng tin vãö læåüng dæî liãûu âem neïn (theo MB), truûc tung mang tè säú neïn tæång æïng.
Biãøu âäö so saïnh tè säú neïn giæîa caïc phæång phaïp neïn khaïc nhau
Hçnh 22 .
I.3. Nháûn xeït vãö tè säú neïn
Trong caïc loaûi dæî liãûu âæåüc choün thê nghiãûm, loaûi file vàn baín thuáön tuïy âãöu cho tè säú neïn cao nháút âäúi våïi caí bäún chæång trçnh, kãú âãún laì loaûi file cå såí dæî liãûu vaì cho tè säú neïn tháúp nháút laì loaûi file thæûc thi. Ba chæång trçnh DhuffDic, NCZip vaì WinZip cho tè säú neïn xáúp xè bàòng nhau åí mäùi loaûi dæî liãûu vaì chuïng âãöu væåüt träüi so våïi DhuffO1.
Theo biãøu âäö, âäúi våïi loaûi file vàn baín thuáön tuïy, caí ba chæång trçnh DhuffDic, NCZip vaì WinZip âãöu cho tè säú neïn khaï cao vaì hån hàón DhuffO1. ÅÍ mæïc 1 MB, caí ba cho tè säú neïn xem nhæ laì bàòng nhau, nhæng tæì mæïc 2 MB tråí âi, WinZip coï pháön chiãúm æu thãú nhæng khäng âaïng kãø. DhuffDic coï tè säú neïn cao hån NCZip trong mäüt vaìi træåìng håüp, caïc træåìng håüp coìn laûi laì ngang nhau.
II. So saïnh täúc âäü neïn
II.1. Baíng so saïnh täúc âäü neïn
Loaûi dæî liãûu
Chæång trçnh neïn
File vàn baín thuáön tuïy (*.TXT,...)
File vàn baín âënh daûng (*.DOC)
File cå såí dæî liãûu
(*.MDB, *.MDE)
File thæûc thi
(*.EXE)
DhuffDic
20MB
68.04
KB/s
10MB
47.52 KB/s
10MB
56.48 KB/s
10MB
53.61
KB/s
301s
215.5s
181.3s
191s
NCZip (NC 5.0)
20MB
204.80
KB/s
10MB
170.67 KB/s
10MB
170.67 KB/s
10MB
162.54 KB/s
100s
60s
60s
63s
WinZip 7.0
20MB
200.78
KB/s
10MB
341.33KB/s
10MB
379.26 KB/s
10MB
330.32 KB/s
102s
30s
27s
31s
DhuffO1
20MB
125.18
KB/s
10MB
91.10 KB/s
10MB
108.36 KB/s
10MB
93.09
KB/s
163.6s
112.4s
94.5s
110s
II.2. Biãøu âäö so saïnh täúc âäü neïn
Biãøu âäö âæåüc veî coï truûc hoaình biãøu diãùn cho khäúi læåüng dæî liãûu âem neïn (MB), truûc tung biãøu diãùn cho thåìi gian neïn (tênh bàòng giáy) tæång æïng.
Biãøu âäö so saïnh täúc âäü neïn giæîa caïc phæång phaïp neïn khaïc nhau
Hçnh 23.
II.3. Nháûn xeït vãö täúc âäü neïn
Täúc âäü neïn cuía DhuffDic khaï cháûm, cháûm nháút trong säú bäún chæång trçnh âæåüc thæí nghiãûm. Thåìi gian neïn trung bçnh cuía DhuffDic gáúp khoaíng ba láön so våïi NCZip vaì WinZip, tuy nhiãn, dæûa vaìo biãøu âäö, ta tháúy caïc chè säú thåìi gian cuía noï laì coï thãø cháúp nháûn âæåüc trong thæûc tãú.
IV. So saïnh täúc âäü giaíi neïn
IV.1. Baíng so saïnh täúc âäü giaíi neïn
Loaûi dæî liãûu
Chæång trçnh neïn
File vàn baín thuáön tuïy (*.TXT,...)
File vàn baín âënh daûng (*.DOC)
File cå såí dæî liãûu
(*.MDB, *.MDE)
File thæûc thi
(*.EXE)
DhuffDic
20MB
392.26 KB/s
10MB
265.29 KB/s
10MB
330.32KB/s
10MB
239.25 KB/s
52.21s
38.6s
31s
42.8s
NCZip (NC 5.0)
20MB
731.43
KB/s
10MB
682.67 KB/s
10MB
682.67 KB/s
10MB
512 KB/s
28s
15s
15s
20s
WinZip 7.0
20MB
905.39
KB/s
10MB
1024
KB/s
10MB
1024 KB/s
10MB
930.91 KB/s
22.62s
10s
9s
11s
DhuffO1
20MB
130.03
KB/s
10MB
94.03KB/s
10MB
112.53 KB/s
10MB
94.82
KB/s
157.5s
108.9s
91s
108s
IV.2. Biãøu âäö so saïnh täúc âäü giaíi neïn
Thåìi gian giaíi neïn (giáy) cuía caïc chæång trçnh âæåüc thãø hiãûn åí truûc tung cuía biãøu âäö, vaì tæång æïng laì khäúi læåüng dæî liãûu (MB) giaíi neïn âæåüc, thãø hiãûn trãn truûc hoaình.
Biãøu âäö so saïnh täúc âäü giaíi neïn giæîa caïc phæång phaïp neïn khaïc nhau
Hçnh 24.
IV.3. Nháûn xeït vãö täúc âäü giaíi neïn
Theo baíng vaì biãøu âäö thãø hiãûn thåìi gian giaíi neïn, coï thãø nháûn tháúy ràòng, DhuffDic coï täúc âäü giaíi neïn khaï nhanh, væåüt xa DhuffO1, tuy nhiãn váùn coìn keïm NCZip vaì WinZip. Täúc âäü giaíi neïn trung bçnh cuía DhuffDic nhanh xáúp xè gáúp 3 láön so våïi DhuffO1.
V. Kãút luáûn
Caïc kãút quaí thæûc nghiãûm âaî cho chuïng ta mäüt caïi nhçn khaïi quaït vãö hiãûu quaí cuía phæång phaïp neïn sæí duûng kyî thuáût maî hoïa Huffman âäüng våïi mä hçnh tæì âiãøn thêch æïng so våïi caïc phæång phaïp neïn khaïc. Coï thãø nháûn tháúy ràòng, våïi cuìng mäüt phæång phaïp maî hoïa, chæång trçnh neïn dæûa trãn mä hçnh tæì âiãøn âæåüc caìi âàût cho Âäö aïn cho tè säú neïn vaì täúc âäü giaíi neïn täút hån nhiãöu so våïi caïc chæång trçnh neïn dæûa trãn mä hçnh thäúng kã. Âiãøm haûn chãú cuía noï laì täúc âäü neïn coìn cháûm. Âiãöu naìy hoaìn toaìn coï thãø caíi thiãûn âæåüc bàòng caïch thay âäøi caïc thäng säú neïn trong chæång trçnh (nhæ âäü sáu tçm kiãúm chuäùi, kêch thæåïc tæì âiãøn,...), tuy nhiãn, tè säú neïn khi âoï seî giaím âi mäüt êt. Phæång phaïp neïn sæí duûng trong chæång trçnh cho tè säú neïn ngang bàòng våïi NCZip, nhæng coìn keïm WinZip 7.0 mäüt êt. Vãö màût täúc âäü neïn, chæång trçnh coìn keïm xa NCZip vaì WinZip.
Nhæ váûy, phæång phaïp neïn âaî caìi âàût cho Âäö aïn coï æu âiãøm vãö màût tè säú neïn, täúc âäü giaíi neïn vaì læåüng bäü nhåï sæí duûng (âaî trçnh baìy åí pháön nháûn xeït trong chæång træåïc); nhæng coï nhæåüc âiãøm vãö màût täúc âäü neïn.
Cáön læu yï ràòng, caïc âaïnh giaï trãn chè mang tênh tæång âäúi. Båíi vç, quaï trçnh thæûc nghiãûm coìn phuû thuäüc vaìo nhiãöu yãúu täú nhæ : kyî thuáût truy xuáút âéa cæïng, quaï trçnh xæí lyï dæî liãûu åí mæïc bit,... cuía mäùi chæång trçnh vaì täúc âäü xæí lyï cuía CPU, cuîng nhæ khäúi læåüng vaì loaûi dæî liãûu âæåüc choün thê nghiãûm,v.v...
CHÆÅNG VI
KÃÚT LUÁÛN
Càn cæï vaìo caïc nhiãûm vuû nghiãn cæïu âaî nãu ra trong âãö cæång, qua quaï trçnh thæûc hiãûn âäö aïn, täi âaî hoaìn thaình âæåüc caïc cäng viãûc sau:
Trçnh baìy âæåüc baìi toaïn neïn dæî liãûu vaì táöm quan troüng cuía noï.
Tçm hiãøu lyï thuyãút täøng quan vãö neïn dæî liãûu, caïc kyî thuáût maî hoïa Shannon-Fano, maî hoïa säú hoüc; vaì mäüt säú phæång phaïp neïn dæûa trãn mä hçnh tæì âiãøn nhæ LZ77 vaì LZ78. Nãu âæåüc caïc æu âiãøm cuía maî Huffman so våïi caïc maî khaïc vaì æu âiãøm cuía mä hçnh tæì âiãøn so våïi mä hçnh thäúng kã.
Âi sáu nghiãn cæïu phæång phaïp neïn dæî liãûu aïp duûng kyî thuáût maî hoïa Huffman, maì chuí yãúu laì maî Huffman âäüng, dæûa trãn mä hçnh tæì âiãøn thêch æïng.
Hiãûn thæûc hoïa kyî thuáût maî hoïa Huffman våïi mä hçnh tæì âiãøn âaî nghiãn cæïu bàòng chæång trçnh cuû thãø.
Tiãún haình thæûc nghiãûm våïi chæång trçnh âaî coï, trãn caïc loaûi dæî liãûu khaïc nhau, cuìng våïi caïc chæång trçnh neïn thæång maûi phäø biãún nhæ NCZip vaì WinZip 7.0 nhàòm xaïc minh tênh âuïng âàõn cuía chæång trçnh, vaì âaïnh giaï hiãûu quaí cuía phæång phaïp neïn âæåüc sæí duûng trong Âäö aïn. Kãút quaí thæûc nghiãûm cho tháúy, chæång trçnh chaûy âuïng, thæûc hiãûn neïn vaì giaíi neïn chênh xaïc; âaïp æïng âæåüc yãu cáöu vãö tè säú neïn, täúc âäü giaíi neïn vaì læåüng bäü nhåï sæí duûng, tuy nhiãn, täúc âäü neïn coìn keïm xa NCZip vaì WinZip. Ngoaìi ra, thæûc nghiãûm coìn cho tháúy âæåüc æu thãú cuía phæång phaïp neïn dæûa trãn mä hçnh tæì âiãøn so våïi caïc phæång phaïp neïn dæûa trãn mä hçnh thäúng kã.
Tuy nhiãn, âäö aïn chæa âi sáu vaìo so saïnh caïc phæång phaïp maî hoïa våïi nhau. Caïc váún âãö âæåüc trçnh baìy chæa tháût thäng suäút vaì càûn keî. Mäüt säú cáúu truïc dæî liãûu vaì thuáût toaïn trong chæång trçnh chæa âæåüc phán têch mäüt caïch kyî læåîng.
Trong tæång lai, âãö taìi coï thãø âæåüc phaït triãøn theo caïc hæåïng chênh sau âáy:
Caíi tiãún giaíi thuáût âæåüc sæí duûng trong chæång trçnh âãø tàng täúc âäü neïn maì váùn khäng laìm máút âi caïc æu âiãøm väún coï cuía thuáût toaïn.
Chæång trçnh coï thãø chaûy âæåüc trãn nhiãöu hãû âiãöu haình khaïc nhau nhæ Windows NT, LINUX,...
Chæång trçnh coï khaí nàng phán têch âæåüc nguäön säú liãûu âáöu vaìo âãø coï chiãún læåüc neïn phuì håüp våïi tæìng kiãøu dæî liãûu khaïc nhau nhàòm âaût âæåüc hiãûu quaí neïn täút nháút.
Giao diãûn chæång trçnh âæåüc thiãút kãú âãø hæåïng âãún tênh dãù sæí duûng, coï nhiãöu tuìy choün khaïc nhau nhàòm âaïp æïng âæåüc caïc yãu cáöu cuû thãø khi neïn säú liãûu.
Âäö aïn, vãö cå baín, âaî âæåüc hoaìn thaình. Tuy nhiãn, do kiãún thæïc vaì thåìi gian haûn chãú nãn noï váùn coìn nhiãöu thiãúu soït khäng thãø traïnh khoíi. Ráút mong nháûn âæåüc sæû phã bçnh, goïp yï cuía caïc tháöy cä vaì caïc baûn âãø âãö taìi naìy âæåüc hoaìn thiãûn hån trong thåìi gian tåïi.
TAÌI LIÃÛU THAM KHAÍO chênh
Witten, I., Moffat, A. and Bell, T. Managing Gigabytes: Compressing and Indexing Documents and Images ( Second ed.). Van Nostrand Reinhold, New York, 1999.
Mark Nelson., Jean-Loup Gailly. The Data Compression Book (Second ed.). M & T., 1991.
Fiala, E.R. and Green, D.H. “Data compression with finite windows”. Communications of the ACM, 1989.
Larry Nyhoff., Sanford Leestma. Láûp trçnh náng cao bàòng Pascal våïi cáúu truïc dæî liãûu, táûp 2. Dëch giaí : PTS Lã Minh Trung. Scitec, 1991, 344 t.
Häö Viãút Viãût. Neïn säú liãûu bàòng phæång phaïp Huffman âäüng. Luáûn vàn thaûc syî Khoa hoüc kyî thuáût. 1997.
Nguyãùn Vàn Trung. Kyî thuáût maî hoïa Huffman våïi mä hçnh thäúng kã. Âäö aïn täút nghiãûp Ké sæ Tin hoüc, Khoa Cäng nghãû Thäng tin, Âaûi hoüc Kyî thuáût Âaì Nàông, 1999.
Nguyãùn Thuïy Ván. Lyï thuyãút maî. NXB Khoa hoüc vaì Kyî thuáût, 2000, 207 t.
Vuî Âæïc Thi. Thuáût toaïn trong Tin hoüc. NXB Khoa hoüc vaì Kyî thuáût, 1999, 198 t.
Robert Sedgewick. Cáøm nang thuáût toaïn, táûp I. NXB Khoa hoüc vaì Kyî thuáût, 1998, 409 t.
Các file đính kèm theo tài liệu này:
LUANVAN.DOC- BIA.DOC
CHUONGTRINH.rar- MODAU.DOC
