ICTnews trân trọng giới thiệu bài viết của độc giả Lê Đình Duy, Khoa CNTT, Đại học Khoa học Tự nhiên TP.HCM gửi về từ Nhật Bản.

Tìm kiếm với dữ liệu cấu trúc và phi cấu trúc

Với việc dữ liệu do con người tạo ra ngày càng phong phú, nhu cầu tìm kiếm thông tin ngày càng bức thiết và đa dạng, dẫn đến sự ra đời của nhiều công cụ hỗ trợ tìm kiếm. Trong lĩnh vực tìm kiếm, người ta tạm chia dữ liệu thành hai loại chính, dữ liệu có cấu trúc (structured data) và dữ liệu phi cấu trúc (unstructured data).

Dữ liệu có cấu trúc thường dùng để chỉ dữ liệu lưu trữ trong các hệ quản trị cơ sở dữ liệu quan hệ như MS SQL server hay MySQL, trong đó các thực thể và các thuộc tính được định nghĩa sẵn. Ví dụ, dữ liệu của một thí sinh dự thi đại học có thể bao gồm các thông in như Họ tên, Năm sinh, Trường dự thi, Điểm thi các môn.

Dữ liệu phi cấu trúc thường dùng để chỉ dữ liệu ở dạng tự do (free type) và không cần có cấu trúc định nghĩa sẵn. Các trang web, video, ảnh, âm thanh là các ví dụ của dữ liệu phi cấu trúc (Thông thường, nếu ko nói chi tiết, dữ liệu phi cấu trúc được hiểu là dữ liệu phi cấu trúc dạng văn bản).

Nếu dùng các hệ quản trị cơ sở dữ liệu quan hệ như MS SQL Server hay MySQL để lưu trữ dữ liệu phi cấu trúc, việc truy tìm dữ liệu theo danh sách từ khóa sẽ gặp các hạn chế sau:

- Bị giới hạn ở cú pháp của ngôn ngữ SQL. Ví dụ muốn tìm các trang web nói về Cần Thơ, phải chỉ rõ Cần Thơ trong câu truy vấn, nếu dùng "Can Tho" (vì nghĩ có thể sử dụng tiếng Việt không dấu), kết quả sẽ hoàn toàn khác.

- Tốc độ chậm khi tìm kiếm gần đúng (dùng LIKE) trong cơ sở dữ liệu lớn. Các hệ quản trị CSDL quan hệ không được thiết kế để làm việc hiệu quả cho trường hợp người dùng muốn thực hiện các câu truy vấn như: Tìm các tài liệu về các ngành đào tạo của Đại học Cần Thơ, trừ ngành nông nghiệp và ngành công nghệ thông tin (*).

Điều này đã thúc đẩy cho sự ra đời của các hệ thống hỗ trợ tìm kiếm theo danh sách từ khóa cho dữ liệu phi cấu trúc (full text search - tạm dịch là tìm kiếm toàn văn). Điển hình nhất cho các hệ thống này là các máy tìm kiếm như Google và Yahoo. Gần đây các hệ quản trị CSDL quan hệ như MS SQL Server (phiên bản MS SQL Server 2000 trở đi) và MySQL (phiên bản 3.23.23 trở đi) đều có thêm chức năng hỗ trợ tìm kiếm toàn vẹn cho dữ liệu văn bản mà chúng lưu trữ.

Lucene - thư viện mã nguồn mở hỗ trợ tìm kiếm toàn văn

Lucene là một thư viện mã nguồn mở cho tìm kiếm toàn văn, đượ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. Để có thể sử dụng Lucene, bạn cần phải có sẵn dữ liệu. Dữ liệu có thể là tập hợp các tập tin dạng PDF, Word hay là các trang web HTML; hoặc là dữ liệu lưu trong các hệ quản trị CSDL như MS SQL Server hay MySQL. Dùng Lucene, bạn có thể tiến hành đánh chỉ mục trên dữ liệu hiện có để sau này có thể thực hiện thao tác tìm kiếm toàn văn trên dữ liệu đó.

Mô hình đánh chỉ mục của Lucene

Các bước sử dụng Lucene bao gồm:

Mô tả đối tượng cần đánh chỉ mục

Lucene coi mỗi đối tượng cần đánh chỉ mục là một Document. Mỗi Document có thể có nhiều Field, mỗi Field tương ứng một thuộc tính của đối tượng cần đánh chỉ mục. Ví dụ, bạn muốn tìm kiếm các trang web ở dạng HTML. Như vậy đối tượng cần đánh chỉ mục là trang HTML; các thuộc tính có thể là nơi lưu trữ (host), đường dẫn, tiêu đề, metadata và nội dung của chính trang web.

Minh họa đối tượng Document dùng trong Lucene

Với mỗi Field, bạn có thể chọn giữa đánh chỉ mục hay không đánh chỉ mục. Nếu chọn đánh chỉ mục, bạn có thể tìm kiếm trên Field đó. Các Field không đánh chỉ mục thường là các Field không quan trọng trong quá trình tìm kiếm và phục vụ chủ yếu cho nhu cầu trình bày kết quả trả về.

Đánh chỉ mục

