• Chương 1: Trình bày tổng quan về truy xuất thông tin, các bước cần thực hiện trong quá trình truy xuất thông tin, các phương pháp đánh giá hiệu quả truy xuất thông tin và so sánh một số hệ thống truy xuất thông tin trên thế giới.
• Chương 2: Giới thiệu và trình bày cơ chế lập chỉ mục và tìm kiếm của thư viện mã nguồn mở Lucene.
• Chương 3: Giới thiệu và trình bày ứng dụng quản lý công văn.

CHƯƠNG 1:   TÌM HIỂU CHUNG VỀ TÌM KIẾM THÔNG TIN

Kể từ những năm 40, các vấn đề trong việc lưu trữ thông tin và tìm kiếm thông tin đã thu hút sự chú ý rất lớn. Với lượng thông tin khổng lồ thì việc tìm kiếm chính xác và nhanh chóng càng trở nên khó khăn hơn. Với sự ra đời của máy tính, rất nhiều ý tưởng lớn được đưa ra nhằm cung cấp một hệ thống tìm kiếm thông minh và chính xác. Tuy nhiên, vấn đề tìm kiếm sao cho đạt hiệu quả cao vẫn chưa được giải quyết.

Về nguyên tắc, việc lưu trữ thông tin và tìm kiếm thông tin khá đơn giản. Giả sử chúng ta có một kho chứa các tài liệu và một người muốn tìm các tài liệu liên quan đến yêu cầu của mình. Người đó có thể đọc tất cả các tài liệu trong kho chứa, giữ lại các tài liệu liên quan và bỏ qua các tài liệu không liên quan. Rõ ràng giải pháp này không thực tế bởi vì việc đọc tốn rất nhiều thời gian.

Với sự ra đời của máy vi tính, chúng có thể “đọc” thay cho con người để trích lọc ra các tài liệu có liên quan với yêu cầu trong tập dữ liệu. Tuy nhiên vấn đề lúc này là làm như thế nào để xác định được tài liệu nào liên quan đến yêu cầu của người sử dụng. Do đó, mục tiêu của một hệ thống tìm kiếm thông tin là tìm được tất cả các tài liệu có liên quan đến yêu cầu của người sử dụng.

1.  Khái niệm truy xuất thông tin

Thuật ngữ truy xuất thông tin (Information Retrieval - IR) thường được định nghĩa một cách rộng và không chặt chẽ. Do vậy, thường có sự nhập nhằng giữa các lĩnh vực truy xuất dữ liệu (data retrieval), truy xuất tài liệu (document retrieval), truy xuất thông tin và truy xuất văn bản (text retrieval). Một định nghĩa đầy đủ, dễ hiểu và tránh được sự nhầm lẫn đó được đưa ra bởi Lancaster: Một hệ thống truy xuất thông tin không cho người dùng biết về chủ đề mà họ yêu cầu mà nó chỉ đơn thuần cho biết sự tồn tại (hoặc không tồn tại) và vị trí của các tài liệu có liên quan tới yêu cầu của người dùng. Trong thực tế nghiên cứu, có thể định nghĩa truy xuất thông tin như sau: Truy xuất thông tin là việc tìm kiếm tài liệu ở trạng thái phi cấu trúc (thường là văn bản thuần) thoả mãn một nhu cầu thông tin nào đó từ các tập hợp lớn (thường là trên các máy chủ cục bộ hoặc trên mạng).

Hằng ngày trên thế giới có hàng trăm triệu người thực hiện truy xuất thông tin mỗi khi họ sử dụng một máy tìm kiếm hoặc tìm kiếm trong hộp thư điện tử của mình. IR đang nhanh chóng trở thành hình thức truy nhập thông tin vượt trội, vượt qua dạng tìm kiếm kiểu cơ sở dữ liệu truyền thống.

Do đó IR là lĩnh vực khoa học máy tính chuyên về lý thuyết và thực hành việc tìm kiếm thông tin. Do văn bản là phương tiện phổ biến nhất được sử dụng để biểu diễn và phân bố thông tin một cách hiệu quả, hầu hết các nghiên cứu IR đều tập trung vào việc tìm kiếm trong các tập hợp tài liệu dạng văn bản. Nhiệm vụ chính của IR là tìm kiếm thông tin thoả mãn nhu cầu thông tin của người dùng. Người sử dụng của một hệ thống IR quan tâm nhiều tới việc thu nhận thông tin về một chủ đề hơn là thu thập dữ liệu phù hợp với một câu truy vấn cho trước. Trái lại, truy xuất dữ liệu chỉ nhằm mục tiêu cung cấp các tập hợp thông tin phù hợp với các từ khoá của một câu truy vấn.

