Luận văn Kỹ thuật nén số liệu mã hóa Số học

tree con troí cuía cáy ngáöm âënh. increment biãún tàng duìng trong thuáût toaïn cuía cáy ngáöm âënh. most_freq_symbol laì kê hiãûu coï táön säú låïn nháút. most_freq_count laì biãún âãúm caïc kê hiãûu coï táön säú låïn nháút. most_freq_pos laì vë trê cuía caïc biãún coï táún säú låïn nháút. Trong âoï kiãøu freq_value âæåüc âënh nghéa laì sæû chênh xaïc cuía caïc bit læu giæî táún säú cuía caïc kê hiãûu. Noï âæåüc âënh nghéa nhæ sau: Typedef insigned long freq_value Mä hçnh tæì Våïi mä hênh tæì ta xem âáöu vaìo dæåïi daûng caïc tæì vaì khäng tæì xen keî láùn nhau. Do âoï caïc tæì vaì khäng tråí tæì tråí thaình caïc kê hiãûu âæåüc neïn do váûy chuïng ta coï nhiãöu caïch âãø neïn chuïng. Nhçn chung hiãûu quaí nháút laì mä hçnh báûc khäng cho caïc tæì vaì mä hçnh báûc khaïc khäng cho caïc khäng tæì. ÅÍ âáy noï cho ràòng näüi dung caïc vàn baín laì sæû xen keí giæîa caïc tæì vaì khäng tæì. Do âoï phaíi coï hai mä hçnh khaïc nhau âæåüc duìng luán phiãn åí âáy cho mäùi loaûi kê hiãûu. Thäng thæåìng thç kê hiãûu thoaït âæåüc maî hoaï træåïc vaì tiãúp theo caïc tæì måïi xuáút hiãûn, vaì caïc tæì naìy âæåüc cáúu taûo båíi caïc kê tæû liãn tiãúp nhau. Âäúi våïi caïc kê tæû ta coï thãø duìng mä hçnh âån giaín hån vê duû nhæ mä hçnh kê tæû báûc khäng. Caïc mä hçnh neïn tæì âàûc biãût thêch håüp cho caïc loaûi vàn baín låïn, båíi vç caïc tæì thæåìng âæåüc læu træî våïi muûc âêch âãø laìm chè muûc, do âoï caïc chè muûc naìy coï thãø âæåüc duìng nhæ mäüt pháön cuía mä hçnh neïn. Laìm thãú naìo âãø chia mäüt vàn baín thaình caïc tæì vaì khäng tæì xen keî nhau? Mäüt så âäö âàûc biãût âoï laì coi sæû cháúm cáu nhæ laì mäüt pháön cuía tæì. Caïch chia naìy khäng mang laûi hiãûu quaí neïn, nhæng noï mang laûi kãút quaí laì danh saïch caïc tæì tiãûn låüi cho muûc âêch láûp chè muûc. Mäüt váún âãö khaïc cáön chuï yï åí âáy laì viãûc xæí lyï caïc con säú. Nãúu caïc chæî säú âæåüc xem nhæ caïc kê tæû thç mäüt haìng liãn tiãúp caïc chæî säú seî âæåüc xem nhæ laì mäüt tæì. Sæû phán phäúi táön säú cuía caïc säú khaïc xa våïi sæû phán phäúi táún säú cuía caïc tæì do âoï nãúu ta sæí duûng caïch xæí lyï cuía caïc tæì âãø xæí lyï caïc säú thç noï khäng mang laûi hiãûu quaí neïn cao. Do âoï ta seî chia caïc säú daìi hån thaình caïc säú ngàõn bàòng caïch ta giåïi haûn âäü daìi täúi âa caïc chæî säú trong mäüt säú. Nãúu säú naìo daìi quaï thç ta seî taïch säú âoï thaình hai pháön. Thuáût toaïn duìng cho mä hçnh tæì báûc khäng âæåüc mä taí nhæ åí hçnh dæåïi. Duìng haìm get_word() âãø âoüc vaìo danh saïch caí caïc tæì. Räöi neïn danh saïch tæång æïng âoï, våïi cáúu taûo cuía caïc tæì laì daîy liãn tiãúp caïc kê tæû taûi láön xuáút hiãûn âáöu tiãn räöi thiãút láûp mäüt tæì maî âãø duìng cho caïc láön xuáút hiãûn sau âoï. ÅÍí âáy sæí duûng ba cáúu truïc dæî liãûu laì caïc ngæî caính gäöm: C, W vaì L. Trong âoï: C: laì táûp håüp caïc kê tæû coï giaï trë trong thaình pháön cuía caïc tæì. W: táûp håüp caïc tæì coï giaï trë. L: laì táûp håüp caïc âäü daìi cuía caïc tæì xaïc âënh. Cáúu truïc D laì tæì âiãøn âãø chuyãøn âäøi mäüt tæì trong säú caïc tæì tæång æïng våïi säú caïc tæì âaî gaïn trong láön xuáút hiãûn âáúu tiãn åí trong danh saïch âáöu vaìo. Encode-file() { Âàût W = creat_context() Install_symbol(W, end_of_message) Âàût D = make_empty_dictionary() Âàût C = creat_context() Trong khi kê tæû c coìn håüp lãû laìm Install_symbol(C, c) Âàût L = creat_context() Trong khi âäü daìi l coìn håüp lãû laìm Install_symbol(L, l) start-encode() Trong khi coìn caïc tæì laìm Âàût word = read_one_word() Âàût w = lookup_word_number(D, word) Nãúu (encode(W, w) = escape_transmitted) thç Encode(L, length(word)) Våïi mäùi kê tæû c trong tæì laìm Encode(C, c) Insert_into_dictionary(D, word) Install_symbol(W, w) encode(W, end_of_message) finish_encode() } Hçnh 9: Thuáût toaïn maî hoïa file duìng mä hçnh tæì báûckhäng ÅÍ âáy haìm cread_context() duìng âãø khåíi taûo caïc giaï trë cuía caïc haình pháön mäüt ngæî caính thäng thæåìng noï âæåüc khåíi taûo nhæ sau: Context *create_context(int length, int type) { context *pContext; int size = 1; . . . pContext->initial_size = size; pContext->length = 1; pContext->total = 0; pContext->nSymbols = 1; pContext->type = type; pContext->max_length = size; pContext->most_freq_symbol = -1; pContext->most_freq_count = 0; pContext->most_freq_pos = 0; } Haìm install_symbol() duìng âãø caìi âàût mäüt kê tæû vaìo trong mäüt ngæî caính. Tæïc laì noï gaïn caïc giaï trë cuía kê tæû cho caïc thaình pháön cuía biãún ngæî caính coï liãn quan. Mä hçnh kê tæû . Våïi mä hçnh kê tæû thç noï dãù thæûc hiãûn nhæng hiãûu quaí neïn khäng cao. Chæång trçnh âoüc vaìo láön læåüt caïc kê tæû räöi ãún haình maî hoaï chuîng dæûa vaìo xaïc suáút xuáút hiãûn cuía chuïng. ÅÍ âáy chæång trçnh xeït caïc kê tæû trong baíng maî ASCII måí räüng, mäùi maî ASCII måí räüng coï 8 bit. Thuáût toaïn cuía duìng cho mä hçnh kê tæû báûc khäng âæåüc mä taí åí caïc hçnh dæåïi âáy: Encode_file( ) { Âàût C = creat_context( ) Install_symbol(C, end_of_message) 2 – Trong khi c != end_of_message laìm install_symbol(C, c) 3- start_encode() 4- Trong khi c != end_of_message laìm Âàût c = read_one_character() Encode(C, c) 5- encode(C, end_of_message) 6- finish_encode() } Hçnh 10: Thuáût toaïn maî hoïa file duìng mä hçnh kê tæû báûc khäng Trong caí hai træåìng håüp maî hoaï vaì giaíi maî, ngæî caính C âæåüc khåíi taûo âãø chæïa âæûng caïc kê tæû coï giaï trë cäüng thãm kê hiãûu måí räüng laì end_of_message. decode_file( ) { 1- Âàût C = creat_context( ) Install_symbol(C, end_of_message) 2 - Trong khi c != end_of_message laìm install_symbol(C, c) 3- start_encode() 4- Làûp Âàût c = decode(C) Nãúu c = end_of_message thç break Khaïc write_one_character(c) 5- finish_encode( ) } Hçnh 11: Thuáût toaïn maî hoïa file duìng mä hçnh kê tæû báûc khäng Mä hçnh báûc cao Pháön trãn sæí duûng caïc mä hçnh báûc khäng âãø neïn dæî liãûu. Nãúu chuïng ta chuyãøn âãún báûc cao hån thç seî âaût âæåüc hiãûu quaí neïn täút hån. Khi sæí duûng mä hçnh báûc cao thç noï âoìi hoíi nhiãöu ngæî caính hån do âoï thåìi gian láu hån. Våïi mä hçnh báûc mäüt cáön täúi âa laì 256 ngæî caính, mä hçnh báûc hai cáön täúi âa 256*256 (65536) ngæî caính vaì mä hçnh báûc ba cáön coï täúi âa khoaíng mæåìi saïu triãûu (256*256*256) baíng ngæî caính âãø laìm viãûc. Chuïng ta seî phaíi âoüc vaìo mäüt læåüng vàn baín låïn træåïc khi caïc ngæî caính naìy thäúng kã âuí âãø bàõt âáöu neïn dæî liãûu, vaì ráút nhiãöu baín cuía caïc ngæî caính naìy seî khäng bao giåì âæåüc sæí duûng hãút gáy laîng phê bäü nhåï cuía maïy tênh. Vê duû mäüt khi neïn vàn baín tiãúng Anh chæång trçnh khäng cáön phaíi cáúp khäng gian cho baíng QQW båíi vç noï seî khäng bao giåì xuáút hiãûn. Âãø giaíi quyãút váún âãö naìy ta thiãút láûp xaïc suáút khåíi taûo cuía táút caí caïc kyï hiãûu âãún khäng cho ngæî caính âæa ra vaì quay vãö ngæî caính khaïc khi khäng nhçn tháúy kyï hiãûu xuáút hiãûn phêa træåïc. Laìm thãú naìo chuïng ta sæí duûng ngæî caính quay vãö sau khi phaït âi mäüt maî thoaït ? ÅÍ âáy chuïng ta traí vãö mäüt ngæî caính ngáöm âënh goüi laì ngæî caính thoaït. Ngæî caính thoaït khäng bao giåì âæåüc cáûp nháût, âiãöu naìy coï nghéa ràòng sæí duûng noï thäng thæåìng seî khäng cung cáúp báút kyì sæû neïn naìo. Trong mä hçnh báûc cao nháút, coï mäüt caïch täút hån chè quay tråí vãö ngæî caính ngáöm âënh mäüt caïch tæû âäüng. Nãúu mäüt ngæî caính âang täön taûi khäng thãø maî hoïa kyï hiãûu, quay vãö ngæî caính báûc nhoí hån tiãúp theo. Vê duû nãúu ngæî caính âang täön taûi laì REQ, vaì U cáön âæåüc maî hoïa cho láön âáöu, mäüt maî thoaït seî âæåüc sinh ra. Tiãúp theo, chuïng ta haû xuäúng mä hçnh báûc hai âãø cäú gàõng maî hoïa kyï tæû U sæí duûng ngæî caính EQ. Noï tiãúp tuûc giaím xuäúng cho âãún ngæî caính báûc 0, nãúu maî thoaït váùn âæåüc sinh ra åí báûc 0 chuïng ta quay vãö mäüt ngæî caính âàûc biãût báûc -1 maì ngæî caính khäng bao giåì âæåüc cáûp nháût vaì thiãút láûp cho sæû khåíi taûo âãø coï mäüt bäü âãúm cho moüi kyï tæû coï thãø. Vç váûy noï âæåüc baío âaím âãø maî hoïa moüi kyï hiãûu. ÅÍ trãn ta coï noïi âãún maî thoaït, váûy maî thoaït laì gç? Maî thoaït laì mäüt kyï hiãûu âàût biãût (giäúng nhæ END_OF_MESSAGE) maî naìy chè ra cho chæång trçnh biãút cáön thoaït khoíi ngæî caính hiãûn thåìi. Khi mäüt ngæî caính phaït ra mäüt kyï hiãûu thoaït, noï thæåìng quay vãö ngæî caính báûc tháúp hån, noï coï thãø quay vãö ngæî caính thoaït, mäüt ngæî caính maì khäng bao giåì âæåüc cáûp nháût. Ngæî caính naìy chæïa 257 kyï hiãûu, mäùi kyï hiãûu naìy coï säú âãúm bàòng mäüt. Viãûc naìy baío âaím báút kyì kyï tæû naìo bàõt gàûp trong thäng âiãûp âãöu coï thãø âæåüc maî hoïa båíi viãûc xuáút ra mäüt maî thoaït ngæî caính hiãûn thåìi vaì bàòng caïch maî hoaï kyï hiãûu sæí duûng ngæî caính thoaït. Vê duû cáön maî hoïa cho kyï hiãûu u laì mäüt kyï hiãûu måïi. Nhæ âaî giåïi thiãûu khi sæí duûng maî thoaït noï taûo mäüt sæû khaïc nhau låïn. Vê duû âãø maî hoaï kyï hiãûu u âáöu tiãn láúy 8 bit âãø maî hoïa. Maî thoaït khäng láúy bit naìo âãø maî hoïa vaì trong ngæî caính thoaït u coï xaïc suáút 1/257. Sau âoï u âæåüc thãm vaìo baíng vaì cho säú âãúm bàòng mäüt. Láön xuáút hiãûn tiãúp theo cuía u seî yãu cáöu chè mäüt bit âãø maî hoïa, khi âoï noï coï xaïc suáút 1/2. Khi u âaî xuáút hiãûn 16 láön, trong khi mä hçnh træåïc váùn láúy 4 bit âãø maî hoïa noï, mä hçnh âiãöu khiãøn thoaït seî láúy 0.06 bit. Maî thoaït giaíi phoïng chæång trçnh khoíi gaïnh nàûng caïc mä hçnh cuía caïc kyï tæû maì caïc kyï tæû naìy khäng bao giåì xuáút hiãûn. Âiãöu naìy cho pheïp mä hçnh âiãöu chènh täúc âäü âãø thay âäøi xaïc suáút vaì nhanh choïng giaím säú bit cáön âãø maî hoïa caïc kyï hiãûu coï xaïc suáút cao. Bäü maî hoïa xæí lyï cho sæû caìi âàût riãng naìy cuía mäüt mä hçnh nhiãöu báûc yãu cáöu chè mäüt vaìi thay âäøi cuía chæång trçnh træåïc. Noï phaíi kiãøm tra mäüt kyï hiãûu biãøu diãùn trong ngæî caính âæa ra. Nãúu khäng, maî thoaït âæåüc maî hoïa thay thãú.  CHÆÅNG V chæång trçnh vaì thæûc nghiãûm caìi âàût Chæång trçnh Chæång trçnh thæûc hiãûn trãn ngän ngæî C vaì chaûy trãn hãû âiãöu haình Linux. Do âoï noï khäng âæåüc âeûp vãö màût hçnh thæïc. Maî hoïa Khi maî hoïa duìng caïc thao taïc di chuyãøn /cäüng caïc säú nguyãn âãø tênh toaïn, våïi âäü chênh xaïc tháúp âaî âæåüc cháúp nháûn, trong mäüt vaìi cáúu truïc noï thæûc thi nhanh hån. Mäüt âàûc âiãøm näøi báût cuía maî hoïa laì duìng sæû chênh xaïc roî raìng khi thæûc hiãûn. Täøng táön säú coï thãø lãn âãún 30 bit (giaí sæí ràòng säú nguyãn laì 32 bit, hoàûc hån næîa laì n - 2 cho n bit caïc säú nguyãn). Täøng táön säú coï thãø coï lãn âãún giaï trë ráút låïn laì 1.073.741.824 træåïc khi caïc táön säú cáön phaíi âæåüc chia âãöu. Giaï trë ngáöm âënh cuía säú bit duìng cho viãûc âãúm táön säú laì 27. Mä hçnh Mä hçnh tæì thæûc hiãûn viãûc âoüc vaìo daîy liãn tiãúp caïc tæì vaì khäng tæì xen keî nhau. Sau khi âoüc vaìo daîy caïc tæì vaì khäng tæì noï âæa vaìo baíng läün xäün vaì sàõp xãúp laûi chuïng âãø tçm säú thæï tæû tæång æïng cuía säú læåüng caïc tæì âãø gæíi âi cuìng våïi ngæî caính tæång âæång cuía tæì vaì khäng tæì. Mäüt ngæî caính cáút giæî táún säú tæång æïng våïi thæï tæû cuía caïc kê hiãûu. Âáy laì mä hçnh minh hoüa caïc æu âiãøm cuía caïch thæûc hiãûn maî hoïa måïi khi duìng baíng alphabet låïn vaì sæû thao taïc cuía mmoüt ngæî caính trong mäüt chæång trçnh riãng leî. Mäüt mä hçnh kê tæû báûc khäng thêch æïng laì caïi cuû thãø tæång âæång âãø minh hoüa viãûc thæûc hiãûn cuía táûp CACM. Tuy nhiãn noï mang laûi tyí säú neïn tháúp. Caïc mä âun Chæång trçnh âæåüc viãút dæåïi nhiãöu mä âun khaïc nhau âãø thuáûn låüi cho viãûc theo doîi vaì sæía läùi, noï cuîng âaím baío cho chæång trçnh âæåüc roî raìng hån. Gäöm coï baíy file nguäön (.c), nàm file tiãu âãö (.h), mäüt file måí räüng (.i) vaì mäüt file Makefile. main.c: thæûc hiãûn cäng viãûc nháûn caïc âäúi säú doìng lãûnh vaì thæûc hiãûn neïn hay giaíi neïn. word.c: thæûc hiãûn cäng viãûc xáy dæûng mä hçnh tæì. char.c: thæûc hiãûn cäng viãûc xáy dæûng mä hçnh kê tæû. bitio.c: chæïa caïc haìm thæûc hiãûn viãûc vaìo ra åí mæïc bit vaì mæïc byte. stats.c: chæïa caïc haìm thæûc hiãûn viãûc duy trç vaì tênh toaïn táön säú cuía caïc kê hiãûu. arith.c: chæïa caïc haìm thæûc hiãûn viãûc maî hoïa vaì giaíi maî caïc kê hiãûu. hashtable.c: chæïa caïc haìm häø tråü âãø duy trç viãûc chuyãøn âäøi caïc tæì trong baíng läün xäün thaình caïc tæì coï thæï tæû. arith.h: âënh nghéa caïc nguyãn máùu haìm thæûc hiãûn caïc cäng viãûc trong arith.c. stats.h: âënh nghéa caïc nguyãn máùu haìm thæûc hiãûn caïc cäng viãûc trong stats.c. bitio.h: âënh nghéa caïc macro thæûc hiãûn viãûc vaìo ra åí mæïc bit vaì byte. main.h: âënh nghéa caïc nguyãn máùu haìm thæûc hiãûn caïc cäng viãûc trong caïc mä âun main.c, char.c, word.c. hashtable.h: âënh nghéa caïc nguyãn máùu haìm thæûc hiãûn caïc cäng viãûc trong hashtable.c unroll.i: file måí räüng thæûc hiãûn måí ra caïc voìng làûp thæûc hiãûn caïc âoaûn ma. Makefile: liãn kãút caïc mä âun âãø taûo tãûp thæûc thi âãø thæûc hiãûn caïc cäng viãûc. Caïch duìng Chæång trçnh sæí duûng giao diãûn giao tiãúp chung cho caí hai quaï trçnh neïn vaì giaíi neïn thäng qua viãûc læûa choün caïc thäng säú (thæûc tãú thç åí trong cuìng chæång trçnh). Kãút quaí âæa ra åí âáöu ra chuáøn stdout. Nãúu khäng chè âënh file âáöu vaìo âáöu vaìo seî láúy dæî liãûu tæì âáöu vaìo chuáøn stdin. Mäüt trong caïc thäng säú -e hoàûc -d phaíi âæåüc choün âãø thæûc hiãûn viãûc neïn hay giaíi neïn. Âãø tçm hiãøu caïch duìng thç goî tãn cuía chæång trçnh thæûc thi. Caïch duìng: Tãn chæång trçnh.exe [ -e [ -t s ][ -m n ]| [ -d ]| [ -v ][ filename1 ] [ filename2 ] Trong âoï: -e: choün neïn. -t: choün mä hçnh. Coï mä hçnh tæì vaì mä hçnh kê tæû. -m: choün giåïi haûn kêch thæåïc bäü nhåï tæì 1 âãún 255 MB. Chè choün khi duìng mä hçnh tæì. -d: choün giaíi neïn. -v: âæa ra caïc thäng säú cuía quaï trçnh thæûc hiãûn nhæ: tyí säú neïn, thåìi gian thæûc hiãûn, v.v... Filename1: laì tãn file cáön neïn hoàûc giaíi neïn. Filename2: laì tãn file læu kãút quaí neïn hoàûc giaíi neïn. thæûc nghiãûm Giåïi thiãûu Pháön naìy trçnh baìy kãút quaí thæûc nghiãûm khi chaûy chæång trçnh. Caïc thê nghiãûm tiãún haình våïi caïc kiãøu tãûp vàn tiãúng Anh laì (.txt) vaì (cpp). Viãûc thæûc nghiãûm chæång trçnh tiãún haình våïi hai mä hçnh laì mä hçnh tæì vaì mä hçnh kê tæû. Coï so saïnh våïi kãút quaí neïn cuía Gzip vaì giaíi neïn Gunzip trãn hãû âiãöu haình Linux. Thæûc nghiãûm chæång trçnh trãn maïy coï cáúu hçnh nhæ sau: bäü vi xæí lyï Penium(r) Intel MMX (TX), 32 MB RAM. Caïc kãút quaí âæåüc láúy laì trung bçnh cäüng cuía ba láön tiãún haình khaïc nhau. Våïi caïc file (.txt) duìng âãø thê nghiãûm thç âån thuáön chè gäöm caïc kê tæû vaì caïc chæî säú coìn våïi caïc file (.cpp) thç ngoaìi caïc kê tæû vaì caïc chæî säú noï coìn coï caïc kê hiãûu khaïc nhæ caïc dáúu , +, : ,v.v... vaì caïc kê hiãûu nhæ &, %, #,v.v... Kãút quaí thæûc nghiãûm Kãút quaí thæûc nghiãûm våïi caïc file kiãøu *.txt Tyí säú neïn Tyí säú neïn âæåüc tênh theo cäng thæïc: x 100 (%). Âãø thãø hiãûn kãút quaí thæûc nghiãûm vaì tiãûn cho viãûc so saïnh ta sæí duûng biãøu âäö hçnh cäüt. Våïi truûc âæïng biãøu thë tyí säú neïn (tênh bàòng %) âaût âæåüc cuía caïc mä hçnh, truûc nàòm ngang biãøu thë âäü låïn cuía caïc file (âån vë laì MB) thê nghiãûm. Tyí säú (%) Âäü låïn file (MB) Hçnh 12: So saïnh tyí säú neïn giæîa caïc mä hçnh tæì, kê tæû våïi neïn Gzip Qua hçnh veî ta tháúy ràòng neïn våïi mä hçnh tæì laì coï tyí säú neïn säú neïn täút nháút vaì âaût tyí säú neïn tæång âäúi täút trung bçnh khoaíng 19%. Tyí säú neïn cuía mä hçnh kê tæû tháúp do âoï khoï coï khaí nàng trong thæûc tãú. Thåìi gian neïn Âãø thãø hiãûn kãút quaí thæûc nghiãûm vaì tiãûn cho viãûc so saïnh ta sæí duûng biãøu âäöì hçnh cäüt. Våïi truûc âæïng biãøu thë thåìi gian thæûc hiãûn (tênh bàòng s) neïn cuía caïc mä hçnh, truûc nàòm ngang biãøu thë âäü låïn cuía caïc file thê nghiãûm. Thåìi gian (s) Âäü låïn file (MB) Hçnh 13: So saïnh thåìi gian neïn cuía caïc mä hçnh tæì, mä hçnh kê tæû våïi neïn gzip Qua biãøu âäö ta tháúy mä hçnh kê tæû coï thåìi gian neïn láu nháút vaì láu hån ráút nhiãöu so våïi thåìi gian neïn cuía mä hçnh tæì vaì neïn gzip. Âãø âo âæåüc thåìi gian thæûc hiãûn neïn cuía gzip ta tiãún haình âo bàòng âäöng häö báúm giáy. Thåìi gian giaíi neïn. Thåìi gian (s) Âäü låïn file (MB) Âãø thãø hiãûn kãút quaí thæûc nghiãûm vaì tiãûn cho viãûc so saïnh ta sæí duûng biãøu âäöì hçnh cäüt. Våïi truûc âæïng biãøu thë thåìi gian thæûc hiãûn (tênh bàòng s) giaíi neïn cuía caïc mä hçnh, truûc nàòm ngang biãøu thë âäü låïn cuía caïc file thê nghiãûm. Hçnh 14: So saïnh thåìi gian giaíi neïn giæîa mä hçnh tæì, kê tæû våïi giaíi neïn bàòng gunzip So våïi thåìi gian neïn thç thåìi gian giaíi neïn cuía gunzip laì nhanh nháút vaì nhanh hån nhiãöu so våïi caïc mä hçnh tæì vaì mä hçnh kê tæû. Kãút quaí thæûc nghiãûm våïi caïc file kiãøu *.cpp Caïc bæåïc tiãún haình thê nghiãûm giäúng nhæ khi tiãún haình våïi kiãøu file *.txt. Caïch thãø hiãûn trãn biãøu âäö cuîng giäúng nhæ våïi åí trãn. Ta cuîng tiãún haình våïi mä hçnh tæì, mä hçnh kê tæû vaì neïn vaì giaíi neïn bàòng gzip vaì gunzip. Thåìi gian neïn Âäü låïn file (MB) Thåìi gian (s) Hçnh 15: So saïnh thåìi gian neïn cuía caïc mä hçnh tæì, mä hçnh kê tæû våïi neïn gzip Âäúi våïi kiãøu file naìy thç thåìi gian neïn cuía mä hçnh tæì laì täöi nháút vaì cuía gzip laì täút nháút. Thåìi gian giaíi neïn Âäü låïn file (MB) Thåìi gian (s) Hçnh 16: So saïnh thåìi gian giaíi neïn giæîa mä hçnh tæì, kê tæû våïi giaíi neïn bàòng gunzip Våïi kiãøu file naìy thç thåìi gian giaíi neïn bàòng mä hçnh kê tæû quaï láu so våïi caïc phæång phaïp khaïc. Coìn giaíi neïn bàòng gunzip thç ráút nhanh. Tyí säú neïn Âäü låïn file (MB) Tyí säú neïn (%) Hçnh 17: So saïnh tyí säú neïn giæîa caïc mä hçnh tæì, kê tæû våïi neïn Gzip ÅÍ âáy coï sæû chãnh lãûch âaïng kãø giæîa caïc mä hçnh khaïc nhau vaì sæû chãnh lãûch cuía caïc mä hçnh våïi neïn gzip. Neïn gzip âaût âãún tyí säú ráút täút. Kãút luáûn vãö kãút quaí thæûc nghiãûm Qua caïc kãút quaí thæûc nghiãûm thãø hiãûn bàòng biãøu âäö åí trãn nhàòm âæa ra caïch nhçn täøng thãø vãö phæång phaïp neïn maî hoïa Säú hoücvaì so saïnh noï våïi phæång phaïp khaïc. Caïc kãút quaí so saïnh naìy chè mang tênh cháút tæång âäúi vç noï phuû thuäüc vaìo nhiãöu yãúu täú khaïc nhau nhæ quaï trçnh âoüc ghi åí mæïc bit vaì mæïc byte ngoaìi ra coìn phuû thuäüc vaìo kiãøu dæî liãûu læûa choün. Qua kãút quaí thæûc nghiãûm ta tháúy ràòng våïi mä hçnh tæì thç thåìi gian giaíi neïn luän nhoí hån thåìi gian neïn. Våïi mä hçnh kê tæû thç ngæåüc laûi tæïc laì thåìi gian neïn luän nhoí hån thåìi gian giaíi neïn. Thåìi gian neïn vaì giaíi neïn, tyí säú neïn cuía mä hçnh tæì xáúp xè våïi thåìi gian neïn vaì giaíi neïn cuía phæång phaïp neïn gzip vaì giaíi neïn gunzip. Âiãöu naìy chæïng toí ràòng neïn säú hoüc duìng mä hçnh tæì mang laûi tyí säú ráút täút.  CHÆÅNG VI KÃÚT LUÁÛN Qua quaï trçnh nghiãn cæïu, tçm hiãøu caïc phæång phaïp neïn säú liãûu. Tæì caïc phæång phaïp khåíi âáöu vaìo âáöu nhæîng nàm 50 cho âãún caïc phæång phaïp âaî âæåüc caíi tiãún sau naìy. Em âaî læûa choün phæång phaïp maî hoïa säú hoüc âãø phaït triãøn thaình âãö taìi âãø laìm âäö aïn täút nghiãûp cuía mçnh. Âäö aïn âaî trçnh baìy täøng quan vãö kyî thuáût neïn säú liãûu, æu nhæåüc âiãøm cuía caïc phæång phaïp maî hoïa khaïc nhau, caïc loaûi mä hçnh âæåüc sæí duûng cho viãûc neïn säú liãûu. Troüng tám cuía âäö aïn âi sáu vaìo tçm hiãøu vaì ngiãn cæïu phæång phaïp maî hoïa säú hoüc, triãøn khai caïc thuáût toaïn maî hoïa vaì giaíi maî, xáy dæûng caïc mä hçnh. Trong âoï mä hçnh âæåüc choün læûa laì mä hçnh tæì vaì mä hçnh kê tæû. Våïi mä hçnh kê tæû thç thuáût toaïn xáy dæûng ráút âån giaín tuy nhiãn tè säú neïn cuía chæång trçnh coìn tháúp cuîng nhæ thåìi gian neïn vaì giaíi neïn coìn ráút låïn. Âãø coï tyí säú neïn cao em âaî sæí duûng mä hçnh tæì. Qua quaï trçnh thæûc nghiãûm trçnh baìy trong chæång V ta tháúy nãúu duìng mä hçnh tæì thç kãút quía âaût âæåüc khäng thua bao nhiãu (âäi khi coìn cao hån) so våïi phæång phaïp neïn vaì giaíi neïn bàòng gzip vaì gunzip åí trong Linux. Tuy nhiãn nhæ âaî trçnh baìy trong chæång II khi måïi ra âåìi phæång phaïp neïn sæí duûng maî hoïa säú hoüc chè dæåüc thæûc hiãûn åí trong phaûm vi caïc phoìng thê nghiãûm coï caïc maïy tênh maûnh. Âãún ngaìy nay thç noï âaî âæåüc moüi ngæåìi tçm hiãøu cuîng bhæ nghiã cæïu noï. Qua quaï trçnh thæûc nghiãûm âäúi trãn maïy tênh caï nhán thäng duûng nháút hiãûn nay tyí säú neïn âaût âæåüc cuîng tæång âäúi täút vaì coï thãø chaûy täút trãn caïc maïy caï nhán. Hæåïng phaït triãøn cuía âäö aïn: âãø náng cao hån tyí säú neïn chæång trçnh cáön læûa choün cáúu truïc dæî liãûu täúi æu hån âãø xáy dæûng mä hçnh báûc cao hån båíi vç kãút quaí thæûc nghiãûm åí trãn chè thæûc hiãûn åí mä hçnh báûc khäng. Do âoï våïi mä hçnh báûc cao hån thç kãút quaí mang laûi coï leî laì ráút täút. Caíi tiãún caïc thao taïc âoüc ghi tãûp åí mæïc bêt âãø náng cao täúc âäü .v.v.. Chæång trçnh cáön âæåüc phaït triãøn âãø phaït huy taïc duûng våïi táút caí caïc loaûi táûp tin (vàn baín, hçnh aính, ám thanh, táûp tin nhë phán, ...), vaì giao diãûn cuîng cáön caíi tiãún laûi âãø dãù daìng sæí duûng. Cáön caíi tiãún chæång trçnh âãø coï thãø chaûy âæåüc trãn caïc hãû âiãöu haình khaïc nhæ Windows NT, Windows 98 .v.v... Hiãûn nay neïn säú liãûu khäng phaíi laì mäüt váún âãö måïi meî âäúi våïi ngæåìi sæí duûng maïy tênh, båíi vç táút caí caïc maïy háöu nhæ âãöu âæåüc caìi âàût mäüt hoàûc vaìi tiãûn êch neïn cho ngæåìi sæí duûng. Tuy nhiãn âãø coï mäüt sæû hiãøu biãút vãö cå chãú laìm viãûc cuía quaï trçnh neïn thç chæa coï mäüt taìi liãûu tiãúng Viãût naìo âãö cáûp âãún. Do viãûc tiãúp cáûn caïc cäng nghãû neïn trong thåìi gian ngàõn, kinh nghiãûm láûp trçnh cuía baín thán coìn yãúu vaì coìn gàûp nhiãöu khoï khàn trong viãûc dëch taìi liãûu næåïc ngoaìi nãn khäng traïnh khoíi mäüt säú sai soït. Thãm vaìo âoï sæû hiãøu biãút cuía caï nhán vãö táút caí caïc khêa caûnh chæa tháût sáu sàõc, nãn âãö taìi chæa hoaìn chènh vaì cáön coï sæû caíi tiãún khaïc âãø náng cao hiãûu suáút. Ráút mong âæåüc sæû goïp yï cuía caïc tháöy cä, caïc anh chë âi træåïc vaì caïc baûn âãø em coï thãø hoaìn thaình âãö taìi âæåüc täút hån.  PHUÛ LUÛC Chæång trçnh nguäön Caïc file nguäön (*.c) File arith.c #include #include "arith.h" #include "bitio.h" #define SHIFT_STR "Ma hoa so hoc " char *coder_desc = SHIFT_STR; #define Half ((code_value) 1 << (B_bits-1)) #define Quarter ((code_value) 1 << (B_bits-2)) static code_value in_R; static code_value in_D; static div_value in_r; static code_value out_L; static code_value out_R; static unsigned long out_bits_outstanding; #define ORIG_BIT_PLUS_FOLLOW(b) \ do \ { \ OUTPUT_BIT((b)); \ while (out_bits_outstanding > 0)\ { \ OUTPUT_BIT(!(b)); \ out_bits_outstanding--; \ } \ } while (0) # define BIT_PLUS_FOLLOW(x) ORIG_BIT_PLUS_FOLLOW(x) #define ENCODE_RENORMALISE \ do { \ while (out_R <= Quarter) \ { \ if (out_L >= Half) \ { \ BIT_PLUS_FOLLOW(1); \ out_L -= Half; \ } \ else if (out_L+out_R <= Half) \ { \ BIT_PLUS_FOLLOW(0); \ } \ else \ { \ out_bits_outstanding++; \ out_L -= Quarter; \ } \ out_L <<= 1; \ out_R <<= 1; \ } \ } while (0) #define DECODE_RENORMALISE \ do { \ while (in_R <= Quarter) \ { \ in_R <<= 1; \ ADD_NEXT_INPUT_BIT(in_D,0); \ } \ } while (0) void arithmetic_encode(freq_value low,freq_value high,freq_value total) { code_value temp; M = total << (B_bits - F_bits - 1); if (A >= M) { A -= M; temp += low; temp2 += high; } # define UNROLL_NUM B_bits - F_bits - 1 # define UNROLL_CODE \ A <<= 1; temp <<= 1; temp2 <<= 1; \ if (A >= M) { A -= M; temp += low; temp2 += high; } # include "unroll.i" out_L += temp; if (high < total) out_R = temp2 - temp; else out_R -= temp; ENCODE_RENORMALISE; if (out_bits_outstanding > MAX_BITS_OUTSTANDING) { fprintf(stderr,"Bits_outstanding limit reached - File too large\n"); exit(1); } } freq_value arithmetic_decode_target(freq_value total) { freq_value target; M = total << ( B_bits - F_bits - 1 ); if (A >= M) { A -= M; in_r++; } # define UNROLL_NUM B_bits - F_bits - 1 # define UNROLL_CODE \ A <<= 1; in_r <<= 1; \ if (A >= M) { A -= M; in_r++; } # include "unroll.i" A = in_D; target = 0; if (in_r < (1 << (B_bits - F_bits - 1))) { M = in_r << F_bits; if (A >= M) { A -= M; target++; } A <<= 1; target <<= 1; } else { M = in_r << (F_bits - 1); } if (A >= M) { A -= M; target++; } # define UNROLL_NUM F_bits