Tìm hi u v Search Engine và xây d ng ng d ng minh ho cho Search Engine ti ng Vi tể ề ự ứ ụ ạ ế ệ
L I C M NỜ Ả Ơ
Đ u tiên, chúng em xin g i l i c m n đ n Th y, Cô khoa Công ngh Thôngầ ở ờ ả ơ ế ầ ệ
tin tr ng Đ i h c Khoa h c T nhiên đã t n tình d y d , dìu d t chúng em su t b nườ ạ ọ ọ ự ậ ạ ỗ ắ ố ố
năm đ i h c.ạ ọ
Chúng em c m n Cô Nguy n Th Di m Tiên, ng i t n tình h ng d n, giúpả ơ ễ ị ễ ườ ậ ướ ẫ
đ , đ ng viên chúng em hoàn thành lu n văn này.ỡ ộ ậ
Chúng tôi c m n các anh Tr n Nguy n Hoàng Ph ng, Bùi Ng c Tu n Anh,ả ơ ầ ễ ươ ọ ấ
Đoàn H u Quang Vinh và các b n Nguy n Huy Hoàng, Phan Anh Đ c đã giúp đ ,ữ ạ ễ ứ ỡ
đóng góp ý ki n cho chúng tôi trong quá trình cài đ t, th nghi m ch ng trình.ế ặ ử ệ ươ
Cu i cùng, chúng con c m n Ba, M và nh ng ng i thân đã khích l , đ ngố ả ơ ẹ ữ ườ ệ ộ
viên chúng con trong th i gian h c t p, nghiên c u đ có đ c thành qu nh ngàyờ ọ ậ ứ ể ượ ả ư
nay.
Tháng 7 năm 2004
Sinh viên
Lê Thuý Ng c – Đ M Nhungọ ỗ ỹ
Lê Thuý Ng c - 0012745 ọ1 Đ M Nhung - 0012624ỗ ỹ
Tìm hi u v Search Engine và xây d ng ng d ng minh ho cho Search Engine ti ng Vi tể ề ự ứ ụ ạ ế ệ
NH N XÉT C A GIÁO VIÊN H NG D NẬ Ủ ƯỚ Ẫ
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
…………………………………………………………………………………....
……………………………………………………………………………………
Ngày…… tháng……năm 2004
Ký tên
Lê Thuý Ng c - 0012745 ọ2 Đ M Nhung - 0012624ỗ ỹ
Tìm hi u v Search Engine và xây d ng ng d ng minh ho cho Search Engine ti ng Vi tể ề ự ứ ụ ạ ế ệ
NH N XÉT C A GIÁO VIÊN PH N BI NẬ Ủ Ả Ệ
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
…………………………………………………………………………………....
……………………………………………………………………………………
Ngày…… tháng……năm 2004
Ký tên
Lê Thuý Ng c - 0012745 ọ3 Đ M Nhung - 0012624ỗ ỹ
Tìm hi u v Search Engine và xây d ng ng d ng minh ho cho Search Engine ti ng Vi tể ề ự ứ ụ ạ ế ệ
M C L CỤ Ụ
Ph n 1 : TÌM HI U V N Đầ Ể Ấ Ề ....................................................................................... 2
Ch ng 1: T NG QUAN V H TH NG SEARCH ENGINEươ Ổ Ề Ệ Ố ........................... 2
1. Các b ph n c u thành h th ng search engine ộ ậ ấ ệ ố ................................................... 2
1.1 B thu th p thông tin – Robotộ ậ ......................................................................... 2
1.2 B l p ch m c – Indexộ ậ ỉ ụ ................................................................................... 2
1.3 B tìm ki m thông tin – Search Engineộ ế .......................................................... 3
2. Nguyên lý ho t đ ngạ ộ .............................................................................................. 3
Ch ng 2: B THU TH P THÔNG TIN – ROBOTươ Ộ Ậ ............................................. 5
1. ng d ng c a Robot Ứ ụ ủ ............................................................................................. 5
1.1 Phân tích, th ng kê – Statistical Analysisố ........................................................ 5
1.2 Duy trì siêu liên k - Maintenanceế ................................................................... 5
1.3 Ánh x đ a ch web - Mirroringạ ị ỉ ....................................................................... 5
1.4 Phát hi n tài nguyên – Resource Discoveryệ .................................................... 6
1.5 K t h p các công d ng trên- Combined usesế ợ ụ ................................................. 6
2. Robot ch m c – Robot Indexingỉ ụ ............................................................................ 6
3. Các chi n thu t thu th p d li u [II.1] ế ậ ậ ữ ệ ................................................................ 8
3.1 Chi n thu t tìm ki m theo chi u sâuế ậ ế ề ............................................................. 8
3.2 Chi n thu t tìm ki m theo chi u r ngế ậ ế ề ộ ........................................................... 9
3.3 Chi n thu t tìm ki m theo ng u nhiênế ậ ế ẫ ........................................................... 9
4. Nh ng v n đ c n l u ý c a web robot ữ ấ ề ầ ư ủ ............................................................ 10
4.1 Chi phí và hi m hoể ạ ...................................................................................... 10
4.1.1 Qúa t i m ng và server – Network resource and server loadả ạ .................. 10
4.1.2 S c p nh t quá m c- Updating overheadự ậ ậ ứ ............................................. 11
4.1.3 Nh ng tình hu ng không mong đ i – Bad implementationsữ ố ợ .................. 12
4.2 Tiêu chu n lo i tr robotẩ ạ ừ .............................................................................. 13
4.2.1 File robot.txt ............................................................................................. 13
4.2.2 Th META dành cho robot – Robot META tagẻ ...................................... 14
4.2.3 Nh c đi m c a file robot.txtượ ể ủ ................................................................ 15
Ch ng 3: B L P CH M C – INDEXươ Ộ Ậ Ỉ Ụ ............................................................. 18
1. Khái quát v h th ng l p ch m c ề ệ ố ậ ỉ ụ .................................................................... 18
2. T ng quan v ph ng pháp l p ch m c ([I.1], [I.2], [II.1])ổ ề ươ ậ ỉ ụ .............................. 21
2.1 Xác đ nh m c t quan tr ng c n l p ch m c ([I.1])ị ụ ừ ọ ầ ậ ỉ ụ ................................... 21
2.2 M t s hàm tính tr ng s m c t . ([I.1])ộ ố ọ ố ụ ừ ..................................................... 23
2.2.1 Ngh ch đ o tr ng s t n s tài li u (The Inverse Document Frequencyị ả ọ ố ầ ố ệ
Weight) .............................................................................................................. 24
Lê Thuý Ng c - 0012745 ọ4 Đ M Nhung - 0012624ỗ ỹ
Tìm hi u v Search Engine và xây d ng ng d ng minh ho cho Search Engine ti ng Vi tể ề ự ứ ụ ạ ế ệ
2.2.2 Đ nhi u tín hi u (Signal Noise): ộ ễ ệ .......................................................... 25
2.2.3 Giá tr đ phân bi t c a m c t : ị ộ ệ ủ ụ ừ .......................................................... 25
2.2.4 K t h p t n s xu t hi n m c t và ngh ch đ o t n s tài li uế ợ ầ ố ấ ệ ụ ừ ị ả ầ ố ệ .......... 27
2.3 L p ch m c t đ ng cho tài li uậ ỉ ụ ự ộ ệ ................................................................. 28
3. L p ch m c cho tài li u ti ng Vi t ([III.1], [II.1], [II.2], [II.3], [II.4], [IV.11],ậ ỉ ụ ệ ế ệ
[IV.12]) ..................................................................................................................... 30
3.1 Khó khăn cho vi c l p ch m c ti ng Vi tệ ậ ỉ ụ ế ệ .................................................. 30
3.2 Đ c đi m v t trong ti ng Vi t và vi c tách tặ ể ề ừ ế ệ ệ ừ ........................................ 31
3.2.1 . Đ c đi m v t trong ti ng Vi t:ặ ể ề ừ ế ệ ....................................................... 31
3.2.2 Tách từ ..................................................................................................... 32
3.3 Gi i quy t các v n đ hi n th c a ti ng Vi t (v n đ chính t )ả ế ấ ề ể ị ủ ế ệ ấ ề ả ............. 34
3.3.1 V n đ b ng mãấ ề ả ...................................................................................... 34
3.3.2 V n đ d u thanhấ ề ấ .................................................................................... 35
3.3.3 V n đ d u t h p nguyên âmấ ề ấ ổ ợ ............................................................... 36
3.4 Gi i quy t các v n đ v t c a ti ng Vi tả ế ấ ề ề ừ ủ ế ệ ............................................... 37
3.4.1 Lu t xác đ nh các t láyậ ị ừ .......................................................................... 37
3.4.2 Lu t xác đ nh các liên tậ ị ừ ......................................................................... 37
3.5 Xây d ng t đi n ti ng Vi tự ừ ể ế ệ ........................................................................ 38
Ch ng 4: B TÌM KI M THÔNG TIN – SEARCH ENGINEươ Ộ Ế ......................... 40
1. Vì sao ta c n m t công c tìm ki m (SE) ?ầ ộ ụ ế ........................................................ 40
2. Các ph ng th c tìm ki mươ ứ ế .................................................................................. 40
2.1 Tìm theo t khoá – Keyword searchingừ ......................................................... 40
2.2 Nh ng khó khăn khi tìm theo t khoá ữ ừ .......................................................... 41
2.3 Tìm theo ng nghĩa – Concept-based searchingữ ............................................ 41
3. Các chi n l c tìm ki mế ượ ế ..................................................................................... 42
3.1 Tìm thông tin v i các th m c ch đớ ư ụ ủ ề ......................................................... 42
3.2 Tìm thông tin v i các công c tìm ki mớ ụ ế ....................................................... 43
3.3 T i u câu truy v n ố ư ấ ...................................................................................... 43
3.4 Truy v n b ng ví dấ ằ ụ ..................................................................................... 44
Ch ng 5: M T S SEARCH ENGINE THÔNG D NG TRÊN TH GI Iươ Ộ Ố Ụ Ế Ớ
VÀ VI T NAM Ệ .......................................................................................................... 45
1.1 Th m c c a Yahoo, Google ư ụ ủ ...................................................................... 53
1.2 Alltheweb ...................................................................................................... 54
1.3 AltaVista ....................................................................................................... 54
1.4 Lycos .............................................................................................................. 55
1.5 HotBot ............................................................................................................ 55
2. M t s search engine thông d ng Vi t Namộ ố ụ ở ệ ................................................... 55
2.1 Netnam [IV.12] .............................................................................................. 55
2.1.1 Ph ng pháp Netnam SE l p ch m c d li uươ ậ ỉ ụ ữ ệ ....................................... 58
Lê Thuý Ng c - 0012745 ọ5 Đ M Nhung - 0012624ỗ ỹ