Bạn cần phải tự xây dựng các hàm công cụ để chuyển đổi dữ liệu ban đầu thành dữ liệu mô tả trong Document. Ví dụ, nếu dữ liệu ban đầu của bạn là tập tin PDF hay Word, bạn phải có các hàm để đọc hiểu các định dạng này và chuyển về dạng chuỗi văn bản tương ứng.

Thao tác đánh chỉ mục khá phức tạp. Trước hết dữ liệu văn bản sẽ được phân tích thành các từ khóa, đồng thời loại bỏ các từ không dùng đến (stop words, trong tiếng Anh các từ như a, an, the là các stop words), sau đó các từ khóa sẽ được dùng để tạo inverted index (chỉ mục nghịch đảo) (2) và lưu thành các phân đoạn (segments) dạng thuận tiện cho việc tìm kiếm sau này. Chỉ mục nghịch đảo dùng để chỉ cách lưu trữ danh sách các tài liệu mà có chứa từ cho trước. Gọi là nghịch đảo bởi vì thông thường, với mỗi tài liệu cho trước, người ta lưu trữ danh sách các từ có trong tài liệu đó. Ví dụ, với từ khóa Lucene, ta sẽ lưu trữ danh sách các trang web A, B, C có chứa từ khóa này. Sau này khi người dùng gõ vào từ khóa Lucene, danh sách này có thể giúp định vị nhanh chóng các trang web có chứa nó. Nếu dùng chỉ mục thông thường, phải quét qua hết các trang web có trong cơ sở dữ liệu mới tìm ra. Cách này rất tốn thời gian khi số lượng dữ liệu lớn.

Tìm kiếm

Sau khi dữ liệu đã được đánh chỉ mục, bạn có thể thực hiện tìm kiếm trên chúng. Tìm kiếm toàn vẹn cho phép bạn có thể tìm kiếm theo danh sách các từ khóa cùng với các toán tử luận lí (và, hoặc, phủ định). Ví dụ, bạn có thể chỉ định: "Đại học Cần Thơ" NOT ("nông nghiệp" AND "công nghệ thông tin") cho câu truy vấn (*) ở trên.

Ngoài ra, điểm nổi bật khác của tìm kiếm toàn văn là cho phép xếp hạng các kết quả trả về tùy vào độ tương đồng (relevance) giữa câu truy vấn và kết quả tìm kiếm.

Một số câu hỏi thường gặp

Dùng Lucene khác gì với tìm kiếm toàn văn của MySQL và MS SQL server

Có thể thấy hai điểm khác biệt:

- Thứ nhất, dùng Lucene, bạn có thể cung cấp dịch vụ tìm kiếm toàn văn cho bất kì dữ liệu của hệ quản trị CSDL nào. Trong khi đó chức năng tìm kiếm toàn văn của MySQL hay MS SQL Server chỉ dùng cho chính dữ liệu lưu trong chúng mà thôi.

- Thứ hai, dùng Lucene, bạn có thể mở rộng các thành phần hiện có. Ví dụ, bạn có thể bổ sung bộ phân tích từ khóa cho tiếng Việt (để có thể tách cụm từ: 'học sinh học sinh học' thành 3 từ là học sinh, học và sinh học), hoặc bạn có thể thay đổi cách thức tính độ tương đồng cũng như cách xếp hạng cho kết quả trả về. Những điều này không thể làm được với MySQL hay MS SQL Server.

Có thư viện mở nào khác ngoài Lucene không?

Có một số thư viện sau

- Egothor (http://www.egothor.org/)

- Xapian (http://www.xapian.org/)

- MG4J (http://mg4j.dsi.unimi.it/)

- Sphinx (http://www.sphinxsearch.com/)

Lucene có phải là máy tìm kiếm không?

Không. Lucene chỉ là tập hợp các hàm thư viện hỗ trợ cho việc đánh chỉ mục và tìm kiếm mà thôi. Để có được ứng dụng như máy tìm kiếm, bạn phải viết chương trình sử dụng các hàm thư viện này. Một lưu ý khác, Lucene không có thư viện hỗ trợ thu thập trang web (web crawler). Nếu bạn quan tâm đến một ứng dụng máy tìm kiếm cụ thể dùng Lucene, hãy tham khảo Nutch, được phát triển bởi cùng tác giả của Lucene.

Máy tìm kiếm dùng Lucene có địch nổi Google không?

Lucene chỉ là một mô hình hỗ trợ cho tìm kiếm toàn vẹn dữ liệu phi cấu trúc. Máy tìm kiếm Google phát triển phức tạp hơn nhiều trong quá trình phân tích dữ liệu, đánh chỉ mục và xếp hạng kết quả tìm kiếm. Gần đây, nhà sáng lập Wikipedia phát triển Wikia Search cũng dựa trên thư viện Lucene (được tích hợp trong Nutch).

Cấu trúc của chỉ mục nghịch đảo

Tham khảo

[1] http://www.informit.com/articles/printerfriendly.aspx?p=461633.

[2] Gospodnetic, Otis (2004). Lucene in Action. Manning Publications. ISBN 978-1-932394-28-3.

Lê Đình Duy

ledduy@ieee.org

Theo Ictnews