Luận văn thạc sĩ: Nghiên cứu kiến trúc hệ phân tán và ứng dụng xây dựng hệ thống quản lý thông tin đăng kiểm

Chia sẻ: Sdfas Vfdtg | Ngày: | Loại File: PDF | Số trang:99

Thêm vào BST

Báo xấu

137
lượt xem 32
download

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

Nghiên cứu kiến trúc hệ phân tán và ứng dụng xây dựng hệ thống quản lý thông tin đăng kiểm nhằm nghiên cứu,nắm vững phương pháp thực hiện cảu máy tìm kiếm, nghiên cứu hệ phân tán đa server.

Chủ đề:

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

Lưu

Nội dung Text: Luận văn thạc sĩ: Nghiên cứu kiến trúc hệ phân tán và ứng dụng xây dựng hệ thống quản lý thông tin đăng kiểm

i B GIÁO D C VÀ ĐÀO T O Đ I H C ĐÀ N NG LÊ VĂN TIÊN NG D NG H PHÂN TÁN Đ T I ƯU TH I GIAN X LÝ CHO MÁY TÌM KI M LU N VĂN TH C SĨ K THU T ĐÀ N NG – Năm 2011
ii L I CAM ĐOAN Tôi xin cam ñoan ñây là công trình nghiên c u c a riêng tôi dư i s hư ng d n khoa h c c a PGS. TS. Lê Văn Sơn. Các s li u và k t qu nêu trong lu n là trung th c và chưa t ng ñư c ai công b trong b t kỳ công trình nào khác. Ngư i cam ñoan Lê Văn Tiên
iii M CL C L I CAM ĐOAN ................................................................................................. i M C L C .......................................................................................................... iii DANH M C CÁC T VI T T T.................................................................... vi DANH M C CÁC B NG ............................................................................... vii DANH M C CÁC HÌNH ................................................................................ vii M Đ U ..............................................................................................................1 CHƯƠNG 1: T NG QUAN V MÁY TÌM KI M..........................................5 1.1 Gi i thi u m t s máy tìm ki m thông d ng ..........................................5 1.2 Ki n trúc và cơ ch ho t ñ ng c a máy tìm ki m ..................................9 1.3 B thu th p thông tin – Crawler ...........................................................10 1.3.1 Các th thu t tìm ki m c a Crawler ..............................................11 1.3.2 Tính năng b t bu c crawler ph i tuân theo ....................................13 1.3.3 Tính năng crawler nên tuân theo....................................................13 1.3.4 V n ñ cơ b n c n gi i quy t c a Crawler.....................................14 1.3.5 Xây d ng Crawler ..........................................................................15 1.3.6 V n ñ c n tránh ............................................................................17 1.4 B l p ch m c – Index .........................................................................18 1.5 B tìm ki m thông tin – Search Engine................................................20 1.5.1 Tìm ki m theo t khóa ...................................................................20 1.5.2 Tìm theo ng nghĩa ........................................................................21 1.6 C u trúc lưu tr d li u index files.......................................................22 1.7 K t lu n.................................................................................................23 CHƯƠNG 2: H PHÂN TÁN CHO MÁY TÌM KI M..................................25 2.1 Đ nh nghĩa và các tính ch t h phân tán ...............................................25 2.1.1 Đ nh nghĩa......................................................................................25 2.1.2 Tính ch t ........................................................................................27 2.2 Truy n thông trong h phân tán............................................................32
iv 2.2.1 Mô hình client – server ..................................................................33 2.2.2 Mô hình RPC(Remote Procedure Call: g i th t c t xa) .............34 2.2.3 Truy n thông ñi p (MOM) ............................................................36 2.2.4 Truy n thông hư ng dòng (SOM) .................................................37 2.2.5 Truy n thông ña ñi m (MultiCast) ................................................37 2.3 Đ ng b hóa ti n trình ..........................................................................38 2.3.1 Đ t v n ñ ......................................................................................38 2.3.2 Các gi i pháp ñ ng b ti n trình ....................................................39 2.3.3 K t lu n ..........................................................................................47 CHƯƠNG 3: NG D NG H PHÂN TÁN T I ƯU TH I GIAN X LÝ CHO MÁY TÌM KI M ......................................................................................48 3.1 Phân tích máy tìm ki m trên h t p trung.............................................48 3.1.1 Phân tích ho t ñ ng c a máy tìm ki m trên h t p trung ..............48 3.1.2 M t s h n ch c a máy tìm ki m trên h t p trung......................48 3.1.3 Các y u t nh hư ng ñ n th i gian x lý c a máy tìm ki m .......49 3.1.4 Hư ng gi i quy t v n ñ ................................................................50 3.2 Đ xu t phương th c ho t ñ ng c a máy tìm ki m trên h phân tán ...52 3.2.1 Phương th c ho t ñ ng t ng th c a h th ng...............................52 3.2.2 Phương th c liên k t các tr m trong h th ng ...............................53 3.2.3 Phương th c ho t ñ ng t i các tr m c a h th ng .........................54 3.2.4 Phương th c lưu tr file index c a h th ng .................................57 3.3 Các v n ñ phát sinh và cách gi i quy t ...............................................58 3.3.1 Ch n l a server x lý chính ...........................................................58 3.3.2 V n ñ ñ ng b các ti n trình ........................................................61 3.3.3 V n ñ s c ñư ng truy n ............................................................64 3.3.4 V n add, remove các tr m..............................................................66 3.4 Phân tích h th ng.................................................................................69 3.4.1 Danh sách các tác nhân h th ng ...................................................69 3.4.2 Sơ ñ tác nhân (UC).......................................................................70
v 3.4.3 Bi u ñ tu n t ...............................................................................72 3.4.4 Bi u ñ ho t ñ ng (activity) ..........................................................74 3.4.5 Sơ ñ l p ........................................................................................77 3.4.6 Các b ng d li u c a h th ng file index.......................................77 3.4.7 Xây d ng h th ng .........................................................................79 3.4.8 Đ mô chương trình .......................................................................84 K T LU N .......................................................................................................87 TÀI LI U THAM KH O ..................................................................................89 QUY T Đ NH GIAO Đ TÀI LU N VĂN TH C SĨ (B N SAO).
vi DANH M C CÁC T VI T T T SE Máy tìm ki m DS H phân tán DNS H th ng tên mi n MON Truy n thông hư ng thông ñi p SOM Truy n thông thư ng dòng RPC G i th t c t xa MDR Nh p trôi l n nh t c a ñ ng h WWV Th i gian qu c t UTC Gi ph i h p qu c t P Ti n trình
vii , DANH M C CÁC B NG B ng 1.1. B ng x p h ng search engine năm 2009............................................ 5 B ng 3.1. B ng tiêu chí t i ưu máy tìm ki m....................................................50 B ng 3.2. B ng tiêu chí ch n server t i ưu ........................................................59 B ng 3.3. B ng phân tích ñ r i khác nhau c a các server trong h ..................59 B ng 3.4. B ng d li u tbl_document ................................................................77 B ng 3.5. B ng t khóa tbl_key_word ...............................................................78 B ng 3.6. B ng ch ñ tbl_topics .......................................................................78 B ng 3.7. B ng lo i d li u tbl_data_type .........................................................78
viii DANH M C CÁC HÌNH Hình 1.1 B ng x p h ng search engine năm 2009 ...............................................1 Hình 1.2 Giao di n c a google search engine ......................................................6 Hình 1.3 Giao di n c a xalo.vn search engine .....................................................8 Hình 1.4 Mô hình ho t ñ ng c a máy tìm ki m...................................................9 Hình 1.5 Bi u ñ tr ng thái c a m t liên k t......................................................17 Hình 1.6 Quá trình ñánh ch m c .......................................................................18 Hình 1.7 Các bư c phân tích tài li u ..................................................................19 Hình 1.8 C u trúc lưu tr files index [12] ..........................................................23 Hình 1.9 C u trúc d li u inverted index [11]....................................................23 Hình 2.1 H th ng máy ñơn ...............................................................................25 Hình 2.2 Các th c th c a h phân tán ...............................................................26 Hình 2.3 Mô hình Client – Server ......................................................................33 Hình 2.4 Mô hình Synchronous RPC .................................................................35 Hình 2.5 Mô hình Asynchronos RPC.................................................................36 Hình 2.6 Mô hình MOM.....................................................................................36 Hình 2.7 Mô hình multicast many-to-many .......................................................38 Hình 2.8 Mô hình tr t t t ng ph n....................................................................44 Hình 2. 9 Th t các s ki n t i c a các ti n trình t i các tr m phát nh n ........45 Hình 2. 10 Các th i gian ñánh d u Lamport (Lamport timestamps)..................46 Hình 2. 11 Ví d th i gian logic Lamport ..........................................................47 Hình 3. 1 Mô hình ho t ñ ng c a pha x lý yêu c u ngư i dùng ......................50 Hình 3. 2 Các bư c ho t ñ ng c a máy tìm ki m ng d ng h phân tán ..........51 Hình 3.3 Mô hình ho t ñ ng t ng th máy tìm ki m ng d ng h phân tán......52 Hình 3. 4 Mô hình liên k t các tr m trong h th ng...........................................54 Hình 3. 5 Mô hình ho t ñ ng c a tr m các tr m con trong h th ng.................54 Hình 3. 6 Thu t toán x lý c a crawler ..............................................................56 Hình 3. 7 Mô hình lưu tr h th ng files index t i m i tr m .............................57
ix Hình 3. 8 H th ng index file theo mô hình cây ................................................58 Hình 3. 9. Sơ ñ ch n server t i ưu ....................................................................60 Hình 3. 10 Mô hình không ñ ng b c a hai ti n trình gi a hai tr m .................61 Hình 3. 11.K t qu sau khi ñ ng b ti n trình theo thu t toán lamport .............63 Hình 3. 12 Thu t toán ki m tra tình tr ng URL .................................................64 Hình 3. 13 Mô hình s c ñư ng truy n ............................................................65 Hình 3. 14 C u trúc giao ti p 2PC tuy n tính.....................................................66 Hình 3. 15 Thu t toán x lý tr m remove kh i h .............................................68 Hình 3. 16 Thu t toán x lý vi c add các tr m...................................................69 Hình 3. 17 bi u ñ UC c a ngư i s d ng .........................................................70 Hình 3. 18 Bi u ñ UC c a admin......................................................................71 Hình 3. 19 Bi u ñ tu n t x lý yêu c u ngư i dùng .......................................72 Hình 3. 20 Bi u ñ tu n t truy tìm thông tin t ñ ng .......................................73 Hình 3. 21 Bi u ñ tu n t l p ch m c t ñ ng ................................................73 Hình 3. 22 Bi u b ho t ñ ng x lý yêu c u ngư i dùng...................................74 Hình 3. 23 Bi u ñ ho t ñ ng truy tìm thông tin t ñ ng ..................................75 Hình 3. 24 Bi u ñ ho t ñ ng l p ch m c t ñ ng............................................76 Hình 3. 25 Mô hình quan h gi a các b ng d li u............................................79
1 M Đ U 1. Lý do ch n ñ tài Hơn 40 năm k t khi internet ra ñ i cho ñ n nay, nó mang l i r t nhi u ti n ích h u d ng cho ngư i s d ng ñi n hình như h th ng thư ñi n t (email), trò chuy n tr c tuy n (chat), máy truy tìm d li u (search engine), các d ch v thương m i, chuy n ngân và các d ch v v y t giáo d c...Đi kèm v i s bùng n các d ch v trên internet là s dùng n v s lư ng website trên internet, hi n t i s lư ng website ñã lên con s hàng t và không ng ng tăng lên theo th i gian, ñ ng ñ u là tên mi n có ñuôi .com, theo th ng kê m i nh t ñã lên t i 84.000.000 tên mi n. Tên mi n có ñuôi .vn cũng ñã lên t i 140.000 tên mi n. Chính s bùng n v s lư ng website trên internet ñã b sung cho kho thông tin càng ngày càng kh ng l hơn và ngày nay h u như m i ki n th c c a m i lĩnh v c ñ u có th tìm th y trên internet. V n ñ ñ t ra ñây là làm th nào ñ tìm ki m m t m u thông tin trong kho tàng thông tin kh ng l như v y m t cách chính xác và nhanh nh t, l i gi i cho câu h i ñó là s d ng máy tìm ki m (search engine) và hi n nay nhi u nhà d ch v ñã s d ng nó r t thành công, ñi n hình như: Google, Yahoo, Mirosoft… Máy tìm ki m ñã xu t hi n và ñư c ñưa vào s d ng t r t s m, nhưng ñ t i ưu hóa sao cho th i gian tr l i k t qu tìm ki m nhanh nh t và chính xác nh t thì các chuyên gia cũng ñang ngày càng hoàn thi n. Trong th i gian g n ñây nh s phát tri n vư t b c c a lĩnh v c ph n c ng CNTT và truy n thông, nh v y mà m t gi i pháp m i cho các ng d ng CNTT ñư c ra ñ i và ñang ñư c các chuyên gia ñánh giá cao v l i ích mà mó mang l i ñó là “H phân tán - Distributed Systems”. H phân tán là h th ng x lý thông tin bao g m nhi u b x lý ho c b vi x lý n m t i các v trí khác nhau ñư c liên k t v i nhau thông qua phương ti n vi n thông dư i s ñi u khi n th ng nh t c a m t h ñi u hành nh m tăng t c ñ
2 bình quân trong tính toán x lý, c i thi n tình tr ng luôn s n sàng c a các lo i tài nguyên, tăng ñ an toàn cho d li u, ña d ng hóa các lo i hình d ch v tin h c, b o ñ m tính toàn v n c a thông tin. Xu t phát t nhu c u và các ti n ñ trên, vi c t i ưu hóa máy tìm ki m thông tin, mà ñ c bi t là t i ưu th i gian tìm ki m thông tin c a máy tìm ki m là v n ñ r t có ý nghĩa trong giai ño n CNTT hi n nay và tương lai. Chính vì v y tôi ch n hư ng nghiên c u này và áp d ng “h phân tán” ñ t i ưu th i gian x lý cho máy tìm ki m và l y tên ñ tài là “ ng d ng h phân tán ñ t i ưu th i gian x lý cho máy tìm ki m”. 2. M c ñích và nghi m v nghiên c u c a ñ tài M c ñích c a ñ tài là nghiên c u áp d ng h phân tán vào máy tìm ki m nh m gi i quy t 3 yêu c u ñ t ra như sau: M t: Gi m th i gian tìm ki m cho máy tìm ki m: có 3 nguyên nhân chính + Gi m t i lư ng truy c p vào tài nguyên chung + Rút ng n kho ng cách v t lý gi a ngư i dùng và server + Tăng t c ñ tính toán – x lý Hai: Tăng ñ an toàn cho d li u cho máy tìm ki m: có 3 nguyên nhân chính + D li u ñư c ñ t t i nhi u server khác nhau và có kh năng ph c h i + Đ m b o tính ñ ng b d li u gi a các server + Đ m b o ñư c tính toàn v n c a d li u Ba: Đ m b o h th ng luôn ho t ñ ng thông su t: có 3 nguyên nhân chính + Tính co giãn c a h th ng cao + Tính ch u l i c a h th ng cao + Tính m c a h th ng cao
3 3. Đ i tư ng và ph m vi nghiên c u - Nghiên c u mô hình ho t ñ ng t ng th c a máy tìm ki m và m t s gi i pháp tìm ki m thông d ng - Nghiên c u h phân tán ña server + Xây d ng h phân tán ña server + Lưu tr , truy xu t d li u trên h phân tán ña server - Nghiên c u, ng d ng h phân tán vào máy tìm ki m - Nghiên c u và áp d ng b ñ nh tuy n ưu tiên yêu c u (Request) ngư i dùng - Ngôn ng l p trình Java, Lucene - H qu n tr cơ s d li u My SQL 4. Gi thi t nghiên c u - Hi u ñư c quá trình ho t ñ ng và m t s gi i pháp xây d ng máy SE - Hi u ñư c b n ch t c a h phân tán và quá trình trao ñ i thông tin gi a các thành ph n trong h - Hi u thêm ngôn ng l p trình Java, Lucene và h qu n tr cơ s d li u My SQL - Hi u và v n d ng ñư c gi i pháp ng d ng h phân tán ñ t i ưu th i gian tìm ki m cho máy SE 5. Phương pháp nghiên c u - Thu th p, tìm hi u, phân tích các tài li u và thông tin có liên quan ñ n lu n văn - Phân tích, n m rõ quá trình ho t ñ ng c a máy tìm ki m - N m rõ cách xây d ng, truy xu t và lưu tr d li u trên h phân tán
4 - Phân tích, tìm hư ng gi i quy t cho các v n ñ n y sinh khi áp d ng h phân tán vào máy SE - Tri n khai xây d ng chương trình ch y trên h phân tán - Tri n khai xây d ng chương trình ch y trên h t p trung - Ki m th , ñánh giá k t qu và rút ra k t lu n 6. Ý nghĩa khoa h c và th c ti n c a ñ tài - Nghiên c u, n m v ng phương pháp th c hi n c a máy tìm ki m - Nghiên c u, n m v ng b n ch t và phương pháp ho t ñ ng c a h phân tán ña server - Nghiên c u, xây d ng m t mô hình lưu tr thông tin m i cho máy tìm ki m - Gi m ñáng k th i gian th c hi n cho máy tìm ki m - Tăng ñ an toàn cho d li u - Đ m b o h th ng luôn thông su t - Mang l i l i ích ng d ng r t l n
5 CHƯƠNG 1: T NG QUAN V MÁY TÌM KI M Máy tìm ki m (ti ng Anh: search engine), hay còn ñư c g i v i nghĩa r ng hơn là công c tìm ki m (search tool), nguyên thu là m t ph n m m nh m tìm ra các trang web trên m ng Internet có n i dung theo yêu c u ngư i dùng d a vào các thông tin mà chúng có. Tr lư ng thông tin này c a công c tìm ki m th c ch t là m t lo i cơ s d li u (database) c c l n. Vi c tìm các tài li u s d a trên các t khóa (keyword) ñư c ngư i dùng gõ vào và tr v m t danh m c c a các trang Web có n i dung ch a t khóa mà nó tìm ñư c. Máy tìm ki m ho t ñ ng d a vào 3 b chính: - B thu th p thông tin – Robot - B l p ch m c – Index - B tìm ki m thông tin – Search Engine 1.1 Gi i thi u m t s máy tìm ki m thông d ng B ng 1.2. B ng x p h ng search engine năm 2009
6 Th gi i google.com Hình 1.1 Giao di n c a google search engine Google là b máy tìm ki m (Search Engine) hi n ñang ñư c ñánh giá là “vô ñ ch” trên Internet, v i trên 4,2 t trang Web ñã ñư c l p ch m c và có t c ñ tìm ki m c c nhanh. Google không ch là công c tìm ki m ñư c h u h t nh ng ngư i lư t Web s d ng do h tr t i 97 ngôn ng , ñây còn là ti n ích tìm ki m ñư c nhúng vào r t nhi u website (m t d ch v ñư c Google cung c p dư i nhi u hình th c và cho nh ng ñ i tư ng khác nhau). Các b tìm ki m c a google Google không ng ng tìm ki m và c p nh t các trang m i ñ thêm vào ch m c c a b n. Có chương trình ph trách v n ñ này ñư c g i là các robot hay b tìm ki m (Googlebot). Các Googlebot ñư c g i chương trình tìm ki m có nhi m v duy
7 nh t là ñ thu th p tài li u web ñ xây d ng m t cơ s d li u ñư c s d ng b i các công c tìm ki m c a nó. Các Googlebot s d ng m t quy trình d a trên thu t toán xác ñ nh các trang web ñ thu th p d li u, t n s và s lư ng trang ñ tìm n p t m i trang web. Danh sách này các trang web toàn di n ñ xác ñ nh các liên k t ñ n các trang khác. B l p ch m c c a google Đánh ch m c là m t quá trình quét qua các trang web và t o ra ch s có s d ng Google ñ cho k t qu khi b n tìm ki m. Th c t , các robot các phân tích và ñưa ra m t ch m c c a t t c các t h xem và v trí c a h . Và vi c trang web có ñư c Google ñánh ch hay không luôn là m i quan tâm hàng ñ u c a các nhà thi t k web hi n nay. Các lo i d li u google có th tìm ki m Không h n v y, Google cũng trích xu t thông tin ch m c ho c nhi u lo i t p tin khác nhau: PDF, PS (Adobe PostScript), Excel (xls), tài li u, văn b n MW, DOC, WRI, RTF, ANS, TXT, thuy t trình PowerPoint (ppt) các t p tin, Microsoft Works (wks, wps, Wdb) và swf. Đi u này ñư c th c hi n ñ cung c p cho Google nhi u k t qu hơn, trên th c t , trong quá trình th c hi n tìm ki m b n cũng có th th y hi n th m t s lo i t p tin khác html, ví d : file .doc hay .pdf B pageRank c a google Google PageRank là m t h th ng có nhi m v x p h ng các trang web, ñư c phát tri n b i Larry Page và Sergey Brin thu c Đ i h c Stanford. Trong khi hi n nay Google có r t nhi u k sư làm vi c ñ c i thi n v m i m t c a Google hàng ngày, PageRank ti p t c ñóng m t vai trò trung tâm trong nhi u công c tìm ki m web c a Google.
8 Vi t Nam xalo.vn Hình 1.2 Giao di n c a xalo.vn search engine Xalo.vn là m t Máy tìm ki m (search engine) ñư c Tinhvân Media phát tri n v i tham v ng Xalo.vn s tr thành công c tìm ki m ti ng Vi t hàng ñ u c a Vi t Nam. Xalo.vn hi n t i ñang cung c p 7 d ch v tìm ki m bao g m: - Tìm ki m Web: d ch v tìm ki m thông tin t ng h p trên d li u g n 100 tri u trang văn b n ti ng Vi t hi n có trên các Website c a Vi t Nam - Tìm ki m Tin t c: d ch v t ng h p tin t c và tìm ki m thông tin trên d li u d ng tin t c ñư c t ng h p t g n 70 trang tin ñi n t hàng ñ u c a Vi t Nam
9 - Tìm ki m Di n ñàn: d ch v tìm ki m cho phép ngư i dùng tìm ki m thông tin t hơn 100 di n ñàn l n nh t c a Vi t Nam hi n t i. - Tìm ki m nh: d ch v tìm ki m hình nh trên s lư ng hơn 20 tri u hình nh ñư c ngư i dùng Vi t Nam ñưa lên Internet. - Tìm ki m Blog: d ch v tìm ki m cho phép ngư i dùng tìm ki m thông tin trên h u h t các m ng xã h i ñư c cung c p b i Vi t Nam cũng như trên th gi i mà ngư i Vi t Nam hay s d ng - Tìm ki m Nh c: d ch v tìm ki m d li u Nh c t các Website nghe nh c tr c tuy n l n nh t Vi t Nam hi n t i. - Tìm ki m Rao v t: d ch v t ng h p và tìm ki m thông tin rao v t t hơn 20 Website mua bán rao v t l n nh t Vi t Nam V i các d ch v cung c p và tính năng khác bi t cho t ng d ch v , Xa L ñang không ng ng ñư c hoàn thi n ñ có th ph c v t t nh t nhu c u tìm ki m c a ngư i dùng Internet Vi t Nam và tr thành máy tìm ki m ti ng Vi t hàng ñ u c a Vi t Nam. 1.2 Ki n trúc và cơ ch ho t ñ ng c a máy tìm ki m Crawler Hình 1.3 Mô hình ho t ñ ng c a máy tìm ki m
10 Máy tìm ki m chi thành 2 ph n chính Front-end và ph n Back-end - Front- end: Bao g m giao di n ngư i s d ng (Search engine interface); b s p x p (ranking) và b x lý yêu c u ngư i dùng (query parser) Khi ngư i s d ng g i m t yêu c u tìm ki m m t m u thông tin, máy tìm ki m s phân tích yêu c u và g i ñ n server, server th c hi n so kh p yêu c u v i d li u trong kho index files và s p x p k t qu tìm ñư c theo th t t cao ñ n c a ñ chính xác, cu i cùng là hi n th k t qu cho ngư i dùng. - Back-end: Bao g m b thu th p thông tin (Crawler) và b l p ch m c (indexer) B Crawler d a vào các robot tìm ki m s t ñ ng tìm ki m thông tin trên internet và chuy n thông tin qua b indexer l p ch m c và lưu vào kho d li u index files. Các thành ph n này s ñư c phân tích c th ph n sau. 1.3 B thu th p thông tin – Crawler T m t hay nhi u các liên k t ban ñ u, Crawler lên ñư ng th c hi n công vi c “lùng s c” Internet c a mình. Crawler t i v n i dung các trang web t các liên k t ñã nh n ban ñ u và truy xu t các liên k t m i n m trong n i dung c a các trang này. Các liên k t m i này s ñư c n p vào m t trình ñi u khi n (Crawler Manager). Crawler Manager s quy t ñ nh các liên k t nào s ñư c vi ng thăm k ti p, Crawler Manager s n p chúng vào hàng ñ i ñ ch x lý. Các liên k t này s ñư c qu n lý trong cơ s d li u ñ thu n ti n cho công vi c c p nh t thông tin m i. Trong m t l n th c hi n thì các liên k t ph i ch ñư c truy c p m t l n ñ tăng kh năng ho t ñ ng và tránh trùng l p n i dung. M t crawler ñi qua b n bư c cơ b n: • B t ñ u t m t hay nhi u liên k t • T i n i dung
11 • Phân tích n i dung, tìm liên k t, ñi theo các liên k t • Theo dõi liên k t, tránh trùng l p Có nhi u ch ñ làm vi c cho crawler th c hi n nhi m v truy tìm thông tin. Các ch ñ ñư c phân bi t theo nhi u cách. Các ñ c ñi m phân bi t có th là: • Batch Mode • Incremental Mode Batch mode Crawler s ñánh ch m c liên t c các trang web và không t i n i dung v ñ lưu tr . Cách này n i dung luôn ñư c c p nh t nhưng ch phù h p cho lư ng trang web nh có gi i h n. Ch ng h n như m c tiêu c a crawler ñư c ñ nh ra là th c hi n trên m t s website c th nào ñ y. Crawler ch có nhi m v liên t c ch y qua các wesiste này ñ c p nh t các n i dung m i. Incremental Mode ho t ñ ng ch ñ này crawler s không bao gi xóa các n i dung lưu tr . Khi g p m t tài li u ñư c cho là ñã vi ng thăm thì crawler s tuân theo chi n lư c c p nh t n i dung ñã ñư c cài ñ t. ch ñ này thì crawler c n ph i có kho lưu tr tài li u th t l n. • Breadth-first(Tìm ki m theo chi u r ng) • Depth-first(Tìm ki m theo chi u sâu) 1.3.1 Các th thu t tìm ki m c a Crawler 1.3.1.1Chi n thu t tìm ki m theo chi u sâu (Depth-first) T m t danh sách ch a các liên k t c n duy t, th c hi n các bư c sau : (1) Cho danh sách = {trang ñ u tiên} (2) L y trang ñ u tiên trong danh sách. * N u có qua (3) * N u không qua (5)