2.  Quá trình phát triển của truy xuất thông tin

IR có lịch sử lâu dài giống như lịch sử của việc lưu trữ thông tin, cùng với sự phát triển của lượng thông tin được lưu trữ, con người phải phát triển ngày càng nhiều phương thức để tổ chức lượng thông tin đó để phục vụ cho việc truy xuất về sau. Quá trình phát triển đó được tóm lược như sau:

• Phương pháp đầu tiên là hệ thống bảng chữ cái. Các tài liệu cần được sắp xếp theo cách này, khi mà số lượng tác phẩm văn học Hy Lạp tăng lên buộc các thủ thư của thư viện Alexandria phải nghĩ ra một cách tổ chức các tác phẩm, vào thế kỷ thứ 3 trước Công nguyên. Mục lục là một ví dụ khác về các công cụ ban đầu của IR, nó trở nên thiết yếu khi mà các tác phẩm văn học gia tăng theo số lượng trang. Một ví dụ khác về IR thuở ban đầu là chỉ mục (index). Danh mục đầu tiên là những mảnh giấy da dê nhỏ, chứa đầu đề (title) và đôi khi tác giả của tác phẩm.
• Trong khoảng 20 năm cuối thế kỷ 20, lĩnh vực IR phát triển tốt dựa trên những mục đích cơ bản của nó là lập chỉ mục văn bản và tìm kiếm các tài liệu có ích trong một tập hợp. Ngày nay, nghiên cứu trong IR bao gồm việc mô hình hóa, phân loại văn bản, kiến trúc hệ thống, giao diện người dùng, trực quan hóa dữ liệu, lọc, ngôn ngữ...
• Một trong những dạng IR ban đầu là Memex được mô tả bởi Vanevar Bush. Ngoài ra còn có kết quả của Warren Weaver. Warren Weaver tập trung vào việc xử lý ngôn ngữ và xem đó là nền tảng của IR. Hơn nữa, sự phát triển của IR hiện đại được củng cố cùng sự phát triển của trí tuệ nhân tạo. Trong khi chờ đợi, trí tuệ nhân tạo chỉ được sử dụng trong một số phần của IR. Thuật ngữ IR được Moer đặt ra vào năm 1952. Các hệ thống thương mại đầu tiên được phát triển từ năm 1975 trở về sau. Chúng được sử dụng chủ yếu trong các thư viện. Cuối cùng, kể từ năm 1993, IR được phổ biến rộng rãi nhờ vào sự phát triển và tầm quan trọng ngày càng lớn của World Wide Web. Sự phát triển của World Wide Web dẫn đến sự gia tăng khổng lồ về số lượng các tài liệu, đòi hỏi phải có những kỹ thuật IR hiệu quả.   

Trước khi xuất hiện World Wide Web, hầu hết các hệ thống lưu trữ và truy xuất thông tin đều được sử dụng riêng bởi những người lập chỉ mục và tìm kiếm chuyên nghiệp, họ biết về tập hợp tài liệu, họ biết cách thức các tài liệu được biểu diễn trong hệ thống và họ biết cách sử dụng các toán tử tìm kiếm boolean để giới hạn số lượng tài liệu được thu thập.  

3.  Tìm hiểu về hệ thống truy xuất thông tin

Các hệ thống tự động tìm kiếm thông tin (IR - Information Retrieval) đã được phát triển để quản lý khối lượng lớn tài liệu từ những năm 40 của thế kỷ XX. Chức năng chính của hệ thống IR là lưu trữ và quản trị khối lượng văn bản lớn sao cho dễ dàng truy vấn (query) tài liệu mà người sử dụng quan tâm. Sau đây là định nghĩa về hệ thống tìm kiếm thông tin:

