Xây dựng một search engine đơn giản

Chia sẻ: Lang Huyen | Ngày: | Loại File: PDF | Số trang:7

Thêm vào BST

Báo xấu

193
lượt xem 69
download

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

Hầu hết chúng ta đã từng sử dụng các công cụ như Google, Altasista khi tìm kiếm thông tin trên Web. Đọc xong bài này, bạn sẽ biết được cách làm thế nào để đưa một trang tìm kiếm vào Website của bạn chỉ với một số dòng lệnh Perl đơn giản (Tất nhiên, site của bạn phải được host trên một máy chủ chạy hệ điều hàng Unix và hỗ trợ CGI script). Để có được những tính nǎng vô cùng mạnh mẽ trong các công cụ tìm kiếm nổi tiếng này, những người phát triển đã phải giải...

Chủ đề:

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

Lưu

Nội dung Text: Xây dựng một search engine đơn giản

Xây dựng một search engine đơn giản Hầu hết chúng ta đã từng sử dụng các công cụ như Google, Altasista khi tìm kiếm thông tin trên Web. Đọc xong bài này, bạn sẽ biết được cách làm thế nào để đưa một trang tìm kiếm vào Website của bạn chỉ với một số dòng lệnh Perl đơn giản (Tất nhiên, site của bạn phải được host trên một máy chủ chạy hệ điều hàng Unix và hỗ trợ CGI script). Để có được những tính nǎng vô cùng mạnh mẽ trong các công cụ tìm kiếm nổi tiếng này, những người phát triển đã phải giải quyết hàng loạt những vấn đề phức tạp. Bạn có thể hỏi: Làm sao có thể viết một công cụ tìm kiếm riêng cho Website của mình, chắc hẳn cũng có rất nhiều việc phải làm. Bạn hãy yên tâm, viết một công cụ tìm kiếm nhỏ là một công việc tương đối dễ dàng. Đọc xong bài này, bạn sẽ biết được cách làm thế nào để đưa một trang tìm kiếm vào Website của bạn chỉ với một số dòng lệnh Perl đơn giản (Tất nhiên, site của bạn phải được host trên một máy chủ chạy hệ điều hàng Unix và hỗ trợ CGI script). Bước 1. Bắt đầu với thuật toán Phần lớn Website được tổ chức theo cấu trúc cây thư mục. Điều đó có nghĩa là nếu không quan tâm tới thời gian thực hiện bạn có thể viểt một script sử dụng các lệnh find và grep để tìm kiếm trên site, theo cách bạn vẫn thực hiện từ dấu nhắc dòng lệnh của hệ điều hành. Tuy nhiên, hiệu quả của phương pháp ``tìm lá trong rừng cây`` này sẽ giảm xuống rất thấp, chương trình sẽ chạy rất chậm khi website tǎng trưởng về quy mô vì n ó phải dò tất cả các file trên site của bạn. Một cách tiếp cận phổ biến là bạn hãy xây dựng một cấu trúc gọi là chỉ mục đảo, một bảng gần giống như mục lục cuối mỗi quyển sách. Ví dụ, giả sử bạn có một Website rất đơn giản chỉ có 2 trang html như sau: one.html This is document one. two.html Here is another document. Để lập chỉ mục cho toàn bộ Website, chúng ta cần tạo hai bảng. ở bảng thứ nhất, chúng ta đánh số mỗi trang cùng với tiêu đề và URL của trang. Số đánh của trang sẽ được sử dụng để tham chiếu tới trang tương ứng ở giai đoạn sau. Bảng danh sách trang Web này sẽ có các bản ghi như sau: 1 = > /one.html, ``Doc one`` 2 = > /two.html, ``Doc Two`` Bảng thứ hai chính là bảng chỉ mục đảo. Chúng ta sẽ liệt kê từng từ một và các tài liệu có chứa
từ đó: another = > 2 doc = > 1,2 document = > 1,2 here = > 2 is = > 1,2 one = > 1 this = > 1 two = > 2 Để tìm kiếm, trước hết cần nhìn tìm từ khoá trong bảng chỉ mục đảo, sau đó tra ngược lên trang Web có số trang liệt kê sau từ cần tìm. Chẳng hạn, nếu từ khoá là ``here``, chúng ta sẽ tìm nó trong bảng chỉ mục đảo, tìm được trang đánh số 2, và sau đó tra ngược lên bảng danh sách trang Web để kết xuất các thông tin về tài liệu tương ứng như dưới đây: Doc Two Tương tự, nếu bạn đánh vào 2 từ khoá, chúng ta sẽ tìm cả 2 từ trong bảng chỉ mục đảo và tra ngược lên bảng thứ nhất để liệt kê những trang chứa cả 2 từ khoá cần tìm. Bước 2. Xác định cấu trúc dữ liệu Không có gì khó khǎn khi chúng ta lưu trữ tệp chỉ mục đảo trong một file vǎn bản thông thường và sẽ tìm kiếm từ khoá trong file này. Vì kích thước của tệp chỉ mục nhỏ hơn rất nhiều so với kích thước của site, tìm kiếm trên tệp chỉ mục đảo sẽ nhanh hơn rất nhiều so với cách sử dụng các lệnh find và grep để tìm trên toàn bộ site. Tất nhiên, đối với các site lớn, kích thước của file chỉ mục cũng sẽ lớn lên và việc đọc toàn bộ file chỉ mục chỉ để tìm vài từ là không hiệu quả xét về nhiều mặt. Muốn tǎng hiệu quả, chúng ta có thể sử dụng file DBM để lưu cả bảng danh sách trang Web và bảng chỉ mục ngược thành một file chỉ mục duy nhất. Vì các bản ghi của bảng danh sách trang Web và bảng chỉ mục ngược đều có cấu trúc dạng name = > value (tên = > giá trị) nên việc ánh xạ thành các xâu trong file DBM sẽ rất dễ dàng. Theo quy ước của Perl, tệp chỉ mục mới của chúng ta sẽ như sau: %dbm = ( `-1` = > ` Doc one `,
`-2` = > ` Doc Two `, `another` = > `-2`, `doc` = > `-1-2`, `document` = > `-1-2`, `here` = > `-2`, `is` = > `-1-2`, `one` = > `-1`, `this` = > `-1`, `two` = > `-2` ); (Ơ` trên, chúng ta đã chuyển sang sử dụng các số âm để các số xuất hiện trên trang Web không bị lẫn lộ với số trang). Bước 3. Viết scrrip bọ tìm kiếm Chúng ta phải viết 2 script. Script thứ nhất sẽ đọc tất cả các file trên Website để xây dựng tệp chỉ mục đảo (script này đóng vai trò như một crawler - bọ tìm kiếm) và script thứ hai có nhiệm vụ tìm các trang web theo từ khoá do người sử dụng nhập vào từ một form. Trước hết, chúng ta hãy làm việc với script thứ nhất. Trước tiên, chúng ta mở file DMB là nơi bảng chỉ mục ngược được lưu. Chúng ta sẽ triển khai hệ thống với Berkeley DB vì nó cung cấp các API cho phép thao tác với bản ghi thuận tiện hơn và không bị ràng buộc về độ dài của các bản ghi. Mở tệp chỉ mục bằng lệnh use DB_File; dbmopen(%db,``search_index.db``, 0644) or die ``dbmopen: $!``; Cách nhanh nhất để tìm các tệp trong Unix là sử dụng lệnh find. Trong ví dụ này, chúng ta sử dụng lệnh này để lấy danh sách tất cả các file .html trên Website: open(FILES, ``find . -name `*.html` -print|``) or die ``open for find: $!``; Chúng ta mở lần lượt từng tệp HTML và đọc nội dung của tệp vào một biến.
my $filename; while(defined($filename = )) { print ``indexing $filename``; chop $filename; open(HTML, $filename) or do { warn ``open $filename: $!``; next; }; my $html = join(``, ); close HTML; Sau đó trích phần title (tít) của trang Web và tạo các đầu mục cho trang trong bảng danh sách trang Web: my ($title) = ($html =~ / //g; Nếu chúng ta muốn tìm kiếm không phân biệt chữ hoa và chữ thường, cần chuyển tất cả về cùng một kiểu chữ. Chúng ta hãy chuyển cả tài liệu thành chữ thường: $html =~ tr/A-Z/a-z/; Tiếp đó, chúng ta tạo một danh sách gồm tất cả các từ trong tài liệu: my @words = ($html =~ /w+/g); Cuối cùng, chúng ta nối tất cả các từ vào dòng tương ứng trong tệp chỉ mục đảo, cần đảm bảo rằng không có từ nào được đánh chỉ mục 2 lần. my $last = ````; for (sort @words) { next if($_ eq $last);
$last = $_; $db{$_} = defined $db{$_} ? $db{$_}.$fileno : $fileno; } Về cơ bản là như vậy. Nếu bạn muốn tham khảo chi tiết, có thể tải về script đầy đủ ở địa chỉ http://internet.vnn.vn/doawload/script/webcrawl.txt Khi chạy trên Website, script này sẽ tạo ra tệp search_index.bd trong thư mục gốc của site. File này chứa chỉ mục của tất cả các từ có trên các trang Web trên site của chúng ta. Lưu ý: Thời gian chạy Script này khá lâu, phụ thuộc vào có bao nhiêu tài liệu trên site của bạn và sẽ tạo ra một tệp có kích thước khá lớn. Trong một lần thử, tệp chỉ mục được tạo có kích thước bằng 40% kích thước tổng của tất cả các file trên site. Bước 4. Xây dựng script CGI tìm kiếm Bây giờ chúng ta đã có tệp chỉ mục và cần cung cấp một cách thức cho người sử dụng truy nhập nó. Tiếp theo chúng ta sẽ xây dựng một script tìm kiếm đơn giản để tìm kiếm những trang Web chứa tất cả các từ do người sử dụng nhập vào từ form. Form tìm kiếm hết sức đơn giản: Search.cgi đọc biến form và phân tách giá trị của nó thành cách từ riêng biệt: my $query = $ENV{`QUERY_STRING`}; $query =~ s/s=//; $query =~ s/%[0-9a-fA-F]{2}/ /g; my @words = ($query =~ /w+/g); Tiếp đó, nó mở tệp DBM chứa chỉ mục ngược use DB_File; dbmopen(%db,``search_index.db``,0); Chúng ta sử dụng một counter để lưu số đếm trên các trang . Chúng ta tìm lần lượt tìm theo từng từ khoá và tǎng số đếm cho trang mỗi khi từ khoá được tìm thấy trên trang đó:
my %counters; my $word; for $word (@words) { my $pages = $db{lc $word}; my $page; for $page ($pages =~ /(-d+)/g) { $counters{$page}++; } } Một trang chứa tất cả các từ khoá sẽ có số đếm counter tǎng liên tục qua các vòng lặp và giá trị cuối cùng sẽ bằng bằng số từ khoá được nhập vào. Đoạn script sau sẽ tìm những trang này và in ra. for $page (sort keys %counters) { if($counters{$page}==scalar(@words)) { my $href = $db{$page}; print ``$href ``; } } Tất cả chỉ đơn giản như thế. Bạn có thể tải về script đầy đủ tại địa chỉ href=``http://internet.vdc.com.vn/download/script/webcrawl.txt. Tất nhiên, còn có rất nhiều lựa chọn khác có thể thêm vào search engine này và làm cho nó có độ thân thiện cao hơn với người
sử dung nhưng điều này đơn thuần chỉ là việc lập trình. Hy vọng rằng các bạn sẽ tìm thấy ở bài này những điều thú vị và tự tạo cho mình một search engine với nhiều tính nǎng hơn.