Luận văn 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

an 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-mi