M C L CỤ Ụ
L I MỜ Ở
Đ U................................................................................................4Ầ
PH N I: MẦ Ở
Đ U........................................................................................6Ầ
1. Tính c p thi t c a lu nấ ế ủ ậ
văn.....................................................................6
2. M c đích, nhi m v c a lu nụ ệ ụ ủ ậ
văn...........................................................7
2.1 M c đích c a lu nụ ủ ậ
văn............................................................................7
2.2 Nhi m v c a lu nệ ụ ủ ậ
văn............................................................................7
3. Ph m vi nghiênạ
c u..................................................................................7ứ
4. N i dung lu nộ ậ
văn....................................................................................8
PH N II: N IẦ Ộ
DUNG..................................................................................9
CH NG I: GI I THI U B CÔNG C TÌM KI M THÔNGƯƠ Ớ Ệ Ộ Ụ Ế
TIN.......9
1.1 Khái ni m b công c tìm ki m thôngệ ộ ụ ế
tin............................................9
1
1.2 B công c tìm ki m thông tin trênộ ụ ế
m ng..........................................13ạ
1.3 Mô hình b công c tìm ki m thông tin truy nộ ụ ế ề
th ng......................18ố
1.4 c u trúc d li u trong t ch c và tìm ki m thôngấ ữ ệ ổ ứ ế
tin.......................20
1.4.1 B ngả
băm.............................................................................................20
1.4.1.1 Khái ni m hàmệ
băm........................................................................20
1.4.1.2 Khái ni m b ngệ ả
băm......................................................................22
1.4.1.3 Gi i quy t xungả ế
đ tộ........................................................................23
1.4.2 Cây cân b ng nhi u đ ng B -ằ ề ườ
Tree..................................................27
1.4.2.1 Đ nh nghĩa cây B -ị
Trees................................................................27
1.4.2.2 Cây B* - Tree.................................................................................29
1.4.2.3 Cây B+ - Tree..................................................................................29
1.4.2.4 Cây BLink – Trees.............................................................................31
1.4.2.5 L a ch n ph ng pháp d li u t nự ọ ươ ữ ệ ầ
số.............................................32
2
CH NG II: CÁC CÔNG C TÌM KI M CƯƠ Ụ Ế Ơ
B N.............33Ả
2.1 Thu h i trangồ
Web................................................................................33
2.1.1 Web Crawler.......................................................................................33
2.1.2 Ch n l a cácọ ự
trang.............................................................................34
2.2 L uư
tr ...............................................................................................38ữ
2.2.1 S phân tán trang theo các nút...ự.........................................................39
2.2.2 Các ph ng pháp t ch c trang v tươ ổ ứ ậ
lý.................................................40
2.2.3 Các chi n thu t c pế ậ ậ
nh t....ậ..................................................................40
2.3 L p chậ ỉ
m c........................................................................................43ụ
2.1.1 C u trúc c a b ng chấ ủ ả ỉ
m cụ.................................................................45
2.1.2 M t s tháchộ ố
th c.ứ...............................................................................46
2.3.3 Chia b ng chả ỉ
m c.ụ...............................................................................46
2.4 S p x p và phân tích liênắ ế
k t............................................................48ế
3
2.4.1 Ph ng phápươ
PageRank.......................................................................49
2.4.2 Ph ng phápươ
HIST..............................................................................54
CH NG III: THI T K CÁC CÔNG C TÌM KI M THÔNG TINƯƠ Ế Ế Ụ Ế
TRÊN M NGẠ...............................................................................................61
3.1 Mô đun l p chậ ỉ
m c..............................................................................62ụ
3.1.1 Khái ni m chệ ỉ
m cụ................................................................................62
3.1.1 Các c u trúc l u chấ ư ỉ
m cụ....................................................................62
3.1.2 Các b c xây d ng ch m c theo ph ng pháp Invertedướ ự ỉ ụ ươ
files............68
3.1.4 L p ch m c v i ngu n d li u đ uậ ỉ ụ ớ ồ ữ ệ ầ
vào...............................................76
3.2 Mô đun tìm
ki m..................................................................................77ế
3.2.1 Các d ng truyạ
v nấ...............................................................................80
3.2.2 Phân tích cú pháp truy v nấ.................................................................81
3.2.3 Các ph ng pháp gi i quy t v nươ ả ế ấ
đ ..ề..................................................83
3.3 Mô đun s pắ
x p....................................................................................82ế
4
Các mô hình s p x p và đánhắ ế
giá........................................................82
1. Mô hình
Boolean.................................................................................83
2. Mô hình không gian vector.................................................................84
PH N III: K TẦ Ế
LU N...............................................................................90Ậ
1. K t qu đ t đ c trong lu nế ả ạ ượ ậ
văn.......................................................90
2. H ng phát tri n trong t ngướ ể ươ
lai......................................................91
TÀI LI U THAM KH O..........................................................................94Ệ Ả
PHỤ
L C.....................................................................................................98Ụ
5