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
- Xem thêm -