Ngày nay nhờ sự bùng nổ của công nghệ thông tin, lịch sử nhân loại đã bước
sang một trang mới. Những thành tựu của ngành công nghệ thông tin là vô cùng to lớn,
nó đã chi phối và làm thay đổi mọi mặt của đời sống xã hội, làm cho cuộc sống của
con người văn minh, hiện đại hơn. Sự ra đời của internet chính là bước tiến vĩ đại của
nhân loại, là yếu tố quan trọng bậc nhất chi phối cuộc sống của chúng ta ngày nay.
Nhờ có internet thế giới trở nên ‘phẳng’ hơn, ở mọi nơi trên trái đất chúng ta đều có
thể học tập và tìm kiếm thông tin.
Theo guồng quay của cuộc sống, thế giới internet ngày càng rộng lớn và phong
phú hơn. Cứ mỗi phút trôi qua có thêm hàng triệu trang web được sinh ra đểlàm giàu
cho vốn tài nguyên tri thức của nhân loại. Nhưng cũng chính vì thế mà việc chọn lọc,
tìm kiếm thông tin lại trở nên khó khăn hơn. Với kho dữ liệu đồ sộ như internet, vấn
đề trích xuất và tổng hợp thông tin đã trở thành vấn đề thực sự cấp thiết hiện nay. Nếu
giải quyết được vấn đề này chúng ta sẽ loại bỏ được một chướng ngại lớn trên con
đường tổng hợp thông tin của nhân loại.
Đề tài khóa luậnđặt ra vấn đề tìm hiểu về trìnhthu thập thông tin trên web và
bước đầu sẽ xây dựng một ứng dụng có khả năng tổng hợp thông tin tự động từ các
trang báo điện tử lớn. Đề tài nếu thành công sẽ là bước đi không nhỏ giúp cho việc
tổng hợp thông tin trở nên đơn giản hơn, giảm được nhiều chi phí công sức so với việc
tổng hợp thủ công, và là tiền đề để xây dựng nên một hệ thống máy tìm kiếm, giống
như google, cho người Việt Nam.
Nội dung của khóa luận sẽ tập trung vào các mục tiêu chính sau:
- Đưa ra được một cái nhìn tổng quát về trình thu thập web (web crawler)
-Xây dựng một ứng dụng website tổng hợp thông tin cókhả năng thu thập các
bản tin từ các trang báo lớn như Dân trí.
Để giải quyết được các mục tiêu này, khóa luận được chia thành ba chương lớn:
Chương 1: Tìm hiểu về trình thu thập web
Trong chương này, chúng ta sẽ lần lượt tìm hiểu các khái niệm cơ bản trong trình
thu thập web. Phần lớn nội dung trong chương này sẽ đi sâu vào việc tìm hiểu các
thành phần cấu thành nên một trìnhthu thập, các chiến lược thu thập dữ liệu, việc đánh
giá của trình thu thập đối với trang web. Qua đó chúng ta sẽ có một bức tranh chung
Tìm hiểu về web crawlervà xây dựng websitetổng hợp thông tin 2010
2
về trình thu thập web, và có thể hiểu hơn về các giá trị thực tiễn mà nó mang lại trong
đời sống của con người.
Chương 2: Xây dựng ứng dụng website tổng hợp thông tin
Phần đầu chương sẽ trình bày về các kiến thức nền tảng và các công nghệ liên
quan, ở phần tiếp theo là các đánh giá phân tích và các giải pháp nhằm nâng cao hiệu
suất của trình thu thập, phần cuối chương là việc hiện thực hóa ứng dụng thông qua
việc xây dựng hệ thống cơ sở dữ liệu và thiết kế giao diện website.Cũng trong phần
này tôi sẽnêu ra hai cách thu thập thông tin. Một là cách làm phổ biến hiện nay tôi gọi
là cách làm truyền thống, một là cách làm mới tôi tìm ra. Cách làm mới này tối ưu hơn
và có thể giải quyết được các hạn chế trongcách làm truyền thống.
Chương 3: Kết luận
Phần k ết luận cũng là phần cuối của khóa luận sẽ nhìn lại những điều đã làm
được trong khóa luận này, nêu lên những vấn đề còn vướng mắc, từ đó đề ra hướng
phát triển tiếp theo cho đề tài.
61 trang |
Chia sẻ: oanhnt | Lượt xem: 2121 | Lượt tải: 2
Bạn đang xem trước 20 trang tài liệu Khóa luận Tìm hiểu về web crawler và xây dựng website tổng hợp thông tin, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
Tìm hiểu về web crawler và xây dựng website tổng hợp thông tin 2010
I
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Nguyễn Minh Phúc
TÌM HIỂU VỀ WEB CRAWLER VÀ XÂY DỰNG
WEBSITE TỔNG HỢP THÔNG TIN
KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Công nghệ thông tin
HÀ NỘI - 2010
Tìm hiểu về web crawler và xây dựng website tổng hợp thông tin 2010
II
HÀ NỘI - 20
(chữ hoa, 12pt, đậm, căn giữa)
LỜI CẢM ƠN
Tôi xin bày tỏ lòng biết ơn sâu sắc của mình đến thầy Hoàng Xuân Huấn, thuộc
bộ môn Khoa học máy tính, khoa Công nghệ thông tin, trường Đại học Công Nghệ,
ĐHQGHN. Trong quá trình thực hiện khóa luận, thầy đã nhiệt tình giúp đỡ, giải đáp
các thắc mắc tạo động lực giúp tôi hoàn thành khóa luận tốt nghiệp này.
Tôi cũng xin được bày tỏ lời cảm ơn tới các thầy cô trong bộ môn nói riêng và
trong khoa Công nghệ thông tin nói chung đã nhiệt tình giảng dạy để giúp chúng tôi có
được như ngày hôm nay.
Cuối cùng là lời cảm ơn tới gia đình, bạn bè những người luôn sát cánh bên tôi
những lúc khó khăn, luôn ủng hộ giúp đỡ để tôi hoàn thành khóa luận này.
Tìm hiểu về web crawler và xây dựng website tổng hợp thông tin 2010
III
TÓM TẮT NỘI DUNG
Do nhu cầu thu thập thông tin của con người ngày càng tăng, lượng thông tin trên
internet ngày càng phong phú nên vấn đề tổng hợp thông tin ngày càng trở nên bức
thiết. Với một lượng dữ liệu lớn việc thu thập bằng tay tốn rất nhiều công sức, và
không đạt hiệu quả cao, chính vì thế cần một công nghệ có thể tổng hợp thông tin một
cách tự động và trình thu thập web đã ra đời.
Đề tài khóa luận đặt ra vấn đề tìm hiểu về trình thu thập thông tin trên web và
bước đầu sẽ xây dựng một ứng dụng có khả năng tổng hợp thông tin tự động từ trang
báo điện tử lớn là trang Dân trí ( Ứng dụng được viết bằng ngôn
ngữ lập trình PHP tương tác với cơ sở dữ liệu mySQL và được xây dựng dựa trên các
tiêu chí: tốc độ thu thập nhanh, cơ sở dữ liệu gọn nhẹ, đảm bảo tính toàn vẹn của tài
liệu gốc.
Tìm hiểu về web crawler và xây dựng website tổng hợp thông tin 2010
IV
MỤC LỤC
MỞ ĐẦU ........................................................................................................1
CHƯƠNG 1. TÌM HIỂU VỀ TRÌNH THU THẬP WEB................................3
1.1. GIỚI THIỆU VỀ TRÌNH THU THẬP WEB ............................................3
1.2. CÁCH XÂY DỰNG MỘT HẠ TẦNG THU THẬP .................................4
1.2.1. Frontier..............................................................................................6
1.2.2. Lược sử và kho lưu trữ trang ..............................................................7
1.2.3. Cách lấy trang ....................................................................................8
1.2.3.1. Tiêu chuẩn loại trừ robot ..............................................................9
1.2.4. Bóc tách trang ..................................................................................10
1.2.4.1. Tiêu chuẩn trích xuất URL .........................................................11
1.2.4.2. Mô hình thẻ HTML dạng cây .....................................................12
1.2.5. Trình thu thập đa luồng ....................................................................13
1.3. CÁC CHIẾN LƯỢC THU THẬP DỮ LIỆU...........................................15
1.3.1. Chiến lược thu thập dữ liệu theo chiều sâu .......................................16
1.3.2. Chiến lược thu thập dữ liệu theo chiều rộng......................................16
1.3.3. Chiến lược thu thập dữ liệu theo ngẫu nhiên.....................................17
1.3.4. Chiến lược thu thập dữ liệu theo lựa chọn tốt nhất ngây thơ. ............17
1.4. ĐÁNH GIÁ CỦA TRÌNH THU THẬP...................................................19
1.4.1. Độ quan trọng của trang web ............................................................20
1.4.2. Phân tích tổng quát ...........................................................................21
1.4.2.1. Thước đo độ chính xác...............................................................22
1.4.2.2. Thước đo độ hoàn chỉnh.............................................................22
Tìm hiểu về web crawler và xây dựng website tổng hợp thông tin 2010
V
CHƯƠNG 2. XÂY DỰNG WEBSITE TỔNG HỢP THÔNG TIN...............25
2.1. CÁC KIẾN THỨC NỀN TẢNG .............................................................25
2.1.1. Mạng toàn cầu ..................................................................................25
2.1.2. Giao thức truyền tải siêu văn bản......................................................28
2.1.3. Ngôn ngữ đánh dấu siêu văn bản ......................................................28
2.2. CÁC CÔNG NGHỆ LIÊN QUAN .........................................................30
2.2.1. Ngôn ngữ lập trình PHP ...................................................................30
2.2.1.1. Biểu thức chính quy ...................................................................31
2.2.1.2. Các hàm xử lý chuỗi ..................................................................34
2.2.1.2.1. Tìm kiếm chuỗi trong chuỗi.................................................34
2.2.1.2.2. Tìm vị trí của chuỗi con.......................................................34
2.2.1.2.3. Hàm so sánh chuỗi...............................................................34
2.2.1.2.4. Kiểm tra chiều dài của chuỗi ...............................................35
2.2.2. MySQL ............................................................................................35
2.2.3. Một số công nghệ và tiện ích khác ....................................................37
2.2.3.1. Add-ons firebug của firefox .......................................................37
2.2.3.2. Ajax ...........................................................................................37
2.3. PHÂN TÍCH ...........................................................................................38
2.3.1. Cấu trúc bài viết trong trang báo điện tử ...........................................38
2.3.2. Các cách thu thập bài viết .................................................................42
2.3.2.1. Cách làm truyền thống ...............................................................42
2.3.2.1.1. Các bước thực hiện ..............................................................42
2.3.2.1.2. Nhận xét ..............................................................................44
2.3.2.2. Cách làm mới.............................................................................45
2.3.2.2.1. Các bước thực hiện ..............................................................45
2.3.2.2.2. Nhận xét ..............................................................................46
Tìm hiểu về web crawler và xây dựng website tổng hợp thông tin 2010
VI
2.4. THIẾT KẾ ..............................................................................................47
2.4.1. Cấu trúc cơ sở dữ liệu.......................................................................47
2.4.1.1. Danh sách các bảng....................................................................47
2.4.1.2. Chi tiết các bảng ........................................................................47
2.4.2. Phần quản trị cơ sở dữ liệu ...............................................................49
2.4.3. Phần giao diện chính trang web ........................................................50
CHƯƠNG 3: KẾT LUẬN ..............................................................................50
3.1. CÁC KẾT QUẢ ĐÃ ĐẠT ĐƯỢC ..........................................................51
3.2. HƯỚNG PHÁT TRIỂN CỦA ĐỀ TÀI ...................................................51
TÀI LIỆU THAM KHẢO...............................................................................53
Tìm hiểu về web crawler và xây dựng website tổng hợp thông tin 2010
VII
BẢNG DANH MỤC CÁC HÌNH MINH HỌA
Hình 1: Một vòng thu thập web cơ bản................................................................5
Hình 2: Mô hinh cây tương ứng với một mã nguồn HTML ...............................12
Hình 3: Một mô hình trình thu thập đa luồng.....................................................14
Hình 4: Hình minh họa về độ hoàn chỉnh và độ chính xác .................................21
Hình 5: Hình mình họa thu hồi mục tiêu............................................................23
Hình 6: So sánh giữa thuật toán breadth-first và naive best-first ........................24
Hình 7: World wide web ...................................................................................26
Hình 8. Tương tác client và server .....................................................................28
Hình 9: Add-ons firebug của trình duyệt firefox ................................................37
Hình 10: Cấu trúc phần bài viết .........................................................................39
Hình 11: Cấu trúc phần chuyên mục..................................................................40
Hình 12: Cấu trúc phần trang chủ ......................................................................41
Hình 13: Giao diện phần quản trị cơ sở dữ liệu..................................................49
Hình 14: Giao diện của trang web tổng hợp thông tin ........................................50
Tìm hiểu về web crawler và xây dựng website tổng hợp thông tin 2010
VIII
Tìm hiểu về web crawler và xây dựng website tổng hợp thông tin 2010
1
MỞ ĐẦU
Ngày nay nhờ sự bùng nổ của công nghệ thông tin, lịch sử nhân loại đã bước
sang một trang mới. Những thành tựu của ngành công nghệ thông tin là vô cùng to lớn,
nó đã chi phối và làm thay đổi mọi mặt của đời sống xã hội, làm cho cuộc sống của
con người văn minh, hiện đại hơn. Sự ra đời của internet chính là bước tiến vĩ đại của
nhân loại, là yếu tố quan trọng bậc nhất chi phối cuộc sống của chúng ta ngày nay.
Nhờ có internet thế giới trở nên ‘phẳng’ hơn, ở mọi nơi trên trái đất chúng ta đều có
thể học tập và tìm kiếm thông tin.
Theo guồng quay của cuộc sống, thế giới internet ngày càng rộng lớn và phong
phú hơn. Cứ mỗi phút trôi qua có thêm hàng triệu trang web được sinh ra để làm giàu
cho vốn tài nguyên tri thức của nhân loại. Nhưng cũng chính vì thế mà việc chọn lọc,
tìm kiếm thông tin lại trở nên khó khăn hơn. Với kho dữ liệu đồ sộ như internet, vấn
đề trích xuất và tổng hợp thông tin đã trở thành vấn đề thực sự cấp thiết hiện nay. Nếu
giải quyết được vấn đề này chúng ta sẽ loại bỏ được một chướng ngại lớn trên con
đường tổng hợp thông tin của nhân loại.
Đề tài khóa luận đặt ra vấn đề tìm hiểu về trình thu thập thông tin trên web và
bước đầu sẽ xây dựng một ứng dụng có khả năng tổng hợp thông tin tự động từ các
trang báo điện tử lớn. Đề tài nếu thành công sẽ là bước đi không nhỏ giúp cho việc
tổng hợp thông tin trở nên đơn giản hơn, giảm được nhiều chi phí công sức so với việc
tổng hợp thủ công, và là tiền đề để xây dựng nên một hệ thống máy tìm kiếm, giống
như google, cho người Việt Nam.
Nội dung của khóa luận sẽ tập trung vào các mục tiêu chính sau:
- Đưa ra được một cái nhìn tổng quát về trình thu thập web (web crawler)
- Xây dựng một ứng dụng website tổng hợp thông tin có khả năng thu thập các
bản tin từ các trang báo lớn như Dân trí.
Để giải quyết được các mục tiêu này, khóa luận được chia thành ba chương lớn:
Chương 1: Tìm hiểu về trình thu thập web
Trong chương này, chúng ta sẽ lần lượt tìm hiểu các khái niệm cơ bản trong trình
thu thập web. Phần lớn nội dung trong chương này sẽ đi sâu vào việc tìm hiểu các
thành phần cấu thành nên một trình thu thập, các chiến lược thu thập dữ liệu, việc đánh
giá của trình thu thập đối với trang web. Qua đó chúng ta sẽ có một bức tranh chung
Tìm hiểu về web crawler và xây dựng website tổng hợp thông tin 2010
2
về trình thu thập web, và có thể hiểu hơn về các giá trị thực tiễn mà nó mang lại trong
đời sống của con người.
Chương 2: Xây dựng ứng dụng website tổng hợp thông tin
Phần đầu chương sẽ trình bày về các kiến thức nền tảng và các công nghệ liên
quan, ở phần tiếp theo là các đánh giá phân tích và các giải pháp nhằm nâng cao hiệu
suất của trình thu thập, phần cuối chương là việc hiện thực hóa ứng dụng thông qua
việc xây dựng hệ thống cơ sở dữ liệu và thiết kế giao diện website. Cũng trong phần
này tôi sẽ nêu ra hai cách thu thập thông tin. Một là cách làm phổ biến hiện nay tôi gọi
là cách làm truyền thống, một là cách làm mới tôi tìm ra. Cách làm mới này tối ưu hơn
và có thể giải quyết được các hạn chế trong cách làm truyền thống.
Chương 3: Kết luận
Phần kết luận cũng là phần cuối của khóa luận sẽ nhìn lại những điều đã làm
được trong khóa luận này, nêu lên những vấn đề còn vướng mắc, từ đó đề ra hướng
phát triển tiếp theo cho đề tài.
Tìm hiểu về web crawler và xây dựng website tổng hợp thông tin 2010
3
CHƯƠNG 1. TÌM HIỂU VỀ TRÌNH THU THẬP WEB
1.1. GIỚI THIỆU VỀ TRÌNH THU THẬP WEB
Trình thu thập web (Web crawler) là một chương trình khai thác cấu trúc đồ thị
của web di chuyển từ trang này qua trang khác. Thời kỳ đầu nó có những tên khá
tượng hình như bọ web, rô-bốt, nhện và sâu, nhưng ngày nay tên gọi phổ biến nhất là
vẫn là trình thu thập web [1]. Mặc dù vậy cụm từ ‘thu thập’ không lột tả được hết tốc
độ của những chương trình này, vì chúng có tốc độ làm việc đáng kinh ngạc, có thể thu
thập dữ liệu lên đến hàng chục ngàn trang trong vòng một vài phút.
Từ thời kỳ đầu, một động lực quan trọng thúc đẩy quá trình phát triển của việc
thiết kế trình thu thập web là lấy được nội dung các trang web và thêm chúng hoặc
đường dẫn của chúng vào một kho lưu trữ trang – một kiểu kho lưu trữ có thể dùng để
phục vụ cho các ứng dụng cụ thể trong công cụ tìm kiếm web (search engine).
Các trình thu thập thường bắt đầu bằng cách chọn một số các đường dẫn (URL)
ứng với các trang web sẽ ghé thăm đầu tiên, các trang này được gọi là các trang hạt
giống. Khi ghé thăm một trang hạt giống, trình thu thập sẽ đọc nội dung trang web, lọc
ra tất cả các siêu liên kết (hyperlink) có trong trang web đó và đưa các URL tương ứng
với chúng vào một danh sách gọi là biên giới (frontier). Dựa vào danh sách này, trình
thu thập tiếp tục quá trình duyệt đệ quy để ghé thăm tất cả các URL chưa được duyệt.
Quá trình này chỉ dừng lại khi trình thu thập đã thu thập đủ số trang yêu cầu hoặc
frontier là rỗng, tức là không còn URL để duyệt. Tuy mô tả này có vẻ đơn giản nhưng
đằng sau chúng là khá nhiều vấn đề hóc búa liên quan đến kết nối mạng, bẫy nhện, tiêu
chuẩn trích xuất URL, chuẩn hóa các trang HTML, bóc tách nội dung trang HTML
vv... Ở phần sau của khóa luận tôi sẽ lần lượt trình bày đến các vấn đề này và hướng
giải quyết của chúng.
Sau khi đã có được một danh sách các URL dùng cho việc thu thập, ta sẽ thực
hiện quá trình lấy trang. Tất cả các trang được lấy một lần và được lưu vào một kho
lưu trữ giống như cơ sở dữ liệu của công cụ tìm kiếm, đến đây không cần thu thập
thêm. Tuy nhiên web là một thực thể năng động với các không gian con liên tục phát
triển và thay đổi nhanh một cách chóng mặt, vì thế thông tin phải liên tục được thu
thập để giúp các ứng dụng luôn cập nhật, ví dụ như bổ sung các trang mới loại bỏ các
trang đã bị xóa, di chuyển hoặc cập nhật các trang bị sửa đổi.
Tìm hiểu về web crawler và xây dựng website tổng hợp thông tin 2010
4
Các trang web chủ yếu được viết bằng các ngôn ngữ đánh dấu như HTML,
XHTML và được nhắm đến đối tượng sử dụng là con người chứ không phải máy tính.
Các trang web lại chứa đựng nhiều thông tin có ích mà con người có thể muốn thu
thập và lưu trữ lại, chính vì thế mà cần phải có những kỹ thuật bóc tách và trích xuất
thông tin theo một cơ chế tự động. Các kỹ thuật bóc tách dữ liệu (parsing) có thể ở
mức đơn giản như việc bóc tách các siêu liên kết, hoặc ở mức phức tạp hơn một chút
là bóc tách bất kỳ phần nội dung nào trong một trang web.
Về bản chất, quá trình thu thập web chính là quá trình duyệt đệ quy một đồ thị.
Các web được xem như một đồ thị với các trang là các đỉnh (node) và các siêu liên kết
là các cạnh. Quá trình lấy trang và trích xuất các liên kết bên trong nó tương tự như
việc mở rộng tìm kiếm một đỉnh trong đồ thị. Việc tìm kiếm này là khác nhau trong
các trình thu thập sử dụng chiến lược tìm kiếm khác nhau. Phần sau của khóa luận tôi
sẽ trình bày sâu hơn về các chiến lược tìm kiếm và đưa ra các số liệu thống kê để so
sánh hiệu suất của các chiến lược tìm kiếm này từ đó rút ra đánh giá về hiệu suất của
các trình thu thập.
Trình thu thập web là thành phần đầu tiên trong toàn bộ hệ thống search engine.
Mục đích chung của các hệ thống search engine là số lượng trang web đầu vào đạt giá
trị cao nhất có thể, trong đó trình thu thập web làm công việc chính là duy trì cơ sở dữ
liệu được đánh chỉ mục, trả về giá trị của bộ thu thập và bộ lập chỉ mục cho hàng triệu
truy vấn nhận được từ người dùng. Các trang được đánh chỉ mục dựa trên các thuật
toán ưu tiên hoặc dựa vào các phương pháp dựa trên kinh nghiệm (heuristic). Ngoài ra,
chúng ta có thể sử dụng trình thu thập web để xây dựng các phần mềm tập trung thông
tin, các trang web tổng hợp thông tin, dựa trên cơ chế tự động tìm và phát hiện tài
nguyên.
1.2. CÁCH XÂY DỰNG MỘT HẠ TẦNG THU THẬP
Hình 1 cho ta thấy một chu trình của một trình thu thập web cơ bản [1]
Tìm hiểu về web crawler và xây dựng website tổng hợp thông tin 2010
5
Hình 1 : Một vòng thu thập web cơ bản
Trình thu thập chứa một danh sách các URL chưa được thăm gọi là biên giới
(frontier). Danh sách được khởi tạo bởi một số các URL hạt giống – các URL này
được cung cấp bởi một người dùng hoặc một chương trình khác. Mỗi vòng lặp là một
quá trình gồm các bước :
- Lấy một URL tiếp theo từ frontier ra để thu thập.
- Lấy trang tương ứng với URL thông qua HTTP.
- Bóc tách trang vừa lấy để trích xuất ra các URL và các nội dung thông tin cụ
thể.
- Cuối cùng là thêm các URL chưa thăm vào frontier.
Tìm hiểu về web crawler và xây dựng website tổng hợp thông tin 2010
6
Trước khi các URL được thêm vào frontier chúng có thể được đánh chỉ mục dựa
trên số lượng truy cập vào trang web ứng với URL. Quá trình thu thập sẽ chấm dứt
ngay khi trình thu thập đạt đủ số lượng trang nhất định hoặc frontier rỗng, đây được
gọi là trạng thái kết thúc (dead-end) của trình thu thập.
1.2.1. Frontier
Frontier là một danh sách chứa các URL của các trang chưa thăm. Trong thuật
ngữ tìm kiếm đồ thị, frontier là một danh sách mở các đỉnh chưa được mở rộng. Đối
với một trình thu thập lớn frontier có thể chứa hàng chục ngàn đến hàng trăm ngàn
trang và phải lưu trữ trong ổ cứng. Tuy vậy frontier nào cũng có một miền giới hạn
nhất định, miền giới hạn này lớn hay nhỏ phụ thuộc vào bộ nhớ của máy tính. Khi số
lượng URL thu thập được vượt quá giới hạn này chúng ta sẽ cần một cơ chế để loại bỏ
các URL ứng với các trang ít quan trọng và giữ lại các URL ứng với các trang quan
trọng. Lưu ý rằng tốc độ thêm các URL vào frontier nhanh gần bằng tốc độ thu thập
thông tin. Nó có thể thêm tới 60000 URL ngay khi trình thu thập thu thập dữ liệu của
10000 trang, giả định trung bình mỗi trang có khoảng 7 liên kết.
Frontier có thể coi như một hàng đợi làm việc theo cơ chế FIFO (viết tắt của First
In First Out, [6]) nghĩa là vào trước ra trước trong trường hợp chúng ta sử dụng thuật
toán tìm kiếm theo chiều rộng để thu thập thông tin. Trình thu thập sử dụng chiến thuật
tìm kiếm này gọi là trình thu thập theo chiều rộng [5]. Các URL được lấy ra thu thập
được chọn từ trên xuống dưới trong danh sách và các URL mới được thêm vào đuôi
của danh sách. Do miền giới hạn của frontier, ta phải đảm bảo các URL chỉ được lấy
một lần. Để tìm kiếm xem một URL mới được trích xuất đã có trong danh sách chưa là
khá phức tạp