• Thứ Ba, 16/12/2003 16:38 (GMT+7)

    Smart Spider - Công cụ truy tìm web thông minh

       
    Từ một tập nhỏ URL ban đầu, công cụ truy tìm thông minh này sẽ tự động phân hạng, sàng lọc và lần theo các liên kết thích hợp để mở rộng việc tìm kiếm trên Web. Người dùng có thể can thiệp, thay đổi các điều kiện giới hạn và thứ tự hiển thị kết quả. Công cụ này do nhóm tác giả (NTG) Manu Konchady (manuk@mitre.org) và Ray D’Amore (rdamore@mitre.org) thuộc Trung Tâm Hệ Thống Thông Minh Tích Hợp của công ty Mitre Corp phát triển.

    Thường đa phần người dùng thực hiện tìm kiếm trên Web bắt đầu với câu truy vấn trên một hay nhiều dịch vụ tìm kiếm. Tuy nhiên, với tốc độ phát triển gần 1 triệu trang Web mỗi ngày, các dịch vụ tìm kiếm tổng quát như Google (http://www.google.com), Fast(http://www.alltheWeb.com) và Inktomi (http://www.inktomi.com) ngày càng khó thực hiện kịp việc lập chỉ mục toàn bộ Web. Những quy định do các dịch vụ tìm kiếm đặt ra đã giới hạn việc truy cập chỉ tới một phần nhỏ địa chỉ thoả điều kiện truy vấn. Những quy định này có thể hiệu quả cho việc tìm kiếm thông tin về những chủ đề cụ thể, nhưng lại hạn chế đối với những vấn đề bao quát hoặc thay đổi nhanh do một số nguyên nhân:
    - Hầu hết các dịch vụ tìm kiếm hiện nay thường được xây dựng để hỗ trợ cộng đồng người dùng đại trà và có công cụ truy tìm trên Web (Spider hay Crawler) được thiết kế để thu thập các trang Web dựa trên sự phổ biến của Web site, chi phí thu thập, hoặc tiêu chí kinh tế khác.
    -  Các câu truy vấn bao quát có thể tạo nên hàng ngàn kết quả trả về.
    -  Thuật toán xếp hạng của hầu hết các dịch vụ tìm kiếm đều là sở hữu riêng và người dùng không thể kiểm soát trên thứ tự của danh sách kết quả.
    -  Các dịch vụ tìm kiếm luôn cập nhật chậm một khoảng thời gian tuỳ vào tần suất spider viếng thăm site. Khoảng thời gian này có thể từ 1 ngày đến ba tháng (ví dụ, để phỏng tính khoảng thời gian giữa các lần viếng thăm 1 site của Google, bạn hãy thử câu truy vấn “cache:www.cnn.com” – các liên kết mới không phải luôn được cập nhật ngay lúc truy vấn).
    -  Các dịch vụ tìm kiếm duy trì một số liên kết “chết” (các liên kết không còn tồn tại) trong chỉ mục.

    Thêm nữa, các dịch vụ tìm kiếm chỉ cung cấp phần đầu các trang kết quả, người dùng phải tự duyệt thủ công để xác định các trang liên quan khác. Giả sử những trang thông tin thích hợp nhất trên Web có thể truy cập từ một tập nhỏ các trang liên quan; tuy nhiên có khả năng các trang liên quan không được liên kết đến bởi bất kỳ trang nào trên Web, do vậy các Spider không thể truy cập tới được. Tuy nhiên, những trang thích hợp nhất sẽ có ít nhất một hoặc nhiều liên kết từ các trang khác.

     
    Với ý tưởng này, NTG đã phát triển công cụ Smart Spider có khả năng thực hiện truy tìm trên Web một cách thông minh, xác định các liên kết đáng quan tâm dựa trên các từ khoá của chủ đề. Thay vì lập chỉ mục và thu thập tất cả các trang Web tư liệu có thể truy cập được, Smart Spider sử dụng một nhóm nhỏ URL ban đầu do người dùng chọn để triển khai việc tìm kiếm. Sau đó nó sẽ khai thác các liên kết trong các trang Web, bỏ qua các liên kết dẫn dắt. Các liên kết có ở nhiều site được gán mức quan trọng cao hơn. Khi trang Web có liên kết chỉ tới một trang ở site khác, đây là một sự ngầm xác nhận trang được liên kết. Smart Spider lần theo các liên kết này và trích ra nội dung văn bản liên quan. Các trang không thích hợp được bỏ qua, giới hạn việc truy tìm ở một phần nhỏ nhưng thích đáng của Web (xem hình 1). Liên kết từ các trang thích hợp (các điểm sáng) sẽ được duyệt. Nhờ lược bớt cây Web một cách thông minh, Smart Spider có thể lần theo từ 10 đến 12 cấp liên kết từ tập ban đầu mà không phải thu thập hàng triệu trang Web và làm quá tải hệ thống.

    Có thể nêu một số ưu điểm của phương pháp này:
    -  Không giới hạn số lượng trang truy tìm.
    -  Thuật toán xếp hạng được quyết định bởi người dùng và kết quả có thể được sắp xếp theo bất kỳ thứ tự nào.
    Xác định được các trang có giá trị lần qua nhiều liên kết từ tập URL ban đầu. Các trang này có thể không “hiện hữu” đối với dịch vụ tìm kiếm.
    Đưa ra tập hợp tư liệu có chất lượng cho một chủ đề nhất định. Khối lượng dữ liệu thu thập được tuỳ thuộc vào câu truy vấn và các điều kiện ràng buộc.

     

    Phương Pháp

    Smart Spider triển khai việc tìm kiếm với một số điều kiện ràng buộc nhất định; ví dụ, ấn định số liên kết từ tập địa chỉ URL ban đầu hay tổng số URL được thu thập. Có thể dùng cách thức tự động để thu thập 10.000 URL hoặc hơn. Danh sách URL này được phân hạng dựa trên sự quan tâm của người dùng, chẳng hạn như URL với các liên kết trong cùng (từ các URL khác chỉ đến), URL với các liên kết ngoài cùng (chỉ đến các URL khác), hay site với các trang thích hợp nhất. Trang có nhiều liên kết “đến” có khả năng là trang authority (có thể hiểu là trang nguồn được các trang khác tham khảo đến) cho chủ đề, còn trang có nhiều liên kết “đi” là hub (là trang chủ chứa các liên kết chỉ đến các trang authority). Để xác định các site quan trọng và thu thập dữ liệu về một chủ đề cụ thể, chỉ cần xác định được các trang hub và authority là đủ.

    Để mở rộng việc truy tìm, có thể dùng tập URL ban đầu lớn hơn bằng cách kết hợp kết quả truy vấn từ nhiều dịch vụ tìm kiếm. Với các câu truy vấn mà kết quả trả về lên đến hàng trăm ngàn, Smart Spider sẽ phải cần rất nhiều tài nguyên để thu thập tất cả các kết quả. Tuy nhiên, không nhất thiết phải thu thập tất cả các trang liên quan trên Web vì thường có sự hội tụ, tập URL ban đầu và điều kiện kết thúc sẽ quyết định kết quả truy tìm.

     

    Dùng Nhiều Spider

    Smart Spider dùng CSDL MySQL (theo NTG, cũng có thể dùng các CSDL quan hệ khác). Mọi phát biểu SQL được thực thi thông qua một mô đun chung. Tương tự, một mô đun chung được dùng cho việc giao tiếp bên ngoài. Smart Spider được thực hiện bằng Perl (http://www.ddj.com/ftp/2002/2002_08/spider.zip). Mã lệnh Smart Spider được song song hoá bằng cách dùng hàm fork() - hàm Perl có thể dùng trên Windows và Unix. Các phát biểu SQL khoá/mở khoá bảng dữ liệu được dùng để đồng bộ việc truy cập CSDL.

    Trong tiến trình thực hiện song song với nhiều bộ xử lý, các bảng CSDL được nhân bản qua các bộ xử lý và được đồng bộ bằng phương thức trao đổi thông báo định kỳ. Nếu có nhiều điểm cùng chia sẻ truy cập qua kết nối Internet, giới hạn băng thông có thể hạn chế tổng số spider; tối đa có thể thực hiện song song 8 hay 16 spider. Nếu thực hiện trên một PC, hiệu suất của các tác vụ khác trên cùng máy có thể bị ảnh hưởng. Để giảm đến mức thấp nhất ảnh hưởng trên băng thông kết nối Internet và hiệu suất của máy, có thể dùng 2 hay 4 spider. Ví dụ 1 là giải thuật của spider.

    Việc thực hiện song song làm tăng hiệu suất đáng kể so với thực hiện tuần tự mỗi lúc 1 URL. Khi các URL được xử lý tuần tự, spider dễ bị trì hoãn lâu do liên kết chết hay nghẽn đường truyền. Với nhiều spider được thực hiện song song, khó có khả năng tất cả đều gặp những trục trặc giống nhau.

    Quá trình bắt đầu bằng việc thu thập tập URL ban đầu từ kết quả truy vấn Google. Kích thước tập ban đầu có thể thay đổi từ 100 đến 1000 URL. Kết quả từ nhiều dịch vụ tìm kiếm có thể được dùng để mở rộng tập ban đầu. Quá trình thu thập tập URL ban đầu tương tự quá trình gửi yêu cầu thủ công tới dịch vụ tìm kiếm thông qua trình duyệt. Kết quả trả về của dịch vụ tìm kiếm được phân tích và các địa chỉ URL trả về được lưu vào một bảng dữ liệu.

    Với mỗi câu truy vấn, có 2 bảng dữ liệu được tạo – bảng URL và bảng liên kết. Có một bảng truy vấn riêng quản lý tất cả các câu truy vấn do Smart Spider gửi đi. Bảng liên kết gồm có hai cột: url và liên kết. Bảng URL có các cột: url, status (trạng thái), site, relevancy (mức thích hợp), level (cấp liên kết) và spider.
    -  Status: chỉ tình trạng một URL đã được xử lý hay chưa, hay đang được xử lý.
    -  Site: Web site của địa chỉ URL, có ích cho việc nhóm các URL lại theo site.
    -  Relevancy: giá trị số thực nằm trong khoảng từ 0 đến 1, chỉ mức độ thích hợp với câu truy vấn. Giá trị của cột này được thiết lập dựa trên tiêu chí do người dùng xác định.
    -  Level: số liên kết từ tập ban đầu khi một địa chỉ URL cụ thể được bắt gặp lần đầu. Các URL trong tập ban đầu có giá trị level là 0, các địa chỉ được truy cập ở bước kế tiếp từ tập ban đầu có level là 1, và cứ thế. Giá trị này không nhất thiết chỉ độ dài của đường đi ngắn nhất từ tập ban đầu vì cùng địa chỉ URL đó có thể được truy cập theo một đường khác ngắn hơn.
    -  Spider: số spider xử lý một URL cụ thể. Thông tin này có ích cho việc theo dõi sự phân bố tải trong thực hiện song song.

    Lần theo tập URL ban đầu, bảng URL có một số URL chưa được xử lý dành cho các spider đơn. Từng spider đi vào vòng lặp và thoát ra khi thoả điều kiện kết thúc; ở đây, đó là khi các URL yêu cầu đã được xử lý hay khi không còn URL nào để xử lý nữa. Với từng URL:
    -  Các spider đơn kiểm tra dạng luận lý của chuỗi chứa các từ khoá truy vấn: một hàm so sánh đệ quy kiểm tra từ khoá trùng với các toán tử luận lý AND (và) và OR (hoặc). Nhiều từ khoá được đưa vào mà không có toán tử luận lý thì mặc định dùng toán tử AND.
    -  Mức thích hợp được gán giá trị hằng 0,2 nếu nội dung văn bản của URL hợp với các từ khoá truy vấn.
    -  Mức thích hợp cao hơn có thể được gán cho các tài liệu có từ khoá ở phần đầu đề, tựa, hay các thẻ chỉ mục.
    -  Với những câu truy vấn có nhiều từ khoá, mức thích hợp có thể tỷ lệ nghịch với mức khác biệt từ ngữ giữa các từ khoá trong nội dung văn bản của URL.
    -  Các tiêu chí người dùng khác như độ dài của nội dung văn bản hay site URL có thể được dùng để tính toán mức thích hợp. Tuỳ biến mức thích hợp cho phép người dùng can thiệp vào việc phân hạng các URL.

    Sau khi gán mức thích hợp của một URL, tất cả các liên kết đi được lọc ra, gồm các liên kết đến các site bên trong và bên ngoài. Các liên kết sau không được duyệt:
    -  Liên kết đến quảng cáo, hình ảnh, và tài liệu có định dạng khác.
    -  Liên kết tới các trang trong cùng site, ngoại trừ các liên kết có chứa từ khoá truy vấn trong URL hay văn bản mô tả liên kết trong trang.
    -  Liên kết từ các site dung lượng lớn (bằng cách thiết lập quy định trên số URL).


     Hình 1: Cây Web cho một câu truy vấn


    Ví dụ thuật Smart Spider

    Dữ liệu URL đưa vào trong bảng URL và bảng liên kết sẽ được duyệt. Sau khi Smart Spider kết thúc, một danh sách URL được in ra theo thứ tự mức thích hợp giảm dần. Các trang hub và authority có thể được lọc ra từ bảng liên kết. Thông tin này thường là đủ để tìm các nguồn tư liệu quan trọng về một chủ đề trên Web. Để tìm các trang hub và authority, cần thu thập số lượng URL hợp lý. Cây Web cho từng chủ đề là duy nhất và không thể thiết lập một giới hạn URL cố định cho tất cả các câu truy vấn.

     

    Kết Quả

    Smart Spider đã được thử nghiệm đánh giá bằng cách cho thực hiện với một vài câu truy vấn tổng quát. NTG thực hiện câu truy vấn “censorship” (việc kiểm duyệt) với Google, và nhận được khoảng 530.000 URL. 100 URL đầu tiên từ Google được dùng như là tập URL ban đầu cho Smart Spider. Một trang được xem là thích hợp nếu có ít nhất 2 trong 4 từ: “censorship”, “ban”, “speech”, hay “censor” (tất cả các từ tiếng Anh này có ý nghĩa liên quan với từ “censorship”) trong nội dung văn bản. Việc mở rộng truy tìm thông qua Smart Spider được giới hạn đến 3 mức tính từ tập URL ban đầu.

    Khoảng 10.000 URL được thu thập. Danh sách URL được đánh giá dựa trên số liên kết đến và số liên kết đi. Danh sách các site với số lượng trang cao nhất cũng được xác định.

     

    Lời Kết

    Việc tìm kiếm thông tin thích hợp trên Web là một công việc nặng nhọc. Các dịch vụ tìm kiếm cung cấp tập URL ban đầu để người dùng bắt đầu xác định thông tin. Tập URL này có thể có một số nguồn có giá trị nhưng để tìm ra, người dùng phải duyệt từng URL và xác định một cách thủ công những site thích hợp nhất. Với các câu truy vấn tổng quát, số lượng URL kết quả trả về có thể lên tới hàng trăm ngàn, đòi hỏi rất nhiều công sức và thời gian để xử lý. Công cụ Smart Spider có thể cất đi gánh nặng này cho người dùng bằng việc truy tìm Web thông minh và xác định các URL thích hợp nhiều đến mức có thể. Khi kết thúc việc truy tìm, người dùng có thể nhận diện các nguồn thông tin quan trọng trên Web về một chủ đề cụ thể. Smart Spider là công cụ hữu ích để khai triển việc tìm kiếm Web theo các điều kiện ràng buộc của người dùng. Smart Spider đem đến độ tin cậy cao hơn cho việc tìm kiếm trên Web so với các dạng truy vấn của dịch vụ tìm kiếm thông thường.

    Thanh Phong
    DDJ 08/2002

    ID: A0302_62