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...
Nội dung trích xuất từ tài liệu:
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ếmnổ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ũngcó 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ệctươ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ìmkiế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ánPhầ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 quantâ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ếmtrê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ệuquả 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ạyrấ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ầngiố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ó 2trang html như sau:one.htmlThis is document one.two.htmlHere 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 đánhsố mỗi trang cùng với tiêu đề và URL của trang. Số đánh của trang sẽ được sử dụng để thamchiế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ứatừ đó:another = > 2doc = > 1,2document = > 1,2here = > 2is = > 1,2one = > 1this = > 1two = > 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 trangWeb 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 trangWeb để kết xuất các thông tin về tài liệu tương ứng như dưới đây:Doc TwoTươ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à trangượ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ệuKhô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ườngvà 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ớikí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ụngcá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 tacó 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ộtfile 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 đềucó 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 DBMsẽ 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ôngbị lẫn lộ với số trang).Bước 3. Viết scrrip bọ tìm kiếmChú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ãylà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 khaihệ 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ơnvà không bị ràng buộc về độ dài của các bản ghi.Mở tệp chỉ mục bằn ...