• Salton (1989): Hệ thống tìm kiếm thông tin xử lý các tập tin lưu trữ và những yêu cầu về thông tin, xác đỊnh và tìm từ các tập tin những thông tin phù hợp với những yêu cầu về thông tin. Việc tìm kiếm những thông tin đặc thù phụ thuộc vào sự tương tự giữa các thông tin được lưu trữ và các yêu cầu, được đánh giá bằng các h so sánh các giá trị của các thuộc tính đối với thông tin được lưu trữ và các yêu cầu về thông tin.
• Kowalski (1997): Hệ thống tìm kiếm thông tin là một hệ thống có khả năng lưu trữ, tìm kiếm và duy trì thông tin. Thông tin trong nững trường hợp này c ó thể bao gồm văn bản, hình ảnh, âm thanh, video và những đối tượng đa phương tiện khác.

Tìm kiếm thông tin là lĩnh vực nghiên cứu nhằm tìm ra các giải pháp giúp người sử dụng có thể tìm thấy các thông tin mình cần trong một khối lượng lớn dữ liệu. Nhiệm vụ của một hệ thống tìm kiếm thông tin tương tự như nhiệm vụ tổ chức phân loại tài liệu và phục vụ việc tra cứu của một thư viện.

Một hệ thống tìm kiếm thông tin có hai chức năng chính: lập chỉ mục (indexing) và tra cứu (interrogation). Lập chỉ mục là giai đoạn phân tích tài liệu (document) để xác định các chỉ mục (term/index term) biểu diễn nội dung của tài liệu. Việc lập chỉ mục có thể dựa vào một cấu trúc phân lớp có sẵn (control vocabulary) như cách làm của các nhân viên thư viện, phân loại tài liệu theo một bộ phân loại cho trước. Các chỉ mục trong cách làm này là tồn tại trước và độc lập với tài liệu. Cách thứ hai để lập chỉ mục là rút trích các chỉ mục từ chính nội dung của tài liệu (free text). Cuối giai đoạn lập chỉ mục nội dung của các tài liệu có trong kho tài liệu (corpus) được biểu diễn bằng tập các chỉ mục.

Hình 1.1 Mô hình tổng quát tìm kiếm thông tin

 Quy trình của hệ thống tìm kiếm thông tin như sau:

• Người sử dụng muốn xem tài liệu liên quan đến một chủ đề nào đó.
• Người sử dụng cung cấp mô tả về tài liệu muốn xem dưới dạng câu truy vấn.
• Từ câu truy vấn này hệ thống lọc ra những cụm từ và chỉ mục của tài liệu đã được xử lý trước đó.
• Những tài liệu nào liên quan cao nhất với mô tả sẽ được trả về cho người sử dụng.

Kiến trúc của hệ tìm kiếm thông tin

Hình 1.2 Mô hình kiến trúc của hệ tìm kiếm thông tin

Hình 1.3 Cấu trúc hệ tìm kiếm thông tin tiêu biểu

Hệ thống tìm kiếm thông tin gồm có 3 bộ phận chính: bộ phận phân tích văn bản, bộ phận lập chỉ mục, bộ phận so khớp và sắp xếp các tài liệu trả về

• Bộ phận phân tích văn bản: bộ phận này có nhiệm vụ phân tích các văn bản thu thập được thành các từ riêng biệt. Tương tự, khi người dùng nhập câu truy vấn thì câu truy vấn cũng được phân tích thành các từ riêng biệt.
• Bộ phận lập chỉ mục: các từ trích được từ các vă n bản thu thập được sẽ được bộ phận này lựa chọn để làm các từ chỉ mục. Các từ chỉ mục phải là các từ thể hiện được nội dung của văn bản. Hai bộ phận phân tích văn bản và lập chỉ mục thường đi liền với nhau và thường chỉ gọi là bộ phận lập chỉ mục
• Bộ phận so khớp và sắp xếp các tài liệu trả về: Các lừ trích được từ câu truy vấn và các từ chỉ mục của văn bản sẽ được so khớp với nhau để tìm ra các tài liệu liên quan đến câu truy vấn. Mỗi tài liệu có một độ tương quan với câu truy vấn. Các tài lệu này sẽ được sắp xếp theo độ tương quan giảm dần và trả về cho người sử dụng.

