Đề tài: Một số giải pháp cho bài toán tìm kiếm trong CSDL Hypertext

Chia sẻ: Bluesky_12 Bluesky_12 | Ngày: | Loại File: PDF | Số trang:79

Thêm vào BST

Báo xấu

78
lượt xem 8
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Rất nhiều thứ đã thay đổi và đặc biệt là những cách thức làm SEO truyền thống mà từ trước tới giờ vẫn cho kết quả tốt. Rất nhiều ý kiến trái chiều đã được đưa ra nhắm tới các thay đổi này và mức độ xác đáng cũng khác nhau. Tuy nhiên, có một điều chắc chắn rằng những thay đổi này là cần thiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Đề tài: 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 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 1 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õ. dùa vµo ®Ó ®¸nh gi¸. Néi dung cña c¸c trang web Néi dung cña v¨n b¶n Fulltext 2 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 Trong néi dung c¸c trang C¸c trang v¨n b¶n th«ng th−êng 3 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 Chen- Chuan [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