Nén số liệu bằng kỹ thuật mã hóa huffman với mô hình thống kê
MỞ ĐẦU I. Giới thiệu về đề tài Trong thời đại ngày nay với sự phát triển mạnh mẽ của khoa học công nghệ thông tin, việc ứng dụng Tin học hầu như đã vào trong tất cả mọi lĩnh vực hoạt động sản xuất của con người ở các nước phát triển trên thế giới. Ở nước ta, nhằm góp phần vào công cuộc Công nghiệp hoá-hiện đại hoá đất nước, vấn đề Tin học hoá đã và đang được triển khai. Việc ứng dụng Tin học vào công tác quản lý và điều hành tại các cơ quan xí nghiệp ngày càng cao và đem lại hiệu quả. Bên cạnh đó, đồng nghĩa với nó là vấn đề lưu trữ và xử lý dữ liệu. Cùng với thời gian, sự cập nhật, lưu trữ dữ liệu ngày càng nhiều, điển hình là một số cơ quan hành chính nhà nước như: chi cục thống kê của các tỉnh, thành phố, trung ương . với một khối lượng lớn dữ liệu cần lưu trữ. Vì vậy, vấn đề được đặt ra là làm sao lưu trữ dữ liệu ít tốn kém nhất mà vẫn đảm bảo tính an toàn và chính xác của nó? Do đó, việc tìm ra phương pháp giảm dung lượng lưu trữ mà vẫn đáp ứng được yêu cầu trên là rất cần thiết. Chúng ta thấy rằng: ngày nay với sự phát triển vượt trội trong công nghệ phần cứng, dung lượng đĩa cứng tăng lên một cách đáng kể và nhanh chóng. Một loạt đĩa cứng không ngừng tăng lên về dung lượng ra đời trong khi giá thành sản phẩm lại hạ. Bên cạnh đó còn có các thiết bị lưu trữ khác như băng từ, đĩa quang .cũng được sử dụng rộng rãi. Tuy nhiên, cũng chính vì lý do này mà các nhà lập trình thường sử dụng bất cứ tài nguyên nào có thể, kết quả là nhiều sản phẩm phần mềm ra đời nhưng có kích thước rất lớn, chiếm hàng trăm Mbyte. Thêm vào đó, nhiều lĩnh vực sản xuất áp dụng những phần mềm khác nhau, để đáp ứng được nhu cầu này đòi hỏi người sử dụng tiếp cận nhiều hơn và tạo thói quen lưu trữ nhiều sản phẩm phần mềm, ngoài ra là việc xử lý nhiều tập tin và nhiều loại dữ liệu khác nhau. Do vậy, nén dữ liệu vẫn là vấn đề cần thiết được thực hiện trước khi lưu trữ. Song song với vấn đề trên, một lĩnh vực không thể không kể đến là mạng máy tính. Ngày nay, mạng máy tính mà mọi người đều nhắc đến là mạng Internet -mạng của các mạng- Có thể nói rằng: Internet là mạng thông tin toàn cầu và số người kết nối vào mạng đã lên đến vài chục triệu người. Vì vậy, nhu cầu truyền thông rất lớn. Tất cả mọi người đều muốn có thể tìm kiếm thông tin bất luận chúng ở đâu, đều muốn chia sẻ thông tin, thiết bị với người khác hoặc quản lý thông tin và thực hiện toàn bộ các tác vụ này một cách nhanh chóng, dễ dàng với độ an toàn chính xác cao. Ngoài ra, hiện nay ở nước ta nhằm đáp ứng nhu cầu trao đổi thông tin giữa các cơ quan nhà nước, việc xây dựng Mạng Hành chính Quốc Gia đã được kết nối thông suốt từ năm 1997, dẫn đến vấn đề truyền thông bằng văn bản Tiếng việt càng tăng. Do đó, bên cạnh việc cải tiến phần cứng như: Modem, đường truyền . ta còn phải tìm cách giảm dung lượng dữ liệu cần thiết trước khi truyền để giảm được thời gian truyền và bộ nhớ. Đối với mạng Internet, thực hiện tốt điều đó cho phép giảm được cước phí truy cập mạng. Vậy nén dữ liệu là gì? Ta có thể khái quát: Nén là quá trình giảm dung lượng nhớ cần thiết mà vẫn biểu diễn cùng một dữ liệu cho trước. Trong truyền thông số liệu, nén là một kỹ thuật được áp dụng một cách linh hoạt cho luồng thông tin đang truyền. Công nghệ bên trong về cơ bản cũng như nhau trong cả hai trường hợp là: loại bỏ thông tin dư thừa hoặc biểu thị thông tin dưới dạng chặt chẽ hơn để giảm tổng số byte phải truyền qua phương tiện truyền thông nhằm giảm đến thấp nhất thời gian chiếm phương tiện của một cuộc truyền đã cho. Đối với nén dữ liệu trên máy PC, có nhiều thuật toán nén khác nhau được thiết kế cho nhiều loại dữ liệu khác nhau như: văn bản, hình ảnh, âm thanh . Trong phạm vi của đồ án, ta chỉ xét đến các phương pháp nén văn bản. Nén văn bản là biểu diễn lại lượng thông tin sao cho có kích thước nhỏ hơn ban đầu và một yêu cầu không thể thiếu là dữ liệu của tập tin gốc phải luôn luôn được khôi phục lại hoàn toàn chính xác vì đối với loại văn bản này, sự mất mát thông tin dù chỉ một bit là điều không thể chấp nhận được. Hiện nay, có nhiều phương pháp nén văn bản khác nhau trong đó ta sẽ xét đến phương pháp nén Huffman. Là một trong những phương pháp nén ra đời sớm nhất và đã thành công trong lưu trữ máy tính và viễn thông, phương pháp này thích hợp với kiểu dữ liệu văn bản. Tư tưởng chính của phương pháp như sau: Thay vì lưu trữ mỗi ký hiệu là 8 bit (mã ASCII), dựa vào xác suất (tần suất xuất hiện) của mỗi ký hiệu mà ta sẽ biểu diễn ít bit đối với ký hiệu có xác suất cao và nhiều bit để biểu diễn ký hiệu có xác suất thấp. Ví dụ ta có luồng dữ liệu là :AABBAADCCC, với mỗi ký hiệu được lưu trữ bình thường là 8 bit thì ta phải mất 8x10=80 bit, trong khi đó với phương pháp mã hoá Huffman dựa vào xác suất xuất hiện: A= 4/10, C=3/10,B=2/10,D=1/10, giả sử ta biểu diễn cho ký hiệu A là 1 bit, C là 2 bit, B là 3 bit, D là 4 bit thì chỉ tốn lượng bit là: 1x4+2x3+3x2+4x1=20 bit. Như vậy, ta đã tiết kiệm được 60 bit lưu trữ. Trong phạm vi đồ án, ta sẽ xét đến các phần sau: · Phương pháp mã hoá Huffman với Mô hình thống kê tĩnh bậc 0 · Phương pháp mã hoá Huffman với Mô hình thống kê động bậc 0 · Phương pháp mã hoá Huffman với Mô hình thống kê động bậc 1 · So sánh hiệu suất nén giữa các mô hình với nhau · So sánh hiệu suất nén giữa phương pháp mã hoá Hufman với các phương pháp nén khác trên thị trường. Tuy nhiên cần nói thêm rằng, ở đây ta chỉ xét đến mô hình ký tự trong khi các phương pháp nén hiện có ở thị trường được thực hiện trên mô hình từ điển nên hiệu suất nén của phương pháp mã hoá trên mô hình ký hiệu sẽ thấp hơn. Do đó, mục đích của đồ án là tìm hiểu các kỹ thuật nén không tổn hao nói chung và chủ yếu là kỹ thuật nén số liệu theo phương pháp mã hoá Huffman với mô hình ký tự. Từ mô hình thống kê động bậc 0 sẽ nâng cấp lên mô hình thống kê động bậc 1 để từ đó cho thấy được hiệu suất nén của một kỹ thuật nén phụ thuộc như thế nào vào mô hình hoá?, so sánh giữa phương pháp mã hoá Huffman tĩnh và Huffman động. Với các vấn đề trên, ta sẽ trình bày chi tiết trong các chương tiếp theo. Cấu trúc đồ án : Gồm có 6 chương Chương 1: - Giới thiệu đề tài - Nêu lên mục đích ý nghĩa của đề tài - Khái quát một số lý thuyết tổng quan về nén số liệu Chương 2: Giới thiệu và nên lên nội dung của một bài toán nén số liệu tổng quát, so sánh một số loại mã thống kê tối ưu. Chương 3: Làm rõ bài toán nén số liệu theo phương pháp nén Huffman với mô hình thống kê tĩnh và động bậc 0 Chương 4: Xây dựng cấu trúc dữ liệu và giải thuật cho chương trình nén theo phương pháp Huffman với mô hình thống kê tĩnh và động bậc 0. Cải tiến nâng cấp lên mô hình thống kê động bậc 1. Chương 5: Trình bày các kết quả thực nghiệm, so sánh tỉ số nén, tốc độ nén, tốc độ giải nén đối với các chương trình nén đã được thương mại hoá. Chương 6: Kết luận, nêu lên ưu nhược điểm của phương pháp nén Huffman. Định hướng phát triển của đồ án.
Bạn đang xem trước 20 trang tài liệu Nén số liệu bằng kỹ thuật mã hóa huffman với mô hình thống kê, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
ûu END_OF_STREAM (kãút thuïc luäöng)âäöng thåìi gaïn cho noï giaï trë 256.
Ta coï cáúu truïc dæî liãûu mä taí cáy nhæ sau:
typedef struct tree_node {
unsigned int count;
unsigned int saved_count;
int child_0;
int child_1;
} NODE;
Theo cáúu truïc cuía cáy åí trãn, mäùi nuït trong maíng coï 4 thaình pháön:
unsigned int count: mäüt biãún âãúm duìng âãø giæî troüng læåüng cuía nuït
int child_0;int child_1: hai thaình pháön khaïc laì caïc biãún duìng âãø xaïc âënh hai nuït con cuía nuït âoï
unsigned int saved_count: thaình pháön thæï tæ chè laì mäüt biãún taûm sæí duûng cho viãûc xáy dæûng cáy maî.
Våïi cáúu truïc dæî liãûu nhæ váûy váún âãö âàût ra laì laìm sao ta coï thãø nháûn biãút âæåüc kyï hiãûu âoï laì kyï hiãûu gç (maî ASCII) trong cáy maî? Coï cáön thiãút phaíi sæí duûng thãm mäüt biãún âãø læu træî giaï trë kyï hiãûu hay khäng? Âãø giaíi quyãút âæåüc váún âãö âoï chuïng ta seî sàõp xãúp caïc nuït thaình mäüt maíng trong âoï 257 nuït laï seî âæåüc xãúp åí âáöu maíng tiãúp theo âoï laì caïc nuït nhaïnh vaì cuäúi cuìng laì nuït giaí. Nhæ váûy, viãûc nháûn daûng mäüt nuït laï vaì giaï trë cuía kyï hiãûu tæång æïng coï thãø dæûa vaìo vë trê cuía noï trong maíng.Tráût tæû sàõp xãúp cuía maíng 514 nuït nhæ sau:
Troüng læåüng cuía nuït
Biãún taûm
Giaï trë cuía nuït con thæï nháút
Giaï trë cuía nuït con thæï hai
257 nuït laï
255 nuït nhaïnh
nuït gäúc
nuït giaí
Tráût tæû sàõp xãúp trong mäüt nuït
Hçnh 4-1 Maíng sàõp xãúp caïc nuït trong cáy maî Huffman ténh
Chæång trçnh maî hoaï laìm viãûc theo trçnh tæû: Âáöu tiãn laì âãúm caïc kyï hiãûu coï màût trong file vaì säú læåüng cuía chuïng. Kãút quaí âãúm âæåüc ghi vaìo mäüt maíng gäöm 256 biãún âãúm. Mäùi biãún âãúm coï kêch thæåïc laì 2 byte (giaï trë âãúm âæåüc täúi âa laì 65.535). Sau khi âãúm xong, táút caí caïc kãút quaí âãöu âæåüc quy giaím xuäúng theo mäüt hãû säú tyí lãû xaïc âënh âuí âãø chæïa trong mäüt byte räöi âæåüc sao cheïp vaìo caïc biãún âãúm tæång æïng cuía 256 nuït âáöu tiãn trong maíng caïc nuït âaî noïi træåïc âáy. Tiãúp theo, ta xáy dæûng cáy maî Huffman theo phæång phaïp âaî âãö cáûp åí chæång 3/muûc I.2
Sau khi xáy dæûng xong cáy maî, laìm thãú naìo âãø coï âæåüc caïc tæì maî cuía tæìng kyï hiãûu?. Ta coï quaï trçnh láúy âæåüc tæì maî: do mäùi kyï hiãûu tæång æïng våïi mäùi nuït nãn âiãøm xuáút phaït laì åí mäüt nuït laï. Tæì âoï, ta âi ngæåüc lãn phêa nuït gäúc vaì têch luîy laûi giaï trë cuía caïc nhaïnh trãn âæåìng âi âãún gäúc, sau âoï âaío ngæåüc tráût tæû caïc bit âaî têch luîy måïi coï âæåüc tæì maî âäúi våïi kyï hiãûu cáön phaíi maî hoaï. Nhæng tæì cáúu truïc cáy maî trãn ta khäng thæûc hiãûn âæåüc âiãöu naìy vç khi âæïng åí mäüt nuït, ta khäng thãø xaïc âënh âæåüc nuït cha cuía noï. Nhæ váûy, âãún luïc naìy ta váùn chæa maî hoaï âæåüc kyï hiãûu. Coï 2 giaíi phaïp âæåüc âãö cáûp âãún:
Giaíi phaïp 1:
Khi gàûp mäüt kyï hiãûu, ta xuáút phaït tæì nuït gäúc (cuîng nhæ tæì mäüt nuït nhaïnh) vaì bàõt âáöu duyãût qua toaìn bäü cáy. Nghéa laì ta láön læåüt reî theo caïc nhaïnh , cho âãún khi naìo âæåüc nuït laï laì kyï hiãûu cáön maî hoaï vaì xuáút tæì maî cuía kyï hiãûu cáön maî hoaï. Nhæ váûy, ta khäng cáön âaío ngæåüc caïc bit do noï âæåüc têch luyî tæì gäúc âãún nuït laï trong quaï trçnh tçm kiãúm kyï hiãûu.
Giaíi phaïp 2:
Ta xáy dæûng baíng maî tæì cáy maî. Cáúu truïc dæî liãûu cho baíng maî laì:
typedef struct {
unsigned int code;
int code_bit;
} CODE;
Ta bàõt âáöu duyãût toaìn bäü cáy mäüt láön tæì gäúc âãún táút caí caïc nuït laï vaì xáy dæûng mäüt baíng caïc tæì maî cho táút caí caïc kyï hiãûu coï trong cáy.
Nhæ váûy, tuy caí hai cuìng duìng thuí tuûc âãû qui âãø duyãût cáy maî nhæng ta choün giaíi phaïp 2 vç roî raìng noï maî hoaï nhanh hån do chè duyãût cáy mäüt láön vaì sau âoï viãûc maî hoaï tæìng kyï hiãûu cuía mäüt file säú liãûu seî âæåüc thæûc hiãûn ráút âån giaín dæûa vaìo baíng caïc tæì maî naìy. Khi gàûp mäüt kyï hiãûu, dæûa vaìo baíng maî ta coï âæåüc tæì maî tæång æïng.
Ta coï toaìn bäü quaï trçnh maî hoaï nhæ sau:
Âãúm táön suáút xuáút hiãûn (xaïc suáút) cuía caïc kyï hiãûu trong cáön neïn
Qui giaím xaïc suáút cuía caïc kyï hiãûu âoï
Xuáút säú liãûu thäúng kã ra file neïn
Xáy dæûng cáy maî Huffman ténh
Xáy dæûng baíng maî
Maî hoaï: while (chæa kãút thuïc file)
{ Âoüc mäüt kyï hiãûu;
Xuáút tæì maî tæång æïng dæûa vaìo baíng maî;
}
Phæång phaïp giaíi maî Huffman theo mä hçnh thäúng kã ténh
Chæång trçnh giaíi maî muäún laìm viãûc âuïng phaíi coï âæåüc baín sao cuía cáy maî Huffman âaî âæåüc chæång trinh maî hoaï âaî sæí duûng. ÅÍ âáy, ta cuîng coï 2 giaíi phaïp âæåüc âæa ra:
Giaíi phaïp 1: Gæíi cáúu truïc cuía cáy maî nghéa laì gæíi toaìn bäü säú liãûu cuía maíng gäöm 514 pháön tæí noïi trãn (cåî 4Kbyte) ra âáöu file neïn sau âoï måïi âãún caïc tæì maî. Chæång trçnh giaíi maî seî dæûa vaìo cáy maî naìy âãø maî hoaï caïc kyï hiãûu bàòng caïch âoüc tæì bit mäüt vaì reî theo nhaïnh 0 hoàûc 1 âãø âãún âæåüc nuït laï, sau âoï xuáút kyï hiãûu tæång æïng våïi nuït laï væìa tçm âæåüc ra file giaíi neïn. Nhæ âaî xeït trong caïc chæång træåïc, do maî Huffman laì maî coï tênh cháút tiãön täú nãn ta luän luän giaíi maî âæåüc caïc kyï hiãûu tæång æïng tæì luäöng bit nháûn âæåüc dæûa vaìo cáy maî.
Giaíi phaïp 2: Gæíi 256 biãún âãúm (256 byte) chæïa xaïc suáút tæång æïng våïi 256 kyï hiãûu ra âáöu file neïn. Tuy nhiãn, coï nhæîng træåìng håüp khäng phaíi táút caí 256 kyï hiãûu âãöu coï màût trong mäüt file säú liãûu (nháút laì caïc file vàn baín ASCII), do âoï coï ráút nhiãöu biãún âãúm coï giaï trë bàòng 0 do âoï ta seî khäng gæíi âi caïc biãún âãúm âoï. Bãn caûnh âoï våïi caïc biãún âãúm coï giaï trë khaïc 0 ta gæíi âi theo khuän daûng tiãút kiãûm hån bàòng caïch phán chia thaình tæìng loaût. Khoaíng caïch giæîa hai loaût biãún âãúm phaíi êt nháút laì 3 biãún âãúm coï giaï trë bàòng 0. Trong mäùi loaût biãún âãúm âoï, ta chè gæíi âi giaï trë cuía kyï hiãûu âáöu vaì kyï hiãûu cuäúi cuìng våïi táút caí caïc giaï trë cuía caïc biãún âãúm trong loaût âoï. Dáúu hiãûu kãút thuïc loaûi säú liãûu thäúng kã naìy laì mäüt byte coï giaï trë bàòng 0. Dæûa vaìo säú liãûu naìy, chæång trçnh giaíi maî seî xáy dæûng cáy maî vaì quaï trçnh giaíi maî seî tæång tæû nhæ giaíi phaïp 1. Nhæ váûy våïi giaíi phaïp 2, coï thãø ta chè täún mäüt khoaíng £ 256 byte (báûc 0).
Tæì 2 giaíi phaïp trãn, ta choün giaíi phaïp 2 vç ta seî tiãút kiãûm âæåüc ráút nhiãöu pháön khäng gian daình cho säú liãûu thäúng kã cáön phaíi cung cáúp cho chæång trçnh giaíi maî. Nhåì váûy, hiãûu suáút neïn seî âæåüc náng cao. ÅÍ âáy, våïi mä hçnh báûc 0 thç hiãûu suáút neïn cuía giaíi thuáût 2 trãn chãnh lãûch khäng âaïng kãø nhæng våïi mä hçnh báûc cao säú liãûu thäúng kã låïn thç hiãûu suáút neïn seî chãnh lãûch âaïng kãø giæîa giaíi phaïp 2 so våïi giaíi phaïp 1.
Ta coï quaï trçnh giaíi maî nhæ sau:
Nháûp säú liãûu thäúng kã: Âáöu tiãn, ta taûo ra trong bäü nhåï mäüt cáúu truïc dæî liãûu laì mäüt maíng gäöm 514 nuït nhæ chæång trçnh maî hoaï âaî laìm âãø chuáøn bë cho viãûc xáy dæûng cáy maî. Sau âoï, måí vaì âoüc toaìn bäü caïc byte säú liãûu thäúng kã âæåüc chæïa åí pháön âáöu cuía mäüt file säú liãûu âaî âæåüc chæång trçnh maî hoaï gåíi âáöu file âãø xæí lyï (dæûa trãn khuän daûng âàûc biãût âaî biãút) vaì chuyãøn kãút quaí (giaï trë caïc biãún âãúm cuía táút caí caïc kyï hiãûu) vaìo caïc vë trê thêch håüp trong maíng caïc nuït âaî khåíi taûo.
Xáy dæûng cáy maî: Tæång tæû nhæ chæång trçnh maî hoaï
Giaíi maî dæûa vaìo cáy maî væìa âæåüc xáy dæûng:
Khåíi âäüng con troí p chè âãún gäúc.
while (chæa âaût âãún kãút thuïc thäng baïo)
{
Âàût x laì bit tiãúp theo trong xáu kyï hiãûu.
if (x = 0)
Âàût p bàòng con troí chè âãún con troí bãn traïi cuía noï.
else
Âàût p bàòng con troí chè âãún con bãn phaíi cuía noï.
if (p chè âãún mäüt nuït laï)
{
Xuáút kyï hiãûu tæång æïng våïi nuït laï ra file giaíi neïn.
Âàût laûi p âãø noï chè âãún gäúc cuía cáy Huffman
}
}
Phæång phaïp maî hoaï Huffman theo mä hçnh thäúng kã âäüng (thêch æïng)
Phæång phaïp maî hoaï Huffman theo mä hçnh thäúng kã âäüng
Khaïc våïi mä hçnh thäúng kã ténh laì cáy maî chè âæåüc xáy dæûng mäüt láön dæûa trãn xaïc suáút thäúng kã trãn toaìn nguäön säú liãûu. Våïi mä hçnh thäúng kã âäüng, cáy maî luän luän âæåüc cáûp nháût sau khi maî hoaï âæåüc mäüt kyï hiãûu (cáûp nháût mä hçnh) vaì xaïc suáút cuía caïc kyï hiãûu khäng âæåüc thäúng kã mäüt láön maî âæåüc têch luyî trong suäút quaï trçnh maî hoaï. Nhæ váûy, åí mä hçnh thäúng kã âäüng ta khäng thãø biãút træåïc âæåüc xaïc suáút xuáút hiãûn cuía caïc kyï hiãûu trong toaìn bäü nguäön säú liãûu laì bao nhiãu. Viãûc cáûp nháût hoàûc xáy dæûng laûi cáy maî dæûa vaìo tênh cháút sibling cuía cáy.
Ta xáy dæûng cáúu truïc dæî liãûu cho cáy maî Huffman âäüng nhæ sau:
struct tree {
int leaf [SYMBOL_COUNT];
int next_free_node;
struct node nodes[NODE_TABLE_COUNT];
}Tree;
struct node {
unsigned int weight;
int parent;
int child_is_leaf;
int child;
};
Våïi: SYMBOL_COUNT=257, NODE_TABLE_COUNT=515, nghéa laì khaïc våïi cáy Huffman ténh thay vç chè coï 514 nuït thç cáy Huffman âäüng coï thãm mäüt nuït Escape do âoï ngoaìi kyï hiãûu kãút thuïc luäöng END_OF_STREAM=256 coï thãm nuït Escape =257 âãø maî hoaï luäöng kyï hiãûu vaìo. Trong cáy maî, mäùi nuït gäöm coï 4 thaình pháön:
unsigned int weight: biãún âãúm giæî troüng læåüng cuía nuït naìy.
int parent: biãún duìng âãø xaïc âënh nuït cha cuía nuït naìy.
int child_is_leaf: biãún logic duìng âãø phán biãût giæîa nuït laï vaì nuït nhaïnh. Nãúu biãún naìy coï giaï trë TRUE laì nuït laï, nãúu biãún naìy coï giaï trë FALSE laì nuït nhaïnh.
Int child: biãún duìng âãø xaïc âënh nuït con thæï nháút cuía nuït ( nuït con thæï hai seî âæåüc xaïc âënh nhåì tênh cháút Sibling cuía cáy maî Huffman). Nãúu biãún logic cuía nuït laì TRUE thç biãún naìy seî giæî giaï trë cuía kyï hiãûu tæång æïng våïi nuït laï naìy.
Trong cáy maî, theo tênh cháút sibling caïc nuït âæåüc sàõp xãúp theo thæï tæû tàng dáön, nhæng åí âáy troüng læåüng cuía caïc nuït âæåüc sàõp xãúp theo thæï tæû ngæåüc laûi laì giaím dáön.
Nuït 0 nuït 1 nuït 2 ... nuït 514
Biãún thæï nháút Biãún thæï hai duìng âãø Biãún logic Biãún duìng âãø xaïc
giæî troüng læåüng xaïc âënh nuït cha TRUE=âáy laì nuït laï âënh nuït con thæï
cuía nuït FALSE=âáy laì nuït nhaïnh nháút hoàûc giaï trë
cuía kyï hiãûu
Tráût tæû sàõp xãúp trong mäüt nuït
Hçnh 4-2 Maíng thæï nháút mä taí cáy maî Huffman thêch æïng
Maíng thæï hai duìng âãø truy cáûp cáy maî khi maî hoaï vaì giaíi maî. Maíng naìy gäöm 258 thaình pháön. Tæång æïng cáúu truïc dæî liãûu mä taí cáy åí trãn laì maíng int leaf[SYMBOL_COUNT], trong âoï mäùi pháön tæí duìng âãø xaïc âënh vë trê cuía mäüt nuït laï tæång æïng våïi mäüt kyï hiãûu trong säú 258 kyï hiãûu ( 256 kyï hiãûu ASCII, kyï hiãûu kãút thuïc luäöng EoS vaì kyï hiãûu Escape ).
Vë trê cuía nuït laï Vë trê cuía nuït laï Vë trê cuía nuït laï Vë trê cuía nuït laï
tæång æïng våïi kyï tæång æïng våïi kyï tæång æïng våïi kyï tæång æïng våïi kyï
hiãûu coï giaï trë 0 hiãûu coï giaï trë 1 hiãûu coï giaï trë 256 hiãûu coï giaï trë 257
0 1 256 257
Hçnh 4-3 Maíng thæï hai duìng âãø xaïc âënh vë trê caïc nuït laï
Mäüt thaình pháön khaïc trong cáúu truïc cáy maî laì int next_free_node laì mäüt biãún âãø giæî giaï trë vë trê hiãûn thåìi cuía nuït tiãúp theo sau nuït cuäúi cuìng trong danh saïch caïc nuït âaî coï trong cáy maî âãø biãút âæåüc hiãûn thåìi danh saïch caïc nuït âaî coï trong cáy maî âaî keïo daìi âãún âáu trong maíng mä taí caïc nuït, thaình pháön naìy seî duìng khi xáy dæûng laûi cáy maî.
* Toaìn bäü quaï trçnh maî hoaï nhæ sau:
Khåíi âäüng cáy maî räùng âáöu tiãn;
while (âoüc vaìo mäüt kyï hiãûu END_OF_STREAM)
{
Maî hoaï kyï hiãûu ;
Cáûp nháût cáy maî;
}
Khåíi âäüng cáy maî räùng
Nuït gäúc
Escape (1)
1
EoS(1)
Hçnh 4 4 Cáy maî räùng âáöu tiãn
0
Nhæ âaî xeït, våïi cáy maî Huffman âäüng ta coï thãm nuït Escape, nuït naìy goüi laì maî thoaït (coï giaï trë =257). Âiãöu naìy coï cáön thiãút hay khäng?. Ta tháúy ràòng, våïi mä hçnh thäúng kã âäüng, viãûc maî hoaï vaì giaíi maî âãöu dæûa vaìo cáy maî hiãûn thåìi. Maî thoaït âæåüc sæí duûng trong 2 quaï trçnh naìy. Khi kyï hiãûu chæa coï màût trong cáy maî, luïc naìy dæûa vaìo maî thoaït âaî coï trong cáy maî ta seî gåíi âi tæì maî cuía maî thoaït vaì maî ASCII cuía kyï hiãûu, dæûa vaìo âoï chæång trçnh giaíi maî måïi giaíi maî âæåüc chênh xaïc kyï hiãûu khi noï xuáút hiãûn láön âáöu tiãn (chæa coïmàût trong cáy maî hiãûn thåìi) naìy bàòng caïch cuîng dæûa vaìo maî thoaït. Khi âoüc âãún mäüt nuït laï laì maî Escape, chæång trçnh seî âoüc tiãúp 8 bit vaì xuáút ra kyï hiãûu tæång æïng våïi giaï trë maî ASCII 8 bit naìy. Ngoaìi ra, mäüt khêa caûnh cuîng cáön sæí duûng âãún maî thoaït laì quaï trçnh thãm mäüt nuït måïi vaìo cáy maî. Váûy ta thãm nuït måïi naìy vaìo âáu?, coï thãø thãm vaìo mäüt caïch ngáùu nhiãn åí báút kç nuït naìo trong cáy maî khäng?. Khi thãm mäüt nuït vaìo cáy maî ta cuîng tuán theo mäüt nguyãn tàõc nháút âënh, vaì noï âæåüc thãm vaìo nuït tæång æïng våïi maî thoaït (laì nuït coï troüng læåüng beï nháút). Nuït escape seî âæåüc thay thãú bàòng mäüt nhaïnh måïi gäöm 2 nuït: nuït escape vaì mäüt nuït tæång æïng våïi kyï hiãûu måïi thãm vaìo.
Cáy maî âæåüc khåíi taûo gäöm coï 3 nuït: nuït âáöu tiãn (nuït 0) seî laì nuït gäúc vaì laì nuït coï troüng læåüng låïn nháút trong cáy), caïc nuït tiãúp theo tæì nuït 1 tråí âi seî daình cho caïc nuït phêa trong cáy gäöm caïc nuït nhaïnh vaì caïc nuït laï theo nguyãn tàõc giaím dáön cuía troüng læåüng. Våïi cáy maî trãn ta coï caïc nuït âæåüc gaïn giaï trë nhæ sau:
Nuït 0 (gäúc) coï troüng læåüng bàòng 2 (biãún thæï nháút âàût = 2), khäng coï nuït cha (biãún thæï hai âàût = -1), khäng phaíi laì nuït laï (biãún logic âàût = FALSE), nuït con thæï nháút (gàõn våïi nhaïnh 0) laì nuït EoS (biãún cuäúi cuìng âàût = 1).
Nuït 1 (EoS) coï troüng læåüng bàòng 1 (biãún thæï nháút âàût = 1), nuït cha cuía noï laì nuït gäúc (biãún thæï hai âàût = 0), âáy laì mäüt nuït laï (biãún logic âàût = TRUE), giaï trë cuía kyï hiãûu tæång æïng våïi noï laì 256 (biãún cuäúi cuìng âàût = 256).
Nuït 2 (Escape) coï troüng læåüng bàòng 1 (biãún thæï nháút âàût = 1), nuït cha cuía noï laì nuït gäúc (biãún thæï hai âàût = 0), âáy laì mäüt nuït laï (biãún logic âàût = TRUE), giaï trë cuía kyï hiãûu tæång æïng våïi noï laì 257 (biãún cuäúi cuìng âàût = 257).
Tráût tæû caïc nuït sàõp xãúp trong cáy maî hiãûn thåìi nhæ sau:
2 -1 F 1 1 0 T 256 1 0 T 257
Nuït 0 Nuït 1 Nuït 2
Hçnh 4 5 Khåíi âäüng giaï trë cho 3 nuït âáöu tiãn cuía cáy maî räùng
-1 -1 -1 -1 2 1
0 1 2 255 256 257
Tæång æïng, ta coï caïc thaình pháön trong maíng thæï hai laì:
Hçnh 4-6 Khåíi âäüng caïc giaï trë âáöu cho maíng thæï hai
Âáöu tiãn táút caí caïc nuït âãöu âæåüc gaïn cho giaï trë -1 ngoaûi træì hai thaình pháön tæång æïng våïi caïc kyï hiãûu EoS vaì Escape âæåüc gaïn giaï trë láön læåüt laì 1vaì 2. Ngoaìi ra, biãún next_free_node âàût giaï trë bàòng 3 (vç nuït 2 laì nuït cuäúi cuìng trong danh saïch caïc nuït cuía cáy räùng). Giaï trë -1 laì mäüt giaï trë qui æåïc xaïc âënh xem mäüt kyï hiãûu naìo âoï âaî coï trong cáy maî hay chæa vaì noï duìng cho viãûc cáûp nháût cáy maî sau naìy trong quaï trçnh maî hoaï (hoàûc giaíi maî).
Maî hoaï kyï hiãûu
Kyï hiãûu âoüc vaìo âæåüc thuí tuûc maî hoaï seî kiãøm tra kyï hiãûu trong cáy maî: coï 2 træåìng håüp
Træåìng håüp 1: Nãúu kyï hiãûu âaî coï trong cáy maî thç seî xuáút tæì maî tæång æïng theo cáúu truïc cáy hiãûn thåìi
Træåìng håüp 2: Nãúu kyï hiãûu chæa coï trong cáy maî thç seî xuáút tæì maî tæång æïng våïi kyï hiãûu Escape trong cáy maî hiãûn thåìi vaì theo sau laì maî ASCII cuía kyï hiãûu naìy. Sau âoï, thãm kyï hiãûu (thãm mäüt nuït måïi) vaìo cáy maî
Viãûc xaïc âënh tæì maî âæåüc thæûc hiãûn bàòng caïch bàõt âáöu tæì mäüt nuït laï tæång æïng våïi kyï hiãûu væìa âoüc vaìo vaì láön theo caïc nuït cha âãø cuäúi cuìng âãún cho âæåüc nuït gäúc. Theo cáúu truïc cáy maî âæåüc xáy dæûng trãn, ta qui æåïc sau nuït gäúc (nuït 0), nuït âi træåïc (nuït leí) gàõn våïi nuït cha laì nhaïnh 1, nuït âi sau (nuït chàôn) gàõn våïi nuït cha laì nhaïnh 0. Quaï trçnh âi tæì mäüt nuït laï vãö nuït gäúc coï thãø càn cæï vaìo säú thæï tæû cuía caïc nuït phaíi âi qua vaì tæìng bit maî xaïc âënh âæåüc seî têch luyî vaìo mäüt biãún vaì mäüt biãún khaïc laìm nhiãûm vuû âãúm säú bit maî têch luîy âæåüc seî âæåüc tàng lãn 1 giaï trë âãø theo doîi âäü daìi cuía tæì maî. Hai biãún naìy seî phuûc vuû cho viãûc xuáút tæìng bit mäüt cuía tæì maî ra táûp tin neïn.
Âãø thãm mäüt nuït måïi vaìo cáy maî, ta thæûc hiãûn nhæ sau: Âáöu tiãn xaïc âënh nuït cuäúi danh saïch trong cáy maî nghéa laì nuït coï troüng læåüng beï nháút vaì thay thãú bàòng mäüt nuït nhaïnh måïi. Nuït nhaïnh naìy seî coï hai nuït con: nuït con gàõn våïi nhaïnh 0 laì chênh laì nuït tæång æïng våïi kyï hiãûu vaì khi måïi âæåüc thãm vaìo cáy maî noï coï troüng læåüng bàòng 0, sau âoï hoaût âäüng cáûp nháût måïi tàng troüng læåüng cuía nuït lãn mäüt giaï trë, nuït con gàõn våïi nhaïnh 1 laì nuït coï troüng læåüng beï nháút væìa tçm âæåüc.
Cáûp nháût cáy maî
Sau khi maî hoaï ta seî cáûp nháût cáy maî, quaï trçnh cáûp nháût cáy maî nhæ sau:
if (troüng læåüng cuía nuït gäúc âaî âaût giaï trë ngæåîng)
Xáy dæûng laûi cáy maî ;
else
nuït hiãûn taûi = kyï hiãûu væìa maî hoaï;
while (chæa væåüt quaï nuït gäúc)
{
tàng troüng læåüng cuía nuït hiãûn thåìi lãn 1;
if (vi phaûm tênh cháút sibling)
Traïo âäøi 2 nuït trong cáy
else
Tàng troüng læåüng nuït cha cuía nuït hiãûn thåìi;
}
Xáy dæûng laûi cáy maî
Khi cáy maî âæåüc cáûp nháût nhiãöu láön thç âãún mäüt luïc naìo âoï noï coï thãø âi âãún chäø traìn bäü âãúm troüng læåüng cuía nuït gäúc. Âãø traïnh âiãöu naìy, ta âàût mäüt giaï trë ngæåîng vaì khi troüng læåüng cuía nuït gäúc væåüt quaï giaï trë ngæåîng naìy thç chuïng ta phaíi xáy dæûng laûi cáy maî âang täön taûi. Viãûc xáy dæûng laûi cáy maî âæåüc thæûc hiãûn dæûa vaìo tênh cháút Sibling. Quaï trçnh xáy dæûng laûi cáy maî gäöm ba bæåïc:
1. Däön táút caí caïc nuït laï vãö cuäúi danh saïch, qui giaím troüng læåüng cuía caïc nuït laï xuäúng mäüt næía vaì laìm troìn kãút quaí.
2. Taûo ra caïc nuït nhaïnh måïi bàòng caïch cho troüng læåüng cuía nuït naìy bàòng täøng troüng læåüng cuía hai nuït con trong säú caïc nuït trãn vaì âënh vë trê cho noï trong danh saïch, nghéa laì phaíi cheìn noï vaìo vë trê thêch håüp trong maíng caïc nuït âaî coï.
3. Xaïc âënh nuït cha cho táút caí caïc nuït trong cáy (træì nuït gäúc). Khi xáy dæûng laûi cáy åí bæåïc 2 chuïng ta chæa gaïn giaï trë cho caïc thaình pháön xaïc âënh nuït cha cho caïc nuït laì vç nuït coï troüng læåüng cuía hai nuït laï thç laì nuït cha cuía hai nuït naìy nhæng âãún læåüt noï, noï chæa coï thãø laì nuït con cuía mäüt nuït naìo âoï trong cáy maî.
Kiãøm tênh cháút sibling
Sau khi maî hoaï âæåüc mäüt kyï hiãûu, nãúu kyï hiãûu âoï âaî coï màût trong cáy maî træåïc khi maî hoaï kyï hiãûu naìy hoàûc noï måïi âæåüc thãm vaìo khi khäng tçm tháúy trong cáy maî thç ta âãöu tàng troüng læåüng cuía nuït naìy lãn mäüt giaï trë. Âäöng thåìi, caïc nuït liãn quan âãún kyï hiãûu naìy thç troüng læåüng cuîng âæåüc tàng lãn mäüt giaï trë. Sau khi tàng giaï trë biãún âãúm cuía mäüt nuït thç tênh cháút Sibling cuía cáy maî seî âæåüc kiãøm tra. Nãúu vi phaûm thç cáön phaíi thæûc hiãûn traïo âäøi giaï trë cuía mäüt säú nuït trong maíng våïi nhau.
Tæì cáúu truïc cáy maî ta tháúy: âæïng åí mäüt nuït ta luän tçm tháúy âæåüc nuït cha cuía nuït naìy, do váûy viãûc tàng biãún âãúm troüng læåüng cuía caïc nuït âæåüc thæûc hiãûn tæì nuït laï âãún caïc nuït nhaïnh trãn âæåìng âi ngæåüc vãö nuït gäúc laì viãûc âån giaín.
Dáúu hiãûu vi phaûm tênh cháút Sibling laì biãún âãúm cuía nuït âang chuáøn bë tàng coï giaï trë bàòng våïi biãún âãúm cuía nuït kãú tiãúp trong danh saïch (theo hæåïng vãö phêa nuït gäúc). Khi tênh cháút Sibling bë vi phaûm, chuïng ta phaíi traïo âäøi nuït naìy våïi mäüt nuït åí vë trê cao hån trong danh saïch.
Thuí tuûc traïo âäøi hai nuït
Khi traïo âäøi hai nuït våïi nhau, træåïc hãút ta phaíi xaïc âënh âæåüc hai nuït cáön phaíi âäøi vë trê cho nhau. Nuït thæï nháút laì nuït vi phaûm tênh cháút Sibling (troüng læåüng cuía nuït naìy træåïc khi tàng âaî bàòng våïi troüng læåüng cuía nuït tiãúp theo trong danh saïch kiãøm tra tênh Sibing). Nuït thæï hai chênh laì nuït cuäúi cuìng trong loaût caïc nuït coï troüng læåüng bàòng nhau tiãúp theo sau âoï båíi vç coï thãø coï ráút nhiãöu nuït theo sau nuït naìy coï troüng læåüng bàòng nhau, do váûy nuït cáön phaíi traïo âäøi chênh laì nuït cuäúi cuìng trong loaût caïc nuït coï troüng læåüng bàòng nhau âoï. Nãúu nuït âæåüc traïo âäøi laì mäüt nuït nhaïnh thç khi di chuyãøn âãún vë trê måïi noï seî keïo theo táút caí caïc nuït bãn dæåïi noï (caí mäüt cáy con). Viãûc traïo âäøi hai nuït âæåüc thæûc hiãûn nhæ sau:
Nãúu caí hai nuït 1 vaì nuït 2 âãöu laì nuït laï hoàûc nãúu nuït1 laì nuït nhaïnh vaì nuït 2 laì nuït laï thç ta gaïn nuït 2 tråí thaình nuït nhaïnh vaì 2 nuït con cuía nuït 1 seî nháûn nuït 2 laìm nuït cha vaì ngæåüc laûi nãúu nuït 1 laì nuït laï vaì nuït 2 laì nuït nhaïnh thç gaïn nuït 1 thaình nuït nhaïnh, 2 nuït con cuía nuït 2 nháûn nuït 1 laìm cha vaì nuït 2 tråí thaình nuït laï. Sau âoï, traïo âäøi troüng læåüng giæîa nuït 1 vaì nuït 2, cuäúi cuìng nuït 1 seî nháûn nuït cha cuía nuït 2 laìm nuït cha vaì ngæåüc laûi nuït 2 nháûn nuït cha cuía nuït1 laìm nuït cha.
Phæång phaïp giaíi maî Huffman theo mä hçnh thäúng kã âäüng
Chæång trçnh giaíi maî cuîng hoaût âäüng tæång tæû nhæ chæång trçnh maî hoaï, quaï trçnh giaíi maî âæåüc thæûc hiãûn nhæ sau:
Khåíi âäüng cáy maî räùng âáöu tiãn;
while (giaíi maî 1 kyï hiãûu END_OF_STREAM)
{
Xuáút kyï hiãûu ra file giaíi neïn ;
Cáûp nháût cáy maî;
}
ÅÍ âáy, viãûc Khåíi taûo cáy maî räùng âáöu tiãn vaì viãûc Cáûp nháût cáy maî cuîng âæåüc thæûc hiãûn tæång tæû nhæ chæång trçnh maî hoaï. Báy giåì ta xeït âãún hoaût âäüng cuía thuí tuûc giaíi maî: Thuí tuûc giaíi maî seî âæïng åí nuït gäúc âãø nháûn vaì xæí lyï tæìng bit mäüt tæì luäöng maî. Viãûc reî xuäúng nuït con naìo laì phuû thuäüc vaìo giaï trë cuía bit maî nháûn âæåüc. Nãúu bit maî bàòng 0 thç nuït con nháûn âæåüc choün laì nuït con chàôn, nãúu bit maî bàòng 1 thç nuït con âæåüc choün laì nuït con leí. Viãûc reî theo nhaïnh 0 hoàûc nhaïnh 1 seî tiãúp tuûc tuyì theo bit maî nháûn vaìo âæåüc tiãúp tuûc cho âãún khi naìo âi âãún âæåüc mäüt nuït laï tæång æïng våïi mäüt kyï hiãûu trong cáy maî hiãûn thåìi. Coï 2 træåìng håüp xaíy ra:
Nãúu kyï hiãûu naìy khaïc Escape nghéa laì kyï hiãûu cáön giaíi maî âaî coï trong cáy maî thç ta xuáút kyï hiãûu naìy ra file giaíi neïn.
Nãúu kyï hiãûu naìy = Escape nghéa laì kyï hiãûu naìy chæa coï trong cáy maî hiãûn thåìi thç thuí tuûc giaíi maî seî âoüc tiãúp 8 bit næîa tæì luäöng maî (tæì file neïn) vaì xuáút 8 bit âoï ra file giaíi neïn, 8 bit naìy tæång æïng våïi maî ASCII cuía kyï hiãûu cáön âæåüc giaíi maî. Sau âoï, ta thãm kyï hiãûu (nuït måïi) coï troüng læåüng bàòng 0 naìy vaìo cáy maî. Thuí tuûc thãm vaìo mäüt nuït måïi åí thuí tuûc giaíi maî cuîng tæång tæû nhæ åí thuí tuûc maî hoaï.
Sau thuí tuûc giaíi maî, cáy maî âæåüc cáûp nháût. Viãûc cáûp nháût cáy maî cuîng tæång tæû nhæ chæång trçnh maî hoaï.
Våïi thuí tuûc giaíi maî nhæ trãn, ta tháúy viãûc giaíi maî caïc kyï hiãûu luän luän âæåüc thæûc hiãûn âuïng vaì duy nháút. Ta xeït laûi chæång trçnh maî hoaï: khi maî hoaï mäüt kyï hiãûu nãúu kiãøm tra kyï hiãûu naìy chæa coï màût trong cáy maî thç ta xuáút tæì maî tæång æïng cuía kyï hiãûu Escape ra file neïn, tiãúp âoï xuáút maî ASCII(8 bit) cuía kyï hiãûu naìy ra file neïn räöi ta måïi thãm kyï hiãûu naìy vaìo cáy maî. ÅÍ thuí tuûc giaíi maî, khi âi âãún nuït laï laì kyï hiãûu Escape, ta âoüc tiãúp 8 bit næîa vaì gåíi ra file giaíi neïn, 8 bit naìy chênh laì maî ASCII cuía kyï hiãûu maì ta âaî maî hoaï trong láön âáöu tiãn noï xuáút hiãûn. Âiãöu naìy luän luän chênh xaïc vaì ta âaî giaíi maî âuïng âæåüc kyï hiãûu.
Caíi tiãún mä hçnh thäúng kã âäüng báûc 1
Nhæ ta âaî xeït, åí mä hçnh báûc 0 chè âãúm táön xuáút xuáút hiãûn cuía tæìng kyï hiãûu báút luáûn kyï hiãûu âæïng liãön træåïc laì kyï hiãûu gç. Do âoï, viãûc maî hoaï vaì giaíi maî hoaìn toaìn dæûa trãn mäüt cáy maî duy nháút. Våïi mä hçnh báûc 1, xaïc suáút cuía mäüt kyï hiãûu dæûa vaìo kyï hiãûu âæïng liãön træåïc, kyï hiãûu naìy goüi laì ngæî caính. Ta coï thãø khaïi quaït mäüt caïch âån giaín nhæ sau: våïi 256 kyï hiãûu taûo thaình ngæî caính, thay vç chè maî hoaï vaì giaíi maî trãn mäüt cáy maî thç ta phaíi maî hoaï vaì giaíi maî 257 cáy maî tæång æïng 256 kyï hiãûu âoï vaì mäüt cáy maî cho 256 kyï hiãûu taûo thaình ngæî caính. Ta taûm goüi cáy maî âãø maî hoaï vaì giaíi maî cho 256 kyï hiãûu ngæî caính laì cáy báûc 0 coìn maî hoaï hoàûc giaíi maî mäüt kyï hiãûu naìo âoï trong mäüt ngæî caính báút kç laì cáy ngæî caính.
Quaï trçnh maî hoaï nhæ sau: khi âoüc vaìo mäüt kyï hiãûu ta luän xeït kyï hiãûu âæïng liãön træåïc noï coï phaíi laì ngæî caính hay khäng, nãúu kyï hiãûu âoï laì ngæî caính thç kyï hiãûu måïi âoüc vaìo seî âæåüc maî hoaï trong cáy ngæî caính âoï, sau âoï cáûp nháût nháût cáy ngæî caính tæång tæû nhæ mä hçnh báûc 0, nãúu kyï hiãûu âæïng liãön træåïc khäng phaíi laì ngæî caính thç kyï hiãûu måïi âoüc vaìo seî âæåüc maî hoaï trong cáy báûc 0 vaì cáûp nháût cáy maî báûc 0. Âãø mäüt kyï hiãûu naìo âoï tråí thaình ngæî caính, åí thuí tuûc cáûp nháût cáy maî báûc 0, sau khi tàng troüng læåüng cuía nuït laï (kyï hiãûu) ta luän xeït troüng læåüng naìy âaî væåüt mäüt ngæåîng (goüi laì ngæåîng ngæî caính) do ta qui âënh chæa, nãúu âuïng thç kyï hiãûu âoï tråí thaình ngæî caính. Nhæ váûy, thuí tuûc cáûp nháût cáy báûc 0 khaïc våïi thuí tuûc cáûp nháût cáy ngæî caính laì ta luän kiãøm tra kyï hiãûu âoï coï âaî tråí thaình ngæî caính hay chæa.
Viãûc choün ngæåîng ngæî caính laì mäüt giaï trë ngáùu nhiãn, ngæåîng ngæî caính caìng beï thç quaï trçnh maî hoaï caìng nhanh choïng chuyãøn sang mä hçnh báûc 1, nãúu ngæåîng ngæî caính ® ¥ thç chæång trçnh chè maî hoaï åí mä hçnh báûc 0. Váún âãö phán têch vaì choün ngæåîng ngæî caính dæûa vaìo quaï trçnh thæûc nghiãûm våïi nhæîng giaï trë ngæåîng khaïc nhau âæåüc trçnh baìy trong chæång V.
A
C
D
A D
B C
0
255
0
255
0
255
............
............
Cáy báûc 0
256 Cáy ngæî caính
Hçnh 4-7 Maíng mä taí caïc cáy ngæî caính trong Mä hçnh thêch æïng báûc 1
Xeït vê duû: Giaí sæí ta maî hoaï luäöng bit vaìo laì: AADCDCADB trong mä hçnh báûc 1 vaì ngæåîng choün ngæî caính laì 200, trong âoï: A, D âaî coï trong cáy báûc 0 vaì troüng læåüng cuía hai nuït naìy laì 199 , ta coï thãø minh hoaû qua hçnh veî:
Quaï trçnh maî hoïa cho tæìng kyï hiãûu nhæ sau:
A: giaí sæí kyï hiãûu træåïc noï khäng laì ngæî caính A âæåüc maî hoaï åí báûc 0, cáûp nháût cáy báûc 0, troüng læåüng cuía A âaî âaût âãún giaï trë ngæåîng. Váûy A tråí thaình ngæî caính
A: A liãön træåïc laì ngæî caính nãn A âæåüc maî hoaï trong ngæî caính[A]
D: âæåüc maî hoaï trong ngæî caính [A]; C, D: âæåüc maî hoaï trong báûc 0 vaì D tråí thaình ngæî caính
C: maî hoaï trong ngæî caính[D], A: maî hoaï trong báûc 0 do C chæa phaíi laì ngæî caính
D: maî hoaï trong ngæî caính[A], A: âæåüc maî hoaï trong ngæî caính [D]
Ta tháúy cuîng kyï hiãûu âoüc vaìo laì A nhæng tuyì thuäüc vaìo ngæî caính maî ta maî hoaï åí mä hçnh báûc 0 hoàûc báûc 1.
Thuí tuûc maî hoaï
Trong mä hçnh maî hoaï báûc 1, ta cáön coï 257 cáy âãø maî hoaï khi âoüc vaìo mäüt kyï hiãûu ta luän xem xeït kyï hiãûu âæïng træåïc coï phaíi laì ngæî caính hay khäng. Tuìy theo âoï maì ta seî maî hoaï kyï hiãûu âoüc vaìo theo mä hçnh báûc 0 hoàûc mä hçnh báûc 1. Theo cáúu truïc dæî liãûu mä taí cáy åí mä hçnh báûc 0, ta coï cáy maî laì mäüt maíng gäöm coï 515 nuït, vaì mäüt maíng 257 pháön tæí vaì mäüt biãún âãúm säú nuït coï trong cáy maî taûi mäüt thåìi âiãøm naìo âoï. ÅÍ mä hçnh báûc 1, cáön coï 257 cáy maî, váûy váún âãö vãö bäü nhåï âæåüc giaíi quyãút nhæ thãú naìo? Coï 2 giaíi phaïp âæåüc âæa ra:
Y Giaíi phaïp 1: Nãúu khai baïo mäüt maíng ténh cho caïc ngæî caính gäöm coï 257 cáy, ta cáön dung læåüng bäü nhåï âãø thæûc hiãûn chæång trçnh laì 1,163 Mbyte vç mäùi cáy gäöm coï : 515 nuït, mäùi nuït coï pháön tæí kiãøu int, mäüt maíng gäöm 257 pháön tæí kiãøu int, mäüt biãún âãúm kiãøu int, váûy mäüt cáy täún khoaíng 4,5 Kbyte.
Y Giaíi phaïp 2: Ta duìng maíng con troí troí âãún caïc ngæî caính, khi kyï hiãûu âoï tråí thaình ngæî caính thç ta måïi cáúp phaït bäü nhåï cho ngæî caính âoï. Ngoaìi ra, våïi loaûi file vàn baín thæåìng êt khi sæí duûng táút caí caïc kyï hiãûu, do âoï viãûc cáúp phaït ngæî caính nhæ giaíi phaïp 1 seî gáy ra laîng phê vaì khäng cáön thiãút.
Y Theo giaíi phaïp 2, ta coï caïc maíng sau:
NODE *Tree ;
NODE *CONTEXT[256];
int context[256];
Tree laì con troí troí âãún cáy báûc 0. Tæång æïng våïi ngæî caính A chàóng haûn, ta seî maî hoaï trong cáy âæåüc troí âãún båíi con troí laì CONTEXT[A]; nãúu A laì ngæî caính thç context[A] coï giaï trë laì true. Bãn caûnh âoï, ta tháúy taûi mäüt thåìi âiãøm khi ta âoüc vaìo mäüt kyï hiãûu âãø maî hoïa ta luän xeït kyï hiãûu âæïng træåïc (âaî maî hoaï træåïc âoï) coï phaíi laì ngæî caính khäng nãn ta seî duìng 2 biãún laì nextchar (kyï hiãûu hiãûn taûi cáön maî hoaï hoàûc giaíi maî) laìlastchar (kyï hiãûu træåïc âoï). Ngoaìi ra, ta xáy dæûng mäüt haìm coï kiãøu traí vãö laì True hay False âãø kiãøm tra mäüt kyï hiãûu naìo âoï âaî laì ngæî caính chæa. Haìm naìy chè thæûc hiãûn mäüt cäng viãûc âån giaín laì kiãøm tra troüng læåüng cuía kyï hiãûu âaî væåüt qua mäüt giåïi haûn ngæåîng do ta âënh nghéa hay chæa, nãúu âuïng thç seî traí vãö trë true vaì ngæåüc laûi seî traí vãö false. Ta goüi haìm naìy laì int check ( int n), våïi n laì troüng læåüng cuía nuït laï cáön xeït.
Y Thuí tuûc maî hoaï nhæ sau:
Khåíi taûo cáy báûc 0 Tree;
while (âoüc vaìo mäüt kyï hiãûu laì nexchar EOF)
{if (context [lastchar])
{if (nãúu chæa cáúp phaït ngæî caính cho lastchar)
{cáúp phaït ngæî caính;
khåíi taûo cáy ngæî caính CONTEXT[lastchar];
}
maî hoaï (nextchar, CONTEXT[lastchar]);
cáûp nháût (nextchar, CONTEXT[lastchar]);
}
else
{ maî hoaï (nextchar, Tree );
cáûp nháût ngæî caính (Tree, nextchar);
lastchar = nextchar;
}
maî hoaï (END_OF_STREAM, Tree);
}
Nhæ ta âaî xeït, våïi nhæîng file vàn baín thäng thæåìng thç êt khi sæí duûng âæåüc táút caí 256 kyï hiãûu, nhæng giaí thuyãút ràòng ta sæí duûng táút caí caïc kyï hiãûu âoï vaì trong khi maî hoaï âãún mäüt luïc naìo âoï táút caí chuïng âãöu tråí thaình ngæî caính thç ta cáön cáúp phaït bäü nhåï laì 1,136Mbyte. Våïi ngän ngæî láûp trçnh C for DOS thç khäng thãø cáúp phaït âuí bäü nhåï cho chæång trçnh hoaût âäüng, nhæ váûy åí thuí tuûc maî hoaï ta âæa ra mäüt phæång aïn laì nãúu khäng cáúp phaït âæåüc bäü nhåï khi mäüt ngæî caính måïi sinh ra, thay vç baïo läùi khäng cáúp phaït âæåüc thç ta maî hoaï kyï hiãûu âoï åí mä hçnh báûc 0. Tuy nhiãn, thæûc tãú ta khàõc phuûc váún âãö vãö bäü nhåï bàòng caïch láûp trçnh trãn C for Windows
Thuí tuûc giaíi maî
Ta coï thuí tuûc giaíi maî cuîng âæåüc tiãún haình mäüt caïch tæång tæû nhæ thuí tuûc maî hoaï, nãúu kyï hiãûu âæïng træåïc (væìa âæåüc giaíi maî) laì ngæî caính thç seî giaíi maî kyï hiãûu tiãúp theo tæì luäöng bit vaìo åí cáy ngæî caính, phæång phaïp giaíi maî kyï hiãûu åí cáy ngæî caính cuîng tæång tæû nhæ cáy báûc 0, nãúu kyï hiãûu âæïng træåïc khäng phaíi laì ngæî caính thç ta seî giaíi maî kyï hiãûu tiãúp theo åí cáy báûc 0.
Thuí tuûc giaíi maî âæåüc tiãún haình nhæ sau:
Khåíi taûo cáy báûc 0 Tree;
while (giaíi maî ( netxchar, Tree) END_OF_STREAM)
{
gåíi nextchar ra file giaíi neïn;
cáûp nháût ngæî caính (Tree, nextchar);
lastchar = nextchar;
while ( context[lastchar])
{
if(chæa cáúp phaït ngæî caính lastchar)
{ cáúp phaït bäü nhåï cho ngæî caính;
khåíi taûo cáy ngæî caính CONTEXT[lastchar];
}
giaíi maî (nextchar, CONTEXT[lastchar];
gåíi nextchar ra file neïn;
cáûp nháût cáy ngæî caính CONTEXT[lastchar];
lastchar=nextchar;
}
}
CHÆÅNG 5
CAÌI ÂÀÛT - THÆÛC NGHIÃÛM
Caìi âàût chæång trçnh
Chæång trçnh âæåüc xáy dæûng trãn ngän ngæî láûp trçnh C, våïi giao diãûn âæåüc thiãút kãú trãn ngän ngæî láûp trçnh Visual Bascic. Do ngän ngæî láûp trçnh C laì mäüt ngän ngæî phäø biãún nãn ngæåìi âoüc coï thãø tiãúp cáûn chæång trçnh mäüt caïch nhoïng, bãn caûnh âoï noï coìn laì mäüt ngän ngæî coï tênh khaí chuyãøn. Dæûa vaìo âiãöu naìy, våïi chæång trçnh neïn Huffman âäüng báûc 1 viãûc giaíi quyãút vãö bäü nhåï âaî âæåüc khàõc phuûc nhæ âaî trçnh baìy åí chæång IV/ muûc II.3.2.
Chæång trçnh gäöm coï 9 module vaì 2 thæ viãûn bao gäöm:
dhuff.cpp, unduff.cpp, shuf.cpp: laì caïc chæång trçnh chênh âãø maî hoaï vaì giaíi maî våïi mä hçnh thäúng kã ténh báûc 0, mä hçnh thäúng kã âäüng báûc 0, báûc1.
bitio.h, bitio.cpp, errhand.h, errhand.cpp: bao gäöm caïc thuí tuûc âoüc vaìo vaì ghi ra file neïn hoàûc giaíi neïn, vaì thuí tuûc baïo läùi.
shuf.cpp: bao gäöm caïc thuí tuûc âãø maî hoaï vaì giaíi maî theo mä hçnh thäúng kã ténh báûc 0 nhæ: thuí tuûc maî hoaï hoàûc giaíi maî, thuí tuûc âãúm táön suáút xuáút hiãûn cuía caïc kyï hiãûu trong file cáön neïn, qui giaím xaïc suáút, xáy dæûng cáy maî, xáy dæûng baíng maî...
giainen.cpp: bao gäöm caïc thuí tuûc âãø maî hoaï vaì giaíi maî theo mä hçnh thäúng kã âäüng báûc 0 nhæ: cáûp nháût cáy maî, xáy dæûng laûi cáy maî, kiãøm tra tênh cháút sibling cuía cáy maî, thãm mäüt nuït måïi vaìo cáy maî, maî hoaï hoàûc giaíi maî kyï hiãûu...
giainen2.cpp: bao gäöm caïc thuí tuûc giaíi maî vaì maî hoaï theo mä hçnh thäúng kã âäüng báûc 1 nhæ: thuí tuûc maî hoaï, thuí tuûc giaíi maî, cáûp nháût cáy báûc 0, cáûp nháût cáy ngæî caính...
Thæûc nghiãûm
Sau khi xáy dæûng chæång trçnh, ta tiãún haình thæûc nghiãûm. Dæî liãûu neïn âæåüc täøng håüp tæì nhiãöu loaûi táûp tin khaïc nhau nhæ: caïc file vàn baín (*.DOC; *.TXT), caïc file hçnh aính (*.BMP), file ám thanh (* .WAV..), caïc file (*.CPP; *.PAS). Do âàûc âiãøm cuía phæång phaïp maî hoaï Huffman chuí yãúu duìng âãø neïn caïc loaûi file vàn baín nãn noï seî âæåüc duìng laìm dæî liãûu neïn âãø tiãún haình so saïnh tyí säú neïn våïi phæång phaïp thæång maûi khaïc trãn thë træåìng. Tuy nhiãn, nhæ âaî âãö cáûp ngay tæì chæång måí âáöu, trong phaûm vi cuía âãö taìi chè xáy dæûng phæång phaïp maî hoaï Huffman dæûa trãn mä hçnh kyï tæû trong khi caïc saín pháøm neïn thæång maûi trãn thë træåìng âæåüc xáy dæûng theo caïc phæång phaïp maî hoaï dæûa trãn mä hçnh tæì. Vç váûy, tyí säú neïn åí chæång trçnh luän luän tháúp hån.
Chæång trçnh âæåüc thæûc nghiãûm trãn maïy PC 166MHz, 16MB RAM, quaï trçnh thæûc nghiãûm chuí yãúu cho tháúy âæåüc æu âiãøm cuía phæång phaïp neïn Huffman thêch æïng våïi phæång phaïp neïn Huffman ténh, chæïng minh âæåüc tyí säú neïn cuía mäüt phæång phaïp neïn khäng dæûa vaìo viãûc maî hoaï nhæ thãú naìo maì phuû thuäüc vaìo mä hçnh hoaï...
So saïnh giæîa caïc phæång phaïp maî hoaï Huffman ténh, Huffman âäüng báûc 0, Huffman âäüng báûc 1
So saïnh tyí säú neïn
Mä hçnh
*.DOC
25,7Mbyte
*.TXT
4,7 Mbyte
*.CPP
1,7 Mbyte
*.WAV
3 Mbyte
*.BMP
901Kyte
Huffman ténh báûc 0
17,21
Mbyte
33%
2,742 Mbyte
43%
1,1525
Mbyte
33,23%
2
Mbyte
34%
21%
Huffman âäüng báûc 0
11,63 Mbyte
55%
2,724 Mbyte
43%
1,1515 Mbyte
33,3%
1,8
Mbyte
38%
21%
Huffman âäüng báûc 1
10,25 Mbyte
61%
1,953 Mbyte
59%
756649
byte
57%
1,6 Mbyte
45%
41%
Tæì baíng kãút quaí ta tháúy ràòng:
Âäúi våïi nhæîng loaûi file vàn baín (*.DOC; *.TXT), tyí säú neïn cao hån caïc loaûi file (*.CPP; *.BMP) chæïng toí phæång phaïp maî hoaï Huffman thêch håüp våïi loaûi file naìy.
Cuìng mäüt phæång phaïp maî hoaï nhæng åí báûc mä hçnh caìng cao thç tyí säú neïn caìng cao.
Âäúi våïi file coï kêch thæåïc låïn, maî hoaï Huffman âäüng coï tyí säú neïn cao hån ráút nhiãöu so våïi maî hoaï Huffman ténh.
So saïnh täúc âäü neïn vaì giaíi neïn
Täúc âäü neïn vaì giaíi neïn âæåüc tênh theo âån vë thåìi gian laì: phuït:giáy.miligiáy
Thåìi gian neïn:
Mä hçnh
*.DOC
25,7Mbyte
*.TXT
4,7 Mbyte
*.CPP
1,7 MByte
*.WAV
3 Mbyte
*.BMP
901Kbyte
Huffman ténh báûc 0
1:45.2
0:17.9
0:05.3
0:11.9
0:04.2
Huffman âäüng báûc 0
2:20.0
0:24.3
0:11.6
0:20.3
0:07.2
Huffman âäüng báûc 1
2:35.0
0:26.4
0:09.6
0:23.7
0:07.6
Thåìi gian giaíi neïn
Mä hçnh
*.DOC
25,7Mbyte
*.TXT
4,7 Mbyte
*.CPP
1,7 MByte
*.WAV
3 Mbyte
*.BMP
901Kbyte
Huffman ténh báûc 0
2:09
0:19.3
0:08
0:14.8
0:05.4
Huffman âäüng báûc 0
2:20.5
0:26
0:13
0:22.1
0:08.1
Huffman âäüng báûc 1
2:42.2
0:28.4
0:10.1
0:24.8
0:07.9
Tæì 2 baíng so saïnh thåìi gian neïn vaì giaíi neïn, ta kãút luáûn âæåüc: tyí säú neïn caìng cao thç thåìi gian neïn vaì giaíi neïn caìng cao.
Láûp baíng phán têch giaï trë choün ngæåîng ngæî caính báûc 1
Mä hçnh
Ngæåîng
Kãút quaí cáön so saïnh åí âáy laì : Tyí säú neïn vaì thåìi gian neïn
256
1000
10000
100000
DOC
25,7Mbyte
61%
2’35”
61%
2’35.6”
55%
2’37”
55%
2’52”
TXT
4,7 Mbyte
59%
0’26.4”
59%
0’26.7”
59%
0’26.9”
43%
0’30.4”
CPP
1,7 Mbyte
57%
0’09.6”
56%
0’09.5”
56%
0’09.8”
34%
0’12.3”
Tæì baíng kãút quaí, ta tháúy khi giaï trë ngæåîng âaût âãún mäüt giaï trë âuí låïn thç tyí säú neïn khäng thay âäøi, nghéa laì luïc naìy chæång trçnh neïn hoaût âäüng åí mä hçnh âäüng báûc 0. Xeït vãö màût lyï thuyãút, âäúi våïi mä hçnh báûc 0 thç giaï trë ngæåîng laì ¥, nhæng phuû thuäüc vaìo kêch thæåïc file cáön neïn maî giaï trë naìy seî khaïc nhau. Âäúi våïi ngæåîng coï giaï trë caìng nhoí, thç quaï trçnh maî hoaï caìng chuyãøn nhanh sang mä hçnh báûc 1 theo thuáût toaïn âaî âæåüc xeït âãún trong chæång 4 vaì tyí säú neïn caìng cao. Tuy nhiãn, buì laûi quaï trçnh cáúp phaït cáy ngæî caính caìng nhiãöu, chæång trçnh cuîng cáön læåüng bäü nhåï låïn hån vaì dáùn âãún thåìi gian neïn caìng cao. Qua quaï trçnh thæûc nghiãûm, âäúi våïi nhæîng giaï trë ngæåîng tæång âäúi nhoí (<1000) file kãút quaí coï kêch thæåïc giaím khäng âaïng kãø nãn tyí säú neïn háöu nhæ khäng thay âäøi. Nhæ váûy, giaï trë ngæåîng âæåüc choün khäng quaï låïn vaì cuîng khäng quaï nhoí væìa âaím baío chæång trçnh neïn åí báûc1 luän xaíy ra âãø cho tyí säú neïn cao, vaì thåìi gian neïn caìng tháúp. Vç váûy, khi xáy dæûng chæång trçnh ta choün giaï trë ngæåîng laì 256.
So saïnh phæång phaïp maî hoaï Huffman âäüng våïi caïc phæång phaïp neïn thæång maûi khaïc nhæ (NC,Winzip..)
Ta tiãún haình so saïnh hiãûu suáút neïn giæîa mä hçnh kyï tæû báûc 1 vaì caïc trçnh neïn thæång maûi khaïc nhæ NC,Winzip... ÅÍ âáy, viãûc tiãún haình thæí nghiãûm âæåüc thæûc hiãûn trãn cuìng mäüt maïy PC, thåìi gian âo âæåüc chè mang tênh cháút tæång âäúi. Mäüt váún âãö luän luän âæåüc âãö cáûp trong caïc pháön træåïc laì vç âáy laì Mä hçnh kyï tæû nãn tyí säú neïn seî tháúp hån nhæîng trçnh neïn thæång maûi naìy. Chuïng ta chè coï thãø kãút luáûn ràòng kyî thuáût maî hoaï naìy täút hån kyî thuáût naìo âoï khi viãûc maî hoaï åí caí hai kyî thuáût naìy cuìng maî hoaï dæûa trãn mäüt mä hçnh . Bãn caûnh âoï, sæû chãnh lãûch naìy chè tæång âäúi vç khäng chàõc chàõn ràòng caïc chæång trçnh thæång maûi cuîng âæåüc xáy dæûng trãn ngän ngæî láûp trçnh C. Ngoaìi ra, våïi caïc kyî nàng láûp trçnh täút, thåìi gian âoüc vaì ghi lãn âéa åí nhæîng chæång trçnh thæång maûi seî nhanh hån nãn giaím âæåüc thåìi gian neïn vaì giaíi neïn.
Ta tiãún haình so saïnh våïi dæî liãûu laì file vàn baín (*.TXT) bàòng caïch láûp biãøu âäö trong tæìng træåìng håüp nhæ sau:
MB
Tyí lãû %
MB
giáy
MB
giáy
Tyí säú neïn:
Thåìi gian neïn
Thåìi gian giaíi neïn
Y Nháûn xeït:
Nhæ váûy, våïi mä hçnh kyï tæû thç hiãûu suáút neïn luän tháúp hån so våïi mä hçnh tæì. Quaï trçnh thæûc nghiãûm cho tháúy cå såí lyï thuyãút naìy luän luän âuïng.
CHÆÅNG 6
KÃÚT LUÁÛN
Trong quaï trçnh tçm hiãøu baìi toaïn neïn säú liãûu theo phæång phaïp maî hoaï Huffman våïi mä hçnh thäúng kã, cå baín âäö aïn âaî tçm hiãøu âæåüc kyî thuáût neïn täøng quaït noïi chung vaì neïn Huffman noïi riãng. Våïi viãûc tçm hiãøu caïc thuáût toaïn theo mä hçnh thäúng kã ténh vaì âäüng báûc 0, tæì cå såí âoï caíi tiãún, náng cáúp lãn mä hçnh thäúng kã âäüng báûc 1 âaî cho tháúy âæåüc hiãûu suáút neïn cuía mäüt phæång phaïp neïn phuû thuäüc nhæ thãú naìo vaìo mä hçnh hoaï. Âäö aïn cuîng âaî so saïnh âæåüc nhæîng æu âiãøm væåüt träüi cuía maî Huffman so våïi caïc maî khaïc nhæ maî Shannon-Fano, giæîa phæång phaïp maî hoaï Huffman ténh vaì âäüng...
Tuy nhiãn, báút kyì mäüt phæång phaïp neïn säú liãûu naìo cuîng täön taûi caïc æu, nhæåüc âiãøm cuía noï vaì coìn tuyì thuäüc vaìo kiãøu táûp tin cáön neïn, muûc âêch cuía viãûc neïn. Quaï trçnh thæûc nghiãûm âaî cho tháúy, maî hoaï Huffman coï hiãûu suáút neïn cao âäúi våïi caïc loaûi dæî liãûu vàn baín. Tuy nhiãn, phæång phaïp naìy chè thêch håüp caïc file coï kêch thæåïc låïn âãø buì laûi thåìi gian xáy dæûng vaì cáûp nháût cáy maî. Âäúi våïi maî Huffman ténh âoìi hoíi ta phaíi xáy dæûng mäüt cáy maî Huffman træåïc nãn cáön mäüt khoaíng thåìi gian khäng êt do ta khäng biãút træåïc âæåüc kiãøu dæî liãûu seî âæåüc thæûc hiãûn neïn. Ngoaìi ra, quaï trçnh giaíi maî phæïc taûp do khäng biãút âæåüc âäü daìi tæì maî cuía caïc kyï hiãûu khi chæa âi âãún mäüt nuït laï trong cáy maî.
Trong mäi træåìng buìng näø thäng tin nhæ hiãûn nay, caïc cå såí dæî liãûu låïn våïi caïc loaûi vàn baín khäng cáúu truïc laì mäüt thaïch thæïc âäúi våïi caïc hãû thäúng thäng tin. Do âoï, viãûc sæí duûng caïc giaíi phaïp neïn laì ráút cáön thiãút. ÅÍ âáy, âäö aïn chè âi sáu vaìo kyî thuáût neïn theo phæång phaïp maî hoaï Huffman våïi mä hçnh kyï tæû nãn hiãûu suáút neïn tháúp hån so våïi caïc phæång phaïp neïn thæång maûi khaïc trãn thë træåìng âæåüc xáy dæûng trãn mä hçnh tæì. Do âoï, hæåïng phaït triãøn cuía âäö aïn laì nghiãn cæïu neïn Huffman våïi mä hçnh thêch æïng báûc cao vaì mä hçnh tæì báûc cao nhàòm khai thaïc mäüt caïch coï hiãûu quaí caïc âàûc træng cuía ngän ngæî Tiãúng Viãût, âaïp æïng âæåüc nhu cáöu trao âäøi thäng tin ngaìy caìng âa daûng åí næåïc ta. Chæång trçnh cuîng âæåüc phaït triãøn âãø coï thãø chañy trãn caïc hãû âiãöu haình khaïc nhau nhæ Windows NT, OS2, UNIX..., coï thãø neïn nhiãöu thæ muûc cuìng mäüt luïc vaì giao diãûn ngæåìi duìng seî âæåüc caíi tiãún thán thiãûn hån. Ngoaìi ra, coï thãø caíi tiãún chæång trçnh âãø bäü nhåï laìm viãûc âæåüc sæí duûng coï hiãûu quaí, náng cao âæåc täúc âäü neïn vaì giaíi neïn.
Tuy nhiãn, do kinh nghiãûm láûp trçnh coìn haûn chãú, viãûc tiãúp cáûn caïc cäng nghãû neïn trong mäüt thåìi gian ngàõn nãn khäng traïnh khoíi nhæîng sai soït nháút âënh, viãûc tçm hiãøu chæa tháût sæû sáu sàõc táút caí caïc khêa caûnh. Âãö taìi cáön coï nhæîng caíi tiãún måïi âãø coï thãø náng cao âæåüc hiãûu suáút neïn, täúc âäü neïn vaì giaíi neïn. Ráút mong coï sæû goïp yï cuía caïc tháöy cä, anh chë vaì baûn âoüc âãø täi coï thãø hoaìn chènh âãö taìi mäüt caïch täút hån.
TAÌI LIÃÛU THAM KHAÍO
[1]. WITTEN, I., MOFFAT, A. AND BELL, T. Managing Gigabytes: Compressing and Indexing Documents and Images ( Second ed.); Van Nostrand Reinhold, New York, 1998.
[2]. MARK NELSON., JEAN-LOUP GAILLY. The Data Compression Book (Second ed), M & T., 1991.
[3] Buìi Minh Tiãu. Cå såí lyï thuyãút truyãön tin. Nhaì xuáút baín Âaûi Hoüc vaì Trung Hoüc Chuyãn Nghiãûp Haì Näüi -1987.
[4] 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
[4] NGUYÃÙN TRUNG TRÆÛC., Cáúu truïc dæî liãûu. Khoa tin hoüc, Âaûi hoüc baïch khoa TP.HCM, 1 996.
[5] Cáøm nang Truyãön Thäng Thoaûi vaì Säú Liãûu. Nhaì Xuáút Baín Bæu Âiãûn Haì Näüi-1999
[6]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.1991
[7] GSTS. Hoaìng Kiãúm. Giaïo trçnh Nháûp Män Âäö Hoüa vaì Xæí Lyï Aính. Khoa Tin Hoüc-Âaûi Hoüc Måí-Baïn Cäng TP.Häö Chê Minh-1995
[8] Alistair Moffat,Timothy C.Bell vaì Ian H.Witten, "Lossless Compression for Text and Images", 1997.
PHUÛ LUÛC CAÏC LÆU ÂÄÖ THUÁÛT TOAÏN
NEÏN HUFFMAN THÊCH ÆÏNG BÁÛC 0
Khåíi âäüng cáy maî räùng âáöu tiãn
CÁÛP NHÁÛT CÁY MAÎ
Coï phaíi laì kyï hiãûu kãút thuïc luäöng END_OF_STREAM ?
KT
Â
S
Maî hoaï kyï hiãûu âoï theo cáy maî hiãûn thåìi vaì xuáút tæì maî ra file neïn âaî måí
1
Bàõt âáöu
Âoüc mäüt kyï hiãûu File cáön neïn âaî måí
MÅÍ FILE(S) CÁÖN NEÏN
MÅÍ FILE NEÏN
NEÏN FILE
ÂOÏNG FILE NEÏN
KT
Âoüc caïc tham säú tæì hãû thäúng baíng choün âãø xaïc âënh Tãn file cáön neïn vaì Tãn file neïn
Bàõt âáöu
Thäng baïo tyí säú neïn ra maìn hçnh
LÆU ÂÄÖ CHÆÅNG TRÇNH CHÊNH
PHÆÅNG THÆÏC NEÏN FILE
BÂ
Maî hoaï kyï hiãûu theo vë trê hiãûn thåìi cuía noï trong cáy maî
Maî hoaï kyï hiãûu Escape theo vë trê hiãûn thåìi cuía noï trong cáy maî
Xuáút tæì maî cuía kyï hiãûu ra file neïn âaî måí
Xuáút tæì maî cuía Escape vaì maî ASCII 8 bit cuía kyï hiãûu
Thãm mäüt nuït måïi tæång æïng våïi kyï hiãûu naìy vaìo cáyhiãûu maî
KT
Kyï hiãûu âaî coï màût trong cáy maî chæa ?
PHÆÅNG THÆÏC MAÎ HOAÏ KYÏ HIÃÛU VAÌ XUÁÚT TÆÌ MAÎ RA FILE NEÏN (*)
Traïo âäøi hai nuït trong cáy
XÁY DÆÛNG LAÛI CÁY MAÎ
BÂ
S
Â
Â
S
Â
S
2
3
Bäü âãúm troüng læåüng cuía nuït gäúc âaî âaût giaï trë ngæåîng ?
Âaî væåüt quaï nuït gäúc chæa ?
Nuït cáön tàng troüng læåüng laì nuït æïng våïi kyï hiãûu væìa âæåüc maî hoaï hoàûc giaíi maî
Tàng troüng læåüng cuía nuït hiãûn thåìi lãn 1
Coï vi phaûm tênh cháút Sibling ?
Nuït cán tàòng troüng læåüng laì nuït cha cuía nuït hiãûn thåìi
KT
PHÆÅNG THÆÏC CÁÛP NHÁÛT CÁY MAÎ (1)
BÂ
KT
Â
S
S
Nuït i coï phaíi laì nuït laï ?
Hai nuït con cuía i nháûn j laìm nuït cha
Nuït j tråí thaình mäüt nuït laï
Nuït j coï phaíi laì nuït laï ?
Nuït i tråí thaình mäüt nuït laï
Hai nuït con cuía j nháûn i laìm nuït cha
Traïo âäøi troüng læåüng giæîa i vaì j
+ i nháûn cha cuía j laìm cha
+ j nháûn cha cuía i laìm cha
Â
BÂ
KT
Nuït 0 laì nuït gäúc, troüng læåüng bàòng 2,Khäng coï nuït cha.Nuït con thæï nháút laì nuït 1
Nuït 1 laì nuït laï tæång æïng våïi kyï hiãûu kãút thuïc luäöng END_OF_STREAM, troüng læåüng bàòng 2,Nuït gäúc laì nuït cha
Nuït 2 laì nuït laï tæång æïng våïi kyï hiãûu Escape = 257, Troüng læåüng bàòng 2,
Nuït gäúc laì nuït cha
Caïc nuït coìn laûi trong maíng tæì nuït 3 chæa sæí duûng 255 thaình pháön âáöu tiãn cuía maíng LEAF âãöu gaïn giaï trë -1
PHÆÅNG THÆÏC KHÅÍI ÂÄÜNG CÁY MAÎ RÄÙNG
PHÆÅNG THÆÏC TRAÏO ÂÄØI HAI NUÏT I VAÌ J TRONG CÁY MAÎ (3)
BÂ
A
S
Â
S
Â
j láúy giaï trë nuït cuäúi danh saïch caïc nuït trong cáy maî hiãûn thåìi
i < ------- j
Nuït i coï phaíi laì nuït laï ?
Chuyãøn nuït i vãö cuäúi danh saïch
Qui giaím troüng læåüng cuía nuït i
Giaím j âi 1
Giaím i âi 1
i < 0 ?
PHÆÅNG THÆÏC XÁY DÆÛNG LAÛI CÁY MAÎ
( Bæåïc 1: Däön táút caí caïc nuït laï vãö cuäúi danh saïch vaì qui giaím troüng læåüng )
A
B
S
Â
i láúy giaï trë cuía nuït cuäúi danh saïch
k < ------ i + 1
j >= 0 ?
Troüng læåüng cuía j < ------ Troüng læåüng cuía i + Troüng læåüng cuía k
j laì mäüt nuït laï trong cáy maî
Giaím j âi 1
Cheìn nuït j vaìo vë trê thêch håüp trong maíng
(Bæåïc 2: Xáy dæûng caïc nuït nhaïnh dæûa vaìo tênh Sibling )
B
KT
S
Â
i láúy giaï trë cuía nuït cuäúi danh saïch k láúy giaï trë cuía thaình pháön CHILD cuía nuït i
Nuït i coï phaíi laì nuït laï ?
Nuït cha cuía nuït k laì nuït i
Nuït cha cuía nuït k + 1 laì nuït i
LEAF[k] <-- i
BÂ
MÅÍ FILE(S) GIAÍI NEÏN
MÅÍ FILE(S) CÁÖN GIAÍI NEÏN
GIAÍI NEÏN FILE(S)
ÂOÏNG FILE(S) CÁÖN GIAÍI NEÏN
KT
ÂOÏNG FILE(S) GIAÍI NEÏN
Âoüc caïc tham säú tæì hãû thäúng baíng choün âãø xaïc âënh Tãn file cáön giaíi neïn.
Thäng baïo kãút thuïc cäng viãûc ra maìn hçnh
CHÆÅNG TRÇNH CHÊNH GIAÍI NEÏN HUFFMAN THÊCH ÆÏNG
( Bæåïc 3: Xaïc âënh nuït cha cho caïc nuït )
BÂ
Âæïng åí nuït gäúc âoüc láön læåüt tæìng bit maî tæì file vaìo, reî theo caïc nhaïnh tæång æïng cho âãún khi âãún âæåüc mäüt nuït laï. Xaïc âënh kyï hiãûu tæång æïng våïi nuït laï âoï
Kyï hiãûu xaïc âënh âæåüc phaíi laì kyï hiãûu Escape ?
Âoüc thãm 8 bit maî næîa. Âáy laì maî ASCII cuía kyï hiãûu cáön xaïc âënh âãø xuaït ra file giaíi neïn
Kyï hiãûu âoï laì kyï hiãûu cáön xaïc âënh âãø xuáút ra file giaíi neïn
KT
Thãm mäüt nuït måïi tæång æïng våïi kyï hiãûu naìy vaìo cáy maî
PHÆÅNG THÆÏC GIAÍI MAÎ
BÂ
Khåíi âäüng cáy maî räùng âáöu tiãn
GIAÍI MAÎ
CÁÛP NHÁÛT CÁY MAÎ
KT
S
Â
+
Coï phaíi laì kyï hiãûu kãút thuïc luäöng END_OF_STREAM ?
Xuáút kyï hiãûu âoï ra file âæåüc giaíi neïn âaî måí
PHÆÅNG THÆÏC GIAÍI NEÏN FILE
LÆU ÂÄÖ NEÏN HUFFMAN THÊCH ÆÏNG BÁÛC 1
PHÆÅNG THÆÏC NEÏN FILE
Khåíi âäüng cáy maî räùng âáöu tiãn
CÁÛP NHÁÛT CÁY MAÎ BÁÛC 0
Coï phaíi laì kyï hiãûu kãút thuïc luäöng END_OF_STREAM ?
KT
Â
S
Maî hoaï kyï hiãûu âoï theo cáy maî hiãûn thåìi vaì xuáút tæì maî ra file neïn âaî måí
1
Bàõt âáöu
Âoüc mäüt kyï hiãûu nextchar tæì File cáön neïn
Kyï hiãûu âoú coï phaíi laì ngæî caính ?
CÁÛP NHÁÛT CÁY NGÆÎ CAÍNH[nextchar]
Maî hoaï kyï hiãûu âoï theo cáy ngæî caính [nextchar] vaì xuáút tæì maî ra file neïn âaî måí
Â
S
lastchar=nextchar
PHÆÅNG THÆÏC CÁÛP NHÁÛT CÁY MAÎ BÁÛC 0
XÁY DÆÛNG LAÛI CÁY MAÎ
BÂ
S
Â
2
Bäü âãúm troüng læåüng cuía nuït gäúc âaî âaût giaï trë ngæåîng ?
Nuït cáön tàng troüng læåüng laì nuït æïng våïi kyï hiãûu væìa âæåüc maî hoaï hoàûc giaíi maî
Traïo âäøi hai nuït trong cáy báûc 0
Â
S
Â
S
3
Âaî væåüt quaï nuït gäúc chæa ?
Tàng troüng læåüng cuía nuït hiãûn thåìi lãn 1
Coï vi phaûm tênh cháút Sibling ?
Nuït cán tàòng troüng læåüng laì nuït cha cuía nuït hiãûn thåìi
KT
troüng læåüng cuía nuït âaî âaût âãún giaï trë ngæåîng
Â
S
Nuït âoï laì ngæî caính
PHÆÅNG THÆÏC GIAÍI NEÏN HUFMAN THÊCH ÆÏNG BÁÛC 1
BÂ
Khåíi âäüng cáy maî räùng âáöu tiãn
GIAÍI MAÎ nextchar åí CÁY BÁÛC 0
KT
Â
+
Coï phaíi laì kyï hiãûu kãút thuïc luäöng END_OF_STREAM ?
CÁÛP NHÁÛT CÁY NGÆÎ CAÍNH
S
Xuáút kyï hiãûu âoï ra file âæåüc giaíi neïn âaî måí
lastchar coï phaíi laì ngæî caính khäng
CÁÛP NHÁÛT CÁY BÁÛC 0
S
Xuáút kyï hiãûu âoï ra file âæåüc giaíi neïn âaî måí
lastchar=nextchar
GIAÍI MAÎ nextchar åí CÁY BÁÛC NGÆÎ CAÍNH lastchar
lastchar=nextchar
Â
Các file đính kèm theo tài liệu này:
DUNGLV.DOC
DUNG.rar- DUNGLV1.DOC
