Đề tài Xây dựng hệ thống tìm kiếm thông tin tiếng Việt dựa trên các chỉ mục có cấu trúc

u đó càng liên quan đến câu hỏi. Giả sử một tập tài liệu chỉ gồm có hai từ là t1 và t2. Vector xây dựng được sẽ gồm có 2 thành phần: thành phần thứ nhất biểu diễn sự xuất hiện của t1, và thành phần thứ hai biểu diễn cho sự xuất hiện của t2. Cách đơn giản nhất để xây dựng vector là đánh 1 vào thành phần tương ứng nếu từ đó xuất hiện, và đánh 0 nếu từ đó không xuất hiện. Giả sử tài liệu chỉ gồm có 2 từ t1. Ta biểu diễn cho tài liệu này bởi vector nhị phân như sau: Tuy nhiên, biểu diễn như vậy không cho thấy được tần số xuất hiện của mỗi từ trong tài liệu. Trong trường hợp này, vector nên được biễu diễn như sau: Đối với một câu hỏi đã cho, thay vì chỉ căn cứ so sánh các từ trong tài liệu với tập các từ trong câu hỏi, ta nên xem xét đến tầm quan trọng của mỗi từ. Ý tưởng chính là một từ xuất hiện tập trung trong một số tài liệu thì có trọng số cao hơn so với một từ phân bố trong nhiều tài liệu. Trọng số được tính dựa trên tần số tài liệu nghịch đảo (Inverse Document Frequency) liên quan đến các từ được cho: n: số từ phân biệt trong tập tài liệu tfij : số lần xuất hiện của từ tj trong tài liệu Di (tần số) dfj : số tài liệu có chứa từ tj idfj = trong đó d là tổng số tài liệu Vector được xây dựng cho mỗi tài liệu gồm có n thành phần, mỗi thành phần là giá trị trọng số đã được tính toán cho mỗi từ trong tập tài liệu. Các từ trong tài liệu được gán trọng số tự động dựa vào tần số xuất hiện của chúng trong tập tài liệu và sự xuất hiện của mỗi từ trong một tài liệu riêng biệt. Trọng số của một từ tăng nếu từ đó xuất hiện thường xuyên trong một tài liệu và giảm nếu từ đó xuất hiện thường xuyên trong tất cả các tài liệu. Để tính trọng số của từ thứ tj trong tài liệu Di, dựa vào công thức: dij = tfij * idfj dij : là trọng số của từ tj trong tài liệu Di Đối với hệ thống tìm kiếm thông tin theo mô hình vector, mỗi tài liệu là một vector có dạng : Di(di1, di2 , …, din ) . Tương tự, câu truy vấn Q cũng là một vector có dạng : Q(wq1, wq2, …, wqn) wqj : là trọng số của từ tj trong câu truy vấn Q. Độ tương quan (SC: similarity coeficient) giữa câu truy vấn Q và tài liệu Di được tính như sau: SC(Q,Di) = Tìm kiếm Boolean Mô hình tìm kiếm Boolean khá đơn giản. Câu hỏi đưa vào phải ở dạng biểu thức Boolean. Nghĩa là phải thỏa: Ngữ nghĩa rõ ràng Hình thức ngắn gọn Do các từ hoặc xuất hiện hoặc là không xuất hiện, nên trọng số wij e {0,1}Giả sử đưa vào một câu hỏi dạng biểu thức Boolean như sau: t1 and t2. Sau khi tìm kiếm ta xác định được các tài liệu liên quan đến t1 là { d1, d3, d5} và các tài liệu liên quan đến t2 là {d3, d5, d7}. Như vậy với phép and, các tài liệu thỏa yêu cầu của người dùng là {d3, d5}. Phương pháp này có một số khuyết điểm như sau: Các tài liệu trả về không được sắp xếp (ranking) Câu hỏi tìm kiếm đòi hỏi phải đúng định dạng của biểu thức Boolean gây khó khăn cho người dùng Kết quả trả về có thể là quá ít hoặc quá nhiều tài liệu Tìm kiếm Boolean mở rộng Mô hình tìm kiếm Boolean không hỗ trợ việc sắp xếp kết quả trả về bởi vì các tài liệu hoặc thỏa hoặc không thỏa yêu cầu Boolean. Tất cả các tài liệu thỏa mãn đều được trả về, nhưng không có sự ước lượng nào được tính toán cho sự liên quan của chúng đối với câu hỏi. Mô hình tìm kiếm Boolean mở rộng ra đời nhằm hỗ trợ việc sắp xếp (ranking) kết quả trả về dựa trên ý tưởng cơ bản là đánh trọng số cho mỗi từ trong câu hỏi và trong tài liệu. Giả sử một câu hỏi yêu cầu (t1 OR t2) và một tài liệu D có chứa t1 với trọng số w1 và t2 với trọng số w2 . Nếu w1 và w2 đều bằng 1 thì tài liệu nào có chứa cả hai từ này sẽ có thứ tự sắp xếp cao nhất. Tài liệu nào không chứa một trong hai từ này sẽ có thứ tự sắp xếp thấp nhất. Ý tưởng đơn giản là tính khoảng cách Eclide từ điểm (w1, w2) tới gốc: SC(Q,Di) = Với trọng số 0.5 và 0.5, SC(Q,Di) = =0.707 SC cao nhất nếu w1 và w2 đều bằng 1. Khi đó: SC(Q,Di) = = 1.414 Để đưa SC vào khoảng [0,1], SC được tính như sau: SC( Q t1 v t2 , di) = Công thức này giả sử là câu hỏi chỉ có toán tử OR . Đối với toán tử AND, thay vì tính khoảng cách tới gốc, ta sẽ tính khoảng cách đến điểm (1,1). Câu hỏi nào càng gần đến điểm (1,1) thì nó càng thoả yêu cầu của toán tử AND: SC(Q t1 ^ t2, di) = 1- Mở rộng trong việc thêm vào trọng số của câu hỏi Nếu câu hỏi có trọng số là q1 và q2 thì độ tương quan sẽ được tính như sau: SC(Q q1 v q2, di) = SC(Q q1 ^ q2, di) = 1- () Mở rộng cho số từ tuỳ ý Để tính khoảng cách Euclide trong không gian đa chiều, tham số p được sử dụng. Tham số p chỉ sự biến đổi tầm quan trọng của trọng số trong việc đánh giá độ thích hợp. Độ tương quan SC tổng quát như sau: SC(D, Q ( q i v q j ) ) = SC(D, Q ( q i ^ q j ) ) = 1 - Nếu p : chuyển về hệ thống Boolean thông thường (không có trọng số) Nếu p = 1 : chuyển về hệ thống không gian vector Thêm toán tử tự động Các chiến lược tìm kiếm không đòi hỏi người dùng nhận biết các toán tử phức tạp. Trọng số có thể được gán tự động và tài liệu được sắp xếp bằng cách chèn toán tử OR vào giữa các từ. Bất kỳ tài liệu nào có chứa ít nhất một từ trong câu hỏi sẽ được sắp thứ tự với một số điểm lớn hơn 0. Mô hình xác suất Mô hình tìm kiếm xác suất tính toán độ tương quan giữa câu hỏi và tài liệu dựa vào xác suất mà tài liệu đó liên quan đến câu hỏi. Các lý thuyết về xác suất được áp dụng để tính toán độ liên quan giữa câu hỏi và tài liệu. Các từ trong câu hỏi được xem là đầu mối để xác định tài liệu liên quan. Ý tưởng chính là tính xác suất của mỗi từ trong câu hỏi và sau đó sử dụng chúng để tính xác suất mà tài liệu liên quan đến câu hỏi. Đánh giá chung về các mô hình Mô hình Boolean được xem là mô hình yếu nhất trong các mô hình bởi vì như đã trình bày nó còn rất nhiều khuyết điểm. Theo kinh nghiệm của Salton và Buckley thì nhìn chung mô hình vector làm tốt hơn mô hình xác suất. Luận văn của chúng em sử dụng mô hình không gian vector để xây dựng một hệ thống tìm kiếm thông tin tiếng Việt. Các bước để xây dựng một hệ tìm kiếm thông tin. [3.2] Tách từ tự động cho tập các tài liệu Đối với tiếng Anh, ta tách từ dựa vào khoảng trắng. Tuy nhiên đối với tiếng Việt, giai đoạn này tương đối khó khăn. Cấu trúc tiếng Việt rất phức tạp, không chỉ đơn thuần dựa vào khoảng trắng để tách từ. Hiện nay có rất nhiều công cụ dùng để tách từ tiếng Việt, mỗi phương pháp có ưu, khuyết điểm riêng. Các phương pháp này sẽ được trình bày chi tiết hơn ở chương III : Tách từ tự động. Lập chỉ mục cho tài liệu Sau khi có được tập các từ đã được trích, ta sẽ chọn các từ để làm từ chỉ mục. Tuy nhiên, không phải từ nào cũng được chọn làm từ chỉ mục. Các từ có khả năng đại diện cho tài liệu sẽ được chọn, các từ này được gọi là key word, do đó trước khi lập chỉ mục sẽ là giai đoạn tiền xử lý đối với các từ trích được để chọn ra các key word thích hợp. Ta sẽ loại bỏ danh sách các từ ít có khả năng đại diện cho nội dung văn bản dựa vào danh sách gọi là stop list. Đối với tiếng Anh hay tiếng Việt đều có danh sách stop list. Chi tiết về quá trình lập chỉ mục sẽ được mô tả ở chương IV: Lập chỉ mục. Tìm kiếm Người dùng nhập câu hỏi và yêu cầu tìm kiếm, câu hỏi mà người dùng nhập vào cũng sẽ được xử lý, nghĩa là ta sẽ tách từ cho câu hỏi. Phương pháp tách từ cho câu hỏi cũng nên là phương pháp tách từ cho các tài liệu thu thập được để đảm bảo sự tương thích. Sau đó, hệ thống sẽ tìm kiếm trong tập tin chỉ mục để xác định các tài liệu liên quan đến câu hỏi của người dùng. Sắp xếp các tài liệu trả về (Ranking) Các tài liệu sau khi đã xác định là liên quan đến câu hỏi của người dùng sẽ được sắp xếp lại, bởi vì trong các tài liệu đó có những tài liệu liên quan đến câu hỏi nhiều hơn. Hệ thống sẽ dựa vào một số phương pháp để xác định tài liệu nào liên quan nhiều nhất, sắp xếp lại (ranking) và trả về cho người dùng theo thứ tự ưu tiên. Những khó khăn trong việc xây dựng một hệ thống tìm kiếm thông tin tiếng Việt Hiện nay, chúng ta đã quen thuộc với rất nhiều công cụ hỗ trợ việc tìm kiếm thông tin như Google, Yahoo Search, AltaVista, …. Tuy nhiên, đây là các công cụ của người nước ngoài nên chúng chỉ giải quyết tốt đối với các yêu cầu của họ. Chúng ta cũng có một số công cụ hỗ trợ tìm kiếm thông tin tiếng Việt như: Vinaseek, NetNam,…Các công cụ này cũng tách từ chủ yếu dựa vào khoảng trắng nên việc tìm kiếm cũng chưa được cải thiện. Nhìn chung, để xây dựng một hệ thống tìm kiếm thông tin tiếng Việt, chúng ta gặp khó khăn trong việc tách từ tiếng Việt và xác định bảng mã tiếng Việt. Khó khăn trong việc tách từ tiếng Việt Có thể nói tách từ là giai đoạn khó khăn nhất khi xây dựng một hệ tìm kiếm thông tin tiếng Việt. Đối với tiếng Anh, việc xác định từ chỉ đơn giản dựa vào khoảng trắng để tách từ. Ví dụ, câu: “I am a student” sẽ được tách thành 4 từ : I, am, a, student. Tuy nhiên, đối với tiếng Việt, tách dựa vào khoảng trắng chỉ thu được các tiếng. Từ có thể được ghép từ một hay nhiều tiếng. Từ phải có ý nghĩa hoàn chỉnh và có cấu tạo ổn định. Câu: “Tôi là một sinh viên” được tách thành 4 từ: Tôi, là, một, sinh viên. Trong đó, từ “sinh viên” được hình thành từ 2 tiếng: sinh và viên. Hiện nay, có rất nhiều phương pháp được sử dụng để tách từ tiếng Việt. Tuy nhiên, với sự phức tạp của ngữ pháp tiếng Việt nên chưa có phương pháp nào đạt được chính xác 100%. Và việc lựa chọn phương pháp nào là tốt nhất cũng đang là vấn đề tranh cãi. Vấn đề bảng mã tiếng Việt Không như tiếng Anh, tiếng Việt có rất nhiều bảng mã đòi hỏi phải xử lý. Một số công cụ tìm kiếm tiếng Việt hỗ trợ bảng mã rất tốt như Vinaseek, hỗ trợ mọi bảng mã (VNI, TCVN3, ViQR,…). Các khó khăn khác Tiếng Việt có các từ đồng nghĩa nhưng khác âm. Các công cụ hiện nay không hỗ trợ việc xác định các từ đồng nghĩa. Vì vậy, kết quả trả về sẽ không đầy đủ. Ngược lại, có những từ đồng âm khác nghĩa. Các hệ thống sẽ trả về các tài liệu có chứa các từ đã được tách trong câu hỏi mà không cần xác định chúng có thực sự liên quan hay không. Vì vậy, kết quả trả về sẽ không chính xác. Một số từ xuất hiện rất nhiều nhưng không có ý nghĩa trong tài liệu. Các từ như: và, với, nhưng,… có tần số xuất hiện rất lớn trong bất cứ văn bản nào. Nếu tìm cách trả về các tài liệu có chứa những từ này sẽ thu được kết quả vô ích, không cần thiết. Do đó, chúng ta cần tìm cách loại bỏ các từ này trước khi tìm kiếm. TÁCH TỪ TỰ ĐỘNG Trước khi lập chỉ mục là giai đoạn tách từ cho các tài liệu, đây là công việc quan trọng trong một hệ thống tìm kiếm thông tin. Đối với tiếng Anh chỉ đơn giản dựa vào khoảng trắng để tách từ. Nhưng đối với tiếng Việt không thể dựa vào khoảng trắng được vì tiếng Việt là ngôn ngữ đơn lập. Hiện nay, có rất nhiều phương pháp được đề xuất để tách từ cho tiếng Việt, nhưng vẫn chưa thống nhất là phương pháp nào tốt nhất. Chương này sẽ trình bày chi tiết về một số phương pháp tách từ. Tách từ trong Tiếng Anh Do đặc điểm ngữ pháp của tiếng Anh, tách từ chỉ đơn giản dựa vào khoảng trắng để phân biệt từ. Tách từ trong Tiếng Việt Một số đặc điểm chính về từ tiếng Việt [2.2] Tiếng Về mặt ngữ âm, tiếng là âm tiết. Âm tiết bao gồm những đơn vị ở bậc thấp hơn gọi là âm vị. Mỗi âm vị được ghi bằng một ký tự gọi là chữ. Về mặt ngữ nghĩa, tiếng là đơn vị nhỏ nhất có nghĩa, nhưng cũng có một số tiếng không có nghĩa. Về giá trị ngữ pháp, tiếng là đơn vị cấu tạo từ. Sử dụng tiếng để tạo thành từ, ta có hai trường hợp như sau: Từ một tiếng: gọi là từ đơn. Trường hợp này một từ chỉ có một tiếng. Ví dụ như: ông, bà, … Từ hai tiếng trở lên: gọi là từ phức. Trường hợp này một từ có thể có hai hay nhiều tiếng trở lên. Ví dụ như: xã hội, an ninh, hợp tác xã,… Từ Từ là đơn vị nhỏ nhất để tạo thành câu. Trong đặt câu, chúng ta dùng từ chứ không dùng tiếng. Tách từ tự động tiếng Việt Tách từ tự động tiếng Việt dựa trên một số phương pháp có sẵn. Sau đây chúng ta sẽ nghiên cứu một số phương pháp được sử dụng để tách từ cho các văn bản tiếng Việt. Các phương pháp tách từ tiếng Việt fnTBL (Fast Transformation-based learning) [3.1] Mô tả Ý tưởng chính của phương pháp học dựa trên sự biến đổi (TBL) là để giải quyết một vấn đề nào đó ta sẽ áp dụng các phép biến đổi, tại mỗi bước, phép biến đổi nào cho kết quả tốt nhất sẽ được chọn và được áp dụng lại với vấn đề đã đưa ra. Thuật toán kết thúc khi không còn phép biến đổi nào được chọn. Hệ thống fnTBL gồm hai tập tin chính: Tập tin dữ liệu học (Training): Tập tin dữ liệu học được làm thủ công, đòi hỏi độ chính xác. Mỗi mẫu (template) được đặt trên một dòng riêng biệt. Ví dụ: tập dữ liệu học cho việc xác định từ loại của một văn bản có thể có định dạng như sau: Công ty danhtu An Đông danhturieng bị dongtu giám sát dongtu Trong ví dụ này mỗi mẫu gồm có hai phần: phần đầu tiên là từ, phần thứ hai là từ loại tương ứng. Tập tin chứa các mẫu luật (rule-template): Mỗi luật được đặt trên một dòng, hệ thống fTBL sẽ dựa vào các mẫu luật để áp dụng vào tập tin dữ liệu học. Ví dụ: chunk_-2 chunk_-1 => chunk Áp dụng đối với việc xác định từ loại, với chunk_-2 = động từ, chunk_-1= số từ, chunk=danh từ thì luật trên có ý nghĩa như sau: nếu hai từ trước đó là động từ và số từ thì chuyển từ loại hiện hành thành danh từ. Áp dụng tách từ tiếng Việt Sau khi nghiên cứu về fnTBL, chúng em nhận thấy có thể áp dụng phương pháp này để tách từ cho tiếng Việt, chỉ cần thay đổi một số định dạng cho phù hợp. Xây dựng tập tin dữ liệu học: Tập tin dữ liệu cho việc tách từ tiếng Việt có dạng như sau: Vì Bsao Bcông B ty IViệt BHà Ibị Bđặt Bvào Btình Btrạng I…. Các ký tự B, I gọi là các chunk và có ý nghĩa như sau:Tiếng có chunk=B nghĩa là tiếng đó bắt đầu một từ (begin) Tiếng có chunk=I nghĩa là tiếng đó nằm ở trong một từ (inside) Trong ví dụ trên, ta có được các từ: Vì, sao, công ty, Việt Hà, bị, đặt, vào, tình trạng, … Xây dựng tập tin chứa các mẫu luật: Sau khi tìm hiểu về từ trong tiếng Việt, chúng em xây dựng được 3 luật áp dụng cho việc tách từ tiếng Việt như sau: chunk_0 word_0 => chunk chunk_0 word_-1 word_0 => chunk chunk_0 word_0 word_1 => chunk Quá trình học (1) Từ tập dữ liệu học xây dựng từ điển các từ (2) Khởi tạo các từ (3) Rút ra tập luật Ở bước (1) từ tập dữ liệu học đã có sẵn, sử dụng phương pháp thống kê → ta sẽ có từ điển các tiếng (Lexicon). Các tiếng có thể xuất hiện trong các từ với các chunk khác nhau, ta sẽ ghi nhận lại số lần xuất hiện của mỗi tiếng với các chunk tương ứng. Ví dụ, đối với từ “công ty” thì tiếng “công” có chunk=B nhưng trong từ “của công” thì tiếng công có chunk=I. Ở bước (2) từ tập dữ liệu học, tạo ra tập dữ liệu học không có chunk bằng cách xóa hết các chunk tương ứng. Tập dữ liệu mới này sẽ được sử dụng để khởi tạo lại các chunk thông dụng nhất dựa vào từ điển. Ở bước (3) so sánh tập dữ liệu học với tập dữ liệu đang xét, dựa vào các mẫu luật đã cho, ta sẽ rút ra được các luật ứng viên, ứng với mỗi luật ứng viên ta lại áp dụng vào tập dữ liệu đang xét và tính điểm cho nó (dựa vào số lỗi phát sinh khi so sánh với tập dữ liệu học là tập dữ liệu chuẩn). Chọn luật có điểm cao nhất và lớn hơn một ngưỡng cho trước để đưa vào danh sách luật được chọn. Kết quả ta sẽ được một tập các luật được chọn. Các luật có dạng như sau: SCORE:414 RULE: chunk_0=B word_0=tế => chunk=I SCORE:312 RULE: chunk_0=B word_-1=của word_0=công=>chunk=I SCORE:250 RULE: chunk_0=B word_0=hóa => chunk=I SCORE:231 RULE: chunk_0=B word_0=động => chunk=I SCORE:205 RULE: chunk_0=B word_0=nghiệp => chunk=I SCORE:175 RULE: chunk_0=B word_-1=phát word_0=triển => chunk=I SCORE:133 RULE: chunk_0=B word_-1=xã word_0=hội => chunk=I SCORE:109 RULE: chunk_0=B word_-1=đầu word_0=tư => chunk=I SCORE:100 RULE: chunk_0=B word_0=thể => chunk=I Ở dòng 2 ta có luật: nếu từ hiện hành là “công” (word_0=công) và từ trước đó là “của” (word_-1=của) và chunk của từ hiện hành là B ( chunk_0=B) thì chuyển chunk của từ hiện hành là I , nghĩa là “của công” phải là một từ. Toàn bộ quá trình học được mô tả như sau: Hình 31 Quá trình học Xác định từ cho tài liệu mới (1) Tài liệu mới đưa vào phải có định dạng giống như tập tin dữ liệu học, nghĩa là mỗi tiếng trên một dòng. (2) Dựa vào từ điển, gán chunk thông dụng nhất cho các tiếng trong tài liệu mới (3) Áp dụng các luật có được từ giai đoạn học vào tài liệu đang xét ta sẽ tách được các từ hoàn chỉnh. Giai đoạn xác định từ cho tài liệu mới được mô tả như sau: Hình 32 Giai đoạn xác định từ cho tài liệu mới Longest Matching [1.4] Phương pháp Longest Matching tách từ dựa vào từ điển có sẵn. Theo phương pháp này, để tách từ tiếng Việt ta đi từ trái sang phải và chọn từ có nhiều âm tiết nhất mà có mặt trong từ điển, rồi cứ tiếp tục cho từ kế tiếp cho đến hết câu. Với cách này, ta dễ dàng tách được chính xác các ngữ/câu như: ”hợp tác| mua bán”; “thành lập| nước|Việt Nam| dân chủ |cộng hòa”…Tuy nhiên, phương pháp này sẽ tách từ sai trong trường hợp như: “học sinh |học sinh |học”; “một| ông | quan tài | giỏi”, “trước | bàn là | một | ly| nước”,… Kết hợp giữa fnTBL và Longest Matching Chúng ta có thể kết hợp giữa hai phương pháp fnTBL và Longest Matching để có được kết quả tách từ tốt nhất. Đầu tiên ta sẽ tách từ bằng Longest Matching, đầu ra của phương pháp này sẽ là đầu vào cho phương pháp fnTBL học luật. LẬP CHỈ MỤC Khái quát về hệ thống lập chỉ mục Một cách để tăng tốc độ tìm kiếm thông tin lên là tạo chỉ mục cho các tài liệu. Tuy nhiên, việc lập chỉ mục có một nhược điểm lớn, đó là khi thêm một tài liệu mới, phải cập nhật lại tập tin chỉ mục. Nhưng đối với hệ thống tìm kiếm thông tin, chỉ cần cập nhật lại tập tin chỉ mục vào một khoảng thời gian định kỳ. Do đó, chỉ mục là một công cụ rất có giá trị. Lập chỉ mục bao gồm các công việc sau: Xác định các từ có khả năng đại diện cho nội dung của tài liệu Đánh trọng số cho các từ này, trọng số phản ánh tầm quan trọng của từ trong một tài liệu. Phương pháp lập chỉ mục [1.1] Xác định các từ chỉ mục Cho một tập gồm có n tài liệu. Với mỗi tài liệu, tính tần số của mỗi từ riêng biệt trong tài liệu đó. Gọi FREQik: là tần số xuất hiện của từ k trong tài liệu i. Xác định tần số của từ k trong tập tài liệu, ký hiệu là TOTFREQk bằng cách tính tổng tần số xuất hiện của k trong tất cả n tài liệu: TOTFREQK = Sắp xếp các từ giảm dần dựa vào tần số xuất hiện của nó trong tập tài liệu. Xác định giá trị ngưỡng cao và loại bỏ tất cả các từ có tần số xuất hiện lớn hơn giá trị này. Tương tự, loại bỏ các từ có tần số thấp . Nghĩa là, xác định ngưỡng thấp và loại bỏ tất cả các từ có tần số xuất hiện nhỏ hơn giá trị này. Điều này sẽ loại bỏ các từ ít xuất hiện trong tập tài liệu, nên sự có mặt của các từ này cũng không ảnh hưởng đến việc thực hiện truy vấn. Các từ có tần số xuất hiện trung bình còn lại sẽ được sử dụng làm từ chỉ mục. Hình 41 Các từ được sắp theo thứ tự Các phương pháp tính trọng số của từ Trọng số của một từ phản ánh tầm quan trọng của từ đó trong tài liệu. Ý tưởng chính là một từ xuất hiện thường xuyên trong tất cả các tài liệu thì ít quan trọng hơn là từ chỉ xuất hiện tập trung trong một số tài liệu. Tần số tài liệu nghịch đảo Đây là phương pháp tính trọng số mà mô hình không gian vector đã sử dụng để tính trọng số của từ trong tài liệu. n: số từ phân biệt trong tập tài liệu FREQik : số lần xuất hiện của từ k trong tài liệu Di (tần số từ) DOCFREQk : số tài liệu có chứa từ k Khi đó, trọng số của từ k trong tài liệu Di được tính như sau: WEIGHTik = FREQik * [log (n) – log (DOCFREQk)] Trọng số của từ k trong tài liệu Di tăng nếu tần số xuất hiện của từ k trong tài liệu i tăng và giảm nếu tổng số tài liệu có chứa từ k tăng. Độ nhiễu tín hiệu (The Signal – Noise Ratio) Một quan điểm tương tự được xem xét đó là dựa vào thông tin để đánh giá tầm quan trọng của từ. Trong thực tế, nội dung thông tin của một đoạn hay một từ có thể xác định dựa vào xác suất xuất hiện của các từ trong văn bản đã cho. Rõ ràng, xác suất xuất hiện của một từ càng cao thì thông tin mà nó chứa càng ít. Nội dung thông tin của một từ được xác định như sau: INFORMATION= - log2 p trong đó p là xác suất xuất hiện của từ. Ví dụ: nếu từ “vi tính” xuất hiện 1 lần sau 10.000 từ, xác suất xuất hiện của nó là 0.0001, khi đó thông tin của nó sẽ là: INFORMATION = - log2 (0.0001) = 13.278 Ngược lại, từ “sẽ” xuất hiện 1 lần sau 10 từ, xác suất xuất hiện của nó là 0.1, khi đó thông tin của nó sẽ là: INFORMATION = -log2 (0.1) = 3.223 Nếu một tài liệu có chứa t từ, mỗi từ có xác suất xuất hiện là pk, thông tin trung bình của tài liệu sẽ là: AVERAGE INFORMATION = - Ta định nghĩa độ nhiễu NOISEk của từ k trong tập gồm n tài liệu như sau: NOISEk = Độ nhiễu thay đổi nghịch đảo với “sự tập trung” của một từ trong tập tài liệu. Nghĩa là, một từ có sự phân phối đều trong tất cả các tài liệu thì độ nhiễu của nó càng lớn, ngược lại một từ chỉ tập trung trong một số tài liệu nào đó thì độ nhiễu của nó càng nhỏ.  Giả sử, từ k xuất hiện một lần trong mỗi tài liệu (FREQik=1), khi đó độ nhiễu của nó bằng: NOISEk = = log2 n Ngược lại, giả sử từ k chỉ xuất hiện trong một tài liệu, khi đó độ nhiễu của nó bằng: NOISEk = = 0 Hàm số nghịch đảo của độ nhiễu, gọi là độ signal, được tính như sau: SIGNALk = log2 (TOTFREQk) – NOISEk Trọng số của từ k trong tài liệu i được tính bằng cách kết hợp giữa FREQik và SIGNALk: WEIGHTik = FREQik * SIGNALk Giá trị phân biệt từ (The Term Discrimination Value) Một chức năng khác để xác định tầm quan trọng của một từ là tính giá trị phân biệt của từ đó. Gọi SIMILAR(Di, Dj) là độ tương quan giữa cặp tài liệu Di, Dj. Khi đó, độ tương quan trung bình của tập tài liệu là: AVGSIM= CONSTANT Gọi AVGSIMk là độ tương quan trung bình của tập tài liệu khi bỏ từ k. Rõ ràng, nếu từ k xuất hiện thường xuyên trong tập tài liệu thì khi bỏ từ k, độ tương quan trung bình sẽ giảm. Ngược lại, nếu từ k chỉ tập trung trong một số tài liệu, khi bỏ từ k, độ tương quan trung bình sẽ tăng lên. Giá trị phân biệt DISCVALUEk của từ k được tính như sau: DISCVALUEk = (AVGSIM)k – AVGSIM Trọng số của từ k trong tài liệu i được tính bằng cách kết hợp giữa FREQik và DISCVALUEk: WEIGHTik = FREQik * DISCVALUEk Lập chỉ mục tự động cho tài liệu tiếng Anh Một quá trình đơn giản để lập chỉ mục cho tài liệu có thể được mô tả như sau: Trước hết, xác định tất cả các từ tạo thành tài liệu. Trong tiếng Anh, chỉ đơn giản là tách từ dựa vào khoảng trắng. Loại bỏ các từ có tần số xuất hiện cao. Những từ này chiếm khoảng 40-50% các từ, như đã đề cập trước đây, chúng có độ phân biệt kém do đó không thể sử dụng để đại diện cho nội dung của tài liệu. Trong tiếng Anh, các từ này có khoảng 250 từ, do đó, để đơn giản có thể lưu chúng vào từ điển, gọi là stop list. Sau khi loại bỏ các từ có trong stop list, xác định các từ chỉ mục “tốt”. Trước hết cần loại bỏ các hậu tố để đưa về từ gốc, ví dụ các từ như : analysis, analyzing, analyzer, analyzed, analysing có thể chuyển về từ gốc là “analy.” Từ gốc sẽ có tần số xuất hiện cao hơn so với các dạng thông thường của nó. Nếu sử dụng từ gốc làm chỉ mục, ta có thể thu được nhiều tài liệu có liên quan hơn là sử dụng từ ban đầu của nó. Đối với tiếng Anh, việc loại bỏ hậu tố có thể được thực hiện dễ dàng bằng cách sử dụng danh sách các hậu tố có sẵn (Suffix List). Sau khi có được danh sách các từ gốc, sử dụng phương pháp dựa vào tần số (frequency – based) để xác định tầm quan trọng của các từ gốc này. Chúng ta có thể sử dụng một trong các phương pháp đã được đề cập ở trên như : tần số tài liệu nghịch đảo (inverse document frequency), độ tín hiệu (SIGNALk), độ phân biệt từ (DISVALUEk). Trong hệ thống chỉ mục có trọng số, trọng số của một từ được sử dụng để xác định tầm quan trọng của từ đó. Mỗi tài liệu được biễu diễn là một vector : Di = (di1, di2, …, dit) trong đó dij là trọng số của từ j trong tài liệu Di. Giả sử có 1033 tài liệu nói về y học. Quá trình lập chỉ mục đơn giản được thực hiện như sau ( trong đó chỉ loại bỏ hậu tố tận cùng là s): Hình 42 Quá trình chọn từ làm chỉ mục Lập chỉ mục cho tài liệu tiếng Việt Lập chỉ mục cho tài liệu tiếng Việt cũng tương tự như cho tiếng Anh. Tuy nhiên có vài điểm khác biệt sau: Giai đoạn tách từ trong tiếng Anh chỉ đơn giản dựa vào khoảng trắng, còn tiếng Việt là ngôn ngữ đơn lập, một từ có thể có nhiều tiếng. Điều này đã được đề cập chi tiết ở chương 3 (Tách từ). Giả sử sau giai đoạn tách từ, ta sẽ thu được một danh sách các từ riêng biệt. Đối với tiếng Việt, không phải qua giai đoạn loại bỏ hậu tố. Nói chung, lập chỉ mục cho tài liệu tiếng Việt gồm các bước sau: Xác định các từ riêng biệt trong tài liệu Loại bỏ các từ có tần số cao. ( Trong tiếng Việt, cũng như tiếng Anh, ta có một danh sách Stop List chứa những từ không thể là nội dung của văn bản như: và, với, những, gì, sao, nào, …). Loại bỏ các từ có trọng số thấp Các từ thu được sẽ được chọn làm các từ chỉ mục Tập tin nghịch đảo tài liệu Phân biệt giữa tập tin nghịch đảo và tập tin trực tiếp Tập tin trực tiếp (direct file) là tập tin mà chính các mục thông tin đã cung cấp thứ tự chính của tập tin. Ngược lại, tập tin nghịch đảo (inverted file) được sắp xếp theo chủ đề, mỗi chủ đề lại bao gồm một tập các mục thông tin. Giả sử có một tập các tài liệu, mỗi tài liệu chứa danh sách các từ. Nếu một từ xuất hiện trong một tài liệu, ghi số 1. Ngược lại, ghi 0. Khi đó, tập tin trực tiếp và tập tin nghịch đảo sẽ lưu trữ như sau: Tài liệu 1 Tài liệu 2 Tài liệu 3 Từ 1 1 0 1 Từ 2 1 1 0 Từ 3 0 1 1 Từ 4 1 1 1 Bảng 41 Cách tập tin nghịch đảo lưu trữ Từ 1 Từ 2 Từ 3 Từ 4 Tài liệu 1 1 1 0 1 Tài liệu 2 0 1 1 1 Tài liệu 3 1 0 1 1 Bảng 42 Cách tập tin trực tiếp lưu trữ Tại sao sử dụng tập tin nghịch đảo để lập chỉ mục Trong hệ thống tìm kiếm thông tin, tập tin nghịch đảo có ý nghĩa rất lớn, giúp việc truy cập đến các mục thông tin được nhanh chóng. Giả sử khi người dùng nhập một câu truy vấn, hệ thống sẽ tách thành 2 từ là “từ 1” và “từ 2”. Dựa vào tập tin nghịch đảo, ta dễ dàng xác định được các tài liệu có liên quan đến 2 từ này để trả về cho người tìm kiếm. Tuy nhiên, khó khăn chính của tập tin nghịch đảo là khi thêm một tài liệu mới, tất cả các từ có liên quan đến tài liệu này đều phải được cập nhật lại. Ví dụ khi thêm tài liệu 4 có chứa 2 từ “từ 3” và “từ 4” vào tập tin nghịch đảo: Tài liệu 1 Tài liệu 2 Tài liệu 3 Tài liệu 4 Từ 1 1 0 1 0 Từ 2 1 1 0 0 Từ 3 0 1 1 1 Từ 4 1 1 1 1 Bảng 43 Thêm một tài liệu mới vào tập tin nghịch đảo Rõ ràng việc này tốn một chi phí lớn nếu tập tin nghịch đảo rất lớn. Trong thực tế, tập tin nghịch đảo tài liệu có thể chứa hàng trăm ngàn từ. Tuy nhiên, trong các hệ thống tìm kiếm thông tin, người ta chỉ cập nhật lại tập tin tại một khoảng thời gian định kỳ. Vì vậy, tập tin nghịch đảo vẫn được sử dụng để lập chỉ mục. PHÂN TÍCH VÀ THIẾT KẾ PHÂN TÍCH Sơ đồ UseCase hệ thống Hình 51 Sơ đồ Use-case của hệ thống STT ACTOR Ý NGHĨA 1 Admin Quản trị hệ thống 2 User Người sử dụng chương trình 3 Cac tai lieu Các tài liệu đã được tách từ 4 Cac tai lieu lien quan cau hoi Các tài liệu trả về khi người sử dụng nhập vào câu hỏi 5 Tập tin chi muc Tập tin chứa các từ khóa cùng với các tài liệu chứa từ khóa đó Bảng 51 Danh sách các Actor STT USECASE Ý NGHĨA 1 Tach tu Tách văn bản thành các từ riêng biệt 2 Tao moi tập tin chi muc Tạo mới một tập tin chỉ mục 3 Cap nhat tập tin chi muc Cập nhật thêm các tài liệu mới vào tập tin chỉ mục có sẵn 4 Tim kiem Gõ vào từ khóa và chức năng tìm kiếm sẽ trả về một tập các tài liệu liên quan Bảng 52 Danh sách các UseCase Sơ đồ Lớp Sơ đồ các lớp thể hiện Hình 52 Sơ đồ các lớp thể hiện Sơ đồ các lớp xử lý Hình 53 Sơ đồ các lớp xử lý Tách từ Sơ đồ UseCase Hình 54 Sơ đồ Use-case tách từ Sơ đồ Tuần tự Hình 55 Sơ đồ tuần tự tách từ Sơ đồ Cộng tác Hình 56 Sơ đồ cộng tác tách từ Sơ đồ Lớp Hình 57 Sơ đồ lớp tách từ Lập chỉ mục Sơ đồ UseCase Hình 58 Sơ đồ use-case lập chỉ mục Sơ đồ Tuần tự Tạo mới chỉ mục Hình 59 Sơ đồ tuần tự tạo mới chỉ mục Cập nhật chỉ mục Hình 510 Sơ đồ tuần tự cập nhật chỉ mục Sơ đồ Cộng tác Tạo mới chỉ mục Hình 511 Sơ đồ cộng tác tạo mới chỉ mục Cập nhật chỉ mục Hình 512 Sơ đồ cộng tác cập nhật chỉ mục Sơ đồ Lớp Hình 513 Sơ đồ lớp lập chỉ mục Tìm kiếm Sơ đồ UseCase Hình 514 Sơ đồ use-case tìm kiếm Sơ đồ Tuần tự Hình 515 Sơ đồ tuần tự tìm kiếm Sơ đồ Cộng tác Hình 516 Sơ đồ cộng tác tìm kiếm Sơ đồ Lớp Hình 517 Sơ đồ lớp tìm kiếm THIẾT KẾ VÀ CÀI ĐẶT Ngôn ngữ lập trình : C#, ASP.NET Công cụ lập trình : Microsoft Visual Studio .NET Lưu trữ dữ liệu : tập tin XML Ứng dụng : Xây dựng hệ thống tìm kiếm thông tin tiếng Việt Hệ thống tìm kiếm sẽ được xây dựng theo mô hình không gian Vector. Các tài liệu tiếng Việt và câu truy vấn sẽ được tách từ theo phương pháp Longest Matching. Cấu trúc lưu trữ dữ liệu Tất cả tập tin văn bản, tập tin chứa các từ đã được tách, tập tin chỉ mục đảo, tập tin chứa các từ không quan trọng, tập tin lưu trữ độ tương quan giữa câu truy vấn và tài liệu … đều được lưu trữ dưới dạng Xml. Tập tin lưu nội dung tài liệu Đây là tập tin Xml dùng để lưu nội dung của các tập tin văn bản gốc, mỗi tập tin chứa khoảng 50 tài liệu, có cấu trúc cố định, trong chương trình nó được lưu trong thư mục “VanBanXML”. Cấu trúc DTD / XSD DTD XSD <schema xmlns="urn:schemas-microsoft-com:xml-data" xmlns:dt="urn:schemas-microsoft-com:datatypes"> Tài liệu XML   Thanh niên VN: động lực cho những tầm nhìn mới   Tác giả: Đ.Bình   Ngày :01/12/2000   Tên tờ báo : Tuổi trẻ Thể loại : ,Trang : trang 1, 14   Thanh niên VN: động lực cho những ý tưởng mới, tầm nhìn mới. (TT-Hà Nội) - Tại lễ khai mạc Diễn đàn thanh niên (TN) VN với chủ đề “Sẵn sàng cho thế kỷ 21” sáng 30-11 tại Hà Nội (do Hội Liên hiệp TN VN phối hợp với các cơ quan LHQ tại VN tổ chức), ông Edouard Wattez, điều phối viên thường trú LHQ tại VN, TN VN có vai trò quan trọng trong quá trình mở cửa với thế giới... Đ. Bình. …… Tập tin sau khi tách từ tài liệu Đây là tập tin Xml lưu các từ tách được từ các tập tin văn bản gốc cùng với các ID tham chiếu tới chúng. Mỗi tập tin chứa các từ của 50 tài liệu tương ứng trong tập tin văn bản gốc, trong chương trình các tập tin này được lưu ở thư mục “TachTu”. Cấu trúc DTD / XSD DTD XSD <Schema xmlns="urn:schemas-microsoft-com:xml-data" xmlns:dt="urn:schemas-microsoft-com:datatypes"> Tài liệu XML …… Tập tin chứa các từ không thể hiện nội dung của văn bản (stop list) Đây là tập tin Xml chứa các từ không thể hiện nội dung của văn bản, gọi là danh sách StopList, trong chương trình tập tin này nằm trong thư mục “StopList” Cấu trúc DTD / XSD DTD XSD <Schema xmlns="urn:schemas-microsoft-com:xml-data" xmlns:dt="urn:schemas-microsoft-com:datatypes"> Tài liệu XML Tập tin chỉ mục đảo ( Inverted ). Tập tin chỉ mục đảo lưu các từ chỉ mục, mỗi từ có các tham chiếu đến tài liệu chứa từ đó kèm theo tần số, trọng số của từ đó trong tài liệu, trong chương trình tập tin này được lưu trong thư mục “Inverted ”. Cấu trúc DTD / XSD DTD XSD <Schema xmlns="urn:schemas-microsoft-com:xml-data" xmlns:dt="urn:schemas-microsoft-com:datatypes"> Tài liệu XML …… Tập tin sau khi tách từ câu hỏi. Tập tin này chứa các từ tách được trong câu hỏi, trong chương trình nó được lưu trong thư mục “CauHoi” Cấu trúc DTD / XSD DTD XSD <Schema xmlns="urn:schemas-microsoft-com:xml-data" xmlns:dt="urn:schemas-microsoft-com:datatypes"> Tài liệu XML Tập tin chứa các từ của câu hỏi sau khi loại bỏ các từ trong danh sách StopList Tập tin này được lưu trong thư mục “CauHoi”, tên tập tin là “CauHoiLoaiBoStopList.xml ” Cấu trúc DTD / XSD DTD XSD <Schema xmlns="urn:schemas-microsoft-com:xml-data" xmlns:dt="urn:schemas-microsoft-com:datatypes"> Tài liệu XML Tập tin chứa các từ trong câu hỏi và các tài liệu liên quan Tập tin này chứa các từ trong câu hỏi và các tham chiếu đến các tài liệu chứa các từ này, kèm theo tần số, trọng số của mỗi từ trong tài liệu tương ứng, nó được lưu trong thư mục “CauHoi” và tên tập tin là “CauHoiVaTaiLieu.xml”. Cấu trúc DTD / XSD DTD XSD <Schema xmlns="urn:schemas-microsoft-com:xml-data" xmlns:dt="urn:schemas-microsoft-com:datatypes"> Tài liệu XML Tập tin chứa độ tương quan giữa câu hỏi và các tài liệu Tập tin này chứa tất cả các tài liệu liên quan đến câu hỏi, mỗi tài liệu sẽ có độ tương quan tương ứng và số từ trong câu hỏi mà tài liệu đó chứa. Cấu trúc DTD / XSD DTD XSD <Schema xmlns="urn:schemas-microsoft-com:xml-data" xmlns:dt="urn:schemas-microsoft-com:datatypes"> Tài liệu XML Chi tiết các lớp đối tượng Các lớp trong quá trình tách từ Sơ đồ các lớp Hình 61 Sơ đồ lớp tách từ Lớp tách từ ghép Hình 62 Lớp tách từ ghép Lớp tách từ ghép sẽ có nhiệm vụ tách một văn bản thành các từ riêng biệt. Đầu vào là một chuỗi văn bản và đầu ra là một chuỗi chứa các từ, mỗi từ sẽ cách nhau bởi dấu xuống dòng ( ‘\r\n’ ). Ví dụ : chuỗi đầu vào = “Thanh niên VN: động lực cho những ý tưởng mới, tầm nhìn mới.” chuỗi đầu ra = “Thanh niên\r\nVN\r\nđộng lực\r\ncho\r\nnhững\r\ný tưởng\r\n mới\r\ntầm nhìn\r\nmới\r\n”. Ý nghĩa của các biến thành phần: ch : mảng các ký tự đặc biệt (dấu chấm, dấu phẩy, chấm than, chấm hỏi, hai chấm,…) để tách văn bản thành các cụm từ. hVietnamese : bảng băm để lưu tất cả các từ trong từ điển tiếng Việt. Các hàm chính : - Hàm TachThanhCumTu( ) : tách chuỗi văn bản thành các cụm từ dựa vào các kí tự đặc biệt như : dấu chấm, phẩy, chấm hỏi, chấm than… * Thuật toán : void TachThanhCumTu (chuỗi văn bản) { while(gặp tự đặc biệt đầu tiên trong chuỗi văn bản) { // Cắt phần đầu thành một cụm từ. // Gán chuỗi văn bản thành phần sau. } } Ví dụ : chuỗi đầu vào = “Thanh niên VN: động lực cho những ý tưởng mới, tầm nhìn mới.” trả về ta sẽ có 3 chuỗi cụm từ : chuỗi 1 = “Thanh niên VN” chuỗi 2 = “động lực cho những ý tưởng mới” chuỗi 3 = “tầm nhìn mới” - Hàm TachMangTieng( ) : tách một cụm từ thành từng tiếng dựa vào khỏang trắng. * Thuật toán : void TachMangTieng(cụm từ) { while(gặp ký tự khoảng trắng đầu tiên trong cụm từ) { // Cắt phần đầu thành một tiếng. // Gán cụm từ thành phần sau. } } Ví dụ : chuỗi đầu vào = “động lực cho những ý tưởng mới” trả về là mảng chuỗi chứa các tiếng = {động”;”lực”;”cho” “những”;”ý”;”tưởng”;”mới”} - Hàm XacDinhTu( ) : gộp các tiếng lại thành từ, so sánh trong từ điển tiếng Việt và ta sẽ lưu lại các từ này vào mảng các từ. * Thuật toán : void XacDinhTu(mảng các tiếng) { B1 : gán từ = tiếng đầu tiên. B2 : so sánh từ có trong từ điển hay không. B3 : nếu từ có trong từ điển và có 2 tiếng trở lên thì ta sẽ lưu lại. B4 : Nếu trong mảng tiếng vẫn còn thì từ := từ + tiếng tiếp theo. Ngược lại kết thúc hàm. B5 : Quay lại B2 } Với các mảng tiếng của ví dụ trên sau khi gọi hàm này thì ta sẽ có mảng các từ như sau: mảng chuỗi các từ={”động lực”;”cho” “những”;”ý tưởng”; ”mới”} Lớp tách từ Hình 63 Lớp tách từ Lớp tách từ sẽ có nhiệm vụ tạo tập tin văn bản Xml từ tập tin văn bản gốc, sau đó sẽ trích các từ trong văn bản và cuối cùng lưu lại các từ trích được cùng với các tài liệu chứa từ đó thành tập tin Xml tách từ. Ý nghĩa của các biến thành phần: ttg : đối tượng thuộc lớp CTachTuGhep Các hàm chính : - Hàm TaoXML( ) : chuyển một tập tin văn bản có cấu trúc thành tập tin XML * Thuật toán : void TaoXML (tập tin văn bản) { Tạo tập tin Xml để lưu lại nội dung tập tin văn bản. // Dịch con trỏ tập tin while(chưa hết tập tin văn bản) { B1 : tìm từ khóa DOC lấy phần giá trị. B2 : tìm từ khóa TITLE lấy phần giá trị. B3 : tìm từ khóa AUTHOR lấy phần giá trị. B4 : tìm từ khóa DATE lấy phần giá trị. B5 : tìm từ khóa NEW lấy phần giá trị. B6 : tìm từ khóa CONTENT lấy phần giá trị. lưu lại phần giá trị vào tập tin Xml. }// ENDWHILE } - Hàm Tachtu( ) : Đọc phần nội dung của tập tin XML văn bản và dùng đối tượng thuộc lớp CTachTuGhep để trích thành các từ. * Thuật toán : string Tachtu (tập tin văn bản Xml) { Lấy phần nội dung (CONTENT) trong tập tin Xml Dùng đối tượng của lớp tách từ ghép để tách từ. Kết quả trả về sẽ là một mảng chứa các từ riêng biệt. } - Hàm KetQuaToXmlWord( ) : các từ sau khi trích sẽ được lưu thành tập tin XML mới gọi là “tập tin sau khi tách từ tài liệu” * Thuật toán : void KetQuaToXmlWord(chuỗi chứa các từ) { B1 : Tạo một tập tin Xml B2 : Tách ra từng từ trong chuỗi B3 : Kiểm tra từ đó có lưu trong tập tin Xml chưa ? Nếu chưa : lưu từ đó và lưu tài liệu tương ứng Nếu rồi : kiểm tra tài liệu đó đã được lưu trong từ đó chưa. Nếu chưa ta mới lưu tài liệu đó. B4 : Nếu chưa hết chuỗi quay lại bước 2. B5 : Lưu tập tin Xml lại. } Lớp giao diện tách từ Hình 64 Lớp giao diện tách từ * Giao diện tách từ : Hình 65 Màn hình tách từ - Người dùng có thể chọn đường dẫn tới các tập tin văn bản cần tách từ. - ListBox1 chứa các tập tin văn bản trong đường dẫn đã chọn. - ListBox2 chứa các tập tin văn bản được chọn để tách từ. - ListBox3 chứa các tập tin xml đã được tách từ. - ListBox4 chứa các DocID trong tập tin xml đã được tách từ. Vì một tập tin văn bản xml sẽ chứa nhiều tài liệu và mỗi tài liệu sẽ có 1 DocID. Người dùng có thể chọn DocID nào đó để xem kết quả tách từ và tần số của mỗi từ trong tài liệu đó. Sau khi chọn một DocID sẽ có giao diện như sau : Hình 66 Màn hình chi tiết tách từ - Hàm xử lý TachTu_Click( ) : hàm này sẽ tách từ tất cả các tập tin được chọn trong ListBox2. Các lớp trong quá trình lập chỉ mục Sơ đồ các lớp Hình 67 Sơ đồ lớp lập chỉ mục Lớp lập chỉ mục Hình 68 Lớp lập chỉ mục Đầu vào của lớp lập chỉ mục là các tập tin tài liệu đã được tách từ và đầu ra sẽ là tập tin chỉ mục tài liệu. Nó sẽ làm nhiệm vụ tính tần số, trọng số của từ trong tài liệu sau đó sẽ lưu các thông tin này lại thành tập tin Xml chỉ mục tài liệu. Ý nghĩa của các biến thành phần : sl : đối tượng thuộc lớp CstopList để kiểm tra từ có nằm trong danh sách StopList hay không. Các hàm chính : - Hàm TinhTanSo( ) : tính số lần xuất hiện của từ trong tài liệu. * Thuật toán : int TinhTanSo(string Tu, string MaTL) { - Từ mã tài liệu xác định được tên tập tin chứa nội dung của tài liệu. - Duyệt từ đầu đến cuối văn bản ta tìm từ khóa cần tìm, nếu tìm thấy thì tăng biến đếm lên một đơn vị. - Trả về biến đếm } - Hàm TinhTrongSo( ) : tính trọng số của từ trong tài liệu. * Thuật toán : double TinhTrongSo( int Tầnsố) { return TanSo* log 10 (tổng số tài liệu / số tài liệu chứa từ đó) } - Hàm ThemTaiLieuVaoInverted() : hàm này dùng để cập nhật thêm tập tin tài liệu vào tập tin Inverted. * Thuật toán : void ThemTaiLieuVaoInverted( ) { B1 : Duyệt qua từng từ của tập tin tài liệu. B2 : Nếu từ đó có nằm trong StopList thì quay lại B1. B3 : Tính tần số của từ trong tài liệu. B3 : Kiểm tra từ đó có trong tập tin Inverted chưa ? - Nếu chưa ta thêm từ mới và thêm mã tài liệu, tần số, trọng số cho bằng 0. - Nếu có rồi ta chỉ cần thêm mã tài liệu, tần số, trọng số ( 0 ) vào từ mà ta tìm thấy trong tập tin Inverted. B4 : Cập nhật lại trọng số tòan bộ tập tin Inverted. } - Hàm CapNhatTrongSo() : Sau khi thêm tài liệu mới vào trọng số sẽ không còn chính xác nữa nên ta phải cập nhật lại trọng số. * Thuật toán : void CapNhatTrongSo() { - Duyệt qua từng từ trong tập tin Inverted. - Tính số tài liệu chứa từ đó (số nút con của nó) - Tính tổng số tài liệu. - Cập nhật lại thuộc tính trọng số (gọi hàm TinhTrongSo) } Lớp giao diện tạo mới chỉ mục Hình 69 Lớp giao diện tạo mới chỉ mục Lớp này sẽ có các đối tượng hỗ trợ giao diện cho người sử dụng lập chỉ mục, tạo ra tập tin Inverted mới Ý nghĩa của các biến thành phần : lcm : đối tượng thuộc lớp lập chỉ mục. Màn hình giao diện tạo mới chỉ mục : Hình 610 Màn hình tạo mới chỉ mục txtDuongDan : chứa đường dẫn đến các tập tin đã được tách từ. btnDuongDan : chọn đường dẫn đến các tập tin đã được tách từ. ListBox1 : chứa các tập tin Xml trong đường dẫn của txtDuongDan ListBox2 : chứa các tập tin Xml được chọn lập chỉ mục. btnLeft, btnRight : chuyển các tập tin qua lại giữa 2 ListBox chkSelectAll : chọn tất cả các tập tin để lập chỉ mục. chkRemoveAll : Loại bỏ tất cả. btnThoat : trở lại Form chính. btnLapChiMuc : chương trình bắt đầu lập chỉ mục. - Sự kiện btnLapChiMuc_Click() : dùng đối tượng lcm (của lớp lập chỉ mục) để lập chỉ mục cho tất cả các tập tin trong ListBox2. Lớp giao diện cập nhật chỉ mục Hình 611 Lớp Màn hình cập nhật chỉ mục Lớp MH_CapNhatChiMuc sẽ làm nhiệm vụ cập nhật các tập tin Xml đã được tách từ vào tập tin đã lập chỉ mục Inverted. Ý nghĩa của các biến thành phần : lcm : đối tượng thuộc lớp lập chỉ mục. Màn hình giao diện cập nhật chỉ mục : Hình 612 Màn hình cập nhật chỉ mục txtDuongDan : chứa đường dẫn đến các tập tin đã được tách từ. btnDuongDan : chọn đường dẫn đến các tập tin đã được tách từ. ListBox1 : chứa các tập tin Xml trong đường dẫn của txtDuongDan ListBox2 : chứa các tập tin Xml được chọn lập chỉ mục. ListBox3 : chứa các tập tin đã được lập chỉ mục. btnLeft, btnRight : chuyển các tập tin qua lại giữa ListBox1 và ListBox2 chkSelectAll : chọn tất cả các tập tin để lập chỉ mục. chkRemoveAll : loại bỏ tất cả. btnThoat : trở lại Form chính. btnCapNhat : chương trình bắt đầu cập nhật chỉ mục. - Sự kiện btnCapNhat_Click( ) : dùng đối tượng lcm (của lớp lập chỉ mục) để cập nhật chỉ mục cho tất cả các tập tin trong ListBox2, các tập tin nếu đã được lập chỉ mục rồi thì chương trình tự động bỏ qua. Các lớp trong quá trình tìm kiếm Sơ đồ các lớp Hình 613 Sơ đồ lớp tìm kiếm Lớp tìm kiếm Hình 614 Lớp xử lý tìm kiếm Lớp CTimKiem sẽ có nhiệm vụ tách từ câu hỏi, loại bỏ các từ trong danh sách StopList, sau đó tìm các từ khóa của câu hỏi trong tập tin Inverted để xác định các tài liệu liên quan đến câu hỏi, cuối cùng là tính độ tương quan giữa các tài liệu với câu hỏi, sắp xếp độ tương quan giảm dần và hiển thị cho người sử dụng. Ý nghĩa của các biến thành phần: ttg : đây là đối tượng của lớp tách từ ghép dùng để tách từ câu hỏi. sl : đây là đối tượng của lớp CstopList dùng để kiểm tra các từ trong câu hỏi có nằm trong danh sách StopList không. Các hàm chính : - Hàm TachTuCauHoi( ) : hàm này nhằm mục đích tách câu hỏi thành các từ riêng biệt. Ta dùng một đối tượng thuộc lớp CTachTuGhep để tách từ câu hỏi. Kết quả trả về là một chuỗi chứa các từ đã được tách ta sẽ lưu vào một tập tin CauHoi.xml trong thư mục CauHoi. * Thuật toán : void TachTuCauHoi(câu hỏi) { CTachTuGhep ttg = new CTachTuGhep String str = ttg.TachTuGhep(câu hỏi) Lấy từng từ trong chuỗi str đưa vào tập tin CauHoi.xml } Ví dụ : tập tin CauHoi.xml - Hàm LoaiBoSLCauHoi( ) : hàm này nhằm mục đích loại bỏ các từ không quan trọng trong câu hỏi. * Thuật toán : void LoaiBoSLCauHoi() { Mở tập tin CauHoi.xml Duyệt qua các từ xem có nằm trong StopList hay không ? Nếu không đưa vào tập tin CauHoiLoaiBoSL.xml ( tập tin này cũng nằm trong thư mục CauHoi) } Ví dụ : tập tin CauHoiLoaiBoSL.xml - Hàm ThemDocVaWeight( ) : hàm này nhằm mục đích là tìm kiếm trong tập tin Inverted các tài liệu liên quan đến các từ khóa của câu hỏi. * Thuật toán : void ThemDocVaWeight() { Mở tập tin CauHoiLoaiBoST.xml và duyệt qua từng từ. Tạo tập tin CauHoiVaTaiLieu.xml Đối với từng từ ta dùng công cụ XPath để xác định vị trí từ trong tập tin Inverted Đưa từ khóa và các tài liệu liên quan ( mã tài liệu, tần số, trọng số) vào tập tin CauHoiVaTaiLieu.xml } Ví dụ : tập tin CauHoiVaTaiLieu.xml sau khi gọi hàm ThemDocVaWeight - Hàm BoSungCacDocThieu( ) : hàm này nhằm mục đích bổ sung các tài liệu có trong từ khóa này mà không có trong từ khóa khác ( phần tần số và trọng số ta sẽ để giá trị là 0 ). Ví dụ : tập tin CauHoiVaTaiLieu.xml sau khi gọi hàm BoSungCacDocThieu - Hàm TaoFileDoTuongQuan( ) : hàm này nhằm mục đích tạo ra tập tin TuongQuan.xml chứa câu hỏi và các tài liệu liên quan đến câu hỏi kèm với độ tương quan dựa vào tập tin CauHoiVaTaiLieu.xml Theo lý thuyết thì độ tương quan giữa tài liệu Di và câu hỏi Q sẽ được tính theo công thức : SC(Q,Di) = Với : n : Số từ phân biệt trong tập tài liệu. dij : trọng số của từ j trong tài liệu di. (ta đã tính được trước đó) wqj : trọng số của từ j trong câu truy vấn Q. Sẽ có 2 giá trị như sau : wqj = 1 : Nếu từ j có trong câu truy vấn Q. wqj = 0 : Nếu từ j không có trong câu truy vấn Q. Thực chất là ta chỉ cần cộng các độ tương quan từng từ khóa của câu hỏi là ta sẽ có độ tương quan của câu hỏi với tài liệu. Ví dụ : tập tin TuongQuan.xml sau khi gọi hàm TaoFileDoTuongQuan - Hàm TinhDoTuongQuan( ) : hàm này nhằm tính độ tương quan giữa câu hỏi và các tài liệu có liên quan đến nó. Trên thực tế là ta gọi 3 hàm vừa nêu trên. * Thuật toán : void TinhDoTuongQuan() { ThemDocVaWeight(); BoSungCacDocThieu(); TaoFileDoTuongQuan(); } Lớp giao diện tìm kiếm Hình 615 Lớp giao diện tìm kiếm 8.3.1. Ý nghĩa của các biến thành phần : Term : mảng chuỗi chứa các từ khóa của câu hỏi. DocID : mảng chuỗi chứa DocID liên quan đến câu hỏi. Sim : mảng số thực chứa các độ tương quan của câu hỏi với các tài liệu (DocID tương ứng). Words : mảng số nguyên chứa số từ của câu hỏi có trong tài liệu (DocID tương ứng). n : tổng số tài liệu liên quan đến câu hỏi. tk : đối tượng của lớp xử lý tìm kiếm. * Giao diện tìm kiếm : Hình 616 Màn hình tìm kiếm - Sau khi tìm kiếm xong người sử dụng có thể xem từ khóa của câu hỏi. Ví dụ với câu hỏi : an toàn giao thông tại Tp. HCM bạn sẽ có được từ khóa như sau : Hình 617 Xem từ khóa câu hỏi - Xem từ khóa của tài liệu : nghĩa là khi người sử dụng chọn một tài liệu nào đó và chọn chức năng xem từ khóa tài liệu thì họ sẽ thấy từ khóa đó xuất hiện với tần số bao nhiêu và trọng số tương ứng của nó. Hình 618 Xem từ khóa tài liệu 8.3.2. Các hàm chính của lớp : - Hàm TimKiem_Click( ) : hàm này sẽ dùng đối tượng của lớp xử lý tìm kiếm để tách từ câu hỏi rồi tính độ tương quan của các tài liệu với câu hỏi * Thuật toán : void TimKiem_Click() { CtimKiem tk = new CtimKiem; tk.TachTuCauHoi(câu hỏi) tk.LoaiBoSLCauHoi(câu hỏi); tk.TinhDoTuongQuan(); // Sau khi gọi 3 hàm này ta sẽ tạo ra được tập tin TuongQuan.xml Đọc tập tin TuongQuan.xml ta đưa vào mảng các DocID, Sim, Words SapXepUuTien(); HienThiTaiLieu(); } - Hàm sắp xếp ưu tiên : dùng giải thuật InterchangeSort để sắp xếp tài liệu nào liên quan đến câu hỏi nhiều nhất. * Thuật toán : void SapXepUuTien () { // Ưu tiên theo Words (số từ của câu hỏi trong tài liệu) // Ưu tiên theo Sim (độ tương quan của tài liệu với câu hỏi) } - Hàm hiển thị tài liệu : ta sẽ hiển thị tài liệu lên Form cho người dùng xem. Một số màn hình giao diện khác Màn hình chính của chương trình Hình 619 Màn hình chính Chương trình sẽ có 6 chức năng : Tách từ : tách từ các tài liệu. Tạo mới chỉ mục : tạo tập tin Inverted. Cập nhật chỉ mục : cập nhật thêm tài liệu vào tập tin Inverted. Tìm kiếm : gõ câu hỏi và nhận các tài liệu trả về. Thoát : thóat hệ thống chương trình. Màn hình tìm kiếm nhiều câu hỏi Hình 620 Màn hình tìm kiếm nhiều câu hỏi Các câu hỏi sẽ được lưu trong một tập tin Xml và theo cấu trúc. Ví dụ tập tin CauHoi.xml sau :   kinh tế tri thức vụ án tham nhũng lớn di tích lịch sử công nghệ thông tin đất nước và con người Việt Nam Màn hình tìm kiếm chính ( giao diện Web) Hình 621 Giao diện tìm kiếm trên Web Màn hình trả về các tài liệu tìm được ( giao diện Web) Hình 622 Giao diện các tài liệu trả về sau khi tìm kiếm Màn hình chi tiết của một tài liệu ( giao diện Web) ` Hình 623 Giao diện chi tiết nội dung của tài liệu TỔNG KẾT Chương trình thử nghiệm Hệ thống tìm kiếm thông tin tiếng Việt (Search4VN) được cài đặt trên máy có cấu hình : Pentium IV, CPU 2.0 Ghz, bộ nhớ Ram 256 MB, đĩa cứng 40 GB, số tài liệu được lập chỉ mục là 13.000 tài liệu tổng dung lượng khoảng 35 MB. Lập chỉ mục cho toàn bộ dữ liệu trên tạo thành tập tin Inverted.xml có dung lượng là 40 MB. Chương trình hỗ trợ 2 dạng giao diện : giao diện Web chỉ cho người sử dụng tìm kiếm, và giao diện Window Application cho Admin sử dụng, cả hai giao diện trên đều được phát triển trên môi trường Visual studio .NET. Đánh giá kết quả đạt được Nhìn chung, luận văn đã hoàn thành những yêu cầu đề ra: Nghiên cứu được cách thức hoạt động của một hệ thống tìm kiếm thông tin. Tìm hiểu được các mô hình xây dựng một hệ tìm kiếm thông tin. Tìm hiểu các phương pháp tách từ. Tìm hiểu phương pháp lập chỉ mục cho tài liệu. Áp dụng xây dựng hệ thống tìm kiếm thông tin tiếng Việt dựa trên các chỉ mục có cấu trúc. Hệ thống có một số ưu điểm như sau: Tách từ tiếng Việt khá chính xác. Tham số hóa các yếu tố liên quan đến lập chỉ mục và tra cứu. Tìm kiếm khá nhanh. Các tài liệu trả vế được sắp xếp khá chính xác. Tóm tắt được nội dung tài liệu trả về Giao diện thân thiện, dễ sử dụng Tuy nhiên, hệ thống còn một số khuyết điểm cần cải thiện: Chưa tự động lấy được các tài liệu mới giống như một hệ thống Search Engine. Chưa hỗ trợ bộ gõ Chưa hỗ trợ các chức năng tìm kiếm nâng cao Hướng phát triển Tìm hiểu kết hợp các công cụ tách từ để cho kết quả tách từ tốt nhất Hỗ trợ các bộ gõ tiếng Việt Hỗ trợ các chức năng tìm kiếm nâng cao. Tăng tốc độ cập nhật chỉ mục, tìm kiếm. Thêm chức năng tự động lấy các tài liệu và cập nhật vào tập tin chỉ mục để phát triển thành một trang Web tìm kiếm cho tiếng Việt. TÀI LIỆU THAM KHẢO Sách [1.1] Gerard Salton/ Michael J.McGill; Introduction to Modern Information Retrieval [1.2] David A.Grossman/Ophir Frieder; Information Retrival: Algorithms and Heuristics [1.3] C.J van RIJSBERGEN Department of Computing Science University of Glassgow; Information Retrival. [1.4] Đinh Điền; Xử lý ngôn ngữ tự nhiên Luận văn [2.1] Thành Giang. Luận án thạc sĩ khoa học. Tìm hiểu về cách xác định từ loại và xây dựng công cụ xác định từ loại. Giáo viên hướng dẫn : T.S Hồ Bảo Quốc. [2.2] Nguyễn Hải Quyền, Lương Thị Hoàng Thuý. Luận văn cử nhân tin học. Tạo từ khoá cho văn bản tiếng Việt. GVHD: Chu Tất Bích San. [2.3] Lê Thúy Ngọc, Đỗ Mỹ Nhung. Luận văn cử nhân tin học. Tìm hiểu về Search Engine và xây dựng ứng dụng cho Search Engine tiếng Việt. Giáo viên hướng dẫn : Th.S Nguyễn Thị Diễm Tiên. Website [3.1] [3.2] [3.3] [3.4] [3.5]