Các hệ tìm kiếm văn bản thường được sử dụng hiện nay ngoài GoogleDesktop và DTSearch là hệ tìm kiếm văn bản Lucene: Hệ tìm kiếm văn bản Lucene là hệ tìm kiếm mã nguồn mở. Hệ thống được phát triển cả trên nền .Net và cả trên ngôn ngữ Java. Hệ thống hiện cũng được khá nhiều lập trình viên phát triển.

CHƯƠNG 2:   TỔNG QUAN LUCENE

1.  Giới thiệu Lucene

Lucene là một thư viện mã nguồn mở hỗ trợ việc tìm kiếm thông tin. Lucene cho phép chúng ta có thể tích hợp vào các ứng dụng. Lucene nguyên thuỷ được phát triển bằng ngôn ngữ Java, ngày nay Lucene được phát triển bằng nhiều ngôn ngữ khác nhau như Delphi, Perl, C#, C++, Python, Ruby và PHP…

Thành phần chức năng chính của Lucene bao gồm hai phần: thành phần tạo chỉ mục và thành phần tìm kiếm. Đây chính là hai thành phần quan trọng cho một hệ thống tìm kiếm.

Hình 2.1. Các thành phần Lucene hỗ trợ cho hệ thống tìm kiếm

• Thành phần tạo chỉ mục:
  • Directory: cho phép định nghĩa vùng nhớ, xác định nơi lưu trữ trên bộ nhớ ngoài và bộ nhớ trên RAM trong quá trình tạo chỉ mục.
  • Document và Field: định nghĩa tài liệu và các trường thông tin của tài liệu sử dụng cho lập chỉ mục, sử dụng cho việc lấy kết quả trả về cho thành phần tìm kiếm.
  • Analyzer: thực hiện chức năng xử lý và tách văn bản để lấy nội dung, chuẩn hóa, loại bỏ mục từ không cần thiết,… để chuẩn bị cho việc lập chỉ mục.
  • IndexWriter: là phần chính trong thành phần tạo chỉ mục, nó thực hiện việc tạo mới hoặc mở chỉ mục, sau đó thực hiện thêm mới hoặc cập nhật nội dung của chỉ mục.
• Thành phần tìm kiếm:
  • Term: Term là một đơn vị cơ bản của tìm kiếm, Term bao gồm tên và giá trị tương ứng.
  • Query: bao gồm nhiều loại truy vấn khác nhau, nó chứa nhiều phương thức, nhưng hầu hết đều quan tâm đến việc thiết lập chỉ số Boost
  • IndexSearcher: cho phép tìm kiếm trên tập chỉ mục do IndexWriter tạo ra, đây là thành phần chỉ thực hiện nhiệm vụ mở tập chỉ mục, không cho phép chỉnh sửa hay thay đổi.
  • TopDoc: là một lớp đơn giản, dùng cho việc chứa các thứ hạng cao nhất của N tài liệu có liên quan đến truy vấn. Với mỗi đối tượng trong danh sách này sẽ cho một docID dùng để liên kết đến tài liệu.

• Lucene không phải là một ứng dụng hay một máy tìm kiếm hoàn chỉnh để người dùng có thể sử dụng ngay lập tức, Lucene chỉ là một thư viện cung cấp các thành phần quan trọng nhất của một máy tìm kiếm đó là tạo chỉ mục và thực hiện truy vấn.

1. Lập chỉ mục

1.    Cấu trúc của chỉ mục

Lucene hỗ trợ hai cấu trúc chỉ mục: các chỉ mục đa tệp (multifile indexes) và các chỉ mục ghép (compound indexes). Chỉ mục đa tệp là cấu trúc chỉ mục đưa ra từ những phiên bản đầu tiên của Lucene ; cấu trúc chỉ mục ghép được đưa ra trong Lucene 1.3 và từ phiên bản 1.4 thì trở thành cấu trúc mặc định.

• Chỉ mục đa tệp: một chỉ mục đa tệp là một thư mục bao gồm các tệp chỉ mục

Hình 2.2: Ví dụ các tệp chỉ mục đa tệp

• Chỉ mục ghép: một chỉ mục ghép là một thư mục chứa một tệp .cfs duy nhất, cấu trúc chỉ mục ghép đóng gói các tệp chỉ mục riêng lẻ trong một tệp .cfs duy nhất.

Hình 2.3: Ví dục các tệp chỉ mục ghép

2. Quy trình đánh chỉ mục

