Nếu bạn có ý định xây dựng một search engine, vấn đề đặt ra đầu tiên là: Xây dựng một search engine phức tạp như thế nào? Bài viết " Why Writing Your Own Search Engine Is Hard", có thể giúp bạn hình dung phần nào. Nói một cách tóm tắt:
i. Bạn phải cần có một crawler, một con robot chuyên đi thu thập các trang web/tài liệu.
ii. Bạn phải cần có một chương trình đánh chỉ mục. Việc đánh chỉ mục sẽ giúp cho việc tìm kiếm các tài liệu liên quan đến một hay nhiều từ khóa cho trước sau này. Một ví dụ điển hình là inverted list, trong đó với mỗi từ khóa, lưu danh sách các tài liệu liên quan đến nó.
iii. Bạn cần phải có thuật toán xếp hạng kết quả trả về. Với việc có rất nhiều tài liệu liên quan đến các từ khóa mà người dùng nhập vào, vấn đề là làm thế nào để trả về kết quả gần với mong đợi của người dùng nhất. Một ví dụ điển hình là Page rank, thuật toán gắn với sự thống trị của Google trong lĩnh vực tìm kiếm hiện nay.
iv. Bạn cần phải có tài nguyên. Đây là chuyện những người làm academic có vẻ ít quan tâm nhất nhưng với các ứng dụng thực tế, đây là một trong những vấn đề mấu chốt. Bạn lưu trữ 100,000 trang web thì có thể sẽ chẳng có vấn đề gì với một máy PC, nhưng nếu bạn muốn lưu trữ hàng chục tỉ trang web (Google lưu khoảng 25 billions, số liệu năm 2006), thì đó lại là chuyện khác. Lúc này các vấn đề như phân tán dữ liệu thế nào, xử lí việc nhất quán dữ liệu thế nào (ví dụ lưu dữ liệu nhiều máy, nhưng một trong số đó bị hư), việc phân bổ các câu query thế nào, etc sẽ không đơn giản. Ngoài ra, băng thông cũng là vấn đề quan trọng không kém. Nếu muốn nhiều người có thể sử dụng dịch vụ của mình thì server phải mạnh, băng thông phải đủ lớn để có thể cho phép nhiều người cùng tải dữ liệu về một cách nhanh chóng, etc.
Như vậy, có thể thấy rằng, việc xây dựng một search engine from scratch là chuyện cực kì phức tạp. Đó cũng chính là lí do tại sao chúng ta nên tìm những open sources liên quan đến ứng dụng này. Nổi bật nhất trong số này là các ứng dụng/phần mềm dựa trên thư việnLucene.
2. Lucene
Lucene là một thư viện mã nguồn mở, được phát triển bởi Dough Cutting (hiện đang làm việc cho Yahoo). Thư viện này cung cấp các hàm cơ bản hỗ trợ cho việc đánh chỉ mục và tìm kiếm. Từ thư viện Lucene này, có nhiều kịch bản sử dụng sau:
i. Dùng Lucene tích hợp vào ứng dụng hiện có. Ví dụ tôi đang muốn phát triển một semanticvideo search engine, trong đó tôi có dữ liệu văn bản là các transcript và tôi muốn có một công cụ hỗ trợ cho việc tìm kiếm dựa trên văn bản. Bằng cách này, người dùng có thể gõ vào từ khóa President Bush để tìm các video transcript có nói về President Bush. Sử dụng các hàm trong thư viện Lucene liên quan đến việc đánh chỉ mục và tìm kiếm, tôi có thể thực hiện thao tác này khá dễ dàng.
ii. Xây dựng một search engine cho riêng bạn. Lúc này bạn cần phải có một web crawler chuyên đi thu thập các trang web trên Internet, để đem về đánh chỉ mục và cho phép tìm kiếm. Ứng dụng kiểu này có thể thấy tương tự ở trang www.baomoi.com. Trong ứng dụng này, web crawler sẽ được dùng để đi thu thập các tin từ các website (chủ yếu là tin tức, ví dụ vnexpress, tuoitre.com.vn, nld.com.vn, etc), sau đó tiến hành phân loại, lập chỉ mục để hỗ trợ tìm kiếm. Trong trường hợp cần web crawler, Nutch là một phần mềm mã nguồn mở, cũng do chính tác giả của Lucene là Dough Cutting phát triển, có thể giúp bạn việc này. Để có thể tiến hành thu thập và lưu trữ hàng triệu trang web một cách có hiệu quả ở nhiều máy khác nhau, Hadoop sử dụng công nghệ của GoogleFS có thể được tích hợp cùng. Bên cạnh đó Solr, một phần mềm mã nguồn mở dùng cho xây dựng các search server, cung cấp giao diện bằng web với người sử dụng cũng được xây dựng dựa trên thư viện Lucene.
Lucene ban đầu được viết hoàn toàn bằng Java. Sau đó được port qua các ngôn ngữ khác ví dụ như C, C++ ( CLucene), .NET (Lucene.NET ), Perl (Plucene), Ruby ( Ferret) và đặc biệt là PHP (Zend Framework ).
3. Lucene and MySQL
Nếu bạn đã từng làm về các ứng dụng của hệ thống thông tin, trong đó có sử dụng chức năng tìm kiếm của các hệ quản trị cơ sở dữ liệu, ví dụ như MySQL. Câu hỏi có thể đặt ra là: Dùng chức năng tìm kiếm của Lucene và của hệ quản trị CSDL như MySQL có gì khác nhau? Có thể chỉ ra một số ý như sau:
i. Khác với MySQL, dữ liệu được index phải được lưu trữ trong database, trong khi đó Lucene chỉ tạo chỉ mục trên dữ liệu hiện có. Bằng cách này, Lucene có thể tạo chỉ mục cho dữ liệu lưu trữ trong database, trong các thư mục của hệ thống tập tin. Hơn thế nữa, với việc dùng các plug-in về parsing, Lucene có thể đánh chỉ mục cho các tập tin pdf, html, MS Word, etc.
ii. Câu truy vấn của MySQL bị giới hạn bởi cú pháp của SQL query, trong khi câu truy vấn của Lucene gần với các hệ thống information retrieval hơn. Với Lucene, bạn có thể dùng proximity search, fuzzy search, wildcard search và quan trọng nhất là term boosting có thể giúp rank các kết quả trả về theo mức độ liên quan (relevancy).
iii. Tốc độ của Lucene tốt hơn so với MySQL trong trường hợp dữ liệu lớn.
Nhân tiện cũng nói thêm, để có thể tăng khả năng tìm kiếm của các hệ quản trị CSDL,Sphinx là một ứng dụng như vậy.
4. A Case Study
Một trong những lí do tôi phải tìm hiểu về Lucene đó là tôi đang làm về Person X. Ứng dụng này có thể tóm tắt như sau: Giả sử tôi có một cơ sở dữ liệu các ảnh cùng captions của nó (ví dụ như trang này http://www.cs.berkeley.edu/
Bước đầu tiên là thu thập dữ liệu. Một chương trình như Teleport có thể giúp tải hết các trang của site ở trên ( http://www.cs.berkeley.edu/
Bước tiếp theo là dùng Lucene để tạo chỉ mục cho tập các files trên và tiến hành tìm kiếm. Để làm điều này, trước tiên là download Lucene, phiên bản cho Java về từ địa chỉ này. Tôi dùng Windows và ko cần build lại nên chọn download bản đã build sẵn của Lucene, ví dụ như http://ftp.kddilabs.jp/infosyst
Sau khi unzip, có thể dùng Eclipse để load chương trình Demo trong đó có hỗ trợ các thao tác tạo chỉ mục và tìm kiếm. Lưu ý rằng Eclipse ko thể dùng file build.xml để tạo project nên tôi phải tự tạo một project mới trong Eclipse, trong đó src trỏ về thư mục src/demo. Sau khi khai báo trong mục Java Build Path/Libraries để sử dụng thư viện Lucene build sẵn lucene-core-2.2.0.jar, tôi có thể chạy các ứng dụng tạo chỉ mục và tìm kiếm một cách dễ dàng.
Một lưu ý là một khi đã tạo được chỉ mục, chúng ta có thể sử dụng ứng dụng Luke để có thể thực hiện các câu truy vấn với giao diện khá trực quan.
5. Future Plan
Từ việc tìm hiểu về Lucene, tôi có ý định làm một ứng dụng kiểu như site www.baomoi.com . Bước đầu tiên là thu thập dữ liệu thông qua dùng web crawler. Với web crawler, chúng ta có thể customize Nutch. Một khi đã có được dữ liệu, các ứng dụng tương tự như baomoi.comcó thể được phát triển tiếp.
Lê Đình Duy
PS: Bài mới hơn về Lucene có thể xem tại đây: Lucene -Thư viện mã nguồn mở hỗ trợ phát triển máy tìm kiếm
No comments:
Post a Comment