Cơ chế vấn tin dạng logic cho cơ sở dữ liệu văn bản không cấu trúc

g táûp saïch naìy, dáùu viãút vãö tçnh yãu cuäüc säúng våïi nhæîng bæån chaíi cuía låïp ngæåìi treí tuäøi, vãö tçnh caím, nãúp säúng, suy tæ cuía ngæåìi giaì trong hiãûn taûi hay khi láût laûi nhæîng têch cuî váùn luän luän thäøi vaìo nhæîng trang vàn håi thåí cuía nhëp säúng âæång âaûi, tæåi måïi. Trong táûp coï nhiãöu taïc pháøm läi cuäún nhæ : Tráöu tãm caïnh phæåüng, máy nuïi thaïi haìng... Gioï nàõng Træåìng Sån (NXB vàn nghãû TP HCM ) Táûp buït kyï ghi laûi caím xuïc cuía taïc giaí Phan Lai Triãöu qua nhæîng thaïng ngaìy säúng chiãún âáúu trãn daîi Træåìng Sån trong cuäüc khaïng chiãún chäúng Myî cæïu næåïc. Taïc giaí khàõc hoaû hçnh aính ngæåìi lênh træåïc bom âaûn keí thuì váùn laûc quan yãu âåìi, hçnh aính caïc anh chëu âæûng gian khäø, hy sinh anh duîng, cäúng hiãún caí tuäøi xuán cuía mçnh cho âáút næåïc... Hçnh 1.1 : Trêch mäüt cå såí dæî liãûu vàn baín Nhæ váûy cå såí dæî liãûu vàn baín âæåüc âënh nghéa nhæ laì táûp caïc vàn baín riãng leî vaì mäùi vàn baín âæåüc coi laì mäüt máùu tin âæåüc læu dæåïi daûng maì maïy tênh coï thãø âoüc âæåüc. Våïi viãûc xáy dæûng chè muûc, mäùi vàn baín âæåüc coi laì mäüt chuäùi näúi tiãúp caïc tæì. Tæì coï thãø laì tæì âån hay xáu kyï tæû coï âæåüc bàòng mäüt quy æåïc naìo âoï trong vàn baín. Caïch âënh nghéa naìy laì khäng âäöng nháút trong nhiãöu vàn baín. Mäüt cå såí dæî liãûu vàn baín cuîng nhæ baín thán caïc vàn baín khäng coï sæû giåïi haûn vãö âäü daìi. Mäüt vàn baín coï thãø gäöm mäüt vaìi byte hoàûc vaìi Megabyte. Mäüt cå såí dæî liãûu vàn baín gäöm vaìi tràm hoàûc vaìi triãûu vàn baín nhæ thãú. Caïc âàûc træng quan troüng cuía cå såí dæî liãûu vàn baín âæåüc liãût kã trong baíng sau: Kyï hiãûu YÏ nghéa Vê duû N F n D f Säú caïc vàn baín trong CSDL Täøng säú tæì xuáút hiãûn Säú caïc tæì khaïc biãût Kêch thæåïc CSDL (Mbyte) Säú con troí chè muûc 31 102 884 988 9 020 4,33 699 131 Baíng 1.1: Caïc âàûc træng cuía CSDL vàn baín Mäùi vàn baín trong cå såí dæî liãûu vàn baín coï mäüt âënh danh duy nháút. Âãø âån giaín, ta giaí sæí caïc vàn baín âæåüc âënh danh bàòng caïc säú tæû nhiãn ( tæì 1 âãún N ) theo thæï tæû nháûp vaìo cå såí dæî liãûu. Trong âäö aïn naìy âënh danh coìn goüi laì säú hiãûu vàn baín. Hçnh sau âáy laì mäüt vê duû vãö âënh danh cuía vàn baín: Säú hiãûu vàn baín Vàn baín 1 2 3 4 Taïc pháøm vaì taïc giaí âæåüc yãu thêch Thå vaì truyãûn ngàõn caïch maûng Giåïi thiãûu taïc pháøm måïi, taïc pháøm âæåüc giaíi Caïc taïc pháøm truyãûn ngàõn cuía taïc giaí BaíoVuî Hçnh 1.2 : Vê duû vãö âënh danh cuía vàn baín Vê duû trãn âæåüc xem nhæ laì mäüt vê duû xuyãn suäút caí âãö taìi naìy våïi mäùi doìng laì mäüt vàn baín. Yãu cáöu váún tin: Mäüt thaình pháön ráút quan troüng âäúi våïi hãû thäúng truy tçm thäng tin laì caïc yãu cáöu váún tin. Âáy laì mäi træåìng giao tiãúp chênh giæîa ngæåìi váún tin vaì hãû thäúng truy tçm thäng tin. Mäüt yãu cáöu váún tin laì mäüt yãu cáöu dæûa trãn ngän ngæî tæû nhiãn, coï thãø laì mäüt tæì hay mäüt chuäùi caïc tæì âæåüc liãn kãút våïi nhau båíi caïc pheïp toaïn logic nhæ : AND, OR, XOR, NOT. Trãn cå såí caïc yãu cáöu âoï, hãû thäúng truy tçm thäng tin seî tçm caïc vàn baín chæïa thäng tin tæång æïng trong cå såí dæî liãûu vàn baín vaì hiãøn thë cho ngæåìi cáön váún tin. Vê duû vãö yãu cáöu váún tin nhæ: Taïc pháøm AND Taïc giaí Thå OR Truyãûn ngàõn (Taïc pháøm OR Taïc giaí) AND (Thå OR Truyãûn ngàõn) ............ Kãút luáûn: Våïi nhæîng gç trçnh baìy åí trãn, pháön naìo âaî hçnh thaình mäüt hãû thäúng truy tçm thäng tin mäüt caïch täøng quaït nháút. Qua âoï biãút âæåüc caïch thæïc täø chæïc mäüt cå såí dæî liãûu vàn baín, mäüt yãu cáöu váún tin laì gç vaì hãû thäúng âæåüc xáy dæûng trãn cå såí naìo. Tuy nhiãn âáy måïi chè laì caïi nhçn täøng quan vãö daïng maûo cuía hãû thäúng, caïc chæång tiãúp theo seî trçnh baìy chi tiãút vãö cáúu taûo vaì nguyãn tàõc hoaût âäüng bãn trong cuía hãû thäúng truy tçm thäng tin. CHÆÅNG 2 KHAÏI NIÃÛM VÃÖ CHÈ MUÛC ÂAÍO VAÌ CÅ CHÃÚ VÁÚN TIN Chè muûc âaío: Nhæ âaî âãö cáûp trong chæång træåïc, ngaìy nay våïi sæû tiãún bäü cuía khoa hoüc cäng nghãû âàûc biãût laì cäng nghãû thäng tin, cuìng våïi sæû buìng näø cuía thäng tin thç caïc hãû thäúng truy tçm thäng tin ra âåìi. Nhiãûm vuû cuía hãû thäúng truy tçm thäng tin laì tçm vaì hiãøn thë nhæîng thäng tin thoaí maîn yãu cáöu naìo âoï cuía ngæåìi váún tin. Trong âãö luáûn naìy âoï laì caïc vàn baín trong cå såí dæî liãûu vàn baín. Våïi mäüt cå såí dæî liãûu cæûc låïn, giaí sæí gäöm haìng triãûu vàn baín, thç âoï laì thaïch thæïc âäúi våïi caïc hãû thäúng truy tçm thäng tin. Viãûc tçm låìi giaíi cho caïc yãu cáöu theo hæåïng træûc tiãúp âãún tæìng vàn baín trong cå såí dæî liãûu seî aính hæåíng låïn âãún thåìi gian truy tçm. Vç váûy âãø náng cao täúc âäü truy tçm cuía hãû thäúng ta tiãún haình xáy dæûng chè muûc cho cå såí dæî liãûu. Coï nhiãöu kyî thuáût xáy dæûng chè muûc nhæ chè muûc âaío, chè muûc chæî kyï, chè muûc hçnh aính. Tuy nhiãn chè muûc chæî kyï vaì chè muûc hçnh aính âoìi hoíi dung læåüng bäü nhåï låïn nãn trong âäö aïn naìy em choün caïch xáy dæûng chè muûc dæûa trãn mäüt kyî thuáût goüi laì kyî thuáût chè muûc âaío. Trãn cå såí chè muûc âaío naìy, caïc hçnh thæïc váún tin seî âæåüc xáy dæûng phuì håüp våïi caïc yãu cáöu cuía ngæåìi váún tin. Pháön naìy thaío luáûn vãö caïch thæïc caìi âàût hãû thäúng truy tçm vàn baín âãø coï thãø tçm cáu traí låìi cho caïc yãu cáöu daûng logic vaì xãúp haûng. Mäüt yãu cáöu logic âoìi hoíi, âäúi våïi mäùi tæì cuía yãu cáöu, mäüt phæång phaïp xaïc âënh mäùi vàn baín coï chæïa tæì âoï hay khäng. Yãu cáöu xãúp haûng bãn caûnh âiãöu naìy coìn âoìi hoíi thäng tin vãö táöm quan troüng cuía tæì trong vàn baín. Caïch thæïc caìi âàût håüp lyï âaïp æïng caí hai yãu cáöu trãn laì chè muûc âaío. Chè muûc âaío âæåüc xáy dæûng trãn cå såí ba thaình pháön: danh saïch âaío, tæì âiãøn vaì troüng læåüng vàn baín, tãûp âaío. Hãû thäúng seî xæí lyï træûc tiãúp trãn caïc thaình pháön naìy âãø âæa ra caïc vàn baín coï thäng tin âaïp æïng âæåüc yãu cáöu cuía ngæåìi váún tin. Danh saïch âaío: Danh saïch âaío laì thaình pháön quan troüng nháút trong chè muûc âaío, âæåüc xáy dæûng tæì cå såí dæî liãûu vàn baín ban âáöu. Våïi mäùi tæì khaïc biãût trong cå såí dæî liãûu, danh saïch âaío tæång æïng cho pheïp xaïc âënh tæì âoï coï màût trong nhæîng vàn baín naìo vaì coï táöm quan troüng ra sao trong caïc vàn baín âoï. Nhæ váûy danh saïch âaío laì danh saïch caïc càûp nhán täú . Âãø læu træî mäüt càûp nhán täú nhæ váûy cáön 8 byte, 4 byte cho säú hiãûu vàn baín vaì 4 byte cho troüng læåüng. Våïi mäüt cå såí dæî liãûu låïn thç säú càûp nhán täú seî ráút låïn vaì âoìi hoíi khäng gian nhåï cuîng låïn. Âãø tiãút kiãûm khäng gian nhåï, ta thay nhán täú troüng læåüng bàòng táön suáút tæì trong vàn baín. Táön suáút naìy âæåüc biãøu diãùn båíi säú nguyãn 2 byte hoàûc 1 byte. Våïi caïch thay thãú naìy thç danh saïch âaío cuía tæì t laì mäüt danh saïch caïc càûp , trong âoï d laì säú hiãûu vàn baín chæïa tæì t vaì fd,t laì säú láön tæì t xuáút hiãûn trong d. Tãûp âaío: Tãûp âaío laì mäüt tãûp duìng âãø læu træî troüng læåüng cuía mäùi vàn baín tæïc laì bao gäöm caïc danh saïch âaío cuía táút caí caïc tæì khaïc biãût trong cå såí dæî liãûu vàn baín. Coï thãø coi tãûp âaío laì mäüt chuäùi näúi tiãúp caïc säú thæûc tæåüng træng cho troüng læåüng cuía caïc vàn baín theo thæï tæû tàng cuía säú hiãûu vàn baín. Chi tiãút vãö cáúu truïc cuía tãûp âaío vaì phæång phaïp truy cáûp caïc thaình pháön trong tãûp âaío seî âæåüc thaío luáûn åí chæång tiãúp theo. Xeït mäüt vê duû âån giaín vãö tãûp âaío våïi mäùi vàn baín âæåüc âån giaín hoaï thaình mäüt chuäùi näúi tiãúp caïc chæî caïi vaì xem âoï nhæ laì caïc tæì cuía cå såí dæî liãûu. Säú hiãûu vàn baín c b b c a c d a b b e a a c b e a b c b b b b b e b e e e c e 1 2 3 4 5 6 1,3 2,1 5,1 1,2 2,2 3,5 4,1 5,2 2,3 4,1 5,1 6,1 1,3 1,1 3,1 4,1 6,4 a b c d e Vàn baín Danh saïch âaío Tæì t Tãûp âaío CSDL vàn baín Hçnh 2.1 : Vê duû vãö tãûp âaío Trong vê duû naìy, cå såí dæî liãûu vàn baín bao gäöm 6 vàn baín âæåüc âaïnh säú tæì 1 âãún 6 vaì säú caïc tæì khaïc biãût laì 5 æïng våïi danh saïch âaío âæåüc biãøu diãùn nhæ trãn. Tæì âiãøn vaì troüng læåüng vàn baín: Mäüt thaình pháön cuîng ráút quan troüng khaïc trong chè muûc âaío laì tæì âiãøn. Tæì âiãøn duìng âãø ghi laûi táút caí caïc tæì khaïc biãût cuía cå såí dæî liãûu cuìng våïi âëa chè cuía danh saïch âaío tæång æïng cuía noï trong tãûp âaío. Chæïc nàng chênh cuía tæì âiãøn laì duìng âãø tçm kiãúm tæì vaì tæì âiãøn thæåìng âæåüc xáy dæûng theo cáúu truïc cáy nhë phán âãø âaïp æïng âæåüc yãu cáöu cuía hãû thäúng. Cáúu truïc cuía tæì âiãøn seî âæåüc mä taí chi tiãút åí chæång sau. Nhæ âaî âãö cáûp åí tãûp âaío, troüng læåüng cuía thæûc thãø vàn baín coï thãø âæåüc tênh theo nhiãöu phæång phaïp nhæng háöu hãút laì dæûa trãn hai thæìa säú sau: TF vaì IDF. TF goüi laì táön suáút tæì tæïc laì säú láön xuáút hiãûn cuía tæì t trong thæûc thãø vàn baín d vaì âæåüc kyï hiãûu laì fd,t. IDF laì táön suáút vàn baín ngæåüc thæåìng âæåüc tênh theo cäng thæïc log(N/ft) , trong âoï N laì säú vàn baín trong cå såí dæî liãûu vaì ft laì säú vàn baín coï chæïa tæì t. Thäng thæåìng troüng læåüng cuía thæûc thãø vàn baín : TF* IDF. Cå chãú váún tin: Trong pháön naìy giåïi thiãûu khaïi quaït vãö hai cå chãú váún tin daûng logic vaì daûng xãúp haûng. Váún tin daûng xãúp haûng: Giaí sæí ta coï mäüt yãu cáöu q (gäöm mäüt säú tæì t = 1..n) vaì mäüt cå såí dæî liãûu låïn gäöm N vàn baín khäng cáúu truïc. Âãø âaïp æïng âæåüc yãu cáöu váún tin q thç hãû thäúng phaíi thæûc hiãûn viãûc tênh toaïn troüng læåüng vaì âäü tæång håüp cuía yãu cáöu âoï våïi mäùi vàn baín coï chæïa thäng tin cáön tçm. Sau âoï caïc vàn baín seî âæåüc hiãøn thë cho ngæåìi váún tin theo thæï tæû giaím dáön cuía âäü tæång håüp. Theo nhæ taìi liãûu Managing Gigabytes, âäü tæång håüp cuía yãu cáöu q vaì vàn baín d âæåüc tênh nhæ sau: Trong âoï laì troüng læåüng cuía yãu cáöu q. laì troüng læåüng cuía vàn baín d. Vaì Nhæ váûy Vê duû vãö âäü tæång håüp nhæ sau: Giaí sæí ta coï cå såí dæî liãûu nhæ hçnh 2.1. Caïc giaï trë fd,t vaì Wd tæång æïng âæåüc liãût kã trong baíng 2.1 D Tæì t Wd a b C d e 1 2 3 4 5 6 3 1 0 0 1 0 2 2 5 1 2 0 0 3 0 1 1 1 0 1 0 0 0 0 1 0 1 1 0 4 3,10 3,31 1,42 0,86 1,27 2,39 ft Wt 3 1,00 5 0,26 4 0,58 1 2,58 4 0,58 Baíng 2.1 : Caïc giaï trë fd,t vaì Wd tæång æïng våïi CSDL hçnh 2.1 Âäü tæång håüp giæîa yãu cáöu q vaì vàn baín d âæåüc tênh toaïn nhæ vê duû liãût kã trong baíng sau: D Yãu cáöu d Wq=2,58 C Wq=0,58 c,d Wq=2,64 a,b,e Wq=1,18 a,b,c,d,e Wq=2,90 1 2 3 4 5 6 0,00 0,78 0,00 0,00 0,00 0,00 0,00 0,53 0,00 0,67 0,46 0,24 0,00 0,88 0,00 0,15 0,10 0,05 0,95 0,29 0,40 0,40 0,76 0,48 0,39 0,92 0,16 0,30 0,40 0,24 Top 2 4 2 1 2 Baíng 2.2 : Âäü tæång håüp giæîa yãu cáöu q vaì vàn baín d Váún tin daûng logic: Cå chãú váún tin naìy âæåüc thæûc hiãûn dæûa trãn caïc pheïp toaïn logic laì caïc pheïp toaïn AND , OR vaì NOT vaì sæí duûng kyî thuáût chè muûc âaío. Våïi mäüt yãu cáöu q gäöm mäüt säú tæì t âæåüc liãn kãút båíi caïc pheïp toaïn logic nhæ trãn thç âáöu tiãn caïc tæì seî âæåüc tçm trong tæì âiãøn , xaïc âënh caïc danh saïch âaío tæång æïng vaì sau âoï dæûa trãn caïc pheïp toaïn logic tæång æïng âãø xaïc âënh táûp caïc vàn baín thoaí maîn yãu cáöu vaì trçnh baìy cho ngæåìi váún tin. Cå chãú váún tin daûng logic cho kãút quaí coï âäü chênh xaïc cao hån so våïi váún tin daûng xãúp haûng. Trong âãö luáûn naìy chè xeït cå chãú váún tin daûng logic. Chi tiãút vãö xæí lyï váún tin daûng naìy seî âæåüc trçnh baìy åí chæång bäún. Mäüt vê duû minh hoüa cho cå chãú váún tin daûng logic : Cho cå såí dæî liãûu nhæ hçnh 1.2, ta xáy dæûng tãûp âaío nhæ sau: Tæì t Danh saïch âaío It 4 , 1 2 , 1 4 , 1 3 , 1 3 , 1 3 , 1 4 , 1 1 , 1 4 , 1 1 , 1 3 , 1 4 , 1 1 , 1 3 , 2 4 , 1 1 , 1 4 , 1 2 , 1 4 , 1 1 , 1 2 , 1 Baío Vuî Caïc Caïch maûng Cuía Âæåüc Giaíi Giåïi thiãûu Måïi Taïc pháøm Taïc giaí Thå Truyãûn ngàõn Vaì Yãu thêch Giaí sæí coï yãu cáöu váún tin q= ( taïc giaí AND taïc pháøm ). Sau khi thæûc hiãûn tçm kiãúm trong tæì âiãøn ta coï kãút quaí nhæ sau: t Î q D Taïc giaí Taïc pháøm 1 , 4 1 , 3 , 4 Våïi pheïp toaïn logic laì AND nãn caïc vàn baín ( 1 , 4 ) seî âæåüc ghi nháûn vaì trçnh baìy cho ngæåìi váún tin. Kãút luáûn: Chæång naìy âæa ra nhæîng khaïi niãûm cå baín vãö phæång phaïp xáy dæûng chè muûc dæûa trãn kyî thuáût chè muûc âaío vaì caïc cå chãú váún tin, tæì âoï giuïp cho viãûc xáy dæûng hãû thäúng truy tçm thäng tin mäüt caïch nhanh choïng vaì chênh xaïc. Chi tiãút vãö kyî thuáût chè muûc âaío seî âæåüc trçnh baìy åí chæång ba. CHÆÅNG 3 XÁY DÆÛNG CHÈ MUÛC ÂAÍO Cáúu truïc dæî liãûu: Cáúu truïc dæî liãûu laì thaïch thæïc phaíi âæång âáöu khi xáy dæûng chè muûc. Caïch âån giaín nháút âãø mä taí cáúu truïc chè muûc âaío cho cå såí dæî liãûu laì ma tráûn tuáön tæû cáúp hai (m,n). Våïi cå såí dæî liãûu nhæ hçnh 1.2 ta coï ma tráûn tuáön tæû nhæ sau: Tæì t Säú hiãûu vàn baín 1 2 3 4 Baío Vuî Caïc Caïch maûng Cuía Âæåüc Giaíi Giåïi thiãûu Måïi Taïc pháøm Taïc giaí Thå Truyãûn ngàõn Vaì Yãu thêch - - - - 1 - - - 1 1 - - 1 1 - - 1 - - - - - - - 1 1 1 - - - - - 1 1 1 1 2 - - - - - 1 1 - 1 - - - - 1 1 - 1 - - Hçnh 3.1 : Biãøu diãùn chè muûc bàòng ma tráûn tuáön tæû Ma tráûn tuáön tæû cáúp hai m haìng, n cäüt våïi caïc thaình pháön cäüt laì säú hiãûu vàn baín vaì caïc thaình pháön haìng laì tæì t trong cå såí dæî liãûu. Giaï trë giæîa haìng vaì cäüt laì säú láön tæì t xuáút hiãûn trong vàn baín âoï, kyï hiãûu laì f Št , d‹. Giaí sæí giaï trë f Št , d‹ coï âäü daìi laì 4 byte thç kêch thæåïc cuía cå såí dæî liãûu chè muûc laì: S = 4*m*n (byte) Våïi vê duû trãn thç khäng gian nhåï cáön thiãút cho cå såí dæî liãûu chè muûc laì: S = 4*7*4 = 112 (byte) Viãûc xáy dæûng cáúu truïc chè muûc âaío cho cå såí dæî liãûu theo ma tráûn tuáön tæû nhæ trãn laì ráút täún khäng gian nhåï. Båíi vç theo caïch xáy dæûng trãn thç caïc vàn baín khäng chæïa tæì t nhæng váùn chiãúm giæî 4 byte nhåï trong ma tráûn. Nhæ váûy, våïi mäüt cå såí dæî liãûu ráút låïn thç dung læåüng nhåï chi phê cho viãûc læu træî caïc vàn baín khäng chæïa tæì t cuîng ráút låïn. Cho nãn cáúu truïc trãn laì khäng thêch håüp. Âãø khàõc phuûc nhæåüc âiãøm cuía cáúu truïc chè muûc theo ma tráûn tuáön tæû, ta sæí duûng mäüt cáúu truïc khaïc, âoï laì danh saïch liãn kãút. Âäúi våïi mäüt tæì khaïc biãût trong cå såí dæî liãûu seî coï mäüt danh saïch liãn kãút tæång æïng vaì chè coï nhæîng vàn baín coï chæïa tæì âoï måïi âæåüc læu træî trong danh saïch naìy. Sæí duûng danh saïch liãn kãút âãø biãøu thë giaï trë f Št , d‹ âaî giaím âaïng kãø khäng gian nhåï khäng cáön thiãút trong ma tráûn tuáön tæû. Bãn caûnh âoï sæí duûng danh saïch liãn kãút coï thãø truy cáûp âæåüc theo mäüt kiãøu ngáùu nhiãn, båíi vç mäùi pháön tæí cuía thäng tin mang theo noï mäüt mäúi liãn kãút âãún pháön tæí liãön kãú tiãúp trong dáy chuyãön vaì âäöng thåìi noï cho pheïp khaí nàng bäø sung vaìo danh saïch. Âiãöu naìy ráút quan troüng, båíi vç trãn thæûc tãú ta khäng chè xáy dæûng chè muûc cho cå såí dæî liãûu vàn baín ténh maì coìn cho caïc cå såí dæî liãûu vàn baín âäüng tæïc laì caïc vàn baín luän luän âæåüc bäø sung hoàûc loaûi boí. Vê duû sau minh hoaû cho viãûc xáy dæûng cáúu truïc chè muûc âaío våïi cå såí dæî liãûu hçnh1.2. Baío Vuî 1 Caïc 1 Caïch maûng 1 Cuía 1 Âæåüc 2 Thå 1 Truyãûn ngàõn 2 Vaì 2 Yãu thêch 1 Giaíi 1 Giåïi thiãûu 1 Måïi 1 Taïc pháøm 3 Taïc giaí 2 3 1 X 4 1 X 4 1 X 4 1 X 4 1 X 4 1 X 4 1 X 4 1 X 4 1 X 2 1 X 4 1 X 1 1 3 1 X 3 1 X 3 1 X 1 1 1 1 2 1 X 2 1 1 1 1 1 X 4 1 X 4 1 X 3 2 4 1 X 2 1 X Cáúu truïc Danh saïch liãn kãút Hçnh 3.2 : Biãøu diãùn chè muûc cho cå såí dæî liãûu bàòng danh saïch liãn kãút Trong vê duû trãn, X quy æåïc nháûn giaï trë NULL. Âäúi våïi mäüt cå såí dæî liãûu nhoí thç khoï coï thãø âaïnh giaï tênh hiãûu quaí cuía caïc cáúu truïc dæî liãûu nhæng våïi mäüt cå såí dæî liãûu låïn bao gäöm haìng triãûu vàn baín thç mä hçnh cáúu truïc duìng danh saïch liãn kãút laì ráút hiãûu quaí. Thåìi gian cuîng laì mäüt trong nhæîng yãúu täú quan troüng duìng âãø âaïnh giaï hiãûu quaí cuía hãû thäúng. Vç váûy viãûc giaím täúi thiãøu thåìi gian thæûc thi chæång trçnh laì váún âãö âæåüc âàût ra trong âäö aïn naìy. Cáúu truïc cáy nhë phán giaíi quyãút âæåüc váún âãö naìy båíi cáy nhë phán váùn âæåüc xem laì âàûc biãût vç khi sàõp xãúp chuïng tæû laìm cho caïc pheïp cheìn, tçm kiãúm vaì xoaï âæåüc nhanh hån. Theo caïc nhaì nghiãn cæïu thç mäüt cáy nhë phán coï daûng nhæ sau: T1 · · T2 · · T4 0 0 T5 0 0 T3 0 · T6 0 0 Hçnh 3.3 : Mäüt cáy nhë phán biãøu diãùn bàòng danh saïch liãn kãút Pháön tæí âáöu tiãn cuía cáy goüi laì Root, mäùi pháön tæí dæî liãûu âæåüc goüi laì mäüt node cuía cáy vaì báút cæï mäüt pháön naìo cuía cáy âãöu âæåüc goüi laì cáy con. Mäüt node khäng coï cáy con näúi vaìo thç âæåüc goüi laì node kãút thuïc hay laì laï. Mäùi pháön tæí cuía mäüt cáy bao gäöm thäng tin cuìng våïi mäüt liãn kãút âãún pháön tæí bãn traïi vaì mäüt liãn kãút âãún pháön tæí bãn phaíi. Cáy nhë phán cuîng coï thãø âæåüc biãøu diãùn båíi danh saïch âàûc. Caïc nuït trãn cáy nhë phán âæåüc âaïnh säú bàõt âáöu tæì 1 tråí âi theo thæï tæû tæì mæïc naìy âãún mæïc khaïc vaì caïc nuït trãn cuìng mäüt mæïc thç âæåüc âaïnh tæì traïi sang phaíi. Nuït i seî coï 2 con laì nuït 2i vaì nuït 2i+1. Duìng vecto V âãø læu træî caïc pháön tæí cuía cáy, trong âoï pháön tæí VŠi‹ seî chæïa nuït i cuía cáy. T1 T2 T3 T4 T5 T6 Hçnh 3.4 : Mäüt cáy nhë phán biãøu diãùn bàòng danh saïch âàûc Caïc cáy nhë phán cho chuïng ta mäüt sæïc maûnh, sæû linh âäüng vaì hiãûu quaí ráút låïn, khi chuïng ta sæí duûng våïi caïc chæång trçnh quaín lyï cå såí dæî liãûu. Coï âiãöu naìy laì vç caïc thäng tin cho cå såí dæî liãûu naìy phaíi nàòm trãn âéa, vaì thåìi gian truy cáûp laì ráút quan troüng. Vç mäüt cáy cán bàòng coï log2n pheïp so saïnh trong pheïp tçm kiãúm (trong træåìng håüp täöi nháút ), noï täút hån ráút nhiãöu so våïi danh saïch liãn kãút maì phaíi tçm kiãúm tuáön tæû. Tæì nhæîng æu âiãøm cuía cáy nhë phán nãn trong âäö aïn naìy em choün cáúu truïc cáy nhë phán âãø xáy dæûng chè muûc âaío. Trong âäö aïn naìy mäüt cáúu truïc cáy nhë phán coï thãø âæåüc âënh nghéa bàòng ngän ngæî láûp trçnh nhæ sau : Struct tree Œ char t Š20‹ ; long ft ; dsd TIt; tree Tleft; tree Tright;  ; Trong âoï dsd laì cáúu truïc cuía mäüt danh saïch âaío âæåüc âënh nghéa nhæ sau: Struct dsd Œ long d; int fd,t ; dsd Tnext ;  ; Xáy dæûng cáúu truïc tæì âiãøn Trong chæång 2 âaî âënh nghéa vãö tæì âiãøn, âoï laì mäüt cáúu truïc bao gäöm caïc thaình pháön : tæì t, táön suáút ft vaì âëa chè cuía danh saïch âaío It. Viãûc tçm kiãúm âæûåc thæûc hiãûn trãn tæì âiãøn vaì thäng qua âëa chè cuía It xaïc âënh âæåüc danh saïch âaío tæång æïng trong tãûp âaío. Cáúu truïc âån giaín nháút cuía tæì âiãøn laì daûng maíng caïc baíng ghi bao gäöm mäüt chuäùi cuìng våïi hai træåìng nguyãn. Cáúu truïc âoï âæåüc mä taí nhæ hçnh 3.5. Viãûc læu tæî theo phæång thæïc naìy seî laîng phê khoaíng khäng gian nhåï ráút låïn. Giaí sæí, âãø læu træî mäüt chuäùi cáön 20 byte cuìng våïi 4 byte cho giaï trë ft vaì 4 byte cho âëa chè cuía danh saïch âaío It thç khäng gian nhåï maì tæì âiãøn cáön âãø læu træî seî låïn hån 28 Mbyte. Khäng gian nhåï cáön âãø læu træî caïc chuäùi seî giaím nãúu nhæ táút caí caïc chuäùi âoï kãút näúi thaình mäüt chuäùi daìi liãn tiãúp vaì sæí duûng con troí 4 byte âãø truy cáûp. Luïc naìy, mäùi mäüt chuäùi seî bao gäöm chênh xaïc säú kyï tæû cuía chuäùi âoï cäüng thãm 4 cho con troí truy cáûp. Cáúu truïc naìy âæåüc phaït thaío trong hçnh 3.6. Khi mäüt chuäùi âæåüc chè muûc thç noï khäng cáön thiãút phaíi læu træåìng chiãöu daìi hoàûc kyï tæû kãút thuïc vç con troí tiãúp theo trong maíng seî xaïc âënh vë trê kãút thuïc cuía chuäùi. Theo giaí thuyãút nhæ thãú, nãúu mäüt tæì âiãøn khoaíng mäüt triãûu tæì thç khäng gian nhåï seî giaím tæì 8 Mbyte âãún 20Mbyte. Tæì t ft Âëa chè It Baío Vuî 1 Caïc 1 Caïch maûng 1 Cuía 1 Âæåüc 2 Giaíi 1 Giåïi thiãûu 1 Måïi 1 Taïc pháøm 3 Taïc giaí 2 ............ Hçnh 3.5 :Læu træî tæì âiãøn nhæ mäüt maíng caïc baíng ghi ....... âæåücgiaíigiåïithiãûumåïitaïcpháømtaïcgiaí....... ft âc t âc It 2 1 1 1 3 2 Hçnh 3.6 :Læu træî tæì âiãøn nhæ mäüt maíng caïc con troí Âãø giaím hån næîa khäng gian nhåï vaì náng cao täúc âäü tçm kiãúm thç ta laûi xáy dæûng chè muûc cho chè muûc âaío tæïc laì loaûi boí nhiãöu hån næîa caïc con troí chè muûc åí trãn. Coï n tæì nhæng khäng nháút thiãút phaíi sæí duûng n con troí chè muûc, giaí sæí cæï 4 tæì thç coï 1 tæì âæåüc chè muûc. Nhæ váûy chè cáön 4 byte âãø læu træî thäng tin vãö chiãöu daìi cuía caí nhoïm. Cáúu truïc naìy âæåüc minh hoaû nhæ hçnh dæåïi âáy: k k +1 Âëa chè It 2 1 1 2 3 1 ft 4k 4k + 1 4k + 2 4k + 3 4(k + 1) ........4âæåüc4giaíi9giåïithiãûu3måïi7taïcpháøm6taïcgiaí Hçnh 3.7 : Læu træî tæì âiãøn våïi xáy dæûng chè muûc cho chè muûc âaío Våïi mä hçnh tæì âiãøn âæåüc xáy dæûng nhæ trãn seî thêch håüp cho viãûc xæí lyï tçm kiãúm nhë phán âäöng thåìi tiãút kiãûm âæåüc khäng gian nhåï vaì náng cao täúc âäü xæí lyï cuía hãû thäúng. Xáy dæûng tãûp âaío: Nhæ âaî khaío saït åí caïc chæång træåïc, âäúi våïi mäùi tæì t bao gäöm caïc thaình pháön: tæì t táön suáút ft danh saïch âaío It Mäüt tãûp âaío cuîng bao gäöm caïc thaình pháön trãn. Trãn cå såí caïc thaình pháön cuía tãûp âaío seî xaïc âënh chênh xaïc caïc vàn baín chæïa thäng tin cáön truy váún. Cáúu truïc cuía mäüt tãûp âaío âæåüc xáy dæûng theo caïch thæïc truyãön thäúng nhæ sau: t1 ft1 d1 fd1 , t1 d2 fd2 , t2 .......... di fdi , ti t2 ft2 fd1 , tn d2 fd2 , tn ....... di fdi , tn d1 fd1 , t2 d2 fd2 , t2 ......... di fdi , ti .......... tn ftn d1 Hçnh 3.8 : Mä hçnh tãûp âaío âån giaín Theo mä hçnh naìy thç caïc thaình pháön trong cå såí dæî liãûu âæåüc chè muûc nhæ H 3.2 seî âæåüc læu træî nhæ sau: Baîo Vuî 1 4 1 Caïc 1 4 1 Caïch maûng 1 2 1 Cuía 1 4 1 Âæåüc 2 1 1 3 1 Giaíi 1 3 1 Giåïi thiãûu 1 3 1 Måïi 1 3 1 Taïc pháøm 3 1 1 3 2 4 1 Taïc giaí 2 1 1 4 1 Thå 1 2 1 Truyãûn ngàõn 2 2 1 4 1 Vaì 2 1 1 2 1 Yãu thêch 1 1 1 Hçnh 3.9 : Vê duû vãö chè muûc tãûp âaío Theo caïch xáy dæûng tãûp âaío nhæ trãn thç viãûc xæí lyï truy tçm trãn tãûp âaío âæåüc tiãún haình tuáön tæû âãún tæìng thaình pháön. Våïi cå såí dæî liãûu cæûc låïn thç phæång thæïc truy cáûp tuáön tæû laì khäng hiãûu quaí vaì vç thãú mä hçnh tãûp âaío nãu trãn laì khäng thêch håüp. Mäüt caïch täø chæïc khaïc cuía tãûp âaío khàõc phuûc âæåüc nhæåüc âiãøm trãn laì xáy dæûng chè muûc cho tãûp âaío. Âáöu tiãn, xaïc âënh kêch thæåïc khäúi chè muûc, chuí yãúu laì chè muûc tæì t ,mäùi tæì bàõt âáöu cuía khäúi seî âæåüc âæa lãn pháön tiãu âãö cuìng våïi âëa chè bàõt âáöu cuía khäúi âoï. Tiãúp tuûc caïc thaình pháön khaïc seî âæåüc xáy dæûng chè muûc tæång tæû. Cáúu truïc âæåüc mä taí nhæ hçnh dæåïi âáy : t1 150 t2 400 .......... tn 4250 150 400 4250 T1 Ft1 6250 ........... T2 Ft2 8500 ........... ......... .......... ........... ........... Tn Ftn 25500 ........... 6250 D1 fd1 , t1 d2 fd2 , t2 ....... 8500 d1 fd1 ,t2 D2 Fd2 , t2 ........ ......... ........ ...... 25500 D1 fd1 , tn d2 fd2 , tn ....... Hçnh 3.10 : Cáúu truïc chè muûc cho tãûp âaío Vê duû sau minh hoüa cho mä hçnh tãûp âaío trãn våïi cå såí dæî liãûu chè muûc âæåüc trçnh baìy åí H 3.2. Baío Vuî 150 Âæåüc 400 Taïc pháøm 650 ........ 150 400 650 Caïc 1 300 Caïch maûng 1 450 Cuía 1 600 Giaíi 1 750 Giåïi thiãûu 1 900 Måïi 1 1050 Taïc giaí 2 1350 Thå 1 1500 Truyãûn ngàõn 2 1800 ........... ..... ....... 300 4 1 450 2 1 600 4 1 750 3 1 900 3 1 1050 3 1 1350 1 1 4 1 1500 2 1 1800 2 1 4 1 ......... ......... .......... Hçnh 3.11 :Tãûp âaío cho cå såí dæî liãûu trçnh baìy åí H 3.2 Giaíi thuáût xáy dæûng chè muûc âaío: Giaíi thuáût xáy dæûng chè muûc âaío cho bäü sæu táûp vàn baín: Khåíi taûo cáúu truïc tæì âiãøn räùng S Våïi mäùi vàn baín d trong bäü sæu táûp {1 £ d £ N} (a). Âoüc vàn baín d (b). Våïi mäùi tæì t Î d Âàût fd , t bàòng säú láön xuáút hiãûn tæì t trong d Tçm kiãúm t trãn S Nãúu t Ï S , cheìn t vaìo S , khåíi âäüng danh saïch âaío It räùng Thãm càûp ( d , fd , t ) vaìo It Våïi mäùi tæì t Î S (a). Bàõt âáöu mäüt muûc âaío måïi (b). Ghi danh saïch âaío vaìo tãûp âaío. CHÆÅNG 4 XÆÍ LYÏ VÁÚN TIN LOGIC Phán têch yãu cáöu váún tin : Âäúi våïi hãû thäúng truy tçm thäng tin thç yãu cáöu váún tin laì mäüt pháön ráút quan troüng khäng thãø taïch råìi khoíi hãû thäúng. Trãn cå såí dæî kiãûn cuía yãu cáöu, hãû thäúng seî xæí lyï yãu cáöu vaì âæa ra caïc kãút quaí tæång æïng våïi dæî kiãûn yãu cáöu âoï. Mäüt yãu cáöu váún tin dæûa trãn ngän ngæî tæû nhiãn, noï coï thãø laì mäüt tæì hay laì mäüt chuäùi caïc tæì âæåüc liãn kãút våïi nhau bàòng caïc pheïp quan hãû logic nhæ pheïp AND, OR vaì NOT nhæ âaî giåïi thiãûu åí chæång måí âáöu. Trãn thæûc tãú, caïc yãu cáöu váún tin chuí yãúu sæí duûng hai pheïp quan hãû laì AND vaì OR båíi vç noï gáön våïi ngän ngæî tæû nhiãn coìn pheïp NOT ráút êt khi âæåüc duìng, mäüt pháön cuîng do thoïi quen ngæåìi sæí duûng. Våïi lyï do âoï kãút håüp våïi âiãöu kiãûn thåìi gian coï haûn nãn trong âäö aïn naìy em chè xæí lyï yãu cáöu váún tin våïi caïc pheïp logic AND vaì OR. Mäùi yãu cáöu váún tin âãöu täön taûi cáy cuï phaïp cuía noï. Quaï trçnh tçm ra cáy cuï phaïp cuía mäüt yãu cáöu âæåüc goüi laì quaï trçnh phán têch cuï phaïp yãu cáöu âoï. Quaï trçnh phán têch cuï phaïp âæåüc thæûc hiãûn dæûa trãn cå såí caïc luáût cuï phaïp cuía ngän ngæî, âæåüc goüi laì luáût sinh. Cuï phaïp cuía ngän ngæî laì táûp luáût sinh, noï cung cáúp cho ta mäúi quan hãû giæîa mäùi cáu cuía ngän ngæî våïi cáúu truïc cuï phaïp. Kãút quaí cuía quaï trçnh phán têch cuï phaïp cuía mäüt yãu cáöu laì cáúu truïc cuï phaïp âæåüc biãøu diãùn bàòng cáúu truïc cáy coìn goüi laì cáy cuï phaïp hay cáy phán têch. Våïi mäüt yãu cáöu vaì táûp luáût sinh cho træåïc thç bäü phán têch cuï phaïp seî tæû âäüng tçm ra cáy cuï phaïp cho yãu cáöu âoï. Khi cáy cuï phaïp âæåüc xáy dæûng xong thç quaï trçnh phán têch cuï phaïp cuía yãu cáöu cuîng kãút thuïc thaình cäng. Ngæåüc laûi, nãúu bäü phán têch cuï phaïp aïp duûng táút caí caïc luáût sinh hiãûn coï nhæng khäng thãø xáy dæûng âæåüc cáy cuï phaïp cuía yãu cáöu cho træåïc thç bäü phán têch cuï phaïp seî thäng baïo ràòng yãu cáöu âaî viãút sai cuï phaïp. Bäü phán têch hoaût âäüng theo så âäö dëch nhæ sau: Åí traûng thaïi bàõt âáöu bäü phán têch khåíi âäüng laìm viãûc våïi kyï hiãûu âáöu tiãn. Sau mäüt säú haình vi noï âaût âãún traûng thaïi s. Tæì traûng thaïi s våïi caûnh coï tãn laì kyï hiãûu kãút thuïc a, bäü phán têch seî âi âãún traûng thaïi t, nãúu kyï hiãûu kãú tiãúp laì a. Sau âoï bäü phán têch seî chuyãøn âáöu âoüc sang phaíi mäüt kyï hiãûu. Ngæåüc laûi, nãúu caûnh xuáút phaït tæì s coï tãn laì kyï hiãûu khäng kãút thuïc A, thç bäü phán têch seî âi âãún traûng thaïi bàõt âáöu cuía så âäö A, âáöu âoüc khäng dëch chuyãøn.Sau khi bäü phán têch âaût âãún traûng thaïi kãút thuïc cuía A, noï láûp tæïc âi âãún traûng thaïi t. Nãúu caûnh tæì s âãún t coï tãn laì kyï hiãûu räùng, bäü phán têch seî âi tæì s âãún ngay t maì khäng âoüc kyï hiãûu tiãúp. Bäü phán têch khi hoaût âäüng trãn cå såí cuía så âäö dëch, noï luän cäú gàõng so truìng kyï hiãûu âæåüc âoüc våïi caûnh coï tãn laì kyï hiãûu kãút thuïc. Khi caûnh coï tãn laì kyï hiãûu khäng kãút thuïc, bäü phán têch seî taûo ra lãûnh goüi thuí tuûc âãû quy tæång æïng. Mäüt yãu cáöu váún tin coï thãø xem laì mäüt biãøu thæïc logic. Vàn phaûm biãøu thæïc logic âæåüc xáy dæng nhæ sau: E à E Ù T | T T à T Ú F | F F à ( E ) | dh Ta coï thãø loaûi boí âãû quy traïi âån giaín cho E vaì T, luáût sinh nhæ sau: E à TE’ E’ à ÙTE’ | Î T à FT’ T’ à ÚFT’ | Î F à ( E ) | dh Báy giåì ta taûo så âäö dëch cho vàn phaûm trãn: Âáöu tiãn chuïng ta taûo så âäö truyãön cho tæìng kyï hiãûu khäng kãút thuïc cuía vàn phaûm, noï laì vãú traïi cuía luáût sinh. 2 0 1 E : E’ T 9 7 8 T : T’ F 6 3 4 E’: T Ù 5 E’ Î 10 11 T’: F Ú 12 T’ 13 Î 14 15 F : E ( 16 ) 17 dh Hçnh 4.1 : Så âäö dëch cuía caïc kyï hiãûu khäng kãút thuïc cuía vàn phaûm Traûng thaïi 3 cuía så âäö E’ vaì traûng thaïi 10 cuía så âäö T’ coï hai sæû truyãön. Mäüt trong hai sæû truyãön âoï laì sæû truyãön räùng. Nhæ váûy nãúu tæì traûng thaïi 3, ta seî thæûc hiãûn sæû truyãön trãn kyï hiãûu Ù, nãúu kyï hiãûu nháûp âæåüc âoüc laì Ù, ngæåüc laûi seî thæûc hiãûn sæû truyãön räùng. Tæång tæû nhæ thãú tæì traûng thaïi 10 trãn kyï hiãûu Ú, hoàûc räùng. Caïc så âäö åí hçnh 4.1 coï thãø thu goün laûi. Træåïc tiãn ta thu goün så âäö dëch cho E. Âãø thu goün så âäö dëch cho E, ta tiãún haình thu goün så âäö dëch cho E’. 6 3 4 E’ : T Ù 5 Î Î 6 3 4 Ù T Î Thu goün tiãúp E’: Ta thay så âäö E’ âaî thu goün vaìo vë trê E’ trong så âäö cuía E. 6 0 3 E: Ù T 4 T Î 6 0 3 T Ù Î Thu goün tiãúp E: Tæång tæû ta thu goün så âäö dëch cuía T. Âáöu tiãn ta cuîng seî thu goün så âäö dëch cuía T’. 10 11 T’: F Ú 12 T’ 13 Î 10 11 T’: F Ú 12 13 Î Î 10 11 Ú 13 Î F Thu goün tiãúp T’: Thu goün T’: Thay så âäö T’ âaî thu goün vaìo så âäö cuía T. 10 11 Ú 13 Î F 7 7 10 13 Î F Thu goün T: Cuäúi cuìng ta coï så âäö dëch kãút quaí cho E , T , F nhæ H.4.2. 14 15 F : E ( 16 ) 17 dh 6 0 3 T Ù Î E : 7 10 13 Î F T : Hçnh 4.2 : Så âäö dëch âaî âæåüc thu goün cuía caïc kyï hiãûu khäng kãút thuïc Sau khi coï så âäö dëch kãút quaí, ta bàõt âáöu xáy dæûng chæång trçnh phán têch cuï phaïp cho caïc yãu cáöu logic. Giaíi thuáût nhæ sau: E ( ) { T ( ); While c = ‘Ù’ do T ( ); } T ( ) { F ( ); While c = ‘Ú ‘ do F ( ); } F ( ) { if ( c = ‘( ‘) { match ( ‘ ( ‘); E ( ); match ( ‘ ) ‘); } else { if ( c = dh) match ( dh ); else error( ); } } match ( w ) { if ( w = c) doctu( ); else error( ); } doctu ( ) { if ( pt < strlen(p)) { while (pt < strlen(p) and p[pt] = ‘ ’) pt++; while (pt < strlen(p) and p[pt] != ‘ ’) { c[i] = p[pt]; i++; pt++; } c[i] = ‘\0’; } else printf(” het yeu cau” ); } Trong âoï doctu( ) laì thuí tuûc âoüc tæì kãú tiãúp, c laì tæì âaî âoüc. Match ( ) laì thuí tuûc so truìng vaì error ( ) laì thuí tuûc baïo läùi. Theo caïc nhaì nghiãn cæïu thç chæång trçnh phán têch cuï phaïp dæûa trãn så âäö dëch âaî âæåüc thu goün seî thæûc thi nhanh hån 20% - 25% so våïi chæång trçnh phán têch cuía så âäö dëch chæa âæåüc thu goün. Xæí lyï caïc pheïp logic: Tênh âuïng âàõn cuía hãû thäúng phuû thuäüc chênh vaìo kãút quaí cuía quaï trçnh xæí lyï caïc pheïp logic. Quaï trçnh xæí lyï âuïng thç hãû thäúng seî âaïp æïng näüi dung mäüt caïch chênh xaïc tæång æïng våïi yãu cáöu váún tin vaì ngæåüc laûi seî cho mäüt kãút quaí sai khäng thoaí maîn yãu cáöu. Nhæ váûy cäng viãûc xæí lyï caïc pheïp logic laì mäüt pháön quan troüng quyãút âënh sæû thaình cäng cuía hãû thäúng truy tçm thäng tin. Nhæ âaî trçnh baìy åí caïc chæång træåïc, âäúi våïi mäùi tæì khaïc biãût trong cå såí dæî liãûu seî coï mäüt danh saïch âaío tæång æïng. Danh saïch âaío cuía mäüt tæì laì mäüt danh saïch læu træî caïc säú hiãûu vàn baín maì coï chæïa tæì âoï. Theo caïch thæïc xáy dæûng cáúu truïc danh saïch âaî phán têch åí caïc chæång træåïc thç danh saïch laì coï thæï tæû. Quaï trçnh xæí lyï caïc pheïp logic laì dæûa trãn caïc danh saïch naìy. Giaí sæí ta coï 2 daîy coï cuìng thæï tæû, daîy x gäöm m pháön tæí vaì daîy y gäöm n pháön tæí. Ta choün 2 daîy naìy âãø taûo ra mäüt daîy z coï säú pháön tæí laì kãút quaí cuía pheïp AND vaì OR cuía 2 giaï trë m vaì n. Ta goüi i , j , k láön læåüt laì chè säú cuía caïc daîy x , y , z. Pheïp AND: Våïi pheïp AND thç kãút quía âæåüc læu trong z laì caïc pháön tæí maì væìa coï trong x laûi væìa coï trong y. Thuáût toaïn nhæ sau: xuáút phaït taûi pháön tæí âáöu tiãn cuía x vaì y trong khi x vaì y chæa kãút thuïc (a). Nãúu x[i] = y[j] thç gaïn z[k] = x[i] tàng i , j vaì k (b). Nãúu x[i] < y[j] thç tàng i (c). Coìn khäng thç tàng j våïi mäùi k Î z (a). Xaïc âënh âëa chè cuía vàn baín d (b). Traí vãö vaì hiãøn thë cho ngæåìi váún tin Hçnh 4.3 : Thuáût toaïn xæí lyï pheïp logic AND Thuí tuûc pheïp xæí lyï AND âæåüc xáy dæûng nhæ sau: void xu_ly_and ( int z[30]; int n ) { int i, j, k; i = j = k =0; while ( ( i < m ) || ( j < n ) ) { if ( x[i] = y[j] ) { z[k] = x[i]; i++; j++; k++; } else { if ( x[i] < y[j] ) i++; else j++; } } } Pheïp OR: Âäúi våïi pheïp logic OR thç sau khi thæûc hiãûn z seî coï säú pháön tæí låïn hån hoàûc bàòng säú pháön tæí trong x hoàûc trong y. Thuáût toaïn âæåüc trçnh baìy åí hçnh 4.4. xuáút phaït taûi pháön tæí âáöu tiãn cuía x vaì y trong khi x vaì y chæa kãút thuïc (a). Nãúu x[i] <= y[j] thç gaïn z[k] = x[i] tàng i vaì k (b). Coìn khäng thç gaïn z[k] = y[j] tàng j vaì k trong khi x coìn vaì y âaî hãút (a). Gaïn z[k] = x[i] (b). Tàng i vaì k trong khi y coìn vaì x âaî hãút (a). Gaïn z[k] = y[j] (b). Tàng j vaì k Hçnh 4.4 : Thuáût toaïn xæí lyï pheïp logic OR Thuí tuûc pheïp xæí lyï OR âæåüc xáy dæûng nhæ sau: void xu_ly_or ( int z[30]; int n ) { int i, j, k; i = j = k =0; while ( ( i < m ) || ( j < n ) ) { if ( x[i] <= y[j] ) { z[k] = x[i]; i++; k++; } else { z[k] = y[j] ) j++; k++; } } while ( i < m ) { z[k] = x[i]; i++; k++; } while ( j < n) { z[k] = y[j]; j++; k++; } } Kãút luáûn: Qua nhæîng gç phán têch åí trãn thç coï thãø khàóng âënh ràòng hãû thäúng truy tçm thäng tin coï khaí nàng âaïp æïng âæåüc táút caí caïc yãu cáöu váún tin våïi caïc pheïp AND vaì OR cuía ngæåìi sæí duûng mäüt caïch chênh xaïc. Âäöng thåìi coìn coï khaí nàng kiãøm tra cuï phaïp cuía yãu cáöu váún tin. Nãúu mäüt yãu cáöu viãút sai cuï phaïp thç hãû thäúng seî baïo läùi coìn khäng thç seî phán têch vaì âaïp æïng yãu cáöu âoï. Tuy nhiãn âoï måïi chè laì cå såí lyï thuyãút, âãø chæïng minh tênh æu viãûc cuía hãû thäúng thç cáön phaíi thæí nghiãûm nhiãöu trãn nhiãöu cå såí dæî liãûu khaïc nhau vaì viãûc âæa hãû thäúng vaìo æïng duûng thæûc tãú laì caïch âaïnh giaï täút nháút. CHÆÅNG 5 THIÃÚT KÃÚ HÃÛ THÄÚNG VAÌ THÆÛC NGHIÃÛM Muûc âêch xáy dæûng hãû thäúng: Ngaìy nay, sæû buìng näø cuía thäng tin laì thaïch thæïc maì con ngæåìi phaíi luän âäúi màût, laìm thãú naìo âãø coï thãø tçm âæåüc caïc thäng tin quan troüng vaì cáön thiãút mäüt caïch nhanh nháút. Tæì nhu cáöu âoï, nhiãöu hãû thäúng truy tçm thäng tin âaî ra âåìi goïp pháön âaïp æïng âæåüc caïc yãu cáöu cuía ngæåìi váún tin. Våïi mäùi hãû thäúng, viãûc xáy dæûng coï thãø càn cæï trãn caïc cå chãú khaïc nhau. Mäùi mäüt cå chãú âãöu coï nhæîng æu thãú riãng. Nhæ âaî trçnh baìy åí caïc chæång træåïc, trong âäö aïn naìy hãû thäúng âæåüc xáy dæûng trãn cå chãú chè muûc âaío vaì khäng ngoaìi muûc âêch laì truy tçm vàn baín âaïp æïng âæåüc nhu cáöu tra cæïu thäng tin. Så âäö doìng thäng tin cuía hãû thäúng âæåüc mä taí nhæ sau: CSDL Vàn baín CSDL Chè muûc Bäü xæí lyï Bäü pháûn giao tiãúp 1 6 2 3 4 5 Hçnh 5.1 : Så âäö mä taí doìng thäng tin Yãu cáöu váún tin (4) Säú hiãûu vàn baín Caïc tæì (5) Näüi dung vàn baín Caïc danh saïch âaío (6) Kãút quaí âaïp æïng Mä hçnh phán cáúp chæïc nàng: Mä hçnh phán cáúp chæïc nàng cuía hãû thäúng giuïp cho ngæåìi sæí duûng tiãúp cáûn hãû thäúng mäüt caïch tæåìng minh. Mäüt hãû thäúng nháút thiãút phaíi coï chæïc nàng naìy. Mä hçnh âæåüc thiãút kãú nhæ hçnh 5.2 TRA CÆÏU VÀN BAÍN Cáûp nháût Thäng tin tra cæïu Tråü giuïp Thoaït Hçnh 5.2 : Mä hçnh phán cáúp chæïc nàng Ê Chæïc nàng cáûp nháût vàn baín Âäúi våïi mäùi hãû thäúng âæåüc xáy dæûng våïi cå såí dæî liãûu âäüng thç chæïc nàng naìy laì khäng thãø thiãúu. Noï cho pheïp ngæåìi sæí duûng hãû thäúng bäø sung vàn baín vaìo cå såí dæî liãûu mäüt caïch dãù daìng. Nhæ âaî giåïi thiãûu thç caïc vàn baín âæåüc xáy dæûng trãn mäüt âoaûn våïi kêch thæåïc täúi âa laì 1000 Byte (khoaíng 150 - 200 tæì) nhàòm muûc âêch xáy dæûng chè muûc. Nguyãn tàõt cuía chæïc nàng cáûp nháût vàn baín laì caïc vàn baín cáûp nháût âæåüc bäø sung vaìo cuäúi cå såí dæî liãûu âang âæåüc sæí duûng. Ë Chæïc nàng thäng tin tra cæïu Âáy laì chæïc nàng chênh cuía hãû thäúng, laì mäi træåìng giao tiãúp giæîa hãû thäúng vaì ngæåìi váún tin. Caïc yãu cáöu váún tin âæåüc âæa vaìo hãû thäúng thäng qua chæïc nàng naìy. Trãn cå såí caïc yãu cáöu naìy, hãû thäúng seî phán têch, xæí lyï vaì âæa ra kãút quaí tæång æïng våïi yãu cáöu. Chæïc nàng thäng tin tra cæïu laì chæïc nàng quan troüng nháút trong caïc chæïc nàng. Ì Chæïc nàng tråü giuïp Chæïc nàng naìy cho pheïp ngæåìi sæí duûng hiãøu vãö caïch thæïc hoaût âäüng cuía hãû thäúng vaì caïch sæí duûng hãû thäúng nhæ thãú naìo. Âäúi våïi mäüt hãû thäúng thç chæïc nàng naìy cuîng cáön thiãút, noï giuïp ngæåìi sæí duûng tiãúp cáûn hãû thäúng mäüt caïch dãù daìng. Tuy nhiãn âáy chè laì thäng tin mang tênh cháút tham khaío. Caïc thäng tin tråü giuïp åí âáy bao gäöm: Hæåïng dáùn ngæåìi váún tin âæa vaìo caïc yãu cáöu håüp lãû. Hæåïng dáùn ngæåìi váún tin cáûp nháût vàn baín cho hiãûu quaí Caïc thäng tin khaïc vãö hãû thäúng. Í Chæïc nàng thoaït Cho pheïp ngæåìi duìng thoaït khoíi hãû thäúng laìm viãûc tæïc laì ngæìng moüi hoaût âäüng tra cæïu hay caïc pheïp bäø sung vàn baín. Chæïc nàng naìy coï veî âån giaín nhæng ráút phæïc taûp vç phaíi hoaìn traí laûi bäü nhåï cå såí dæî liãûu maì hãû thäúng chiãúm giæî. Xáy dæûng chæång trçnh Ngän ngæî sæí duûng Trãn thæûc tãú âaî coï nhiãöu hãû thäúng truy tçm thäng tin âæåüc xáy dæûng trãn nhiãöu ngän ngæî khaïc nhau. Mäùi mäüt loaûi æïng duûng âæåüc viãút bàòng mäüt mäüt ngän ngæî naìo âoï âãöu coï hãû thäúng truy tçm thäng tin tæång æïng våïi noï. Âäö aïn naìy chuí yãúu mang tênh cháút nghiãn cæïu nãn hãû thäúng truy tçm vàn baín âæåüc viãút bàòng ngän ngæî láûp trçnh TURBO C++ 3.0 for Dos. Xáy dæûng cå såí dæî liãûu Âãø âaïp æïng nhu cáöu nàõm bàõt thäng tin nhanh choïng cuía con ngæåìi træåïc sæû buìng näø cuía thäng tin thç viãûc loüc thäng tin mäüt caïch khoa hoüc laì ráút cáön thiãút. Caïc vàn baín mang thäng tin ráút âa daûng vaì phong phuï vç thãú seî âæåüc thu gon laûi bàòng caïch loaûi boí nhæîng tæì thäng duûng vaì giæî laûi näüi dung troüng tám nháút. Mäùi vàn baín nhæ váûy bao gäöm khoaíng 150 âãún 200 tæì. Caïc vàn baín âæåüc táûp håüp laûi taûo thaình cå såí dæî liãûu cuía hãû thäúng. Säú hiãûu cuía vàn baín laì säú thæï tæû khi nháûp vàn baín vaìo cå såí dæî liãûu. Trong cå såí dæî liãûu, caïc vàn baín âæåüc âàût caïch nhau båíi dáúu ngàõt doìng vaì mäüt khoaíng träúng. Xáy dæûng chæång trçnh Chæång trçnh âæåüc xáy dæûng qua tæìng pháön nhæ sau: Ê Xáy dæûng chè muûc âaío Pháön naìy coï nhiãûm vuû laì xáy dæûng chè muûc tãûp âaío cho cå såí dæî liãûu vàn baín âaî coï. Cäng viãûc naìy âæåüc thæûc hiãûn thäng qua mäüt säú haìm con coï chæïc nàng khaïc nhau. \ Chuáøn hoaï tæì: Muûc âêch cuía chæïc nàng naìy laì trêch ra nhæîng tæì mong muäún våïi mäùi vàn baín trong cå såí dæî liãûu. Hãû thäúng truy tçm thäng tin âæåüc xáy dæûng cho cå såí dæî liãûu vàn baín tiãúng Viãût, mäüt ngän ngæî coï cáúu truïc ngæî phaïp ráút phæïc taûp. Trong giåïi haûn cuía âäö aïn naìy khäng âãö cáûp âãún viãûc xæí lyï tæì ngæî tiãúng Viãût nãn chæïc nàng chuáøn hoaï tæì laì cáön thiãút. Trêch tæì coï thãø xæí lyï theo nhiãöu caïch khaïc nhau nhæ trêch tæì theo caïch cäüng däön kyï tæû hay trêch tæì træûc tiãúp. ÅÍ âáy nghiãn cæïu caïch thæïc trêch tæì træûc tiãúp, caïc pheïp toaïn trêch tæì âi cuìng våïi viãûc xæí lyï so saïnh choün ra tæì phuì håüp. Caïc tæì âæåüc xæí lyï bàõt buäüc phaíi coï daûng chæî thæåìng. Vç váûy sau khi trêch tæì, caïc tæì âãöu phaíi chuyãøn sang máùu tæû thæåìng. \ Xáy dæûng cáy tçm kiãúm chè muûc âaío: Muûc âêch laì xáy dæûng chè muûc cho táút caí caïc tæì khaïc nhau trong cå såí dæî liãûu. Trong chæång trçnh sæí duûng cáy tçm kiãúm nhë phán båíi æu âiãøm cuía noï. Ø Khaí nàng sàõp xãúp caïc tæì theo thæï tæû abc Ø Thêch håüp våïi pheïp tçm kiãúm vaì bäø sung vaìo cáy. Âãø tiãún haình xáy dæûng cáy tçm kiãúm chè muûc âaío cáön khåíi taûo cáy våïi gäúc laì tæì âáöu tiãn xuáút hiãûn trong cå såí dæî liãûu. Tiãúp theo xáy dæûng danh saïch âaío cho tæì âoï våïi mäùi pháön tæí trong danh saïch âaío laì mäüt càûp : säú hiãûu vàn baín vaì säú láön xuáút hiãûn tæì trong vàn baín âoï. Do âoï säú pháön tæí trong danh saïch âaío cho biãút säú læåüng vàn baín coï chæïa tæì âoï trong cå såí dæî liãûu. Tæång tæû cho caïc tæì khaïc nhau trong cå såí dæî liãûu. \ Xáy dæûng tãûp âaío: Âáy laì cå såí dæî liãûu kãút quaí cho quïa trçnh xáy dæûng chè muûc, tuy nhiãn mä hçnh tãûp tin naìy cho pheïp bäú trê nhiãöu caïch khaïc nhau. Bàòng nhæîng phán têch vaì âaïnh giaï åí pháön træåïc, ta âaî xáy dæûng tãûp âaío våïi cáúu truïc hiãûu quaí nháút. Caïch thæïc xáy dæûng cáúu truïc bãn trong tãûp âaío seî quyãút âënh täúc âäü truy tçm thäng tin trãn tãûp âaío âoï. Tæì âoï seî aính hæåíng âãún täúc âäü cuía caí hãû thäúng. Nhæ váûy giaíi thuáût chung cuía táút caí caïcpháön coï thãø så læåüc nhæ sau Chuáøn hoïa âäúi våïi mäùi vàn baín trong cå såí dæî liãûu Xáy dæûng cáy tçm kiãúm chè muûc âaío (a). Xáy dæûng cáy (b). Våïi mäùi tæì khaïc nhau, xáy dæûng danh saïch âaío Xáy dæûng tãûp âaío Ë Xáy dæûng chæång trçnh váún tin Pháön naìy âæåüc xáy dæûng våïi muûc âêch laì tçm caïc vàn baín trong cå såí dæî liãûu thoaí maîn yãu cáöu váún tin naìo âoï. Trong âäö aïn naìy, caïc yãu cáöu sæí duûng cå chãú váún tin logic. Quaï trçnh xáy dæûng thäng qua caïc haìm coï chæïc nàng khaïc nhau vaì âæåüc cå cáúu nhæ sau: \ Så læåüc giaíi thuáût Phán têch yãu cáöu Våïi mäùi tæì thuäüc yãu cáöu (a). Tçm danh saïch âaío tæång æïng våïi tæì âoï (b). Thæûc hiãûn caïc pheïp logic tæång æïng vaì âæa ra caïc säú hiãûu vàn baín Hiãøn thë näüi dung kãút quaí tçm âæåüc cho ngæåìi váún tin \ Phán têch yãu cáöu Pháön naìy coï nhiãûm vuû kiãøm tra cuï phaïp cuía yãu cáöu váún tin. Mäüt yãu cáöu váún tin daûng logic coï thãø coi laì mäüt biãúu thæïc toaïn hoüc vç váûy noï coï tráût tæû vaì pheïp æu tiãn. Nãúu mäüt yãu cáöu váún tin âæa vaìo hãû thäúng khäng âuïng cuï phaïp thç pháön naìy seî kiãøm tra vaì baïo läùi cho ngæåìi sæí duûng biãút. \ Xæí lyï yãu cáöu Quaï trçnh xæí lyï yãu cáöu tiãún haình âäöng thåìi våïi quaï trçnh phán têch. Pháön naìy coï chæïc nàng chuyãøn âäøi caïc tæì trong yãu cáöu váún tin vãö daûng chæî thæåìng, sau âoï tçm ra caïc säú hiãûu vàn baín tæång æïng våïi tæì âoï vaì thæûc hiãûn caïc pheïp logic âãø âæa ra kãút quaí chung nháút. \ Hiãøn thë kãút quaí Muûc âêch cuía pháön naìy laì hiãøn thë näüi dung caïc vàn baín æïng våïi caïc säú hiãûu vàn baín trong táûp kãút quaí cho ngæåìi váún tin. Phæång phaïp hiãøn thë theo caïch træûc tiãúp âãún tæìng vàn baín bàòng caïch xaïc âënh âëa chè bàõt âáöu vaì kêch thæåïc cuía vàn baín âoï. Thæûc nghiãûm: Bàòng nhæîng phán têch vaì láûp luáûn trãn cå såí lyï thuyãút qua caïc chæång træåïc ta âaî cå baín hoaìn thaình mäüt hãû thäúng truy tçm thäng tin âæåüc xáy dæûng bàòng cå chãú chè muûc âaío. Hãû thäúng âæåüc xáy dæûng gäöm hai pháön :xáy dæûng chè muûc âaío vaì cå chãú váún tin daûng logic. Trong âäö aïn naìy chuí yãúu âi sáu vaìo nghiãn cæïu cå chãú xáy dæûng chè muûc âaío vaì xæí lyï váún tin laì hçnh thæïc âaïnh giaï tênh hiãûu quaí cuía cå chãú âoï qua nhiãöu cå såí dæî liãûu khaïc nhau. Nhàòm xáy dæûng mäüt hãû thäúng truy tçm thäng tin æïng duûng trong tra cæïu saïch thæ viãûn, âäö aïn naìy sæí duûng cå såí dæî liãûu vàn baín laì mäüt bäü sæu táûp saïch. Bäü sæu táûp saïch bao gäöm nhæîng näüi dung toïm tàõt cuía caïc loaûi saïch thuäüc nhiãöu lénh væûc khaïc nhau. Sau âáy laì mäüt säú thæí nghiãûm thæûc tãú trãn hãû thäúng 1/ Våïi mäüt yãu cáöu váún tin laì mäüt tæì : “ Taïc_pháøm ” Ta coï kãút quaí nhæ sau: HÃÛ THÄÚNG TRA CÆÏU VÀN BAÍN Cáûp nháût vàn baín Thäng tin tra cæïu Tråü giuïp Thoaït Máy nuïi thaïi haìng Truyãûn ngàõn treí choün loüc 15 truyãûn ngàõn cuía taïc giaí Baío Vuî trong táûp saïch naìy, dáùu viãút vãö tçnh yãu, cuäc säúng våïi nhæîng bæån chaíi cuía låïp ngæåìi treí tuäøi vãö tçnh caím, nãúp säúng, suy tæ cuía ngæåìi giaì trong hiãûn taûi hay khi láût laûi nhæîng têch cuî váùn luän luän thäøi vaìo nhæîng trang vàn håi thåí cuía nhëp säúng âæång âaûi, tæåi måïi. Trong táûp coï nhiãöu taïc pháøm läi cuäún nhæ : Tráöu tãm caïnh phæåüng, Máy nuïi thaïi haìng... Máy nuïi thaïi haìng 2/ Våïi yãu cáöu laì pheïp AND : “ khoa_hoüc AND kyî_thuáût AND maïy_tênh “ Kãút quaí nhæ sau: Trçnh biãn dëch Láûp trçnh hãû thäúng Trçnh biãn dëch laì mäüt män cuía ngaình khoa hoüc maïy tênh. Cuìng våïi sæû phaït triãøn cuía caïc chuyãn ngaình lyï thuyãút ngän ngæî, automat vaì ngän ngæî hçnh thæïc, lyï thuyãút vaì kyî thuáût thiãút kãú trçnh biãn dëch ngaìy caìng hoaìn thiãûn hån. Cuäún saïch naìy nhàòm cung cáúp cå såí lyï thuyãút vaì caïc phæång phaïp cå baín nháút âãø thiãút kãú caïc bäü pháûn cuía trçnh biãn dëch. Saïch âæåüc chia laìm taïm chæång vaì mäüt phuû chæång. HÃÛ THÄÚNG TRA CÆÏU VÀN BAÍN Cáûp nháût vàn baín Thäng tin tra cæïu Tråü giuïp Thoaït 3/ Våïi yãu cáöu laì pheïp OR : “ Giaïo_trçnh OR taûp_chê OR baïo “ Kyî thuáût vi xæí lyï MCSE SQL Server 6.5 Niãn giaïm baïo chê Viãût Nam Âáy laì bäü saïch âáöu tiãn cuía baïo chê Viãût Nam âãö cáûp âãún toaìn caính baïo chê gäöm : baïo, taûp chê, caïc âaìi phaït thanh, caïc âaìi truyãön hçnh, thäng táún xaî, baïo âiãûn tæí. Niãn giaïm baïo chê Viãût Nam giuïp cho viãûc tçm hiãøu : tãn cå quan baïo chê, cå quan chuí quaín, ngän ngæî thãø hiãûn, täøng biãn táûp, täøng giaïm âäúc, âiãûn thoaûi, fax, email vaì nhiãöu näüi dung khaïc liãn quan âãún baïo chê. HÃÛ THÄÚNG TRA CÆÏU VÀN BAÍN Cáûp nháût vàn baín Thäng tin tra cæïu Tråü giuïp Thoaït 4/ Mäüt yãu cáöu váún tin phæïc håüp : “ ( thå OR truyãûn ) AND tçnh_yãu OR tám_lyï Máy nuïi thaïi haìng Truyãûn ngàõn treí choün loüc Haït rong ( NXB Âaì Nàông ) Saïch táûp håüp 28 truyãûn cuía 28 taïc giaí âaûi diãûn cho âäüi nguî nhæîng ngæåìi viãút vàn treí xuáút hiãûn máúy nàm gáön âáy. Mäùi ngæåìi mäüt neït riãng. Baîo Caït cuía taïc giaí Tráön Thanh Haì háúp dáùn bàòng nhæîng caính huäúng, tçnh tiãút laû. Taïc pháøm “Hai ngæåìi meû” cuía taïc giaí Nguyãùn Vàn Vinh âi sáu phán têch diãùn biãún tám lyï cuía tçnh máùu tæí, gáy xuïc caím. Caïc taïc giaí khaïc våïi nhæîng taïc pháøm nhæ “Riãng chung”, “Chë”, “Thaïng chên” laì nhæîng khaïc khao tiãúc nuäúi træåïc tçnh yãu khäng thaình, nhæng nghë læûc vaì niãöm laûc quan tuäøi treí giuïp hoü nhanh choïng væåüt qua. HÃÛ THÄÚNG TRA CÆÏU VÀN BAÍN Cáûp nháût vàn baín Thäng tin tra cæïu Tråü giuïp Thoaït Qua táút caí caïc láön thæí nghiãûm, ta nháûn tháúy hãû thäúng hoaût âäüng phuì håüp våïi nhæîng gç maì âaî nãu lãn trong pháön lyï thuyãút. Hãû thäúng âaïp æïng âæåüc caïc yãu cáöu váún tin sæí duûng caïc pheïp logic khaïc nhau hoàûc laì caïc yãu cáöu phæïc taûp, kãút håüp nhiãöu quan hãû logic. Toaìn bäü caïc vàn baín coï chæïa näüi dung yãu cáöu âãöu âæåüc hiãøn thë. Nhæ váûy coï thãø khàóng âënh ràòng laì hãû thäúng khäng sai. CHÆÅNG 6 KÃÚT LUÁÛN Kãút quía âaût âæåüc Våïi muûc âêch laì xáy dæûng hãû thäúng truy tçm thäng tin vàn baín dæûa trãn kyî thuáût chè muûc âaío, cho âãún chæång naìy thç ta coï thãø khàóng âënh hãû thäúng âaî cå baín âaût âæåüc muûc âêch. Âäö aïn âaî hoaìn thaình viãûc xáy dæûng chè muûc âaío cho cå såí dæî liãûu vàn baín. Tæì mäüt cå såí dæî liãûu vàn baín ban âáöu, hãû thäúng âaî xáy dæûng nãn mäüt cå såí dæî liãûu chè muûc troün veûn nhàòm phuûc vuû cho quaï trçnh váún tin. Âaî aïp duûng caïc phæång phaïp xæí lyï vaì täø chæïc dæî liãûu coï hiãûu quaí laìm giaím täúi thiãøu khaí nàng chiãúm duûng bäü nhåï vaì thåìi gian thæûc thi chæång trçnh. Âaî xáy dæûng âæåüc chæïc nàng váún tin våïi caïc yãu cáöu daûng logic. Hãû thäúng coï khaí nàng kiãøm tra läùi cuï phaïp cuía yãu cáöu âäöng thåìi xæí lyï yãu cáöu nhanh vaì chênh xaïc âaïp æïng âæåüc näüi dung yãu cáöu cuía ngæåìi váún tin. Hãû thäúng cuîng âæåüc hoaìn thiãûn båíi khaí nàng cáûp nháût vàn baín, cho pheïp bäø sung caïc vàn baín vaìo cå såí dæî liãûu. Haûn chãú Do tênh cháút nghiãn cæïu nãn hãû thäúng âæåüc xáy dæûng trong mäi træåìng Dos nãn giao diãûn khäng âæåüc thán thiãûn våïi ngæåìi sæí duûng. Chæa xæí lyï âæåüc cáúu truïc tæì ngæî trong tiãúng Viãût nãn caïc tæì gheïp âãöu phaíi sæí duûng dáúu gaûch näúi ( _ ) âãø chuáøn hoaï tæì. Chæïc nàng váún tin chæa xæí lyï pheïp NOT vaì NEAR. Hãû thäúng chæa âæåüc thæí nghiãûm våïi cå såí dæî liãûu låïn. Hæåïng phaït triãøn Xáy dæûng mäi træåìng giao tiãúp thán thiãûn våïi ngæåìi sæí duûng Xæí lyï tæì gheïp trong tiãúng Viãût Bäø sung caïc pheïp NOT vaì NEAR. Xáy dæûng cå såí dæî liãûu låïn phuì håüp våïi thæûc tãú. Phaït triãøn hãû thäúng tråí thaình cäng cuû truy váún cho nhiãöu hãû thäúng khaïc våïi caïc cå såí dæî liãûu khaïc nhau. TAÌI LIÃÛU THAM KHAÍO [1] WITTEN, I., MOFFAT, A. AND BELL, T. Managing Gigabytes: Compressing and Indexing Documents and Imagesn (Second ed.). Van Nostrand Reinhold, NewYork, 1998. [2] Phan Thë Tæåi. Trçnh biãn dëch. Træåìng âaûi hoüc kyî thuáût TP HCM, nhaì xuáút baín giaïo duûc. [3] Chuí biãn Thaûc syî Nguyãùn Cáøn. C tham khaío toaìn diãûn (C- The complete reference). Nhaì xuáút baín Âäöng Nai, 1996.