Tài liệu Phương pháp biểu diễn ngữ nghĩa lân cận siêu liên kết cho máy tìm kiếm vietseek

Môc lôc PhÇn më ®Çu........................................................................................................................... 3 Ch−¬ng 1. Tæng quan vÒ t×m kiÕm th«ng tin trªn web.................................... 5 1.1 Giíi thiÖu vÒ t×m kiÕm th«ng tin............................................................... 5 1.2 Bµi to¸n t×m kiÕm th«ng tin ...................................................................... 5 1.2.1 Giai ®o¹n 1: Thu thËp vµ ph©n tÝch th«ng tin .................................... 9 1.2.2 Giai ®o¹n 2: Xö lý c©u hái vµ tr¶ lêi................................................10 1.3 M« h×nh biÓu diÔn th«ng tin cña v¨n b¶n ...............................................11 1.3.1 M« h×nh biÓu diÔn th«ng tin theo tõ kho¸ .......................................12 1.3.2 M« h×nh biÓu diÔn th«ng tin theo néi dung .....................................14 1.4 Ph©n tÝch có ph¸p vµ ng÷ nghÜa ..............................................................15 1.5 Ph©n líp v¨n b¶n.....................................................................................15 1.6 Ph©n côm v¨n b¶n...................................................................................15 1.7 Khai th¸c th«ng tin cÊu tróc web............................................................16 1.8 Khai th¸c th«ng tin sö dông web ............................................................16 Ch−¬ng 2. ph−¬ng ph¸p biÓu diÔn trang web theo ng÷ nghÜa l©n cËn siªu liªn kÕt ......................................................................................................................... 18 2.1 Giíi thiÖu ................................................................................................18 2.2 Ph−¬ng ph¸p ®¸nh gi¸ chÊt l−îng ®é ®o t−¬ng tù ..................................19 2.2.1 Chän ph−¬ng ph¸p ®¸nh gi¸ ............................................................19 2.2.2 X¸c ®Þnh thø tù nÒn trong ODP .......................................................20 2.2.3 So s¸nh sù t−¬ng quan gi÷a c¸c tËp thø tù.......................................23 2.2.4 MiÒn cña tËp thø tù ..........................................................................24 2.3 §Þnh nghÜa m« h×nh vector biÓu diÔn th«ng tin v¨n b¶n ........................26 2.3.1 Vector biÓu diÔn th«ng tin v¨n b¶n..................................................27 2 Ph−¬ng ph¸p biÓu diÔn ng÷ nghÜa l©n cËn siªu liªn kÕt cho m¸y t×m kiÕm VietSeek 2.3.2 Lùa chän tõ kho¸ biÓu diÔn .............................................................27 2.3.3 L−îc bít tõ kho¸ ..............................................................................28 2.3.4 X¸c ®Þnh träng sè cña tõ kho¸ .........................................................29 2.4 §Þnh nghÜa ®é ®o t−¬ng tù......................................................................30 2.5 §¸nh gi¸ chÊt l−îng xÕp h¹ng ®èi víi mçi ph−¬ng ph¸p x©y dùng vector ..............................................................................................................31 2.5.1 §¸nh gi¸ chÊt l−îng ®èi víi c¸ch chän tõ kho¸ ..............................32 2.5.2 §¸nh gi¸ chÊt l−îng ®èi víi c¸ch chuÈn ho¸ träng sè tõ kho¸........39 2.5.3 §¸nh gi¸ chÊt l−îng ®èi víi ph−¬ng ph¸p l−îc bít tõ kho¸............42 2.6 C¸c thuËt to¸n t×m kiÕm theo m« h×nh vector.........................................42 Ch−¬ng 3. m¸y t×m kiÕm vietseek vµ thö nghiÖm ThuËt to¸n t×m kiÕm theo ng÷ nghÜa l©n cËn siªu liªn kÕt .................................................................... 45 3.1 M¸y t×m kiÕm VietSeek ..........................................................................45 3.1.1 C¸c ®Æc ®iÓm c¬ b¶n cña Vietseek ..................................................45 3.1.2 C¬ së d÷ liÖu cña Vietseek ..............................................................46 3.2 §Ò xuÊt thuËt to¸n t×m kiÕm míi cho m¸y t×m kiÕm VietSeek ..............49 3.2.1 Nh÷ng c¬ së ®Ó ®Ò xuÊt thuËt to¸n ..................................................49 3.2.2 C¸c thuËt to¸n ¸p dông cho m¸y t×m kiÕm VietSeek.......................53 3.2.3 KÕt qu¶ thùc hiÖn.............................................................................62 PhÇn kÕt luËn...................................................................................................................... 67 Tµi liÖu tham kh¶o........................................................................................................... 69 Phô lôc.................................................................................................................................... 72 §Æng TiÓu Hïng – LuËn v¨n cao häc 3 Ph−¬ng ph¸p biÓu diÔn ng÷ nghÜa l©n cËn siªu liªn kÕt cho m¸y t×m kiÕm VietSeek PhÇn më ®Çu Cïng víi sù ph¸t triÓn m¹nh mÏ cña Internet lµ mét khèi l−îng khæng lå d÷ liÖu ®−îc ph¸t sinh, tuy nhiªn (theo th«ng tin tõ tËp ®oµn Oracle) kho¶ng 90% d÷ liÖu ë d¹ng phi cÊu tróc hoÆc nöa cÊu tróc. Nhu cÇu khai th¸c, t×m kiÕm th«ng tin mét c¸ch chÝnh x¸c trªn internet ®· ngµy cµng trë nªn bøc thiÕt h¬n, do ®ã xuÊt hiÖn c¸c hÖ t×m kiÕm theo tõ kho¸ (côm tõ kho¸) nh− Yahoo, Google ... Tuy nhiªn viÖc t×m kiÕm theo tõ kho¸ vÉn ch−a ®ñ ®Ó gióp ng−êi sö dông nhanh chãng t×m ®−îc trang Web cÇn thiÕt v× sè l−îng kÕt qu¶ tr¶ l¹i rÊt lín vµ nhiÒu khi chØ lµ c¸c trang Web Ýt cã liªn quan. V× vËy c¸c hÖ thèng t×m kiÕm cÇn ®−îc c¶i tiÕn ®Ó ngµy cµng th«ng minh h¬n. XuÊt hiÖn nh÷ng hÖ h−íng tíi môc tiªu cô thÓ nh− tra cøu th«ng tin vÒ c¸c chñ ®Ò y tÕ, gi¸o dôc, luËt ph¸p, ©m nh¹c ... Tuy vËy, viÖc nghiªn cøu c¸c gi¶i ph¸p t×m ®−îc c¸c trang th«ng tin theo mét néi dung nµo ®ã s¸t víi yªu cÇu ng−êi sö dông vÉn cßn nhiÒu h¹n chÕ. §· cã nhiÒu m« h×nh t×m kiÕm ®−îc ®Ò xuÊt, song nh÷ng m« h×nh lý t−ëng vÒ mÆt lý thuyÕt th× l¹i ch−a cã tÝnh kh¶ thi khi cµi ®Æt. Do ®ã, trong c¸c hÖ t×m kiÕm, ng−êi ta t×m c¸ch c¶i tiÕn c¸c ph−¬ng ph¸p cã s½n ®Ó ¸p dông trong thùc tÕ. LuËn v¨n nµy h−íng tíi viÖc nghiªn cøu, ph©n tÝch, ®¸nh gi¸ mét sè thuËt to¸n t×m kiÕm theo néi dung, tõ ®ã ®Ò xuÊt ph−¬ng ¸n c¶i tiÕn ®Ó n©ng cao hiÖu qu¶ vÒ tÝnh chÝnh x¸c cña néi dung còng nh− vÒ tèc ®é. Tõ viÖc t×m hiÓu, ®¸nh gi¸ 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 theo môc tiªu n©ng cao hiÖu qu¶ t×m kiÕm, luËn v¨n ®Ò xuÊt gi¶i ph¸p thùc hiÖn “Ph−¬ng ph¸p biÓu diÔn ng÷ nghÜa l©n cËn siªu liªn kÕt cho m¸y t×m kiÕm VietSeek”. Néi dung cña luËn v¨n ®−îc ®Þnh h−íng vµo c¸c vÊn ®Ò sau: 1. M« h×nh to¸n häc biÓu diÔn trang v¨n b¶n Web, §Æng TiÓu Hïng – LuËn v¨n cao häc 4 Ph−¬ng ph¸p biÓu diÔn ng÷ nghÜa l©n cËn siªu liªn kÕt cho m¸y t×m kiÕm VietSeek 2. Kh¸i qu¸t c¸c ph−¬ng ph¸p tiÕp cËn trong t×m kiÕm trang Web cã néi dung t−¬ng tù. §¸nh gi¸ −u ®iÓm vµ nh−îc ®iÓm cña mçi ph−¬ng ph¸p ®−îc kh¶o s¸t. 3. §Ò xuÊt ph−¬ng ph¸p kÕt hîp ®Ó n©ng cao hiÖu qu¶ trong t×m kiÕm trang Web cã néi dung t−¬ng tù LuËn v¨n bao gåm PhÇn më ®Çu, ba ch−¬ng néi dung vµ PhÇn kÕt luËn víi 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Ò c¸c ph−¬ng ph¸p biÓu diÔn vµ t×m kiÕm th«ng tin trªn web giíi thiÖu kh¸i qu¸t vÒ c¸c ph−¬ng ph¸p biÓu diÔn vµ t×m kiÕm trªn web. Tiªu ®Ò cña ch−¬ng 2 lµ Ph−¬ng ph¸p biÓu diÔn trang web theo ng÷ nghÜa l©n cËn siªu liªn kÕt. Ch−¬ng nµy tr×nh bµy c¬ së, néi dung cña ph−¬ng ph¸p ®−îc ®Ò xuÊt vµ ®¸nh gi¸ ph−¬ng ph¸p ®−îc ®Ò xuÊt víi c¸c ph−¬ng ph¸p kh¸c. LuËn v¨n còng tr×nh bµy chi tiÕt c¸c lùa chän ®−îc ®Ò xuÊt trong mçi b−íc cña ph−¬ng ph¸p, tõ ®ã chän ra gi¶i ph¸p tèt nhÊt. Ch−¬ng 3 M¸y t×m kiÕm VietSeek vµ thö nghiÖm ThuËt to¸n t×m kiÕm theo ng÷ nghÜa l©n cËn siªu liªn kÕt giíi thiÖu kiÕn tróc logic cña m¸y t×m kiÕm VietSeek, thiÕt kÕ logic 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ë biÓu diÔn trang web do luËn v¨n ®Ò xuÊt. Ch−¬ng nµy còng ®Ò xuÊt nh÷ng c¶i tiÕn khi ¸p dông vµo thùc tÕ ®Ó n©ng cao hiÖu suÊt thùc hiÖn cña ph−¬ng ph¸p biÓu diÔn. 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 vµ chØ ra mét sè h¹n chÕ cña luËn v¨n. §ång thêi luËn v¨n ®Ò xuÊt mét sè h−íng nghiªn cøu cô thÓ tiÕp theo cña luËn v¨n. PhÇn phô lôc bæ sung mét sè th«ng tin chi tiÕt vÒ viÖc ¸p dông thuËt to¸n cho m¸y t×m kiÕm VietSeek nh− s¬ ®å khèi mét sè module cÇn bæ sung chøc n¨ng, nh÷ng lÖnh bæ sung vµo c¬ së d÷ liÖu cña VietSeek. §Æng TiÓu Hïng – LuËn v¨n cao häc 5 Ph−¬ng ph¸p biÓu diÔn ng÷ nghÜa l©n cËn siªu liªn kÕt cho m¸y t×m kiÕm VietSeek 1 Ch−¬ng 1. Tæng quan vÒ t×m kiÕm th«ng tin trªn web 1.1 Giíi thiÖu vÒ t×m kiÕm th«ng tin Khai ph¸ d÷ liÖu trªn web (Web Mining) lµ qu¸ tr×nh kh¶o s¸t vµ ph©n tÝch d÷ liÖu web mét c¸ch tù ®éng hoÆc b¸n tù ®éng ®Ó ph¸t hiÖn ra th«ng tin. Tõ th«ng tin ®−îc khai ph¸, t×m kiÕm th«ng tin (Infomartion Retrieval) trªn web lµ ph−¬ng ph¸p ®Ó truy cËp mét c¸ch hiÖu qu¶ nhÊt ®Õn th«ng tin mµ ng−êi dïng quan t©m, kú väng cung cÊp mét tËp hîp nhá c¸c v¨n b¶n gÇn nhÊt ®Õn lÜnh vùc hoÆc chñ ®Ò mµ ng−êi dïng mong muèn tiÕp cËn. H×nh 1. T×m kiÕm th«ng tin 1.2 Bµi to¸n t×m kiÕm th«ng tin Cã 2 bµi to¸n c¬ b¶n trong t×m kiÕm th«ng tin lµ t×m kiÕm theo tõ kho¸ vµ t×m kiÕm theo néi dung. Bµi to¸n t×m kiÕm theo tõ kho¸ lµ bµi to¸n t×m kiÕm th«ng tin theo §Æng TiÓu Hïng – LuËn v¨n cao häc 6 Ph−¬ng ph¸p biÓu diÔn ng÷ nghÜa l©n cËn siªu liªn kÕt cho m¸y t×m kiÕm VietSeek c¸c tõ khãa do ng−êi dïng cung cÊp [1][1]. HÖ t×m kiÕm sÏ tr¶ vÒ cho ng−êi dïng c¸c trang web cã chøa nh÷ng tõ kho¸ trong c©u hái. Tuy vËy, víi sè l−îng khæng lå c¸c trang web trªn internet nh− hiÖn nay th× sè l−îng kÕt qu¶ t×m ®−îc theo tõ kho¸ lµ qu¸ lín. VÝ dô nÕu t×m c¸c trang web cã tõ kho¸ find similar web page th× cho kÕt qu¶ 858 trang web. H×nh 2. T×m kiÕm th«ng tin theo tõ kho¸ B»ng c¸ch t×m kiÕm theo côm tõ kho¸ th× sè l−îng kÕt qu¶ tr¶ vÒ chÝnh x¸c h¬n, sè kÕt qu¶ tr¶ vÒ lµ 25 trang web. §Æng TiÓu Hïng – LuËn v¨n cao häc 7 Ph−¬ng ph¸p biÓu diÔn ng÷ nghÜa l©n cËn siªu liªn kÕt cho m¸y t×m kiÕm VietSeek H×nh 3. T×m kiÕm th«ng tin theo côm tõ kho¸ NÕu t×m trang web t−¬ng tù víi mét trang web mÉu th× sè l−îng kÕt qu¶ chØ lµ 8 trang web. §Æng TiÓu Hïng – LuËn v¨n cao häc 8 Ph−¬ng ph¸p biÓu diÔn ng÷ nghÜa l©n cËn siªu liªn kÕt cho m¸y t×m kiÕm VietSeek H×nh 4. T×m kiÕm th«ng tin theo néi dung mét trang web mÉu Mét c¸ch tiÕp cËn kh¸c lµ t×m kiÕm theo c¸c site ®−îc ®Ò cËp trong luËn v¨n cña Ph¹m Thanh Nam [1] v× sè l−îng c¸c site Ýt biÕn ®éng vµ Ýt h¬n rÊt nhiÒu so víi c¸c trang web. Tuy vËy, do l−îng th«ng tin øng víi mçi lÜnh vùc ®Òu rÊt lín nªn vÉn qu¸ khã kh¨n ®Ó tiÕp cËn c¸c trang v¨n b¶n ®¸p øng mong muèn víi yªu cÇu ng−êi dïng. ChÝnh v× lý do ®ã mµ c¸c ®Ò tµi nghiªn cøu nh÷ng n¨m gÇn ®©y ®i s©u vÒ lÜnh vùc t×m kiÕm theo néi dung t−¬ng tù víi trang v¨n b¶n mÉu nh− luËn v¨n th¹c sÜ cña Ph¹m Thanh Nam n¨m 2003 [1], luËn ¸n tiÕn sÜ cña Se¸n Slattery n¨m 2002 [13] hoÆc trong mét sè b¸o c¸o vÒ WWW ®−îc tæ chøc n¨m 2002[12], n¨m 2003. §Ó ®¸p øng c¸c yªu cÇu t×m kiÕm th«ng tin cña ng−êi dïng mét c¸ch nhanh nhÊt, tÊt c¶ c¸c gi¶i ph¸p t×m kiÕm th«ng tin ®Òu chia thµnh 2 giai ®o¹n thùc hiÖn t−¬ng ®èi ®éc lËp víi nhau §Æng TiÓu Hïng – LuËn v¨n cao häc 9 Ph−¬ng ph¸p biÓu diÔn ng÷ nghÜa l©n cËn siªu liªn kÕt cho m¸y t×m kiÕm VietSeek • Giai ®o¹n 1: Thu thËp vµ ph©n tÝch th«ng tin vÒ c¸c trang web. • Giai ®o¹n 2: Xö lý c©u hái vµ tr¶ lêi Giai ®o¹n 1 WWW Giai ®o¹n 2 Index database index process Client web repository Webserver searchd daemon H×nh 5: KiÕn tróc c¸c hÖ t×m kiÕm th«ng tin Do giai ®o¹n 1 kh«ng t−¬ng t¸c trùc tiÕp víi ng−êi dïng nªn c¸c th«ng tin ®−îc ph©n tÝch mét c¸ch ®Çy ®ñ nhÊt ®Ó gi¶m thiÓu c¸c ph©n tÝch ë giai ®o¹n sau. Sè l−îng c¸c trang web ®−îc ph©n tÝch rÊt lín (hµng triÖu trang) nªn thêi gian thùc hiÖn giai ®o¹n 1 rÊt lín (tÝnh b»ng giê) cßn thêi gian thùc hiÖn giai ®o¹n 2 lµ rÊt nhá (tÝnh b»ng phÇn tr¨m gi©y). 1.2.1 Giai ®o¹n 1: Thu thËp vµ ph©n tÝch th«ng tin C¸c b−íc xö lý chÝnh: • T×m duyÖt c¸c trang web. Tõ c¸c danh s¸ch ®Þa chØ ban ®Çu, bé phËn t×m duyÖt sÏ t¶i trang web vµ chuyÓn cho bé phËn ph©n tÝch néi dung trang web. C¸c trang web ban ®Çu cã ®é s©u lµ 0, c¸c liªn kÕt cã trong trang web sÏ ®−îc bé phËn ph©n tÝch ghi nhËn l¹i víi ®é s©u lµ 1. Sau khi ®· ph©n tÝch xong c¸c trang web cã ®é s©u lµ 0 th× bé t×m duyÖt tiÕp tôc t¶i néi dung c¸c trang web cã ®é s©u lµ 1 ®Ó ph©n tÝch vµ t×m ra c¸c trang web cã ®é s©u lµ §Æng TiÓu Hïng – LuËn v¨n cao häc 10 Ph−¬ng ph¸p biÓu diÔn ng÷ nghÜa l©n cËn siªu liªn kÕt cho m¸y t×m kiÕm VietSeek 2. Qu¸ tr×nh t¶i trang web sÏ dõng l¹i khi ®¹t ®Õn mét ®é s©u nhÊt ®Þnh nµo ®ã do ng−êi dïng ®Æt tham sè nh− trong VietSeek lµ 256. • Ph©n tÝch vµ l−u tr÷ th«ng tin biÓu diÔn trang web. §©y lµ b−íc c¬ b¶n quyÕt ®Þnh ®Õn chÊt l−îng cña c¸c hÖ t×m kiÕm. C¸c trang web ®−îc ph©n tÝch vÒ mÆt néi dung ®Ó x©y dùng thµnh vector biÓu diÔn trang web. C¸c liªn kÕt cã trong trang web còng ®−îc ghi nhËn l¹i. C¸c trang web còng ®−îc ®¸nh gi¸ mèi t−¬ng quan víi c¸c trang kh¸c theo môc tiªu cña bµi to¸n, vÝ dô nh− sù t−¬ng tù vÒ néi dung so víi c¸c trang web kh¸c hoÆc ph©n vµo líp c¸c chñ ®Ò. Toµn bé thêi gian vµ tµi nguyªn cña c¸c hÖ t×m kiÕm ®−îc sö dông trong b−íc nµy. Do ®ã b−íc nµy còng ®−îc chia thµnh bµi to¸n nhá h¬n cÇn ph¶i gi¶i quyÕt lµ x©y dùng cÊu tróc biÓu diÔn th«ng tin ®−îc cung cÊp tõ c¸c v¨n b¶n ®−îc ph©n tÝch, ph©n tÝch có ph¸p/ng÷ nghÜa, sinh vector biÓu diÔn, ph©n líp v¨n b¶n, ph©n côm v¨n b¶n, ph©n tÝch kÕt qu¶. Nh÷ng néi dung nµy sÏ ®−îc tr×nh bµy trong môc 1.3, 1.4 vµ 1.5 cña ch−¬ng nµy. • L−u tr÷ b¶n sao trang web. §Ó nhanh chãng truy xuÊt ®Õn néi dung trang web t×m thÊy, th«ng th−êng c¸c hÖ t×m kiÕm th−êng l−u tr÷ s½n b¶n sao c¸c trang web d−íi d¹ng nÐn cung cÊp cho ng−êi dïng. Ph−¬ng ph¸p nÐn th−êng ®−îc dïng zip. ViÖc chän mét kü thuËt nÐn th−êng ®−îc c©n nh¾c gi÷a tèc ®é vµ tû lÖ nÐn. Tû lÖ nÐn cña zip lµ 3/1 tuy cã nhá h¬n so víi c¸c ph−¬ng ph¸p nÐn kh¸c nh−ng tèc ®é nÐn vµ gi¶i nÐn cña zip l¹i nhanh ®¸ng kÓ. 1.2.2 Giai ®o¹n 2: Xö lý c©u hái vµ tr¶ lêi C¸c b−íc xö lý chÝnh: • Ph©n tÝch c©u hái cña ng−êi dïng. C¸c hÖ t×m kiÕm th«ng th−êng cho phÐp ng−êi dïng t×m kiÕm c¸c trang web d−íi d¹ng biÓu thøc logic, ngoµi ra ®Ó thuËn tiÖn vµ n©ng cao tÝnh chÝnh x¸c cña c©u hái, c¸c hÖ t×m kiÕm §Æng TiÓu Hïng – LuËn v¨n cao häc 11 Ph−¬ng ph¸p biÓu diÔn ng÷ nghÜa l©n cËn siªu liªn kÕt cho m¸y t×m kiÕm VietSeek còng cho phÐp ng−êi dïng ®−a vµo c¸c ®iÒu kiÖn n©ng cao nh− t×m tõ trong chñ ®Ò, t×m c¸c trang theo néi dung cña mét trang web, t×m theo thêi gian xuÊt hiÖn, t×m theo ng«n ng÷ ..v.v. C©u hái cña ng−êi dïng sÏ ®−îc ph©n tÝch thµnh c¸c ®iÒu kiÖn ®Ó hÖ t×m kiÕm cã nh÷ng øng xö phï hîp. • §Þnh vÞ c¸c trang web kÕt qu¶ vµ xÕp h¹ng. Dùa trªn c¸c ®iÒu kiÖn cña ng−êi dïng vµ c¸c trang web ®· ®−îc ph©n tÝch trong giai ®o¹n “thu thËp vµ ph©n tÝch th«ng tin” hÖ t×m kiÕm nhanh chãng ®Þnh vÞ ra ®−îc c¸c trang web kÕt qu¶, h¬n n÷a c¸c trang web còng ®−îc lÊy ra theo møc ®é t−¬ng quan víi c©u hái cña ng−êi dïng theo mét sè tiªu chÝ s¾p xÕp, vÝ dô nh− thø tù cã xuÊt hiÖn c¸c tõ kho¸ trong c©u hái, møc ®é gÇn víi néi dung trang web mÉu. Møc ®é chÝnh x¸c cña trang web ®èi víi c©u hái cña ng−êi dïng (h¹ng cña trang web) còng ®−îc tÝnh to¸n vµ cung cÊp cho ng−êi dïng. Mét sè hÖ t×m kiÕm cßn bæ sung thªm tÝnh n¨ng xö lý c¸c ph¶n håi cña ng−êi dïng víi kÕt qu¶ ®Ó n©ng cao ®é chÝnh x¸c cho c¸c lÇn tr¶ lêi sau nh− ghi nhËn sè lÇn truy cËp cña trang web ®Ó t¨ng ®é −u tiªn vÒ h¹ng cña trang web, thay ®æi ®é t−¬ng tù cña c¸c trang web ®· ph©n tÝch, chuyÓn trang web vµo nhãm v¨n b¶n cã chñ ®Ò chÝnh x¸c h¬n. • HiÓn thÞ néi dung trang web s½n cã. Ng−êi dïng cã thÓ lÊy trang web tõ ®Þa chØ ®−îc cung cÊp bëi hÖ t×m kiÕm hoÆc cã thÓ xem néi dung trang web s½n cã trong kho l−u tr÷ cña hÖ t×m kiÕm. Thao t¸c nµy yªu cÇu hÖ t×m kiÕm gi¶i nÐn trang web vµ hiÓn thÞ. Th«ng th−êng th× hÖ t×m kiÕm sÏ t« s¸ng c¸c thµnh phÇn cã trong c©u hái cña ng−êi dïng b»ng c¸c mµu s¾c ®Ó ng−êi dïng nhanh chãng nhËn ra vÞ trÝ cña chóng trong trang web kÕt qu¶. 1.3 M« h×nh biÓu diÔn th«ng tin cña v¨n b¶n C¬ së d÷ liÖu Fulltext lµ c¬ së d÷ liÖu phi cÊu tróc biÓu diÔn th«ng tin cña v¨n b¶n mµ d÷ liÖu chøa trong ®ã bao gåm c¸c néi dung v¨n b¶n vµ c¸c thuéc tÝnh cña c¸c 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 §Æng TiÓu Hïng – LuËn v¨n cao häc 12 Ph−¬ng ph¸p biÓu diÔn ng÷ nghÜa l©n cËn siªu liªn kÕt cho m¸y t×m kiÕm VietSeek 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 v¨n b¶n, vµ phÇn tËp hîp néi dung c¸c v¨n b¶n ®−îc qu¶n lý [3]. C¬ së d÷ liÖu Fulltext C¬ së d÷ liÖu vÒ thuéc tÝnh tµi liÖu C¬ së d÷ liÖu vÒ néi dung tµi liÖu H×nh 6. M« h×nh tæ chøc cña c¬ së d÷ liÖu Fulltext HiÖn nay cã ba m« h×nh c¬ së d÷ liÖu Fulltext ®iÓn h×nh lµ 1. M« h×nh logic 2. M« h×nh có ph¸p 3. M« h×nh vector M« h×nh vector lµ m« h×nh ®−îc sö dông phæ biÕn nhÊt trong c¸c hÖ t×m kiÕm hiÖn nay. 1.3.1 M« h×nh biÓu diÔn th«ng tin theo tõ kho¸ Mçi v¨n b¶n ®−îc biÓu diÔn nh− mét vector cã c¸c thµnh phÇn lµ thÓ hiÖn tõ kho¸ t−¬ng øng cã mÆt hoÆc kh«ng cã mÆt trong v¨n b¶n ®ã. Mçi tõ kho¸ l¹i cã mét träng sè biÓu diÔn vÒ møc ®é quan träng cña nã trong v¨n b¶n. Qu¸ tr×nh g¸n c¸c gi¸ trÞ ®ã ®−îc gäi lµ qu¸ tr×nh ®¸nh chØ sè (indexing). HiÖn nay cã nhiÒu ph−¬ng ph¸p ®¸nh chØ sè nh− TF, IDF, TF*IDF, LSI [3]... trong ®ã chñ yÕu dùa vµo tÇn sè xuÊt hiÖn cña c¸c tõ §Æng TiÓu Hïng – LuËn v¨n cao häc 13 Ph−¬ng ph¸p biÓu diÔn ng÷ nghÜa l©n cËn siªu liªn kÕt cho m¸y t×m kiÕm VietSeek hoÆc mèi quan hÖ gi÷a sù xuÊt hiÖn cña c¸c tõ trong v¨n b¶n. Nh− vËy th× sè chiÒu cña kh«ng gian vector lµ lùc l−îng cña tËp c¸c tõ kho¸. VÝ dô v¨n b¶n thø nhÊt cã néi dung “VietKey 32-Bit lµ ch−¬ng tr×nh hç trî gâ tiÕng ViÖt trong c¸c m«i tr−êng Windows 32-Bit cña Microsoft”. Vµ v¨n b¶n thø 2 “VietKey cã thÓ nhóng ®−îc tiÕng ViÖt trong hÇu hÕt c¸c øng dông 16-bit vµ 32-bit trong m«i tr−êng Windows 32-bit” Vector biÓu diÔn v¨n b¶n sÏ gåm c¸c thµnh (tõ kho¸, tÇn suÊt cña tõ trong v¨n b¶n): Tõ kho¸ Vector biÓu diÔn v¨n b¶n 1 Vector biÓu diÔn v¨n b¶n 2 16 0 1 32 2 2 bit 1 3 c¸c 1 1 cã 0 1 cña 1 0 ch−¬ng 1 0 dông 0 1 ®−îc 0 1 gâ 1 0 hÇu 0 1 hÕt 0 1 hç 1 0 lµ 1 0 §Æng TiÓu Hïng – LuËn v¨n cao häc 14 Ph−¬ng ph¸p biÓu diÔn ng÷ nghÜa l©n cËn siªu liªn kÕt cho m¸y t×m kiÕm VietSeek m«i 1 1 microsoft 1 0 nhóng 0 1 thÓ 0 1 tiÕng 1 1 tr×nh 1 0 tr−êng 1 1 trî 1 0 trong 1 2 øng 0 1 vµ 0 1 vietkey 1 1 viÖt 1 1 windows 1 1 B¶ng 1. Vector biÓu diÔn v¨n b¶n 1.3.2 M« h×nh biÓu diÔn th«ng tin theo néi dung §èi víi bµi to¸n t×m kiÕm theo néi dung, phÇn lín c¸c gi¶i ph¸p t×m kiÕm th«ng tin ®Òu lùa chän m« h×nh vector. Cã ba ph−¬ng ph¸p tiÕp cËn trong viÖc x¸c ®Þnh tõ kho¸ trong vector biÓu diÔn v¨n b¶n. 1. Ph−¬ng ph¸p biÓu diÔn theo néi dung v¨n b¶n: Tõ kho¸ trong vector biÓu diÔn v¨n b¶n u lµ nh÷ng tõ cã mÆt trong v¨n b¶n u. 2. Ph−¬ng ph¸p tiÕp cËn theo liªn kÕt: Tõ kho¸ trong vector biÓu diÔn v¨n b¶n u lµ nh÷ng tõ khãa cã trong ®Þnh danh cña nh÷ng v¨n b¶n v cã liªn kÕt ®Õn v¨n b¶n u. §Æng TiÓu Hïng – LuËn v¨n cao häc 15 Ph−¬ng ph¸p biÓu diÔn ng÷ nghÜa l©n cËn siªu liªn kÕt cho m¸y t×m kiÕm VietSeek 3. Ph−¬ng ph¸p tiÕp cËn theo ng÷ nghÜa l©n cËn liªn kÕt: Tõ kho¸ trong vector biÓu diÔn v¨n b¶n u lµ nh÷ng tõ xuÊt hiÖn trong cöa sæ ng÷ nghÜa l©n cËn liªn kÕt tõ nh÷ng v¨n b¶n v ®Õn v¨n b¶n u. LuËn v¨n ®Ò cËp tíi gi¶i ph¸p kÕt hîp c¸c ph−¬ng ph¸p tiÕp cËn trªn ®©y. 1.4 Ph©n tÝch có ph¸p vµ ng÷ nghÜa Trong trang web kh«ng chØ cã th«ng tin thÓ hiÖn néi dung mµ cßn c¸c th«ng tin phô trî nh− c¸c comment, c¸c ®o¹n m·, c¸c thÎ HTML. Do ®ã cÇn ph¶i t¸ch läc th«ng tin mµ trang web biÓu diÔn, t¸ch th«ng tin vÒ c¸c liªn kÕt. CÇn ph¶i x¸c ®Þnh tõ gèc cña tõ biÓu diÔn v¨n b¶n, x¸c ®Þnh vÞ trÝ cña tõ trong v¨n b¶n, x¸c ®Þnh c¸c biªn cña ®o¹n v¨n theo có ph¸p c©u (dÊu ng¾t c©u) hoÆc biªn theo chñ ®Ò ®o¹n v¨n (ng¾t ®o¹n, ng¾t b¶ng, ng¾t trang). 1.5 Ph©n líp v¨n b¶n Ph©n líp v¨n b¶n ®−îc xem nh− lµ qu¸ tr×nh g¸n c¸c v¨n b¶n vµo mét hay nhiÒu líp v¨n b¶n ®· ®−îc x¸c ®Þnh tr−íc. Sau khi ®−îc ph©n líp, c¸c v¨n b¶n sÏ ®−îc ®¸nh chØ sè ®èi víi tõng líp t−¬ng øng. Ng−êi dïng cã thÓ yªu cÇu hÖ t×m kiÕm giíi h¹n sè kÕt qu¶ trong mét chñ ®Ò hoÆc líp v¨n b¶n mong muèn. Ph©n líp v¨n b¶n cã thÓ thùc hiÖn tù ®éng b»ng c¸c ph−¬ng ph¸p c©y quyÕt ®Þnh [3], m¹ng Bayer, m¸y vector trî gióp. Ngoµi ra, c¸c trang web cã thÓ thÓ ®−îc ph©n líp b»ng thñ c«ng nhê sù t×nh nguyÖn cña ng−êi dïng trªn internet nh− th− môc chñ ®Ò c¸c trang web ODP (Open Directory Project) [17]. 1.6 Ph©n côm v¨n b¶n Ph©n côm v¨n b¶n lµ viÖc tù ®éng sinh ra c¸c líp v¨n b¶n dùa vµo sù t−¬ng tù cña c¸c v¨n b¶n. C¸c líp v¨n b¶n ë ®©y lµ ch−a biÕt tr−íc, ng−êi dïng cã thÓ chØ yªu cÇu sè l−îng c¸c líp cÇn ph©n lo¹i, hÖ sÏ ®−a ra c¸c v¨n b¶n theo tõng tËp hîp, tõng côm, mçi tËp hîp chøa c¸c v¨n b¶n t−¬ng tù nhau. §Æng TiÓu Hïng – LuËn v¨n cao häc 16 Ph−¬ng ph¸p biÓu diÔn ng÷ nghÜa l©n cËn siªu liªn kÕt cho m¸y t×m kiÕm VietSeek 1.7 Khai th¸c th«ng tin cÊu tróc web Trong t×m kiÕm th«ng tin trªn web, c¸c trang web ®· chøa ®ùng th«ng tin nöa cÊu tróc, ®ã chÝnh lµ c¸c liªn kÕt gi÷a c¸c trang web. Th«ng th−êng, c¸c web ®em l¹i nhiÒu th«ng tin sÏ ®−îc trÝch dÉn nhiÒu do ®ã cã thÓ khai th¸c th«ng tin liªn kÕt gi÷a c¸c trang web ®Ó ®¸nh gi¸ träng sè cña trang web nh− Slattery ®· ®Ò xuÊt [13]. 1.8 Khai th¸c th«ng tin sö dông web Th«ng tin sö dông web ®−îc chøa trong mét tËp hîp c¸c file liªn quan ®−îc ®Þnh s½n trªn nh÷ng m¸y chñ web. Môc ®Ých cña viÖc khai th¸c th«ng tin sö dông web ®Ó ph¸t hiÖn ra nh÷ng mÉu d÷ liÖu cã ý nghÜa ®−îc sinh ra trong nh÷ng giao dÞch kh¸ch/chñ. Th«ng th−êng c¸c d÷ liÖu ®ã ë phÝa m¸y chñ lµ access logs, referrer logs, agent logs vµ phÝa m¸y tr¹m lµ cookies. Mét d¹ng th«ng tin vÒ ng−êi dïng web lµ c¸c profile cña hä. Trong t×m kiÕm th«ng tin, c¸c trang web ®em l¹i nhiÒu th«ng tin th−êng ®−îc truy cËp nhiÒu h¬n c¸c trang web kh¸c trong cïng chñ ®Ó. Do ®ã tÇn suÊt truy cËp (th«ng tin sö dông web) cña c¸c trang web còng lµ mét thµnh phÇn cÇn xem xÐt khi ®¸nh gi¸ träng sè cña trang web. Tuy nhiªn, víi mçi ng−êi dïng th× cã thÓ cã tËp hîp c¸c trang web ®−îc yªu thÝch cña riªng m×nh. Ng−êi sö dông cã thÓ yªu cÇu mµ hÖ t×m kiÕm cho phÐp giíi h¹n c¸c trang kÕt qu¶ trong mét tªn miÒn nµo ®ã nh− .com.vn vµ nh÷ng tham sè nh− vËy cã thÓ ®−îc ®Þnh nghÜa trong c¸c profile. KÕt luËn ch−¬ng 1 Trong ch−¬ng nµy, luËn v¨n ®· giíi thiÖu tæng qu¸t bµi to¸n t×m kiÕm th«ng tin trªn web vµ c¸c ph−¬ng ph¸p t×m kiÕm th«ng tin trªn web: 1. C¸c ph−¬ng ph¸p t×m kiÕm theo tõ kho¸ gåm m« h×nh có ph¸p, m« h×nh logic vµ m« h×nh vector. C¸c ph−¬ng ph¸p nµy ®· ®−îc nghiªn cøu kh¸ kü l−ìng vµ tiªu biÓu nhÊt lµ m« h×nh vector. §Æng TiÓu Hïng – LuËn v¨n cao häc 17 Ph−¬ng ph¸p biÓu diÔn ng÷ nghÜa l©n cËn siªu liªn kÕt cho m¸y t×m kiÕm VietSeek 2. C¸c ph−¬ng ph¸p t×m kiÕm theo néi dung ®ang ®−îc nghiªn cøu hiÖn nay lµ t×m kiÕm theo néi dung toµn v¨n, theo liªn kÕt vµ theo ng÷ nghÜa l©n cËn liªn kÕt. LuËn v¨n ®· ph©n tÝch nguyªn t¾c ho¹t ®éng còng nh− −u ®iÓm vµ nh−îc ®iÓm cña mçi ph−¬ng ph¸p. Tõ nh÷ng ph©n tÝch trªn, luËn v¨n sÏ tr×nh bµy ph−¬ng ph¸p biÓu diÔn v¨n b¶n míi trong ch−¬ng 2 vµ ®Ò xuÊt thuËt to¸n t×m kiÕm theo néi dung trong ch−¬ng 3. §Æng TiÓu Hïng – LuËn v¨n cao häc 18 Ph−¬ng ph¸p biÓu diÔn ng÷ nghÜa l©n cËn siªu liªn kÕt cho m¸y t×m kiÕm VietSeek 2 Ch−¬ng 2. ph−¬ng ph¸p biÓu diÔn trang web theo ng÷ nghÜa l©n cËn siªu liªn kÕt 2.1 Giíi thiÖu Môc tiªu cña viÖc t×m kiÕm trang Web t−¬ng tù lµ cho phÐp ng−êi sö dông t×m nh÷ng trang Web t−¬ng tù víi trang Web mÉu. VÒ c¬ b¶n, khi ®−a ra mét v¨n b¶n, mét thuËt to¸n t×m kiÕm t−¬ng tù ph¶i cung cÊp danh s¸ch thø tù cña c¸c v¨n b¶n t−¬ng tù víi v¨n b¶n mÉu. Trong ch−¬ng nµy, luËn v¨n sÏ tr×nh bµy mét sè ph−¬ng ph¸p tiÕp cËn cña gi¶i ph¸p t×m kiÕm theo néi dung vµ ®¸nh gi¸ chÊt l−îng cña mçi ph−¬ng ph¸p. Trªn c¬ së ph−¬ng ph¸p biÓu diÔn trang web theo ng÷ nghÜa l©n cËn siªu liªn kÕt [12], luËn v¨n ®Ò xuÊt mét sè bæ sung, c¶i tiÕn thµnh gi¶i ph¸p t×m kiÕm theo néi dung. C¨n cø trªn nh÷ng kÕt qu¶ ®¸nh gi¸ qua thö nghiÖm, gi¶i ph¸p t×m kiÕm theo néi dung do luËn v¨n ®Ò xuÊt ®−îc xem lµ cã chÊt l−îng tèt h¬n so víi c¸c ph−¬ng ph¸p ®· kh¶o s¸t kh¸c vµ ®−îc ¸p dông cho m¸y t×m kiÕm VietSeek. ThuËt to¸n t×m kiÕm gåm hai b−íc: 1. TiÒn xö lý c¸c trang web: T¹o vector biÓu diÔn trang web. So s¸nh c¸c trang web trong cïng chñ ®Ò cña ODP ®Ó tÝnh to¸n s½n ®é t−¬ng tù c¸c trang web. 2. Thùc hiÖn t×m kiÕm th«ng tin, chØ ®¬n thuÇn lµ thao t¸c ®Þnh vÞ vµ ®äc d÷ liÖu s½n cã trong c¬ së d÷ liÖu. Ph−¬ng ph¸p nµy ®· ®−îc thö nghiÖm b»ng tËp d÷ liÖu lín vµ chøng tá tÝnh kh¶ thi cña nã. C¸c vÊn ®Ò chÝnh cÇn ph¶i gi¶i quyÕt trong ph−¬ng ph¸p biÓu diÔn ng÷ nghÜa l©n cËn siªu liªn kÕt lµ: 1. X¸c ®Þnh ph−¬ng ph¸p ®¸nh gi¸ chÊt l−îng cho ®é ®o t−¬ng tù. 2. X¸c ®Þnh m« h×nh vector biÓu diÔn trang web. 3. X¸c ®Þnh nghÜa ®é ®o t−¬ng tù víi m« h×nh biÓu diÔn ®· chän §Æng TiÓu Hïng – LuËn v¨n cao häc 19 Ph−¬ng ph¸p biÓu diÔn ng÷ nghÜa l©n cËn siªu liªn kÕt cho m¸y t×m kiÕm VietSeek 4. Kh¶o s¸t c¸c thµnh phÇn cña vector biÓu diÔn trang web 5. X©y dùng c¸c thuËt to¸n: - ThuËt to¸n t¹o vector biÓu diÔn trang web - ThuËt to¸n tÝnh ®é t−¬ng tù gi÷a c¸c trang web - ThuËt to¸n t×m kiÕm trang web t−¬ng tù C¸c vÊn ®Ò 1, 2, 3 vµ 4 sÏ ®−îc tr×nh bµy trong ch−¬ng 3 cña luËn v¨n. VÊn ®Ò 5 cã trong ®Ò xuÊt ph−¬ng ¸n thùc hiÖn cho m¸y t×m kiÕm VietSeek trong ch−¬ng 4. 2.2 Ph−¬ng ph¸p ®¸nh gi¸ chÊt l−îng ®é ®o t−¬ng tù 2.2.1 Chän ph−¬ng ph¸p ®¸nh gi¸ Khi kh¶o s¸t c¸c c¸ch tiÕp cËn ®Ó t×m ra ®−îc mét gi¶i ph¸p t×m kiÕm th«ng tin tèt nhÊt th× cÇn thiÕt ph¶i cã mét ph−¬ng ph¸p ®¸nh gi¸ chÊt l−îng cho c¸c mçi ph−¬ng ¸n. ChÊt l−îng xÕp h¹ng trang web cña m¸y t×m kiÕm th−êng ®−îc ®¸nh gi¸ bëi ng−êi dïng dùa trªn c¸c ®é ®o vÒ kho¶ng c¸ch vµ ®Æc tr−ng cña v¨n b¶n. Tuy nhiªn, sö dông trùc tiÕp sù ®¸nh gi¸ cña ng−êi dïng th−êng tèn thêi gian vµ c«ng søc, nªn ®iÒu ®ã kh«ng thÝch hîp cho nh÷ng nghiªn cøu mµ ®ßi hái sù so s¸nh ®¸nh gi¸ cña nhiÒu tham sè. Trong v¨n b¶n vÒ ph©n côm, nhiÒu ph−¬ng ph¸p ®¸nh gi¸ chÊt l−îng tù ®éng ®· ®−îc ®Ò xuÊt [20]. Steinback [20] chia nh÷ng ph−¬ng ph¸p nµy thµnh 2 líp tæng qu¸t. Ph−¬ng ph¸p ®¸nh gi¸ sö dông c¸c ®é ®o chÊt l−îng néi t¹i, nh− ®é t−¬ng tù trung b×nh, chØ ra chÊt l−îng cña mét côm v¨n b¶n ®−îc ®Ò xuÊt dùa hoµn toµn trªn néi t¹i h×nh häc vµ thèng kª, kh«ng dùa trªn mét tËp ch©n lý nÒn cã s½n. Ph−¬ng ph¸p ®¸nh gi¸ dùa trªn c¸c ®é ®o chÊt l−îng ngoµi, nh− ®é ®o entropy, kiÓm tra sù t−¬ng quan cña mét côm víi mét tËp ch©n lý nÒn cã s½n. §©y còng lµ ph−¬ng ph¸p ®¸nh gi¸ ®−îc sö dông ®Ó ®o chÊt l−îng cña mét ph−¬ng ¸n. C©y ph©n lo¹i chñ ®Ò c¸c trang web ODP [17] ®−îc x©y dùng vµ phæ dông trªn Internet. Trong ODP, c¸c trang web ®−îc s¾p ph©n líp theo c¸c chñ ®Ò vµ thø tù cña nã §Æng TiÓu Hïng – LuËn v¨n cao häc 20 Ph−¬ng ph¸p biÓu diÔn ng÷ nghÜa l©n cËn siªu liªn kÕt cho m¸y t×m kiÕm VietSeek trong chñ ®Ò cã thÓ coi lµ h¹ng cña trang web trong chñ ®Ò t−¬ng øng. §é ®o t−¬ng tù cña c¸c v¨n b¶n t−¬ng øng víi mét ph−¬ng ¸n biÓu diÔn th«ng tin vÒ v¨n b¶n cung cÊp mét tËp thø tù. Do ®ã, cã thÓ dïng ODP lµm tËp thø tù nÒn ®Ó kiÓm tra chÊt l−îng xÕp h¹ng cña mét ®é ®o t−¬ng tù. C¸c ®é ®o ®¸nh gi¸ ®é t−¬ng quan gi÷a h¹ng cña trang web trong ODP vµ h¹ng cña trang web t−¬ng øng víi ®é ®o t−¬ng tù ®−îc x©y dùng ®−îc coi nh− lµ sù ®¸nh gi¸ gi¸n tiÕp cña ng−êi dïng vÒ chÊt l−îng xÕp h¹ng. TÊt nhiªn lµ kh«ng thÓ sö dông trùc tiÕp ODP lµm thø tù cho gi¶i ph¸p t×m kiÕm v× nã chØ chøa mét bé phËn c¸c trang web cã mÆt trªn Internet. 2.2.2 X¸c ®Þnh thø tù nÒn trong ODP Dùa theo viÖc ph©n líp s½n cã c¸c v¨n b¶n cña ODP, dÔ thÊy r»ng c¸c v¨n b¶n cïng mét líp (cïng chñ ®Ò) sÏ gÇn nhau vÒ néi dung h¬n so víi c¸c v¨n b¶n ë líp kh¸c (chñ ®Ò kh¸c). VÝ dô, mét v¨n b¶n trong líp recreation/aviation/un-powered th−êng cã néi dung gÇn víi c¸c v¨n b¶n kh¸c cïng líp so víi c¸c v¨n b¶n kh«ng thuéc líp ®ã. H¬n n÷a, v¨n b¶n nµy l¹i "gÇn" víi c¸c v¨n b¶n kh¸c cña líp recreation/aviation h¬n lµ c¸c v¨n b¶n ë khu vùc kh¸c cña c©y. TÊt nhiªn lµ vÞ trÝ cña v¨n b¶n trong c©y ph©n lo¹i chñ ®Ò kh«ng thÓ mang l¹i sù chÝnh x¸c vÒ néi dung mét c¸ch tuyÖt ®èi. VÝ dô trong chñ ®Ò recreation/autos, hÇu hÕt gÇn víi c¸c v¨n b¶n ë shopping/autos h¬n lµ c¸c v¨n b¶n ë recreation/smoking. Tuy vËy cã thÓ c¨n cø vµo ®ã ®Ó x©y dùng mét tiªu chuÈn cho ®é ®o t−¬ng tù v× c¸c c©y ph©n lo¹i chñ ®Ò ®· cã sù s¾p xÕp ®é t−¬ng tù vÒ mÆt néi dung. §Ó chuÈn ho¸ kh¸i niÖm kho¶ng c¸ch tõ mét v¨n b¶n nµy ®Õn mét v¨n b¶n kh¸c trong c©y, kho¶ng c¸ch t−¬ng quan ®· ®−îc x¸c ®Þnh nh− d−íi ®©y. ‰ Kho¶ng c¸ch t−¬ng quan Kho¶ng c¸ch t−¬ng quan df(s,d) tõ mét v¨n b¶n mÉu s ®Õn mét v¨n b¶n d kh¸c trong mét c©y ph©n líp lµ kho¶ng c¸ch tõ líp chøa s ®Õn líp cã kho¶ng c¸ch gÇn nhÊt chøa c¶ s vµ d. §Æng TiÓu Hïng – LuËn v¨n cao häc