Hình 2.4: Quy trình đánh chỉ mục của Lucene

Quy trình đánh chỉ mục của Lucene gồm có 3 bước: Convert to text, Analysis và Writing index.

1. Convert to text:

Để Lucene có thể phân tích và đánh index, trước hết ta phải chuyển tài liệu về dạng văn bản thuần túy (.txt), vì tài liệu đầu vào có thể có rất nhiều định dạng khác nhau (PDF, word, excel,…..) nên bước này rất quan trọng.

2. &nsp; Analysis:

Mỗi khi ta chuẩn bị cho việc index và tạo ra đối tượng Document với các Field, thì Lucene sẽ phân tích dữ liệu này sao cho phù hợp nhất với việc index. Để làm điều này, Lucene sẽ phân chia dữ liệu thành các chuỗi hoặc là các kí tự (tokenize) thông qua việc lựa chọn các toán tử thực thi trên chúng. Chẳng hạn như việc bạn phân tích thành các kí tự thường, hoặc bỏ đi các từ ngữ không có nghĩa… Lucene hỗ trợ ta 4 bộ phân tích dữ liệu: WhitespaceAnalyzer, SimpleAnalyzer, StopAnalyzer, StandardAnalyzer.

2. • WhitespaceAnalyzer không thực hiện lowercase(chuyển tất cả sang  ký tự thường ) , vẫn giữ dấu “-” , loại bỏ tất cả các khoảng trắng, và dựa vào các khoảng trắng để làm đường biên phân chia tokenize.
   • SimpleAnalyzer thực hiện lowercase, vẫn giữ các từ nằm trong danh sách stop-word,  dùng các ký tự không phải là các chữ cái alphabetic để làm đường biên phân chia tokenize.
   • Cả SimpleAnalyzer và WhitespaceAnalyzer đều làm sai lệch tên của tên các công ty như ví dụ xy&z bị rã ra thành [xy] [z] , loại bỏ ký hiệu &.
   • StopAnalyzer  và StandardAnalyzer loại bỏ các từ nằm trong Stop-Word ví dụ như “the” ở ví dụ trên.
   • StopAnalyzer chia các từ cơ bản trong dữ liệu đưa vào và lowercasing , còn loại bỏ những stop words. Đưa vào các từ English thuộc stopword vào trong StopAnalyzer
   • StandardAnalyzer là bộ phân tích chung nhất , nền tảng gắn liền với analyzer trong Lucene. Tokenizing thông minh với các loại từ vựng, chữ cái, viết tắt của các chữ đầu dòng, tên công ty, địa chỉ email, tên miền , số, serial number, IP address, CJK (Chinese, Japanese, Korean) character. Loại bỏ các từ nằm trong stopword , vì vậy StandardAnalyzer thường là lựa chọn đầu tiên.
3. Writing index

Sau khi phân tích dữ liệu, Lucene sẽ lưu dữ liệu này theo cấu trúc inverted index(chỉ mục có thể  nghịch đảo ). Cấu trúc này sẽ có hiệu quả để tiết kiệm dung lượng ổ đĩa và cho phép tìm kiếm nhanh hơn các từ khóa trong quá trình search.

3. Inverted index

Xây dựng và duy trì một inverted index là vấn đề trung tâm khi xây dựng một hệ thống tìm kiếm hiệu quả. Để lập chỉ mục một tài liệu, trước hết phải duyệt qua nó để tạo một danh sách các posting. Các posting mô tả các thể hiện của một từ trong một tài liệu; chúng thường gồm một từ, một mã tài liệu và có thể cả các vị trí hoặc tần số của từ đó trong tài liệu.

Lucene xây dựng nhiều phân đoạn chỉ mục và kết hợp chúng lại với nhau một cách định kỳ. Với mỗi tài liệu mới được lập chỉ mục, Lucene tạo một phân đoạn chỉ mục, nhưng nó sẽ nhanh chóng kết hợp các phân đoạn nhỏ với những phân đoạn lớn hơn - việc này giữ cho tổng số các phân đoạn luôn nhỏ nhằm đảm bảo tốc độ tìm kiếm vẫn nhanh. Để tối ưu chỉ mục cho tìm kiếm được nhanh, Lucene kết hợp tất cả các phân đoạn thành một, Lucene không bao giờ thay đổi ngay các phân đoạn mà nó chỉ tạo ra phân đoạn mới. Khi kết hợp các phân đoạn, Lucene ghi một phân đoạn mới và xoá những phân đoạn cũ

