Search Engine Knowledge - Kiến Thức về Máy Tìm Kiếm

Chủ Nhật, 31 tháng 1, 2010

Lucene - A Full-Featured Text Search Engine

1. Building a Search Engine
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ện Lucene.
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 semantic video 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.
Có thể xem thêm so sánh tại đây tại đây .
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.


Tham khảo:
[1]: Blog Lê Đình Duy, http://ledduy.blogspot.com/2008/06/lucene-full-featured-text-search-engine.html

Thứ Hai, 28 tháng 12, 2009

Lucene là gì?

Lucene là phần mềm mã nguồn mở, dùng để phân tích, đánh chỉ mục và tìm kiếm thông tin với hiệu suất cao bằng Java. Lucene được phát triển đầu tiên bởi Doug Cutting được giới thiệu đầu tiên vào tháng 8 năm 2000. Tháng 9 năm 2001 Lucene gia nhập vào tổ chức Apache và hiện tại được Apache phát triển và quản lý. Cần lưu ý rằng Lucene không phải là một ứng dụng mà chỉ là một công cụ đặc tả API cần thiết cho việc một search engine. Được xây dựng và thiết kế theo hướng hướng đối tượng nên các API cũng được cung cấp theo dạng hướng đối tượng. Mặc dù thiết kế và xây dựng ban đầu từ java nhưng hiện nay cũng đã có một số phiên bản cho các ngôn ngữ khác : .NET, C++, Perl, ….

Tham khảo:
[1]: http://vi.wikipedia.org/wiki/Lucene