Tài liệu Một số giải pháp cho bài toán tìm kiếm trong csdl hypertext

 Luận văn tốt nghiệp Một số giải pháp cho bài toán tìm kiếm trong CSDL Hypertext 1 Mét sè gi¶i ph¸p cho bµi to¸n t×m kiÕm trong CSDL Hypertext PhÇn më ®Çu……………………………………………………………………………….2 Ch−¬ng I. Tæng quan vÒ web-mining ...................................................................... 9 1.1 Giíi thiÖu vÒ c¬ së d÷ liÖu Fulltext vµ Hypertext ....................................................... 9 1.1.1 C¬ së d÷ liÖu Fulltext.......................................................................................... 9 1.1.2 C¬ së d÷ liÖu Hypertext .................................................................................... 12 1.1.3 So s¸nh ®Æc ®iÓm cña d÷ liÖu Fulltext vµ d÷ liÖu trang web ............................. 15 1.2 Tæng quan vÒ ph−¬ng ph¸p biÓu diÔn v¨n b¶n trong c¬ së d÷ liÖu trang web .......... 16 1.2.1 Giíi thiÖu s¬ bé vÒ c¸c ph−¬ng ph¸p biÓu diÔn trang web................................ 17 1.2.2 C¸ch tiÕp cËn theo web site............................................................................... 19 KÕt luËn ch−¬ng mét............................................................................................................. 28 Ch−¬ng II. Mét sè ph−¬ng ph¸p biÓu diÔn trang web vµ gi¶i ph¸p kÕt hîp. ......................................................................................................................................... 29 2.1 Ph−¬ng ph¸p biÓu diÔn trong c¸c m¸y t×m kiÕm....................................................... 30 2.1.1 CÊu tróc c¬ b¶n vµ ho¹t ®éng cña mét m¸y t×m kiÕm....................................... 31 2.1.2 Ph−¬ng ph¸p biÓu diÔn d÷ liÖu trong c¸c m¸y t×m kiÕm................................... 34 2.2 Ph−¬ng ph¸p biÓu diÔn trang web theo m« h×nh vector ............................................ 45 2.2.1 Ph−¬ng ph¸p biÓu diÔn vector ........................................................................... 45 2.2.2 Ph−¬ng ph¸p biÓu diÔn trang web theo m« h×nh vector .................................... 48 2.3 §Ò xuÊt gi¶i ph¸p biÓu diÔn vector trong m¸y t×m kiÕm ........................................... 55 KÕt luËn ch−¬ng 2 ................................................................................................................. 59 Ch−¬ng III. m¸y t×m kiÕm vietseek vµ thö nghiÖm ThuËt to¸n t×m kiÕm theo néi dung ................................................................................................................... 61 3.1 M¸y t×m kiÕm VietSeek ............................................................................................ 61 3.1.1 C¸c ®Æc ®iÓm c¬ b¶n cña Vietseek.................................................................... 61 3.1.2 C¬ së d÷ liÖu cña Vietseek................................................................................ 62 3.2 §Ò xuÊt thuËt to¸n t×m kiÕm míi cho m¸y t×m kiÕm VietSeek ................................. 69 3.2.1 Nh÷ng c¬ së ®Ó ®Ò xuÊt thuËt to¸n.................................................................... 69 3.2.2 ThuËt to¸n ......................................................................................................... 71 KÕt luËn ch−¬ng 3 ................................................................................................................. 74 PhÇn kÕt luËn……………………………………………………………………………75 tµi liÖu tham kh¶o…………………………………………………………………….77 Ph¹m ThÞ Thanh Nam – LuËn v¨n cao häc 2 Mét sè gi¶i ph¸p cho bµi to¸n t×m kiÕm trong CSDL Hypertext PhÇn më ®Çu Trong nh÷ng n¨m gÇn ®©y, trªn c¬ së ph¸t triÓn vµ øng dông c«ng nghÖ Internet, khèi l−îng d÷ liÖu trªn m¸y tÝnh ®· t¨ng tr−ëng kh«ng ngõng theo c¶ hai ph−¬ng diÖn t¹o míi vµ thu thËp. Sù më réng c¸c d÷ liÖu khoa häc vÒ ®Þa lý, ®Þa chÊt, khÝ t−îng do vÖ tinh thu thËp, sù giíi thiÖu qu¶ng b¸ m· v¹ch ®èi víi hÇu hÕt c¸c s¶n phÈm th−¬ng m¹i, viÖc tin häc ho¸ s©u réng c¸c th−¬ng vô vµ giao dÞch, sù ph¸t triÓn viÖc øng dông CNTT trong qu¶n lý hµnh chÝnh nhµ n−íc ... ®· ph¸t sinh ra mét khèi l−îng d÷ liÖu khæng lå. MÆt kh¸c, trong bèi c¶nh nÒn t¶ng cho mét x· héi th«ng tin, nhu cÇu nhËn ®−îc th«ng tin mét c¸ch nhanh chãng, chÝnh x¸c còng nh− nhu cÇu thu nhËn ®−îc "tri thøc" tõ khèi l−îng th«ng tin khæng lå nãi trªn ®· trë nªn cÊp thiÕt. Bèi c¶nh ®ã ®· ®ßi hái nh÷ng ph−¬ng ph¸p tiÕp cËn míi mµ trong ®ã ®iÓn h×nh nhÊt lµ c¸c ph−¬ng ph¸p thuéc lÜnh vùc khai ph¸ d÷ liÖu vµ kh¸m ph¸ tri thøc trong c¸c c¬ së d÷ liÖu [7,9]. Sù t¨ng tr−ëng hµng n¨m vÒ sè l−îng c«ng tr×nh ®−îc c«ng bè, vÒ héi th¶o khoa häc quèc tÕ liªn quan ®Õn viÖc nghiªn cøu, gi¶i quyÕt tõng b−íc nhiÒu bµi to¸n ®iÓn h×nh thuéc lÜnh vùc nµy ®· thÓ hiÖn ®Çy ®ñ sù ph¸t triÓn v−ît bËc cña lÜnh vùc nãi trªn. C¸c bµi to¸n biÓu diÔn d÷ liÖu, l−u tr÷ d÷ liÖu, t×m kiÕm d÷ liÖu, ph©n líp d÷ liÖu, ph©n côm d÷ liÖu ... [2-4,6,8-14] lµ nh÷ng bµi to¸n ®iÓn h×nh nhÊt. Trong xu thÕ t¨ng tr−ëng kh«ng ngõng nguån d÷ liÖu, th«ng qua sù ph¸t triÓn cña c«ng nghÖ Web, d¹ng d÷ liÖu phi cÊu tróc vµ nöa cÊu tróc (®iÓn h×nh lµ hÖ thèng c¸c trang web trªn Internet) cµng t¨ng tr−ëng theo tèc ®é nh¶y vät. §©y lµ d¹ng d÷ liÖu gÇn nhÊt víi con ng−êi, mµ qua chóng con ng−êi mong muèn l−u tr÷ th«ng tin, tri thøc hoÆc chuyÓn t¶i nã cho nhiÒu ng−êi kh¸c. Trong nh÷ng n¨m gÇn ®©y WWW ®· trë thµnh mét kªnh th«ng tin quan träng nhÊt cho viÖc ph©n t¸n c¸c th«ng tin vÒ c¸ nh©n, khoa häc vµ th−¬ng m¹i. Mét lý do cña viÖc WWW ph¸t triÓn nhanh chãng lµ gi¸ c¶ cho viÖc t¹o vµ xuÊt b¶n c¸c trang web rÊt rÎ. So s¸nh víi c¸c ph−¬ng ph¸p kh¸c nh− s¶n xuÊt tê r¬i hay qu¶ng c¸o trªn b¸o vµ t¹p chÝ th× trang web rÎ h¬n rÊt nhiÒu vµ l¹i ®−îc cËp nhËt th−êng xuyªn h¬n ®Õn hµng tû ng−êi sö dông, v× vËy mµ ngay c¶ c¸c c«ng ty rÊt nhá còng cã kh¶ n¨ng ®−a c¸c s¶n phÈm vµ dÞch vô cña hä lªn WWW. H¬n n÷a cã rÊt nhiÒu Ph¹m ThÞ Thanh Nam – LuËn v¨n cao häc 3 Mét sè gi¶i ph¸p cho bµi to¸n t×m kiÕm trong CSDL Hypertext c¸c c«ng ty ho¹t ®éng b¸n hµng trùc tuyÕn trªn Internet, v× vËy mµ nhu cÇu ®−a c¸c th«ng tin lªn WWW lµ hoµn toµn tù nhiªn. Nh−ng víi viÖc t¨ng kh«ng ngõng c¸c site th× viÖc t×m ra mét trang hay thËm chÝ mét site mµ mçi c¸ nh©n ®ang cÇn l¹i thùc sù lµ mét vÊn ®Ò ngµy cµng khã kh¨n. ViÖc nghiªn cøu c¸c bµi to¸n liªn quan ®Õn hÖ thèng c¸c d÷ liÖu d¹ng nµy (biÓu diÔn v¨n b¶n, t×m kiÕm vµ ph©n líp v¨n b¶n) cïng víi viÖc ®Ò xuÊt nh÷ng gi¶i ph¸p ®èi víi c¸c bµi to¸n ®ã lu«n lµ nh÷ng vÊn ®Ò khoa häc vµ c«ng nghÖ thêi sù [1-4,6,8-14]. Ch¼ng h¹n, vÊn ®Ò ph¸t hiÖn ra mét website míi thùc sù thó vÞ cho ng−êi sö dông lµ mét vÊn ®Ò ch−a ®−îc quan t©m ®óng møc. C¸c hÖ t×m kiÕm trªn Internet hiÖn nay nh− Yahoo, Altavista, Google... lµ nh÷ng hÖ triÓn khai ®Ó gi¶i quyÕt bµi to¸n t×m kiÕm vµ ®−îc sö dông kh¸ phæ biÕn hiÖn nay. Tuy nhiªn vÉn cßn cã c¸c vÊn ®Ò ch−a tho¶ m·n ®−îc nhu cÇu thùc tÕ cña ng−êi sö dông. §ã lµ khi sö dông dÞch vô t×m kiÕm trªn c¸c site nµy th× chØ cã thÓ t×m ®−îc c¸c trang th«ng tin theo nh÷ng ®iÒu kiÖn t×m kiÕm hÕt søc gi¶n ®¬n. Thªm vµo ®ã, cã rÊt nhiÒu tr−êng hîp môc tõ lµ kh«ng trän vÑn vµ ®«i khi qu¸ h¹n v× kh«ng ®−îc cËp nhËt th−êng xuyªn. H¬n n÷a c¸c dÞch vô t×m kiÕm nµy kh«ng cung cÊp tÊt c¶ c¸c lÜnh vùc chuyªn s©u h¬n, nhÊt lµ c¸c lÜnh vùc hÑp cho mét sè ng−êi sö dông ®Æc biÖt. C¸c hÖ nµy còng ch−a cho phÐp khai th¸c nh÷ng th«ng tin truy nhËp cña ng−êi sö dông v× vËy kh«ng cã c¬ chÕ ph¶n håi th«ng tin ®Ó sö dông kÕt qu¶ t×m kiÕm tr−íc ®©y vµo lÇn t×m kiÕm tiÕp theo. C¬ chÕ nµy lµ cÇn thiÕt v× lµm ®−îc nh− vËy hiÖu qu¶ vµ ®é chÝnh x¸c t×m kiÕm ch¾c ch¾n ®−îc n©ng cao. Mét vÊn ®Ò n÷a lµ c¸c hÖ t×m kiÕm nµy th−êng xö lý c¸c yªu cÇu t×m kiÕm d−íi d¹ng c¸c tõ kho¸ t×m kiÕm. Khi cã nhiÒu h¬n mét tõ kho¸ th× hÖ t×m kiÕm xö lý c¸c tõ kho¸ nµy theo cïng mét c¸ch thøc mµ kh«ng cã c¬ chÕ cho phÐp ng−êi sö dông x¸c ®Þnh ®é quan träng kh¸c nhau cho c¸c tõ kho¸ t×m kiÕm. Còng nh− vËy, c¸c hÖ t×m kiÕm ®iÓn h×nh hiÖn nay ch−a quan t©m ®Õn vÊn ®Ò ®ång nghÜa vµ ®a nghÜa cña tõ khãa, v× vËy trong qu¸ tr×nh t×m kiÕm cã thÓ ®· bá qua rÊt nhiÒu c¸c kÕt qu¶ t×m kiÕm. NhiÒu nghiªn cøu liªn quan ®· ®Ò xuÊt mét sè ph−¬ng ph¸p biÓu diÔn v¨n b¶n cho phÐp thi hµnh ®−îc nh÷ng khÝa c¹nh ®· ®Ò cËp trªn ®©y [2-4,8-14]. Ph¹m ThÞ Thanh Nam – LuËn v¨n cao häc 4 Mét sè gi¶i ph¸p cho bµi to¸n t×m kiÕm trong CSDL Hypertext Tõ viÖc t×m hiÓu vµ ph©n tÝch −u, nh−îc ®iÓm cña c¸c ph−¬ng ph¸p tiÕp cËn kh¸c nhau, dùa trªn ý t−ëng n©ng cao hiÖu qu¶ t×m kiÕm, luËn v¨n ®Ò cËp viÖc sö dông m« h×nh vector biÓu diÔn trang web trong c¸c m¸y t×m kiÕm ®Ó cho phÐp dÔ dµng bæ sung träng sè cho c¸c tõ kho¸ t×m kiÕm vµ t¨ng c−êng ®−îc ng÷ nghÜa néi dung v¨n b¶n vµo qu¸ tr×nh t×m kiÕm. Víi môc tiªu ®Ò xuÊt mét ph−¬ng ph¸p biÓu diÔn vector cho c¸c trang web trong c¸c m¸y t×m kiÕm ®Ó n©ng cao hiÖu qu¶ t×m kiÕm, néi dung cña luËn v¨n ®−îc ®Þnh h−íng vµo c¸c vÊn ®Ò sau: - Giíi thiÖu, ph©n tÝch vµ ®¸nh gi¸ mét sè ph−¬ng ph¸p biÓu diÔn trang web ®iÓn h×nh, - Trªn c¬ së mét sè ph−¬ng ph¸p biÓu diÔn v¨n b¶n trang web theo m« h×nh vector, luËn v¨n nghiªn cøu viÖc c¶i tiÕn c¸c ph−¬ng ph¸p biÓu diÔn ®ã ®Ó nhËn ®−îc mét ph−¬ng ph¸p míi biÓu diÔn trang web, - Nghiªn cøu, ®Ò xuÊt viÖc bæ sung thªm biÓu diÔn vector cho trang web trong c¸c m¸y t×m kiÕm theo ph−¬ng ph¸p míi, ®ång thêi bæ sung chøc n¨ng t×m kiÕm trang Web "theo néi dung" cho hÖ t×m kiÕm Vietseek. LuËn v¨n bao gåm PhÇn më ®Çu, ba ch−¬ng néi dung vµ PhÇn kÕt luËn mµ néi dung c¸c ch−¬ng ®−îc tr×nh bµy nh− d−íi ®©y. Ch−¬ng 1 víi tiªu ®Ò lµ Tæng quan vÒ web-mining giíi thiÖu s¬ bé nh÷ng néi dung tæng quan nhÊt vÒ c¬ së d÷ liÖu Fulltext, c¬ së d÷ liÖu Hypertext, c¬ së d÷ liÖu trang web vµ ph−¬ng ph¸p biÓu diÔn vector. Trong ch−¬ng nµy c¸ch tiÕp cËn theo website ®−îc tr×nh bµy kh¸ chi tiÕt vÒ c¶ khÝa c¹nh biÓu diÔn website lÉn gi¶i ph¸p cho bµi to¸n t×m kiÕm theo website. LuËn v¨n cßn ®Ò xuÊt mét thuËt to¸n x©y dùng c©y website theo c¸ch tiÕp cËn nµy. Tiªu ®Ò cña ch−¬ng 2 lµ Mét sè ph−¬ng ph¸p biÓu diÔn d÷ liÖu web vµ gi¶i ph¸p kÕt hîp. Néi dung cña ch−¬ng nµy xem xÐt vµ ®¸nh gi¸ mét sè ph−¬ng ph¸p biÓu diÔn trang web ®iÓn h×nh. §Çu tiªn luËn v¨n giíi thiÖu vÒ biÓu diÔn trang web trong c¸c m¸y t×m kiÕm, sau ®ã luËn v¨n giíi thiÖu c¸ch tiÕp cËn theo m« h×nh vector ®Ó biÓu diÔn Ph¹m ThÞ Thanh Nam – LuËn v¨n cao häc 5 Mét sè gi¶i ph¸p cho bµi to¸n t×m kiÕm trong CSDL Hypertext trang web vµ mét ®Ò xuÊt vÒ mét c¸ch biÓu diÔn trang web. PhÇn cuèi cïng cña ch−¬ng nµy tr×nh bµy ®Ò xuÊt cña luËn v¨n bæ sung c¸ch biÓu diÔn míi cho trang web vµo m¸y t×m kiÕm vµ s¬ bé vÒ thuËt to¸n t×m kiÕm theo néi dung. Ch−¬ng 3 M¸y t×m kiÕm VietSeek vµ thö nghiÖm thuËt to¸n t×m kiÕm theo néi dung giíi thiÖu chi tiÕt vÒ m¸y t×m kiÕm VietSeek, thiÕt kÕ l«gic vÒ d÷ liÖu theo biÓu diÔn vector vµ thuËt to¸n t×m kiÕm theo néi dung trªn c¬ së do luËn v¨n ®Ò xuÊt. PhÇn kÕt luËn tæng hîp nh÷ng kÕt qu¶ nghiªn cøu chÝnh cña luËn v¨n, chØ ra mét sè h¹n chÕ ch−a hoµn thiÖn cµi ®Æt thùc sù. §ång thêi luËn v¨n còng ®Ò xuÊt mét sè h−íng nghiªn cøu cô thÓ tiÕp theo cña t¸c gi¶ luËn v¨n. Ph¹m ThÞ Thanh Nam – LuËn v¨n cao häc 6 Mét sè gi¶i ph¸p cho bµi to¸n t×m kiÕm trong CSDL Hypertext Lêi c¶m ¬n Em xin bµy tá lßng kÝnh träng vµ biÕt ¬n s©u s¾c tíi ThÇy gi¸o TiÕn sÜ Hµ Quang Thuþ, ng−êi ®· tËn t×nh h−íng dÉn luËn v¨n cho em. Em xin c¶m ¬n c¸c ThÇy C« trong khoa C«ng nghÖ, §¹i häc Quèc Gia Hµ Néi, vµ nhãm Xemina chuyªn m«n "Data Mining vµ KDD" thuéc bé m«n C¸c HÖ thèng Th«ng tin, khoa C«ng nghÖ, nh÷ng ng−êi ®· gióp ®ì cho em trong suèt qu¸ tr×nh häc tËp vµ nghiªn cøu, ®Æc biÖt lµ c¸c b¹n Bïi Quang Minh vµ §oµn S¬n. Em xin bµy tá lßng biÕt ¬n s©u s¾c tíi gia ®×nh, c¸c ®ång nghiÖp ë ViÖn C«ng nghÖ Th«ng tin, §¹i häc Quèc gia Hµ Néi, vµ c¸c b¹n bÌ ®· gióp ®ì vµ ®éng viªn em trong suèt qu¸ tr×nh häc tËp, nghiªn cøu vµ lµm viÖc. Hµ Néi ngµy 15/04/2003 Häc viªn Ph¹m ThÞ Thanh Nam Ph¹m ThÞ Thanh Nam – LuËn v¨n cao häc 7 Mét sè gi¶i ph¸p cho bµi to¸n t×m kiÕm trong CSDL Hypertext b¶ng chó gi¶i mét sè côm tõ viÕt t¾t CSDL: C¬ së d÷ liÖu (DataBase) CNTT: C«ng nghÖ th«ng tin (Information Technology) kNN: k Nearest Neighbour KPDL: Khai ph¸ d÷ liÖu (Data Mining) KPTTCSDL: Kh¸m ph¸ tri thøc trong CSDL (Knowledge Discovery in Databases) SVM: Support Vector Machine WWW: HÖ thèng trang Web (World Wide Web) b¶ng chó gi¶i mét sè thuËt ng÷ tiÕng viÖt Bayes tù nhiªn: Naive Bayes k ng−êi l¸ng giÒng gÇn nhÊt: k Nearest Neighbour M¹ng n¬ron: Neural Net M¸y t×m kiÕm: Search engine Bé ®iÒu khiÓn t×m duyÖt: Crawl Control Bé t×m duyÖt: Crawler Bé t¹o chØ môc: Indexer Module Bé ph©n tÝch tËp: Collection Analysis Modele Bé truy vÊn: Query Engine Bé xÕp h¹ng: Ranking Bé ph©n tÝch URL: URLresolver ChØ môc cÊu tróc: Structure Index ChØ môc liªn kÕt ng−îc: Inverted Index ChØ môc néi dung: Text Index ChØ môc tiÖn Ých: Utility Index H¹ng hiÓn thÞ: Rank H¹ng trang web (H¹ng): Page Rank Kho trang web: Page Repository T¶i trang: Download M¸y vector trî gióp: Support Vector Machine Ph¹m ThÞ Thanh Nam – LuËn v¨n cao häc 8 Mét sè gi¶i ph¸p cho bµi to¸n t×m kiÕm trong CSDL Hypertext M« h×nh (kh«ng gian) vector: Vector (Space) Model Siªu liªn kÕt: Hyperlink Siªu v¨n b¶n: Hypertext T×m kiÕm theo néi dung: text-based retrieval Trang web: web page, HTML page, HTML document Ph¹m ThÞ Thanh Nam – LuËn v¨n cao häc 9 Mét sè gi¶i ph¸p cho bµi to¸n t×m kiÕm trong CSDL Hypertext 1 Ch−¬ng I. Tæng quan vÒ web-mining 1.1 Giíi thiÖu vÒ c¬ së d÷ liÖu Fulltext vµ Hypertext 1.1.1 C¬ së d÷ liÖu Fulltext • Giíi thiÖu chung C¬ së d÷ liÖu Fulltext lµ c¬ së d÷ liÖu phi cÊu tróc mµ d÷ liÖu chøa trong ®ã bao gåm c¸c néi dung text vµ c¸c thuéc tÝnh vÒ tµi liÖu v¨n b¶n víi néi dung ®ã. D÷ liÖu trong c¬ së d÷ liÖu Fulltext th−êng ®−îc tæ chøc nh− mét sù kÕt hîp gi÷a hai phÇn: phÇn c¬ së d÷ liÖu th«ng th−êng qu¶n lý thuéc tÝnh cña c¸c tµi liÖu, vµ phÇn tËp hîp néi dung c¸c tµi liÖu ®−îc qu¶n lý. Chóng ta cã thÓ h×nh dung mét c¬ së d÷ liÖu Fulltext ®−îc tæ chøc nh− sau: C¬ së d÷ liÖu Fulltext CSDL vÒ thuéc tÝnh tµi liÖu TËp hîp néi dung c¸c tµi liÖu H×nh 1.1 M« h×nh tæ chøc cña c¬ së d÷ liÖu Fulltext Trong nh÷ng tr−êng hîp phæ biÕn, néi dung tµi liÖu ®−îc l−u gi÷ gi¸n tiÕp trong c¬ së d÷ liÖu theo nghÜa hÖ thèng chØ qu¶n lý c¸c con trá (®Þa chØ ) trá tíi c¸c ®Þa chØ chøa néi dung tµi liÖu (mét vÝ dô dÔ thÊy nhÊt lµ m¹ng Internet, c¸c trang web th−êng l−u gi÷ c¸c ®Þa chØ chØ tíi n¬i cã l−u néi dung c¸c trang th«ng tin cô thÓ mµ ng−êi sö dông muèn xem). Cßn c¸c con trá (®Þa chØ) vµ c¸c thuéc tÝnh kh¸c vÒ nã th× ®−îc l−u trùc tiÕp trong c¬ së d÷ liÖu b»ng hÖ qu¶n trÞ cã cÊu tróc. Ph¹m ThÞ Thanh Nam – LuËn v¨n cao häc 10 Mét sè gi¶i ph¸p cho bµi to¸n t×m kiÕm trong CSDL Hypertext Tuy nhiªn, trong mét sè tr−êng hîp (®Æc biÖt lµ ®èi víi c¸c m¸y t×m kiÕm trªn Internet nh− Yahoo, Google, AltaVista ...), ®Ó cung cÊp néi dung v¨n b¶n nhanh chãng, ng−êi ta l¹i tæ chøc l−u tr÷ c¸c v¨n b¶n ngay trong hÖ thèng (d−íi d¹ng vïng cache). Néi dung cña d÷ liÖu Fulltext (v¨n b¶n) kh«ng cã cÊu tróc néi t¹i, ®−îc coi nh− mét lµ d·y c¸c tõ, c¸c dÊu ng¨n c¸ch. Ng÷ nghÜa v¨n b¶n dùa trªn ý nghÜa c¸c tõ mang nghÜa (®−îc gäi lµ tõ khãa - term hoÆc keyword) cã trong v¨n b¶n vµ c¸ch bè trÝ c¸c tõ khãa trong v¨n b¶n ®ã. Do kh«ng cã cÊu tróc nªn bµi to¸n “tæ chøc theo cÊu tróc hoµn toµn” c¸c tõ khãa trong v¨n b¶n lµ kh«ng thÝch hîp do tÝnh chÊt qu¸ phøc t¹p khi thùc hiÖn ®iÒu ®ã. Do ®ã, phæ biÕn h¬n ng−êi ta sö dông c¸c ph−¬ng ph¸p biÓu diÔn ng÷ nghÜa v¨n b¶n th«ng qua tËp c¸c tõ kho¸ cã trong v¨n b¶n ®ã. C¸c c¬ së d÷ liÖu Fulltext hiÖn nay th−êng lµ c¸c tËp hîp s¸ch, t¹p chÝ, bµi viÕt ®−îc qu¶n lý trong mét m¹ng th− viÖn ®iÖn tö, tËp c¸c file vµ c¸c trang web (lµ c¸c trang file) ®−îc l−u tr÷ bëi c¸c hÖ thèng web nh− hÖ thèng cña Yahoo, Google, AltaVista … Nh− ®· nãi, lµm thÕ nµo ®Ó hiÓu ®−îc néi dung cña c¸c tµi liÖu trong c¬ së d÷ liÖu? Tån t¹i c¸c ph−¬ng ph¸p biÓu diÔn ®−îc sö dông nh− ph−¬ng ph¸p tãm t¾t, ph−¬ng ph¸p vector, m¹ng logic, l−îc ®å có ph¸p. Nh−ng c¸c ph−¬ng ph¸p ®ã chØ chøa ®ùng ®−îc néi dung s¬ sµi, tãm t¾t cña tµi liÖu. H¬n n÷a mçi mét ph−¬ng ph¸p l¹i cã c¸c khã kh¨n riªng, ®Æc biÖt lµ khi hÖ thèng cho phÐp cËp nhËt thªm d÷ liÖu. V× vËy mµ viÖc c¶i tiÕn c¸c m« h×nh biÓu diÔn nµy lu«n lu«n ®−îc ®Æt ra C¬ së d÷ liÖu Fulltext cã rÊt nhiÒu khÝa c¹nh tiÒm n¨ng tèt cho viÖc khai ph¸ d÷ liÖu vµ KDD, víi c¸c môc tiªu lµ tù ®éng trî gióp ng−êi dïng ®Ó hä cã thÓ sö dông hÖ thèng tµi liÖu hiÖu qu¶ h¬n (ph©n líp tµi liÖu, t×m kiÕm th«ng tin vµ t×m kiÕm tµi liÖu…) vµ m« h×nh vector lµ m« h×nh tèt h¬n c¶ ®Ó tr×nh bµy tµi liÖu Fulltext Do ng÷ nghÜa cña c¸c v¨n b¶n Fulltext th−êng ®−îc biÓu diÔn th«ng qua c¸c tõ kho¸ cña nã nªn trong qu¸ tr×nh xö lý c¸c d÷ liÖu Fulltext th−êng n¶y sinh c¸c vÊn ®Ò vÒ tõ ®ång nghÜa vµ tõ ®a nghÜa. Nh− chóng ta ®· biÕt th× trong ng«n ng÷ tù nhiªn lu«n cã c¸c tõ ®ång nghÜa (lµ tr−êng hîp cã nhiÒu tõ viÕt kh¸c nhau ®Òu chØ chung mét ý Ph¹m ThÞ Thanh Nam – LuËn v¨n cao häc 11 Mét sè gi¶i ph¸p cho bµi to¸n t×m kiÕm trong CSDL Hypertext nghÜa gièng nhau) vµ c¸c tõ ®a nghÜa (lµ tr−êng hîp mét tõ nh−ng cã nhiÒu nghÜa kh¸c nhau). Trong thùc tÕ giao tiÕp chóng ta còng th−êng xuyªn gÆp ph¶i c¸c t×nh huèng hiÓu nhÇm ý nghÜa muèn diÔn ®¹t cña ng−êi nãi khi gÆp ph¶i c¸c tõ ®ång nghÜa vµ ®a nghÜa. V× vËy trong xö lý v¨n b¶n ch¾c ch¾n sÏ kh«ng tr¸nh khái nh÷ng khã kh¨n do vÊn ®Ò nµy g©y ra. Do ®ã chóng ta ph¶i t×m c¸ch kh¾c phôc c¸c vÊn ®Ò nµy. §· cã mét sè h−íng nghiªn cøu gi¶i quyÕt vÊn ®Ò tõ ®ång nghÜa vµ ®a nghÜa ®−îc tiÕn hµnh [1,4,7] nh−: liªn kÕt tõ ®ång nghÜa víi tõ kho¸, dïng träng sè thÓ hiÖn ®é quan träng c¸c tõ, chuÈn ho¸ biÓu diÔn v¨n b¶n, biÓu diÔn ng÷ c¶nh tõ kho¸, biÓu diÔn qua tËp mê... • M« h×nh vector víi gi¶i ph¸p vÊn ®Ò ®a ng«n ng÷ vµ tõ ®ång nghÜa HiÖn nay m« h×nh biÓu diÔn d÷ liÖu fulltext ®iÓn h×nh nhÊt lµ m« h×nh. Theo m« h×nh vector th× hÖ thèng c¬ së d÷ liÖu Fulltext qu¶n lý c¸c tµi liÖu thuéc mét ph¹m vi ho¹t ®éng cña con ng−êi ®−îc thÓ hiÖn qua mét tËp tõ kho¸ V (c¸c tõ kho¸ nµy cã mang ý nghÜa cña néi dung c¸c tµi liÖu). Nh− vËy lµ tËp hîp c¸c tõ kho¸ cã trong tµi liÖu “biÓu diÔn” néi dung cña tµi liÖu ®ã. ¸p dông bµi to¸n t×m kiÕm trong c¬ së d÷ liÖu Fulltext th× qu¸ tr×nh t×m kiÕm gåm hai giai ®o¹n con lµ: qu¸ tr×nh tr×nh bµy c©u hái (m· ho¸ c©u hái) vµ qu¸ tr×nh xö lý trªn c¸c vector. Do sè l−îng c¸c tõ trong c©u hái th−êng lµ nhá nªn thêi gian cña qu¸ tr×nh m· ho¸ c©u hái th−êng ng¾n. Ng−îc l¹i, thêi gian cho viÖc xö lý trªn c¸c vector th−êng kh¸ lín, vµ phô thuéc vµo kÝch th−íc cña c¸c vector vµ sè l−îng c¸c phÐp tÝnh gi÷a c©u hái víi c¸c vector m· ho¸ cña tµi liÖu. Trªn thùc tÕ th× sè l−îng lín nhÊt c¸c phÐp to¸n lµ A* n, víi A lµ sè l−îng tµi liÖu ®−îc l−u tr÷ trong c¬ së d÷ liÖu vµ n lµ sè l−îng c¸c tõ trong c©u hái ®−îc ®−a ra. §Ó gi¶m sè l−îng c¸c phÐp to¸n trong giai ®o¹n xö lý trªn c¸c vector th× chóng ta cã thÓ xem xÐt gi¶m kÝch th−íc cña vector tr×nh bµy tµi liÖu, vµ kÕt qu¶ lµ thay v× ph¶i m· hãa tÊt c¶ c¸c tõ kho¸ xuÊt hiÖn trong kh«ng gian c¬ së d÷ liÖu th× ta chØ cÇn m· ho¸ c¸c tõ kho¸ xuÊt hiÖn trong tµi liÖu. Ngoµi ra cã mét c¸ch rÊt ®¬n gi¶n cã thÓ t¨ng ®é chÝnh x¸c t×m kiÕm lµ t¸ch riªng phÇn tiªu ®Ò cña tµi liÖu ra thµnh mét phÇn. Th«ng th−êng, c¸c tµi liÖu cã phÇn tiªu ®Ò thÓ hiÖn tãm t¾t néi dung Ph¹m ThÞ Thanh Nam – LuËn v¨n cao häc 12 Mét sè gi¶i ph¸p cho bµi to¸n t×m kiÕm trong CSDL Hypertext cña tµi liÖu, chÝnh v× vËy mµ chóng ta cã thÓ t¸ch phÇn tiªu ®Ò ra khái néi dung cña tµi liÖu vµ biÓu diÔn nã b»ng mét vector riªng, ®éc lËp víi phÇn néi dung. Khi ®ã ngoµi viÖc t×m kiÕm theo néi dung chóng ta sÏ ®−a thªm lùa chän t×m kiÕm theo tiªu ®Ò. V× phÇn tiªu ®Ò bao giê còng ng¾n h¬n phÇn néi dung rÊt nhiÒu nªn viÖc t×m kiÕm theo tiªu ®Ò sÏ diÔn ra rÊt nhanh mµ l¹i mang l¹i cho chóng ta ®é chÝnh x¸c t×m kiÕm cao h¬n. Víi bµi to¸n t×m kiÕm th× vÊn ®Ò tõ ®ång nghÜa nh− ®· nªu ë phÇn trªn cÇn ph¶i ®−îc triÓn khai nÕu kh«ng chóng ta sÏ chØ t×m ®−îc c¸c tµi liÖu chøa c¸c tõ cã trong c©u hái, cßn c¸c tµi liÖu cã cïng néi dung nh−ng cã c¸ch thÓ hiÖn kh¸c sÏ bÞ bá qua. §Ó gi¶i quyÕt vÊn ®Ò nµy lµ chóng ta x©y dùng mét b¶ng liÖt kª danh s¸ch c¸c tõ ®ång nghÜa thuéc nhiÒu ng«n ng÷ cïng víi c¸c hÖ sè t−¬ng quan vÒ mÆt ý nghÜa gi÷a chóng. Vµ trong mét nhãm c¸c tõ ®ång nghÜa mÆc dï cïng biÓu ®¹t mét néi dung nh−ng vai trß cña c¸c tõ cã thÓ kh¸c nhau do c¸c lý do sau: víi mét néi dung cô thÓ nµy th× tõ nµy hay ®−îc sö dông h¬n tõ kia, cßn víi mét néi dung cô thÓ kh¸c th× cã thÓ l¹i kh¸c [3,9,12]. ViÖc thèng kª vµ Ên ®Þnh hÖ sè cho c¸c tõ ®ång nghÜa trong mét nhãm c¸c tõ ®ång nghÜa lµ mét viÖc lµm phøc t¹p vµ r¾c rèi, ®ßi hái ph¶i cã tri thøc vÒ ng÷ nghÜa cña c¸c tõ trong nhiÒu ng«n ng÷ kh¸c nhau. V× vËy viÖc nµy cÇn nhËn ®−îc sù phèi hîp víi c¸c nhµ ng«n ng÷ häc. 1.1.2 C¬ së d÷ liÖu Hypertext Hypertext lµ thuËt ng÷ ®−îc Theodore Nelson ®−a ra lÇn ®Çu tiªn n¨m 1965 t¹i héi th¶o cña Héi to¸n häc Mü ACM lÇn thø 20. Theo Nelson th× Hypertext lµ c¸c tµi liÖu d¹ng ch÷ viÕt kh«ng liªn tôc. Chóng ®−îc ph©n nh¸nh vµ cho phÐp ng−êi ®äc cã thÓ chän c¸ch ®äc theo ý muèn cña m×nh, tèt nhÊt lµ nªn ®äc nã trªn c¸c mµn h×nh cã kh¶ n¨ng t−¬ng t¸c. HiÓu theo nghÜa th«ng th−êng th× Hypertext lµ mét tËp c¸c trang ch÷ viÕt ®−îc kÕt nèi víi nhau bëi c¸c liªn kÕt, vµ nã cho phÐp ng−êi ®äc cã thÓ ®äc theo c¸c c¸ch kh¸c nhau. Ph¹m ThÞ Thanh Nam – LuËn v¨n cao häc 13 Mét sè gi¶i ph¸p cho bµi to¸n t×m kiÕm trong CSDL Hypertext Hypertext còng cã thÓ bao gåm mét tËp ch÷ viÕt liªn tôc, vµ ®©y còng chÝnh lµ d¹ng phæ biÕn nhÊt cña ch÷ viÕt. Do kh«ng bÞ h¹n chÕ bëi tÝnh liªn tôc nªn trong Hypertext, chóng ta cã thÓ t¹o ra c¸c d¹ng tr×nh bµy míi, vµ nhê ®ã mµ tµi liÖu cña chóng ta sÏ ph¶n ¸nh tèt h¬n néi dung mµ chóng ta ®ang muèn viÕt. Vµ ng−êi ®äc cã thÓ chän cho m×nh mét c¸ch ®äc phï hîp, vÝ dô hä cã thÓ ®i s©u vµo mét vÊn ®Ò mµ hä thÝch thó, hoÆc cã thÓ tiÕp tôc m¹ch suy nghÜ hiÖn t¹i cña hä theo c¸ch mµ tõ tr−íc vÉn ®−îc coi lµ kh«ng thÓ. Theo tõ ®iÓn cña §¹i häc Oxford (Oxford English Dictionary Additions Series) th× Hypertext ®−îc ®Þnh nghÜa nh− sau: lµ lo¹i Text kh«ng ph¶i ®äc theo d¹ng liªn tôc ®¬n, vµ nã cã thÓ ®−îc ®äc theo c¸c thø tù kh¸c nhau; ®Æc biÖt lµ Text vµ ¶nh ®å ho¹ (Graphic) lµ c¸c d¹ng cã mèi liªn kÕt víi nhau theo c¸ch mµ ng−êi ®äc cã thÓ kh«ng cÇn ®äc nã mét c¸ch liªn tôc. VÝ dô khi ®äc mét cuèn s¸ch ng−êi ®äc kh«ng cÇn ®äc lÇn l−ît tõ ®Çu ®Õn cuèi mµ cã thÓ nh¶y cãc ®Õn c¸c ®o¹n kh¸c nhau ®Ó tham kh¶o c¸c vÊn ®Ò cã liªn quan. S¸ng kiÕn t¹o ra mét tËp c¸c v¨n b¶n cïng víi c¸c con trá trá tíi c¸c v¨n b¶n kh¸c mét c¸ch râ rµng ®Ó liªn kÕt mét tËp c¸c v¨n b¶n cã mèi quan hÖ víi nhau lµ mét c¸ch thùc sù hay vµ rÊt h÷u Ých ®Ó tæ chøc th«ng tin. Víi ng−êi viÕt, c¸ch nµy cho phÐp hä cã thÓ tho¶i m¸i lo¹i bá nh÷ng b¨n kho¨n vÒ thø tù tr×nh bµy nh÷ng vÊn ®Ò cã liªn quan ®Õn nhau ®Ó tËp trung vµo hoµn thµnh c¸c vÊn ®Ò nhá, vµ sau ®ã hä cã thÓ sö dông c¸c kÕt nèi ®Ó chØ ra cho ng−êi ®äc thÊy ®−îc c¸c vÊn ®Ò nhá ®ã cã mèi quan hÖ víi nhau nh− thÕ nµo. T¹i ®©y, theo mét nghÜa nµo ®ã, chóng ta gÆp l¹i t− t−ëng m« ®un hãa trong thiÕt kÕ thuËt to¸n vµ viÕt ch−¬ng tr×nh. Víi ng−êi ®äc, c¸ch nµy cho phÐp hä cã thÓ ®i t¾t trªn m¹ng th«ng tin vµ tù quyÕt ®Þnh phÇn th«ng tin nµo cã liªn quan ®Õn vÊn ®Ò hä ®ang quan t©m ®Ó tiÕp tôc t×m hiÓu. So s¸nh víi c¸ch ®äc tuyÕn tÝnh, tøc lµ ®äc lÇn l−ît, th× Hypertext ®· cung cÊp cho chóng ta mét giao diÖn ®Ó cã thÓ tiÕp xóc víi néi dung th«ng tin hiÖu qu¶ h¬n rÊt nhiÒu. Theo khÝa c¹nh cña thuËt to¸n häc m¸y th× Hypertext ®· cung cÊp cho chóng ta c¬ héi nh×n ra ngoµi ph¹m vi mét tµi liÖu ®Ó ph©n líp nã. TÊt nhiªn kh«ng ph¶i tÊt c¶ c¸c Ph¹m ThÞ Thanh Nam – LuËn v¨n cao häc 14 Mét sè gi¶i ph¸p cho bµi to¸n t×m kiÕm trong CSDL Hypertext tµi liÖu cã liªn kÕt ®Õn nã ®Òu cã Ých cho viÖc ph©n líp, ®Æc biÖt lµ khi c¸c siªu liªn kÕt cã thÓ chØ ®Õn rÊt nhiÒu lo¹i kh¸c nhau cña mèi quan hÖ gi÷a c¸c tµi liÖu. Tuy nhiªn ch¾c ch¾n vÉn cßn tån t¹i c¸c tiÒm n¨ng mµ con ng−êi cÇn tiÕp tôc nghiªn cøu vÒ viÖc sö dông c¸c tµi liÖu liªn kÕt ®Õn mét trang ®Ó n©ng cao ®é chÝnh x¸c ph©n líp trang ®ã. Tµi liÖu Hypertext (Hypertext document): mét tµi liÖu Text ®¬n n»m trong mét tËp Hypertext. NÕu chóng ta t−ëng t−îng tËp Hypertext nh− mét ®å thÞ th× mét tµi liÖu Text ®¬n lµ mét nót trong ®ã. Siªu liªn kÕt (Hypertext link): lµ mét sù tham kh¶o/kÕt nèi tõ mét tµi liÖu Hypertext nµy ®Õn mét tµi liÖu Hypertext kh¸c. C¸c siªu liªn kÕt ®ãng vai trß nh− nh÷ng ®−êng nèi trong ®å thÞ nãi trªn. H×nh 1.2 cho mét vÝ dô minh ho¹ ®¬n gi¶n vÒ tµi liÖu Hypertext. H×nh 1.2. §å thÞ minh ho¹ mèi quan hÖ gi÷a c¸c tµi liÖu Hypertext trong mét tËp tµi liÖu Hypertext Hypertext lµ lo¹i d÷ liÖu rÊt phæ biÕn hiÖn nay, vµ còng lµ lo¹i d÷ liÖu cã nhu cÇu t×m kiÕm vµ ph©n líp rÊt lín. Nã lµ lo¹i d÷ liÖu phæ biÕn trªn m¹ng th«ng tin Internet. C¬ së d÷ liÖu trang web (trang web lµ v¨n b¶n Hypertext phæ dông hiÖn nay) víi tÝnh chÊt “nöa cÊu tróc” do xuÊt hiÖn thªm c¸c “thΔ: thÎ cÊu tróc (tiªu ®Ò, më ®Çu, néi Ph¹m ThÞ Thanh Nam – LuËn v¨n cao häc 15 Mét sè gi¶i ph¸p cho bµi to¸n t×m kiÕm trong CSDL Hypertext dung), thÎ nhÊn tr×nh bµy ch÷ (®Ëm, nghiªng...). Nhê c¸c thÎ nµy mµ chóng ta cã thªm mét tiªu chuÈn (so víi tµi liªu Fulltext) ®Ó cã thÓ t×m kiÕm vµ ph©n líp chóng. Dùa vµo c¸c thÎ ®· quy ®Þnh tr−íc chóng ta cã thÓ ph©n thµnh c¸c ®é −u tiªn kh¸c nhau cho c¸c tõ kho¸ nÕu chóng xuÊt hiÖn ë c¸c vÞ trÝ kh¸c nhau. VÝ dô khi t×m kiÕm c¸c tµi liÖu cã néi dung liªn quan ®Õn “computer” th× chóng ta ®−a vµo tõ kho¸ t×m kiÕm lµ “computer”. Râ rµng c¸c tµi liÖu mµ tõ “computer” xuÊt hiÖn ë phÇn tiªu ®Ò sÏ cã néi dung nãi vÒ computer, vµ sÏ gÇn víi yªu cÇu t×m kiÕm cña chóng ta h¬n. 1.1.3 So s¸nh ®Æc ®iÓm cña d÷ liÖu Fulltext vµ d÷ liÖu trang web Nh− ®· ®−îc tr×nh bµy, trang web lµ mét d¹ng ®Æc biÖt cña d÷ liÖu Full-text. Qua kh¶o s¸t s¬ bé tÝnh chÊt cña hai lo¹i d÷ liÖu nµy, chóng t«i cã mét sè nhËn xÐt sau ®©y vÒ ®Æc ®iÓm gièng nhau vµ kh¸c nhau gi÷a trang web vµ mét trang Fulltext th«ng th−êng. B¶ng d−íi ®©y liÖt kª ra mét sè c¸c ®Æc ®iÓm kh¸c nhau c¬ b¶n nh− vËy. STT 1 Trang web V¨n b¶n th«ng th−êng (Fulltext) V¨n b¶n trang web lµ “nöa V¨n b¶n Fulltext lµ “phi cÊu cÊu tróc”. Trong néi dung cã phÇn tróc”. Trong phÇn néi dung kh«ng cã tiªu ®Ò, vµ cã c¸c thÎ nhÊn m¹nh mét tiªu chuÈn nµo cho phÐp chóng ta nghÜa cña tõ hoÆc côm tõ. 2 Néi dung cña c¸c trang web dùa vµo ®Ó ®¸nh gi¸. Néi dung cña v¨n b¶n Fulltext th−êng ®−îc m« t¶ ng¾n gän, c« th−êng rÊt chi tiÕt vµ ®Çy ®ñ. ®äng, cã c¸c siªu liªn kÕt chØ ®Õn c¸c web cã néi dung liªn quan 3 Trong néi dung c¸c trang C¸c trang v¨n b¶n th«ng th−êng web cã chøa c¸c siªu liªn kÕt cho kh«ng liªn kÕt ®−îc ®Õn néi dung cña phÐp liªn kÕt ®Õn c¸c trang kh¸c c¸c trang kh¸c cã néi dung liªn quan B¶ng 1.1. §èi s¸nh trang Web vµ trang Fulltext Ph¹m ThÞ Thanh Nam – LuËn v¨n cao häc 16 Mét sè gi¶i ph¸p cho bµi to¸n t×m kiÕm trong CSDL Hypertext 1.2 Tæng quan vÒ ph−¬ng ph¸p biÓu diÔn v¨n b¶n trong c¬ së d÷ liÖu trang web Cïng víi sù ph¸t triÓn nhanh chãng cña sè l−îng c¸c trang web trªn m¹ng m¸y tÝnh toµn cÇu Internet, còng nh− sè l−îng ng−êi dïng m¹ng Internet trong nh÷ng n¨m gÇn ®©y th× viÖc xö lý v¨n b¶n trang web còng nhËn ®−îc mèi quan t©m ®Æc biÖt. Do c¸c trang web chØ lµ c¸c tµi liÖu “nöa cÊu tróc” nªn viÖc biÓu diÔn trang web lµ ®Æc biÖt quan träng bëi v× viÖc biÓu diÔn lµ b−íc thùc hiÖn ®Çu tiªn, lµm tiÒn ®Ò cho viÖc gi¶i quyÕt rÊt nhiÒu bµi to¸n nh− t×m kiÕm, ph©n líp, ph©n côm v¨n b¶n... HiÖn nay cã rÊt nhiÒu c¸c c¸ch tiÕp cËn kh¸c nhau trong viÖc biÓu diÔn v¨n b¶n trong c¬ së d÷ liÖu trang web. Víi mçi môc ®Ých kh¸c nhau th× mçi ng−êi l¹i cã c¸ch biÓu diÔn trang web riªng. Cã thÓ kÓ ra mét sè c¸ch biÓu diÔn trang web kh¸c nhau nh−: D«na Mladenic [10], Se¸n Slattery [11] hay Hwanjo Yu, Jiawei Han, Kevin ChenChuan [14] coi trang web nh− v¨n b¶n th«ng th−êng vµ chän m« h×nh vector biÓu diÔn; c¸c m¸y t×m kiÕm nh− Yahoo, Altavista, Google hay Vietseek... kh«ng sö dông m« h×nh vector mµ sö dông hÖ thèng tõ khãa mãc nèi song kh«ng biÓu diÔn néi dung v¨n b¶n. Mét c¸ch tiÕp cËn kh¸c ®ang nhËn ®−îc mèi quan t©m cña nhiÒu ng−êi hiÖn nay, ®ã lµ c¸ch tiÕp cËn biÓu diÔn website, ®èi t−îng quan t©m kh«ng lµ webpage mµ lµ website: NghÜa lµ ®èi t−îng t×m kiÕm kh«ng ph¶i lµ c¸c trang web ®¬n n÷a mµ lµ c¶ mét website [6]. Sau ®©y chóng t«i giíi thiÖu s¬ bé vÒ mçi c¸ch tiÕp cËn biÓu diÔn v¨n b¶n trang web cïng mét sè nhËn xÐt ®¸nh gi¸ cña chóng t«i vÒ ®iÓm m¹nh vµ ®iÓm yÕu cña mçi c¸ch tiÕp cËn. Tr×nh bµy cña chóng t«i tu©n theo sù ph©n lo¹i, lo¹i ®Çu tiªn vÒ c¸c ph−¬ng ph¸p biÓu diÔn trang web ®¬n vµ lo¹i thø hai vÒ c¸c ph−¬ng ph¸p biÓu diÔn website. V× c¸c ph−¬ng ph¸p biÓu diÔn trang web ®¬n lµ ®èi t−îng nghiªn cøu cña luËn v¨n mµ sÏ ®−îc kh¶o s¸t kü l−ìng trong c¸c ch−¬ng sau cña luËn v¨n, nªn trong phÇn d−íi ®©yluËn v¨n tr×nh bµy mét c¸ch s¬ l−îc nh÷ng néi dung nµy. Ph¹m ThÞ Thanh Nam – LuËn v¨n cao häc 17 Mét sè gi¶i ph¸p cho bµi to¸n t×m kiÕm trong CSDL Hypertext 1.2.1 Giíi thiÖu s¬ bé vÒ c¸c ph−¬ng ph¸p biÓu diÔn trang web • Ph−¬ng ph¸p biÓu diÔn trang web trong c¸c m¸y t×m kiÕm Trong hÇu hÕt c¸c m¸y t×m kiÕm hiÖn nay ®Òu kh«ng sö dông m« h×nh vector ®Ó biÓu diÔn c¸c trang web. Nh»m gi¶i quyÕt bµi to¸n t×m kiÕm theo côm tõ, c¸c m¸y t×m kiÕm hiÖn nay sö dông ph−¬ng ph¸p biÓu diÔn v¨n b¶n trang web theo x©u c¸c tõ khãa xuÊt hiÖn trong v¨n b¶n ®ã. Trong mét sè tr−êng hîp, ®Ó phôc vô cho viÖc t×m kiÕm nhanh c¸c v¨n b¶n chøa mét tõ do ng−êi dïng ®−a vµo, tõ khãa ®−îc coi lµ ®èi t−îng trung t©m cña hÖ thèng (xem môc 2.1.2). Lý do kh«ng sö dông m« h×nh vector ®Ó biÓu diÔn trang web trong c¸c m¸y t×m kiÕm ®−îc diÔn gi¶i theo c¸c lËp luËn sau ®©y. Trong c¸c c¬ së d÷ liÖu Fulltext truyÒn thèng, c¸c tµi liÖu cã cÊu tróc th«ng tin ®ång nhÊt (vÒ néi dung, ng«n ng÷ diÔn ®¹t, ®Þnh d¹ng file...), chóng phæ biÕn lµ tËp c¸c tµi liÖu trong cïng mét lÜnh vùc hÑp nµo ®ã, vµ th−êng lµ ®−îc kiÓm so¸t tèt. Do ®ã viÖc sö dông m« h×nh vector ®Ó biÓu diÔn lµ rÊt phï hîp. Trong khi ®ã c¬ së d÷ liÖu trang web lµ mét c¬ së d÷ liÖu phøc t¹p c¶ vÒ néi dung, kÝch th−íc lÉn h×nh thøc tr×nh bµy. Nh÷ng ng−êi thiÕt kÕ m¸y t×m kiÕm coi r»ng hÖ thèng trang Web lµ mét tËp d÷ liÖu khæng lå, kh«ng ®ång nhÊt vµ rÊt khã kiÓm so¸t. Kh«ng ai cã thÓ biÕt chÝnh x¸c ®−îc kÝch th−íc cña web hiÖn nay ra sao, vµ nã sÏ tiÕp tôc ph¸t triÓn nh− thÕ nµo vÒ néi dung lÉn kÝch th−íc, v× hÇu nh− mäi ng−êi ®Òu cã thÓ xo¸, söa ch÷a vµ ®−a thªm c¸c trang míi lªn Internet bÊt cø lóc nµo. Web ®a d¹ng c¶ vÒ néi dung, ng«n ng÷ (ng«n ng÷ cña con ng−êi vµ ng«n ng÷ m¸y) lÉn ®Þnh d¹ng file (text, HTML, PDF, images, sounds...) chÝnh v× thÕ mµ viÖc sö dông m« h×nh vector ®Ó biÓu diÔn cã thÓ lµ kh«ng cßn phï hîp n÷a mµ cÇn ph¶i sö dông c¸c m« h×nh biÓu diÔn kh¸c hoÆc ph¶i c¶i tiÕn m« h×nh vector ®Ó cã thÓ phï hîp víi viÖc xö lý web. Trong ph−¬ng ¸n phæ biÕn hiÖn nay trong c¸c m¸y t×m kiÕm, ng−êi ta ch−a sö dông m« h×nh vector ®Ó biÓu diÔn trang web. C¸c m¸y t×m kiÕm xö lý bµi to¸n t×m kiÕm trang web b»ng c¸ch kiÓm so¸t néi dung cña c¸c trang theo hÖ thèng c¸c tõ khãa vµ kiÓm so¸t c¸c mèi liªn kÕt gi÷a c¸c trang. C¸c m¸y t×m kiÕm ph©n tÝch c¸c trang ®Ó lÊy ra c¸c tõ khãa xuÊt hiÖn trong c¸c Ph¹m ThÞ Thanh Nam – LuËn v¨n cao häc 18 Mét sè gi¶i ph¸p cho bµi to¸n t×m kiÕm trong CSDL Hypertext trang ®ã vµ l−u tr÷ ®Ó lµm c¬ së cho viÖc t×m kiÕm theo néi dung. Trong khi ph©n tÝch c¸c tõ trong trang web th× c¸c m¸y t×m kiÕm ®Òu ghi l¹i c¸c th«ng tin chung nhÊt vÒ tõ nh−: vÞ trÝ xuÊt hiÖn trong trang, ch÷ hoa hay ch÷ th−êng... nªn cã thÓ sö dông ®−îc c¸c th«ng tin tiÒm Èn mµ ng−êi viÕt c¸c trang web ®ã muèn diÔn ®¹t. C¸c m¸y t×m kiÕm cßn ph©n tÝch ®−îc c¸c mèi liªn kÕt gi÷a c¸c trang ®Ó phôc vô cho viÖc xÕp h¹ng c¸c trang lµm c¬ së ®Ó s¾p xÕp c¸c trang kÕt qu¶ khi hiÓn thÞ cho ng−êi dïng. Chi tiÕt vÒ c¸ch biÓu diÔn còng nh− xö lý tµi liÖu web trong c¸c m¸y t×m kiÕm ®−îc ®Ò cËp ®Õn ë phÇn 2.1 cña luËn v¨n nµy. • C¸c ph−¬ng ph¸p dùa trªn m« h×nh vector Ph¸t triÓn kÕt qu¶ cña c¸c nghiªn cøu tr−íc ®©y, trong luËn v¨n tiÕn sÜ n¨m 2002 cña m×nh, Se¸n Slattery [11] ®· giíi thiÖu vµ ®Ò xuÊt sö dông m« h×nh vector biÓu diÔn v¨n b¶n. Trong lÜnh vùc xö lý v¨n b¶n truyÒn thèng tõ tr−íc ®Õn nay th× th«ng th−êng vÉn thùc hiÖn c¸c c«ng viÖc biÓu diÔn, t×m kiÕm, ph©n líp ... trªn c¬ së coi trang web nh− lµ c¸c trang v¨n b¶n th«ng th−êng vµ sö dông m« h×nh kh«ng gian vector ®Ó biÓu diÔn v¨n b¶n. Còng tiÕn hµnh viÖc biÓu diÔn vµ xö lý tµi liÖu web dùa trªn c¸ch tiÕp cËn ®ã, tuy nhiªn Se¸n Slattery còng ®· cã nh÷ng c¶i tiÕn ®Ó cã thÓ tËn dông ®−îc tÝnh nöa cÊu tróc, ®Æc biÖt lµ khai th¸c thÕ m¹nh cña siªu liªn kÕt trong v¨n b¶n. Se¸n Slattery ®· sö dông c¸c siªu liªn kÕt gi÷a c¸c trang web ®Ó cã thÓ lÊy ®−îc c¸c th«ng tin vÒ mèi liªn hÖ gi÷a néi dung c¸c trang, vµ dùa vµo ®ã ®Ó n©ng cao hiÖu qu¶ ph©n líp vµ t×m kiÕm. Tuy nhiªn, mét sè ph−¬ng ph¸p theo c¸ch thøc khai th¸c yÕu tè siªu liªn kÕt l¹i lµm t¨ng nhanh kÝch th−íc vector biÓu diÔn v¨n b¶n trang web vµ v× vËy mét sè c¶i tiÕn nh»m kh¾c phôc t×nh huèng nµy ®· ®−îc ®Ò xuÊt. C¶i tiÕn c¸c ph−¬ng ph¸p biÓu diÔn cña Se¸n Slattery, chóng t«i còng ®Ò xuÊt bæ sung thªm mét ph−¬ng ph¸p biÓu diÔn kh¸c. Mét sè t¸c gi¶ kh¸c ®−a ra c¸ch c¶i tiÕn ®Þnh h−íng vµo viÖc c¸ch liÖt kª thªm c¸c tõ khãa tõ c¸c trang web l¸ng giÒng b»ng c¸ch chØ bæ sung c¸c tõ khãa xuÊt hiÖn trong Ph¹m ThÞ Thanh Nam – LuËn v¨n cao häc 19 Mét sè gi¶i ph¸p cho bµi to¸n t×m kiÕm trong CSDL Hypertext ®o¹n v¨n b¶n l©n cËn víi siªu liªn kÕt. VÊn ®Ò nµy hiÖn còng ®ang ®−îc quan t©m nghiªn cøu vµ triÓn khai. ¦u ®iÓm cña tÊt c¶ c¸c ph−¬ng ph¸p biÓu diÔn trªn ®©y lµ võa khai th¸c ®−îc thÕ m¹nh cña m« h×nh vector trong biÓu diÔn v¨n b¶n l¹i võa ®−a thªm ®−îc yÕu tè liªn kÕt cña c¸c trang web theo c¸c siªu liªn kÕt. Chi tiÕt theo c¸ch tiÕp cËn biÓu diÔn trang web theo m« h×nh vector, mµ träng t©m lµ c¸c gi¶i ph¸p cña Se¸n Slattery bao gåm c¸ch biÓu diÔn webpage do luËn v¨n ®Ò xuÊt, ®−îc ®Ò cËp t¹i phÇn 2.2.2 cña luËn v¨n. 1.2.2 C¸ch tiÕp cËn theo web site C¸ch tiÕp cËn theo website lµ c¸ch coi ®èi t−îng t×m kiÕm lµ c¸c web site thay cho c¸c trang web trong c¸ch tiÕp cËn th«ng th−êng. Vµo nh÷ng n¨m 1999-2000, mét sè t¸c gi¶ [2,4] ®· ®Ò xuÊt s¬ bé vÒ viÖc sö dông website nh− ®èi t−îng cña biÓu diÔn, ph©n líp vµ t×m kiÕm. Ph¸t triÓn c¸c ®Ò xuÊt ®ã, trong c«ng tr×nh nghiªn cøu khoa häc [6], Martin Ester, Hans-Peter Kriegei, Matthias Schubert ®· tr×nh bµy gi¶i ph¸p kh¸ ®Çy ®ñ vÒ vÊn ®Ò nµy. • C¬ së thùc tiÔn cña ph−¬ng ph¸p tiÕp cËn website Toµn bé mét website (cÊu tróc vµ néi dung cña nã) th−êng cho th«ng tin kh¸ trän vÑn vÒ lÜnh vùc ho¹t ®éng cña mét c«ng ty, mét c¬ quan, mét tæ chøc ... Tuy nhiªn, khi chiÕt xuÊt th«ng tin tõ Internet th× hÇu hÕt c¸c ph−¬ng ph¸p ®· thiÕt lËp ®Òu tËp trung vµo viÖc ph¸t hiÖn ra c¸c trang web ®éc lËp, cßn viÖc ph¸t hiÖn hoµn toµn c¸c website th× vÉn ch−a ®−îc quan t©m tháa ®¸ng, mÆc dï vÊn ®Ò nµy rÊt quan träng trong nhiÒu lÜnh vùc. VÝ dô trong lÜnh vùc th−¬ng m¹i vÒ C«ng nghÖ th«ng tin, khi mµ c¸c s¶n phÈm vµ c¸c dÞch vô thay ®æi víi tèc ®é nhanh chãng th× mét hÖ thèng cã n¨ng lùc ®Æc biÖt trong viÖc ph¸t hiÖn c¸c website vµ cung cÊp kh¶ n¨ng ®Ó t×m kiÕm c¸c website ®ã sÏ rÊt cã Ých. Ngµy nay hÇu hÕt c¸c c«ng ty kinh doanh vµ bu«n b¸n trong tÊt c¶ c¸c lÜnh vùc ®Òu thiÕt lËp c¸c website giíi thiÖu vÒ m×nh trªn WWW. Toµn bé néi dung vµ cÊu tróc cña c¸c website th−êng ®−îc thiÕt kÕ cã môc ®Ých vµ dùa vµo néi dung cung cÊp Ph¹m ThÞ Thanh Nam – LuËn v¨n cao häc