Hình 2.5: Ví dụ minh họa định dạng chỉ mục Lucene

• Tệp .fnm: Tệp .fnm bao gồm tất cả các tên trường được sử dụng. Mỗi trường được đánh dấu để thể hiện các thuộc tính của nó. Thứ tự các tên trường trong tệp .fnm được xác định trong quá trình lập chỉ mục và không cần thiết phải theo thứ tự abc.
• Tệp .tis: Tệp .tis chứa các term (tên trường và các giá trị) cùng tần số tài liệu (document frequency: số tài liệu chứa term này) của nó. Các term được sắp xếp theo theo thứ tự ABC của tên trường và giá trị trong một trường.
• Tệp .frq: Tệp frq chứa tần số term trong mỗi tài liệu. Tần số của một term trong một tài liệu được dùng làm thừa số để tính xếp hạng và thường tăng độ liên quan của một tài liệu khi nó có tần số cao
• Tệp .prx: Tệp .prx liệt kê vị trí của từng term trong một tài liệu.

2.  Tìm kiếm

 Mô hình không gian vector

Mô hình không gian véctơ đã được sử dụng rộng rãi trong lĩnh vực tìm kiếm thông tin và hầu hết các máy tìm kiếm đều sử dụng độ đo dựa trên mô hình này để xếp hạng các tài liệu. Mô hình này tạo ra một không gian trong đó cả các tài liệu và các truy vấn được biểu diễn bởi các véctơ term, trong đó các term được đánh trọng số. Ví dụ, một tài liệu D được biểu diễn bởi một véctơ có n trọng số D = (d₁,  d₂, d₃ , …, d_n ), với n là số các term không trùng lặp trong tập tài liệu.

Mô hình không gian véctơ mang lại lược đồ đánh trọng số nhằm phân biệt tài liệu này với tài liệu khác, hầu hết là trọng số idf, với giả thiết rằng độ quan trọng của một term tỷ lệ thuận với số các thể hiện của term đó trong một tài liệu và tỷ lệ nghịch với số các tài liệu có chứa term đó.

Hai véctơ trong không gian véctơ càng gần nhau thì khả năng liên quan của tài liệu tương ứng càng cao. Trong mô hình không gian véctơ, có nhiều độ đo để tính độ đồng dạng này. Độ đo sự đồng dạng phổ biến nhất là hệ số côsin, hệ số này đo góc côsin giữa một véctơ tài liệu và véctơ truy vấn. Sau đó, các tài liệu được xếp hạng theo thứ tự các giá trị côsin giảm dần.

Giả sử cho câu truy vấn “gold silver truck” và 3 tài liệu:

D1: "Shipment of gold damaged in a fire"

D2: "Delivery of silver arrived in a silver truck"

D3: "Shipment of gold arrived in a truck

Các kết quả tính trọng số được tổng kết trong bảng

Hình 2.6: Kết quả tính trọng số

Cột 1 đến cột 5: Danh mục các thuật ngữ được xây dựng từ các tài liệu và tính tần số tf_i cho câu truy vấn trong mỗi tài liệu D_j

Cột 6 đến cột 8: Là tần số tài liệu d_i của từng tài liệu. Từ đó tính IDF_i = log(D/df_i) và D = 3.

Cột 9 đế cột 12: Là trọng số thuật ngữ được xác định bằng cách lấy tích tf_i * IDF_i . Các cột này có thể được xem như là một ma trận thưa, trong đó hầu hết các mục bằng 0.

Tính độ tương đồng

Để tính độ tương đồng, trước tiên tính tất cả các chiều dài vector cho mỗi tài liệu và câu truy vấn:

Tiếp theo tính tất cả các tích điểm (bỏ qua các tích 0)

=> Các giá trị tương đồng

Cuối cùng sắp xếp thứ tự cho các tài liệu theo thứ tự giảm dần theo giá trị tương đồng:

Rank 1: Doc2 = 0.8246

Rank 2: Doc 3= 0.3271

Rank 3: Doc 1= 0.0801

• Demo giao diện chức năng ứng dụng