Tóm tắt văn bản tiếng Việt sử dụng cấu trúc văn bản và từ điển đồng nghĩa

JOURNAL OF SCIENCE OF HNUE Natural Sci., 2013, Vol. 58, No. 3, pp. 154-163 This paper is available online at TÓM TẮT VĂN BẢN TIẾNG VIỆT SỬ DỤNG CẤU TRÚC VĂN BẢN VÀ TỪ ĐIỂN ĐỒNG NGHĨA Lê Quý Tài Khoa Hệ thống thông tin quản lý, Học viện Ngân hàng Tóm tắt. Tóm tắt văn bản là một lĩnh vực quan trọng của xử lí ngôn ngữ tự nhiên. Đối với tiếng Việt, do tính phức tạp của ngôn ngữ nên hiện nay các phương pháp tóm tắt còn gặp nhiều khó khăn. Trong bài báo này, chúng tôi trình bày về việc sử dụng cấu trúc văn bản xây dựng đồ thị liên kết giữa các câu trong văn bản kết hợp với từ điển đồng nghĩa để tóm tắt văn bản tiếng Việt. Kết quả thử nghiệm cho thấy, phương pháp duyệt đồ thị liên kết theo chiều sâu cho kết quả tốt nhất với độ đo F đạt trung bình 52,41%, tốc độ tóm tắt trung bình đạt 8 phút/50 văn bản (với trung bình 40 câu/văn bản). Từ khóa: Tóm tắt văn bản, đồ thị liên kết, từ đồng nghĩa, xử lí ngôn ngữ. 1. Mở đầu Tóm tắt văn bản là một lĩnh vực của xử lí ngôn ngữ tự nhiên và đã được nghiên cứu từ những năm 50 của thế kỉ 20. Đối với ngôn ngữ tiếng Anh đã có nhiều nghiên cứu về tóm tắt văn bản và thu được những kết quả rất khả quan [3]. Với tiếng Việt, do sự phức tạp về ngôn ngữ nên kết quả của các công trình nghiên cứu về tóm tắt băn bản tiếng Việt còn có nhiều hạn chế. Hiện nay đã có những công trình nghiên cứu về tóm tắt văn bản tiếng Việt sử dụng các phương pháp thống kê, một số dựa trên ngữ nghĩa. Chẳng hạn, Đỗ Phúc, Hoàng Kiếm [6] đã sử dụng cây hậu tố để phát hiện các dãy từ phổ biến trong các câu của văn bản, rồi dùng kĩ thuật gom cụm để gom các câu trong văn bản. Nguyễn Trọng Phúc, Lê Thanh Hương [7] lại sử dụng cấu trúc diễn ngôn để tóm tắt văn bản; một số sử dụng phương pháp xây dựng đồ thị quan hệ thực thể để tăng cường tính ngữ nghĩa cho độ tương đồng câu hoặc sử dụng phương pháp phân đoạn văn bản dựa trên chuỗi từ vựng để tóm tắt văn bản. Phương pháp sử dụng cấu trúc văn bản đã được sử dụng với tiếng Anh [4] và đã thu được kết quả khá tốt. Trong bài báo này chúng tôi trình bày về việc cải tiến phương pháp này kết hợp với từ điển đồng nghĩa để thực hiện tóm tắt văn bản tiếng Việt. Ngày nhận bài: 6/9/2012. Ngày nhận đăng: 5/6/2013. Tác giả liên lạc: Lê Quý Tài, địa chỉ e-mail: quytai3985@gmail.com 154 Tóm tắt văn bản tiếng Việt sử dụng cấu trúc văn bản và từ điển đồng nghĩa 2. Nội dung nghiên cứu 2.1. Mô hình tóm tắt văn bản tiếng Việt Hình 1. Mô hình tóm tắt văn bản tiếng Việt Để đánh giá hiệu quả của việc sử dụng bộ tách từ và từ điển đồng nghĩa, chúng tôi đã xây dựng 3 phiên bản cho ứng dụng này. - Phiên bản 1: Hoàn toàn không sử dụng bộ tách từ, các từ được tách ra căn cứ vào dấu trắng phân cách. - Phiên bản 2: Sử dụng bộ tách từ tiếng Việt để tách ra các từ. - Phiên bản 3: Sử dụng bộ tách từ tiếng Việt, kết hợp với từ điển từ dừng và từ điển đồng nghĩa. 2.2. Tiền xử lí Các tập tin được dùng để thử nghiệm được lấy từ trang báo điện tử vnexpress.net và một số bài báo khoa học. Các tập tin được loại bỏ các thẻ HTML, loại bỏ các câu không liên quan đến nội dung và chỉ giữ lại nội dung chính, đồng thời cũng được chuẩn hoá về mặt chính tả. Nội dung của mỗi văn bản được lưu trữ trong một file text và được mã hoá bằng mã Unicode UTF-8. Công cụ WordSegForTV [2] được sử dụng để phân tách các từ và các câu trong toàn bộ các băn bản, kết quả của bước này được dùng làm đầu vào cho pha tiếp theo. 155 Lê Quý Tài 2.3. Xử lí từ Pha này thực hiện tách ra các từ, các câu từ các văn bản có được từ pha trước. Trong bước này, chúng tôi xây dựng tập T chứa toàn bộ các từ có trong văn bản. Chúng tôi sử dụng từ điển từ dừng do website xulyngonngu.com cung cấp để loại bỏ các từ dừng. Đồng thời, từ điển đồng nghĩa cũng được sử dụng để thêm vào tập T các từ đồng nghĩa. Thuật toán dưới đây thể hiện việc chọn ra các từ, các câu, các từ đồng nghĩa và loại bỏ các từ dừng. Từ điển đồng nghĩa được sử dụng là của tài liệu [1]. Thuật toán xử lí từ Input: Tập tin văn bản đã tách từ. Output: Tập các từ T, Tập các câu Sent. 1. Mở tập tin văn bản ST=Nội dung file 2. {Tách ra các câu} n=0; {đếm số lượng câu} k=1; while k<len(st) begin if ST(k)=Dấu kết thúc câu then begin n=n+1; sent(i)=Câu kết thúc tại vị trí k; end; Tăng k; end; 3. {Tách ra các từ} k=1; while k<len(st) begin if ST(k)= “|” then begin word=Chọn ra từ kết thúc tại k; Chuẩn hoá word; {Loại bỏ dấu cách, các kí hiệu vô ích, chuyển về chữ thường} if word có trong từ điển từ dừng then word=”” else if word có trong từ điển đồng nghĩa then Đưa word và các từ đồng nghĩa vào Tập từ Term; Else Đưa word vào Tập từ T; Tăng k; end; 4. return T, Sent; 156 Tóm tắt văn bản tiếng Việt sử dụng cấu trúc văn bản và từ điển đồng nghĩa 2.4. Xây dựng đồ thị liên kết Trong lĩnh vực xử lí ngôn ngữ và tìm kiếm thông tin, mỗi văn bản thường được biểu diễn dưới dạng vector, chẳng hạn Di = (di1 , di2, ..., din) trong đó dikbiểu diễn trọng số của từ trong tài liệuDi. Độ tương tự giữa hai văn bảnDi và Dj là sim(Di, Dj) được tính theo các công thức tính độ tương tự. Nếu độ tương tự này đạt đến một ngưỡng đủ lớn thì ta nói rằng chúng có “liên quan về mặt ngữ nghĩa” và ta có thể thiết lập một liên kết giữa hai văn bản này [5]. Áp dụng phương pháp này vào việc tóm tắt văn bản tự động, chúng tôi xây dựng đồ thị liên kết giữa các câu trong băn bản bằng cách: mỗi câu trong văn bản là một nút trong đồ thị; liên kết giữa hai câu bất kì trong đồ thị được thiết lập nếu giữa các câu có độ tương tự đạt đến một ngưỡng nào đó. Việc xác định ngưỡng để quyết định hai câu trong văn bản có quan hệ với nhau có một ý nghĩa quan trọng. Chúng tôi sẽ tiến hành thử nghiệm với nhiều giá trị ngưỡng khác nhau để chọn ra một ngưỡng thích hợp. Sau khi xây dựng được đồ thị liên kết, ta có được hình vẽ trực quan cấu trúc của văn bản. Từ cấu trúc này, ta có thể xây dựng văn bản tóm tắt bằng cách chọn ra các câu phù hợp [4]. Hình 2. Đồ thị liên kết các câu trong văn bản (gồm 11 câu, 30 liên kết trên 0,2) Hình bên đây là đồ thị liên kết được xây dựng cho văn bản Text(16).txt trong tập văn bản thử nghiệm. Trong bước xây dựng đồ thị liên kết, mỗi câu sẽ được coi như một vectơ trong không gian Euclide nhiều chiều. Ở đây, chúng tôi sử dụng cách biểu diễn tf-idf [8] để biểu diễn các vectơ. Giả sử văn bản cần tóm tắt có n câu được đánh số là sent1, sent2, ..., sentn và m từ t1, t2, ..., tm, gọi nij là số lần xuất hiện của từ trong câu. Mỗi thành phần thứ i của vector văn bản sentj được tính như sau: sentij = TF (ti, sentj) × IDF (ti) (1) trong đó: - i = 1, m, j = 1, n - Giá trị TF (ti, sentj)được tính bằng ln số lần xuất hiện số từ: (2) TF (ti, sentj) = { 0 ifnij = 0 1 + ln(1 + lnnij) ifnij > 0 (2) Gọi S là tập hợp các câu và Sti là tập các câu có chứa từ ti. S = n∑ j=1 sentj (3a) 157 Lê Quý Tài Sti = {sentj |nij > 0} (3b) - Giá trị IDF (ti) được tính bằng hàm logarit: IDF (ti) = log 1 + |S| |Sti | (4) Sau khi vector hoá các câu trong văn bản, ta tính độ tương tự giữa từng cặp câu với nhau theo công thức tính độ tương đồng Cosine đã nêu ở trên. Khi đó, độ tương tự giữa 2 câu senti và sentj bất kì được tính như sau: sim(senti, sentj) = m∑ k,l=1 sentki sent l j√ m∑ k=1 sentki √ m∑ l sentlj (5) Tiếp đó, ta xây dựng đồ thị liên kết giữa các câu trong văn bản. Đồ thị được biểu diễn bằng một ma trận D như sau: D(senti, sentj) = { 0ifsim(senti, sentj) < threshold sim(senti, sentj)ifsim(senti, sentj) >= threshold (6) Trong đó: threshold là một ngưỡng được cho trước và được tính toán bằng thực nghiệm đối với các loại văn bản. Trong thử nghiệm này của chúng tôi, ngưỡng threshold = 0, 2. 2.5. Sinh văn bản tóm tắt Giả sử văn bản cần tóm tắt có độ dài là p% độ dài của văn bản gốc. Chúng tôi xây dựng thủ tục duyệt đồ thị để chọn ra những câu quan trọng theo 3 phương pháp: * Phương pháp 1. Dựa vào bậc của các nút trên đồ thị Bước 1: Tính bậc của mỗi nút trong đồ thị (bậc được tính bằng số liên kết của nút với các nút khác). Bước 2: Sắp xếp các nút theo thứ tự bậc giảm dần. Bước 3: Chọn ra các nút có bậc cao nhất, ngừng chọn khi số câu đủ yêu cầu. * Phương pháp 2. Duyệt theo chiều sâu Bước 1: Chọn nút bắt đầu là nút đầu tiên (theo thứ tự xuất hiện trong văn bản). Bước 2: Duyệt đồ thị theo chiều sâu bắt đầu từ nút xuất phát, chọn các nút theo số bậc cao nhất. Quá trình duyệt dừng lại khi nút cuối cùng được chọn không liên kết với nút nào về sau. Bước 3: Nếu vẫn chưa đủ số câu cần thiết, thực hiện phương pháp 1 đối với các câu còn lại chưa được chọn. * Phương pháp 3. Phân đoạn văn bản Bước 1: Tách văn bản thành những phân đoạn, căn cứ vào độ dài của văn bản và tỉ lệ nén p. 158 Tóm tắt văn bản tiếng Việt sử dụng cấu trúc văn bản và từ điển đồng nghĩa Bước 2: Áp dụng phương pháp 1 đối với từng phân đoạn, ở mỗi phân đoạn chọn ít nhất một câu. Các câu còn lại được chọn là các nút có bậc cao trong các phân đoạn. Quá trình chọn sẽ dừng lại khi đạt đủ số câu cần thiết. 2.6. Kết quả thực nghiệm * Dữ liệu thử nghiệm - Tập văn bản thử nghiệm: Gồm 50 văn bản có nội dung với nhiều lĩnh vực khác nhau, phần lớn được lấy từ website Vnexpress và một số bài báo khoa học khác. Trong đó, có 19 bài viết thuộc lĩnh vực Giáo dục, 16 bài về Xã hội, 6 bài viết về Khoa học Thường thức, 4 bài Tâm sự và 4 bài báo khoa học. Mỗi văn bản được lưu trong một tập tin được đặt tên theo thứ tự từ Text(1).txt đến Text(50).txt. Văn bản có kích thước lớn nhất là 27 KB với 179 câu, văn bản có kích thước nhỏ nhất là 1,45 KB với 9 câu. - Từ điển: + Từ điển từ dừng [9]: gồm 807 từ do website xulyngonngu.com cung cấp. + Từ điển đồng nghĩa [1]: gồm 603 mục từ với tổng cộng 2867 từ đồng nghĩa. * Phương pháp đánh giá Chúng tôi sử dụng phương pháp so sánh văn bản của hệ thống tóm tắt với văn bản do con người thực hiện tóm tắt để đánh giá hệ thống tóm tắt. Gọi hệ thống tóm tắt cần đánh giá là S, hệ thống tóm tắt do con người tóm tắt là GS, ta có bảng đánh giá mức độ liên quan như sau: Hệ thống GS Hệ thống SSố câu S chọn Số câu S không chọn Số câu GS chọn A B Số câu GS không chọn C D Khi đó, độ chính xác Precision (P) được tính như sau: P = A A+ C (7) Độ chính xác P cho biết tỉ lệ giữa các câu S chọn ra chính xác so với tổng số những câu có trong văn bản tóm tắt do S thực hiện. Độ bao phủ Recall(R) được tính như sau: R = A A+B (8) Độ bao phủ R cho biết tỉ lệ giữa các S chọn ra chính xác so với tổng số câu trong văn bản do GS thực hiện. Độ đo F : là tiêu chí đánh giá chung cho kết quả tóm tắt của hệ thống, độ đo này là hàm điều hoà của độ chính xác, độ hồi quy và được tính như sau: 159 Lê Quý Tài F = 2PR P +R (9) Chúng tôi thử nghiệm hệ thống tóm tắt với 3 mức độ nén: 10%, 20% và 30%. Chúng tôi đã xây dựng 3 phiên bản: - Phiên bản 1: Hoàn toàn không sử dụng bộ tách từ, các từ được tách ra căn cứ vào dấu trắng phân cách. - Phiên bản 2: Sử dụng bộ tách từ tiếng Việt để tách ra các từ. - Phiên bản 3: Sử dụng bộ tách từ tiếng Việt, kết hợp với từ điển từ dừng và từ điển đồng nghĩa. Đồng thời, để so sánh kết quả tóm tắt của hệ thống với các hệ thống khác, chúng tôi lựa chọn Microsoft Office Word 2003 làm hệ tóm tắt đối sánh (sử dụng chức năng AutoSummarize). Tập văn bản thử nghiệm trên được tóm tắt bởi con người, mỗi văn bản được tóm tắt thành 3 văn bản với mức độ nén lần lượt là 10%, 20% và 30%. Các văn bản được chuyển cho hai người tóm tắt để chọn ra các câu có ý nghĩa quan trọng. Việc lựa chọn các câu sẽ là chọn ra số thứ tự của câu đó trong văn bản gốc. * Kết quả thử nghiệm Chúng tôi đã tiến hành thử nghiệm các phiên bản với những ngưỡng khác nhau để chọn ra một ngưỡng phù hợp. Hình 3 thể hiện kết quả (tính theo giá trị hàm điều hoà) của từng phiên bản với các ngưỡng từ 0,05 đến 0,4. Hình 3. Kết quả thử nghiệm chọn ngưỡng Chúng tôi nhận thấy với ngưỡng 0,05; 0,1 và 0,2 thì chương trình tóm tắt cho kết quả khả quan nhất. Khi ngưỡng tăng dần thì giá trị hàm điều hoà lại giảm rất nhanh do khi độ tương tự giữa hai câu không đạt đến ngưỡng đó thì hai câu đó không thể được đưa vào đồ thị liên kết, từ đó hai câu này sẽ không được chọn vào văn bản tóm tắt (mà rất có thể hai câu này chứa nội dung chính và sẽ được chọn). Do đó, trong các thử nghiệm dưới 160 Tóm tắt văn bản tiếng Việt sử dụng cấu trúc văn bản và từ điển đồng nghĩa đây, chúng tôi chọn sử dụng ngưỡng 0,2 để đánh giá. Bảng 1. Bảng đánh giá kết quả tóm tắt của Microsoft Word Tỉ lệ nén Độ chính xác P Độ bao phủ R Hàm điều hoà F 10% 34 28 30,71 20% 36 30 32,73 30% 44 41 42,45 Trung bình 38 33 35,32 Đơn vị: % Bảng 2. Kết quả tổng hợp so sánh các phiên bản Phiên bản Phương pháp 1 Phương pháp 2 Phương pháp 3 P R F P R F P R F Phiên bản 1 45,67 42 43,76 44,67 43 43,82 39,67 37 38,29 Phiên bản 2 47 42 44,25 53,67 49,33 51,35 40,67 37,67 39,08 Phiên bản 3 46,33 41,67 43,88 54,67 50,33 52,41 40,67 37,67 39,11 Đơn vị: % Hình 4. Đồ thị so sánh giá trị hàm điều hoà giữa các phiên bản và phương pháp Kết quả cho thấy cả 3 phiên bản đã cho giá trị hàm điều hoà vượt trội hơn hẳn so với Microsoft Word (Word chỉ đạt trung bình 35,32%). Cụ thể: Trong phiên bản 1 giá trị hàm điều hoà đạt cao nhất chỉ là 43,82%. Đó là do trong phiên bản này chúng tôi không sử dụng bộ tách từ mà chỉ sử dung dấu cách làm căn cứ để phân tách từ. Trong phiên bản 2, giá trị hàm điều hoà đã tăng lên 51,35% do bộ tách từ đã được sử dụng, dẫn đến kết quả đánh giá độ tương đồng giữa các câu và đồ thị liên kết cũng thay đổi. Ở phiên bản 3, từ điển từ dừng và từ điển đồng nghĩa được sử dụng giúp 161 Lê Quý Tài cải thiện giá trị hàm điều hoà đạt tới 52,41%. Như vậy, việc sử dụng bộ tách từ đã cho kết quả thấy rõ và việc sử dụng thêm từ điển đồng nghĩa cũng góp phần cải thiện độ chính xác của phương pháp tóm tắt. Đồng thời, qua kết quả này chúng tôi cũng nhận thấy, trong phiên bản 3 với phương pháp 2 (phương pháp duyệt đồ thị theo chiều sâu) cho kết quả tốt nhất với giá trị hàm điều hoà đạt 52,41%. Tuy nhiên, kết quả tóm tắt còn phụ thuộc vào dạng của văn bản tóm tắt, phương pháp này có thể là tốt với dạng văn bản này nhưng cũng có thể không tốt với dạng văn bản khác. Trong thử nghiệm này, chúng tôi thấy rằng: các văn bản thuộc nhóm các bài viết về Giáo dục có giá trị hàm điều hoà cao nhất (trung bình đạt xấp xỉ 65%, cá biệt có bài đạt trên 75%); các văn bản thuộc nhóm các bài viết về xã hội đạt xấp xỉ 60%; tuy nhiên các bài viết thuộc nhóm các Bài báo khoa học và Tâm sự lại có kết quả tương đối thấp (chỉ đạt trung bình 40%). Bên cạnh đó, việc đánh giá kết quả tóm tắt cũng phụ thuộc vào phương pháp đánh giá. Ở đây, chúng tôi sử dụng phương pháp so sánh với văn bản do con người thực hiện tóm tắt nên phần nào cũng phụ thuộc vào chất lượng bản tóm tắt do người đó thực hiện. Chúng tôi đã thực hiện so sánh mức độ giống nhau giữa các văn bản tóm tắt bởi hai người và nhận thấy các văn bản tóm tắt chỉ giống nhau trung bình 80%. Do vậy, cần có những nghiên cứu tiếp theo để cải tiến và đưa ra được phương pháp cho kết quả tốt hơn với nhiều dạng văn bản. 3. Kết luận Tóm tắt văn bản là một lĩnh vực quan trọng của xử lí ngôn ngữ tự nhiên và có rất nhiều ứng dụng thực tế như tóm tắt tin tức, các văn bản khoa học, các cuốn sách một cách tự động. Bài viết này đã trình bày về việc sử dụng từ điển đồng nghĩa và cấu trúc văn bản để tóm tắt văn bản tiếng Việt. Do hạn chế về mặt thời gian, kĩ thuật và đặc biệt chưa có dữ liệu về tiếng Việt đầy đủ: như từ điển từ đồng nghĩa, trái nghĩa, từ dừng. . . nên cần có nhiều thời gian và công sức để xây dựng và cải tiến phương pháp tóm tắt văn bản tiếng Việt để có được hệ thống tóm tắt văn bản hiệu quả. Phương pháp chúng tôi sử dụng thực nghiệm trong đề tài này mới chỉ thuộc dạng trích chọn các câu trong văn bản, cần: thử nghiệm với nhiều dạng văn bản khác nhau: bài báo khoa học, báo điện tử. . . để có thể đưa ra được các tham số cho phù hợp kết hợp với phương pháp tìm các cụm từ dấu hiệu để xác định những câu quan trọng hoặc sử dụng phương pháp phân tích cú pháp, biến đổi từ và một số kĩ thuật xử lí khác để tăng tính mạch lạc cho văn bản tóm tắt. TÀI LIỆU THAM KHẢO [1] Trần Trọng Dương, Nguyễn Quốc Khánh, Bùi Hồng Quế, Nguyễn Đình Phúc và Nguyễn Minh Châu, 2008. Từ điển đồng nghĩa và trái nghĩa tiếng Việt dành cho học sinh. Nxb Từ điển Bách khoa, Hà Nội, tr. 9-323. [2] Dang Duc Pham, Giang Chan Binh and Son Bao Pham, 2009. International Conference on Knowledge and Systems Engineering, pp.154-161. 162 Tóm tắt văn bản tiếng Việt sử dụng cấu trúc văn bản và từ điển đồng nghĩa [3] Jezek, K. and Steinberger, J., 2008. Automatic Text Summarization (The state of the art 2007 and new challenges). Znalosti, FIIT STU Bratislava, Slovakia, pp.1-12. [4] Gerard Salton, Am1t Singha, Mandar Mitra And Chris Buckley, 1997. Automatic Text Structuring and Summarization. Advances in Automatic Text Summarization. The MIT Press Cambridge, Massachusetts London, England, pp. 341-355. [5] Gerard Salton, Chris Buckley and Jame Allan, 1992. Automatic structuring of text files. Electronic Publishing. Vol. 5(1), pp. 1-17. [6] Đỗ Phúc, Hoàng Kiếm, 2006. Rút ý chính từ văn bản tiếng Việt hỗ trợ tạo tóm tắt nội dung. Tạp chí Công nghệ thông tin và truyền thông, Hà Nội. [7] Nguyễn Trọng Phúc, Lê Thanh Hương, 2008. Tóm tắt văn bản tiếng Việt sử dụng cấu trúc diễn ngôn. The ICT.rda conference, Hanoi, Vietnam [8] Zdravko Markov and Daniel T.Larose, 2007. Data mining the web – Uncovering patterns in Web content, structure, and usage. John Wiley & Sons Inc. Publication, New Jersey, USA. [9] Website xulyngonngu.com. ABSTRACT Using document structure and a synonym dictionary for vietnamese text summarization Text summarization is an important part of natural language processing. Currently, the methods used to summarize Vietnamese text are ineffective. In this paper, we present the use of document structure and a Vietnamese thesaurus dictionary to build a graphic link between sentences in order to summarize the text. Test results show that structural methods are used more than a Vietnamese thesaurus with the threshold value of 0.2 for best results (the average F measure is 52.41%) when using the approved method of depth-first search (DFS) based on the node degree to pick out the sentence. Summarization took place at an average speed of 8 minutes/50 documents with an average of 40 sentences/documents. 163