Tài liệu Nghiên cứu kĩ thuật đánh giá độ tương đồng văn bản ứng dụng trong so sánh văn bản tiếng việt

TRƯỜNG ĐẠI HỌC HÀNG HẢI VIỆT NAM KHOA CÔNG NGHỆ THÔNG TIN THUYẾT MINH ĐỀ TÀI NCKH CẤP TRƯỜNG ĐỀ TÀI NGHIÊN CỨU KĨ THUẬT ĐÁNH GIÁ ĐỘ TƯƠNG ĐỒNG VĂN BẢN ỨNG DỤNG TRONG SO SÁNH VĂN BẢN TIẾNG VIỆT Chủ nhiệm đề tài: Thành viên tham gia: Th.S NGUYỄN KIM ANH Th.S TRỊNH THỊ NGỌC HƯƠNG Hải Phòng, tháng 05/2016 MỤC LỤC MỤC LỤC ....................................................................................................................... 2 DANH SÁCH HÌNH ẢNH ............................................................................................. 4 DANH SÁCH BẢNG BIỂU ........................................................................................... 5 MỞ ĐẦU ......................................................................................................................... 6 CHƯƠNG I: TỔNG QUAN VỀ ĐỀ TÀI ....................................................................... 7 1.1. Lý do chọn đề tài ............................................................................................ 7 1.2. Mục đích nghiên cứu ...................................................................................... 7 1.3. Đối tượng nghiên cứu ..................................................................................... 7 1.4. Phương pháp nghiên cứu ................................................................................ 7 CHƯƠNG II: BÀI TOÁN SO SÁNH VĂN BẢN TIẾNG VIỆT ................................... 9 2.1. Bài toán so sánh văn bản ................................................................................ 9 2.2. Đặc điểm ngôn ngữ tiếng Việt ...................................................................... 10 2.2.1. Cấu tạo từ tiếng Việt .................................................................................10 2.2.2. Biến hình từ tiếng Việt ..............................................................................11 2.2.3. Từ đồng nghĩa ...........................................................................................11 2.2.4. Đặc điểm chính tả ......................................................................................12 2.2.5. Bảng mã tiếng Việt trên máy tính .............................................................12 2.3. Hướng tiếp cận cho bài toán so sánh văn bản tiếng Việt ............................. 13 2.3.1. Tiền xử lý văn bản tiếng Việt ....................................................................13 2.3.2. Phương pháp tính độ tương đồng giữa các văn bản ..................................14 2.3.3. Hướng tiếp cận cho bài toán so sánh văn bản tiếng Việt ..........................16 CHƯƠNG III: MÔ HÌNH BIỂU DIỄN VĂN BẢN TIẾNG VIỆT .............................. 18 3.1. Mô hình biểu diễn văn bản truyền thống ...................................................... 18 3.1.1. Mô hình logic ................................................................................................18 3.1.2. Mô hình vector ..............................................................................................19 3.2. Mô hình đồ thị biểu diễn văn bản ................................................................. 22 3.2.1. Mô hình đồ thị khái niệm..............................................................................22 3.2.2. Mô hình đồ thị hình sao ................................................................................23 3.2.3. Mô hình đồ thị vô hướng sử dụng tần số xuất hiện ......................................23 3.2.4. Mô hình đồ thị có hướng, cạnh không gán nhãn ..........................................24 3.3.5. Mô hình đồ thị có hướng, cạnh không gán nhãn, cạnh là khoảng cách n giữa hai từ trong văn bản ................................................................................................24 CHƯƠNG IV: PHƯƠNG PHÁP TÍNH ĐỘ TƯƠNG ĐỒNG VĂN BẢN .................. 26 4.1. Khái niệm độ tương đồng ............................................................................. 26 4.2. Độ tương đồng văn bản dựa trên tập từ chung ............................................. 26 4.2.1. Khoảng cách Jaro ......................................................................................26 4.2.2. Mô hình tương phản (Contrast model) ......................................................27 4.2.3. Hệ số Jaccard .............................................................................................27 4.3. Độ tương đồng văn bản dựa trên vector biểu diễn ....................................... 27 4.3.1. Độ tương đồng Cosine ..............................................................................27 4.3.2. Độ tương đồng dựa vào khoảng cách Euclide ..........................................28 4.3.3. Độ tương đồng dựa vào khoảng cách Manhattan .....................................28 4.4. Độ tương đồng văn bản trong tiếng Việt ...................................................... 29 4.4.1. Độ tương tự ngữ nghĩa từ - từ ...................................................................29 4.4.2. Độ tương tự ngữ nghĩa của văn bản ..........................................................30 4.4.3. Độ tương tự về thứ tự của từ trong văn bản ..............................................31 4.4.4. Kết hợp giữa các độ đo để đánh giá độ tương tự giữa hai văn bản ...........32 CHƯƠNG V: ỨNG DỤNG MÔ HÌNH ĐỒ THỊ ......................................................... 33 5.1. Mô hình hệ thống .......................................................................................... 33 5.1.1. Tiền xử lý ..................................................................................................33 5.1.2. Xử lý từ .....................................................................................................33 5.1.3. * Vector hóa văn bản.................................................................................35 5.1.4. *Tính độ tương tự văn bản ........................................................................36 5.2. Mô hình thực nghiệm.................................................................................... 38 5.2.1. Môi trường thực nghiệm ...........................................................................38 5.2.2. *Chương trình ứng dụng thử nghiệm ........................................................38 5.2.3. *Kết quả thử nghiệm .................................................................................38 KẾT LUẬN ................................................................................................................... 39 TÀI LIỆU THAM KHẢO ............................................................................................. 40 DANH SÁCH HÌNH ẢNH Hình 1: Mô hình vector biểu diễn văn bản ....................................................................19 Hình 2: Ví dụ mô hình đồ thị khái niệm ........................................................................22 Hình 3: Ví dụ mô hình đồ thị hình sao ..........................................................................23 Hình 4: Ví dụ mô hình đồ thị vô hướng sử dụng tần số xuất hiện ................................24 Hình 5: Ví dụ mô hình đồ thị đơn giản..........................................................................24 Hình 6: Ví dụ mô hình đồ thị khoảng cách n đơn giản .................................................25 Hình 7: Mô hình hệ thống so sánh văn bản tiếng Việt ..................................................33 Hình 8: Chương trình thử nghiệm so sánh độ tương tự văn bản ...................................38 DANH SÁCH BẢNG BIỂU Bảng 1: Tần suất xuất hiện độ dài từ tiếng Việt trên vdict.com ....................................11 Bảng 2: Biểu diễn văn bản trong mô hình Logic...........................................................18 Bảng 3: Vector biểu diễn văn bản .................................................................................20 MỞ ĐẦU Hiện nay, với sự phát triển bùng nổ của các ứng dụng trên Internet, dữ liệu văn bản đã tăng nhanh cả về số lượng và nội dung. Trong kho dữ liệu ấy, một lượng lớn là văn bản tiếng Việt. Tuy nhiên, các nghiên cứu về khai thác thông tin trên văn bản tiếng Việt lại chưa nhiều so với tiếng Anh, hầu hết sử dụng các phương pháp đã đề xuất cho tiếng Anh để áp dụng sang tiếng Việt. Do đặc điểm của ngôn ngữ tiếng Việt có nhiều điểm khác so với ngôn ngữ tiếng Anh nên việc áp dụng các phương pháp ấy còn nhiều hạn chế. Mục tiêu của đề tài là nghiên cứu mô hình biểu diễn văn bản tiếng Việt, các kỹ thuật tính độ tương đồng nhằm cải tiến các phép đo tương đồng và ứng dụng vào thiết kế, xây dựng thử nghiệm một số phần chức năng của hệ thống so sánh trên văn bản tiếng Việt. Nội dung báo cáo gồm:  Chương 1: giới thiệu tổng quan về đề tài, mục đích và nội dung nghiên cứu.  Chương 2: trình bày đặc điểm ngôn ngữ tiếng Việt và phương pháp cho bài toán so sánh trên văn bản tiếng Việt.  Chương 3: trình bày các mô hình biểu diễn văn bản truyền thống và mô hình đồ thị, ứng dụng mô hình trong biểu diễn văn bản tiếng Việt.  Chương 4: trình bày phương pháp tính độ tương tự và những cải tiến trên văn bản tiếng Việt.  Chương 5: trình bày thiết kế hệ thống so sánh độ tương tự trong văn bản tiếng Việt. Cuối cùng đề tài đưa ra một số kết luận về kết quả thực hiện và đề xuất các hướng nghiên cứu trong tương lai. Thuyết minh ĐT NCKH CHƯƠNG I: TỔNG QUAN VỀ ĐỀ TÀI CHƯƠNG I: TỔNG QUAN VỀ ĐỀ TÀI 1.1. Lý do chọn đề tài Trong các loại dữ liệu thì dữ liệu văn bản là dạng phổ biến nhất. Ngày nay, với sự phát triển mạnh mẽ của Internet, dữ liệu văn bản đã trở nên phong phú về nội dung và tăng nhanh về số lượng. Chỉ bằng một vài thao tác đơn giản, tại bất kì đâu, tại bất kì thời điểm nào, ta cũng có thể nhận về một khối lượng khổng lồ các trang web và các tài liệu điện tử liên quan đến nội dung tìm kiếm. Chính sự dễ dàng này cũng mang đến cho chúng ta rất nhiều khó khăn trong việc chắt lọc ra các thông tin được coi là mới, là riêng, là hữu ích giữa các tài liệu ấy. Cho đến thời điểm hiện tại, khai phá dữ liệu văn bản trong tiếng Anh đã có rất nhiều công trình nghiên cứu và đạt được nhiều kết quả. Nhìn một cách tổng quan, hầu hết các nghiên cứu này đều dựa vào mô hình biểu diễn văn bản dạng vector và tính toán dựa trên xác suất thống kê thông tin trọng số của các từ trong văn bản. Do các đặc điểm của tiếng Việt khác với tiếng Anh, phương pháp trên có nhược điểm là chưa quan tâm tới vấn đề ngữ nghĩa của văn bản như mối quan hệ giữa các từ/cụm từ, tần số, vị trí hoặc các từ … 1.2. Mục đích nghiên cứu Nghiên cứu tổng quan vấn đề xử lý văn bản và một số phương pháp so sánh độ tương đồng câu đã được áp dụng và thu được kết quả khả quan như phương pháp tính độ tương đồng sử dụng độ đo Cosine, độ đo khoảng cách Euclide… Nghiên cứu đặc điểm của văn bản tiếng Việt, xây dựng mô hình biểu diễn văn bản tiếng Việt nhằm cải tiến các phép đo tương đồng và ứng dụng vào thiết kế, xây dựng thử nghiệm một số phần chức năng của hệ thống so sánh trên văn bản tiếng Việt. 1.3. - - - 1.4. Đối tượng nghiên cứu Nghiên cứu một số mô hình tính toán độ tương đồng văn bản cả về cú pháp và ngữ nghĩa, xác định mức tương đồng văn bản ở cấp độ từ, câu, đoạn văn hay toàn bộ văn bản và ứng dụng trong tiếng Việt. Nghiên cứu phương pháp biểu diễn văn bản tiếng Việt và xây dựng đồ thị liên kết biểu diễn văn bản, tính độ tương tự giữa các văn bản dựa trên mô hình biểu diễn. Xây dựng ứng dụng thử nghiệm so sánh trên văn bản tiếng Việt, hỗ trợ đánh giá việc sao chép bài điện tử. Phương pháp nghiên cứu Tìm hiểu, khảo sát và hệ thống hóa các kết quả nghiên cứu đã có về vấn đề độ tương đồng văn bản và các ứng dụng đối với tiếng Việt. 7 Thuyết minh ĐT NCKH CHƯƠNG I: TỔNG QUAN VỀ ĐỀ TÀI Nghiên cứu lý thuyết về mô hình tính độ tương đồng văn bản, mô hình biểu diễn văn bản và ứng dụng các mô hình vào thiết kế, xây dựng thử nghiệm hệ thống so sánh độ tương đồng giữa các văn bản tiếng Việt. Thực nghiệm trên các dữ liệu mẫu để đánh giá hệ thống. 8 Thuyết minh ĐT NCKH CHƯƠNG II: BÀI TOÁN SO SÁNH VĂN BẢN TIẾNG VIỆT CHƯƠNG II: BÀI TOÁN SO SÁNH VĂN BẢN TIẾNG VIỆT 2.1. Bài toán so sánh văn bản Hiện nay, tình trạng sao chép, vi phạm bản quyền và gian dối, chống đối trong các kết quả học tập, nghiên cứu diễn ra khá sôi nổi và khó kiểm soát. Đặc biệt trong lĩnh vực giáo dục – đào tạo, việc người học tham khảo và chép bài của nhau là phổ biến, làm giảm khả năng tư duy và chất lượng nghiên cứu, học tập. Vấn đề đặt ra là làm thế nào để xác định được phép đo độ giống nhau giữa các văn bản, trên cơ sở đó đưa ra những kết luận về việc sao chép bài điện tử, làm căn cứ để phân loại và đánh giá kết quả bài luận, nghiên cứu của người học. Thực tế đã có một số nghiên cứu đề xuất các phương pháp khác nhau đề xác định xem một đoạn văn bản của một tài liệu có nằm trong một tài liệu nào khác không. Các phương pháp này chủ yếu dựa trên tìm kiếm và so khớp chuỗi, tuy nhiên so khớp chuỗi chỉ có hiệu quả nếu việc sao chép là “nguyên văn”. Việc sao chép có sửa đổi như thay thế một số từ bằng từ đồng nghĩa hay thay đổi thứ tự các câu trong văn bản cần các phương pháp khác hiệu quả hơn. Trong xử lý ngôn ngữ tự nhiên, các công trình nghiên cứu về đánh giá độ tương tự giữa các văn bản tiếng Anh đã và đang diễn ra sôi nổi. Nhiều công trình nghiên cứu và nhiều ứng dụng hữu ích đã thu được kết quả trong việc phát hiện sự vi phạm bản quyền tác giả trong các bài viết như Plagiarism-Detector Personal, Turnitin… Đối với xử lý ngôn ngữ tiếng Việt, hiện nay cũng bắt đầu xuất hiện các nghiên cứu về so sánh trên văn bản tiếng Việt song vẫn chiếm tỉ lệ khá khiêm tốn. Trong tiếng Anh, kho ngữ liệu hay mạng từ tiếng Anh đã và đang phát triển rất tốt nên hiệu quả của các hệ thống so sánh đã cài đặt là rất cao. Do đặc điểm của từ tiếng Việt có nhiều điểm khác với tiếng Anh, việc xử lý văn bản và xây dựng được kho ngữ liệu chuẩn và đầy đủ là cả một vấn đề lớn. Các phương pháp đánh giá độ tương tự văn bản tiếng Việt dựa trên kho ngữ liệu vẫn đang được nghiên cứu và phát triển. Một số phần mềm so sánh văn bản:  Download Compare My Docs: đây là một chương trình so sánh văn bản cho phép người dùng so sánh cùng một lúc nhiều văn bản với nhau để tìm ra sự khác biệt giữa nội dung của chúng. Nhờ nó mà ta có thể biết được các văn bản tài liệu của mình có bị trùng với bất kỳ văn bản nào hay không? Phần mềm này cũng hỗ trợ cả các văn bản tiếng việt theo bảng mã Unicode.  Download UltraCompare: một trong những phần mềm so sánh file văn bản. Chương trình thực hiện so sách nội dung của các tài liệu và đưa ra tỷ lệ trùng, đánh dấu các nội dung trùng một cách chính xác. Ngoài ra chương trình còn cho phép người dùng tìm kiếm, đồng bộ các dữ liệu tìm kiếm và thư mục để thuận việc tìm kiếm, so sánh trở lên nhanh chóng hơn. 9 Thuyết minh ĐT NCKH CHƯƠNG II: BÀI TOÁN SO SÁNH VĂN BẢN TIẾNG VIỆT  Plagiarism-Detector Personal: phần mềm phát hiện các đoạn văn sao chép. Đây là ứng dụng độc đáo với các công cụ hữu ích nhằm hỗ trợ người sử dụng phát hiện ra những đoạn văn hay văn bản sao chép từ các nguồn khác nhau một cách chính xác.  Turnitin: hệ thống hỗ trợ kiểm tra, đánh giá việc sao chép bài điện tử được triển khai tại FPT Polytechnic. Hệ thống này hiện đang làm việc với nhiều trường đại học hàng đầu thế giới và các trung tâm nghiên cứu lớn, một vài tổ chức chính phủ nhằm cung cấp một công cụ hiệu quả phát hiện sự vay mượn, sao chép. 2.2. Đặc điểm ngôn ngữ tiếng Việt 2.2.1. Cấu tạo từ tiếng Việt Tiếng Việt là ngôn ngữ không biến hình từ và âm tiết tính, tức là mỗi âm tiết (tiếng) được phát âm tách rời và được thể hiện bằng một từ [4]. Hai đặc trưng này chi phối toàn bộ toàn bộ tổ chức của hệ thống ngôn ngữ tiếng Việt. a) Tiếng Tiếng là đơn vị cơ sở để cấu tạo lên từ. Tiếng là đơn vị nhỏ nhất có nội dung được thể hiện. Xét về mặt ý nghĩa, các tiếng có thể chia thành các loại sau [1]: - - Tiếng tự thân nó đã có ý nghĩa, thường được quy chiếu vào một đối tượng, khái niệm. Ví dụ: trời, đất, nước, cây, cỏ… Tiếng tự thân nó không có ý nghĩa, không được quy chiếu vào đối tượng, khái niệm nào cả mà chúng thường đi cùng với một tiếng khác có nghĩa và làm thay đổi sắc thái của tiếng đó, ví dụ như: (xanh) lè, (đường) xá, (nắng) nôi… Tiếng tự thân nó không có ý nghĩa nhưng có thể ghép với nhau để tạo thành từ có nghĩa, thường xuyên gặp ở những từ mượn như phéc-mơ-tuya, a-pa-tít, mì-chính... Trong tiếng Việt các tiếng thuộc nhóm đầu tiên chiếm đa số, các tiếng thuộc hai nhóm sau thường chỉ chiếm số ít, đặc biệt là nhóm thứ 3, chúng thường được gọi là tiếng vô nghĩa. b) Từ, cụm từ Từ được cấu tạo từ một hoặc nhiều tiếng. Từ cấu tạo từ một tiếng gọi là từ đơn, ví dụ: tôi, bạn, nhà, hoa… Từ cấu tạo bởi nhiều tiếng là từ ghép, giữa các tiếng có mối quan hệ về nghĩa. Từ ghép được phân thành từ ghép đẳng lập và từ ghép chính phụ. Đối với từ ghép đẳng lập các thành phần cấu tạo từ có mối quan hệ bình đẳng với nhau về nghĩa, 10 Thuyết minh ĐT NCKH CHƯƠNG II: BÀI TOÁN SO SÁNH VĂN BẢN TIẾNG VIỆT ví dụ: ăn nói, bơi lội… Đối với từ ghép chính phụ, các thành phần cấu tạo từ có mối quan hệ phụ thuộc với nhau về nghĩa, thành phần phụ có vai trò làm chuyên biệt hóa, tạo sắc thái cho thành phần chính, ví dụ: hoa hồng, đường sắt… Cụm từ là những kiến trúc gồm hai từ trở lên kết hợp với nhau theo những quan hệ ngữ pháp nhất định. Ví dụ: - Từ “học” là từ gồm một tiếng. Từ “đại học” là từ gồm hai tiếng. Cụm từ “khoa học máy tính” gồm 2 từ hay 4 tiếng. Theo như thống kê trên trang http://vdict.com thì độ dài của một từ tiếng Việt được thể hiện trong bảng [6]: Độ dài của từ 1 2 3 4 ≥5 Tổng cộng Tần số 8399 48995 5727 7040 2301 72994 Tỉ lệ % 12,2 67.1 7.9 9.7 3.1 100 Bảng 1: Tần suất xuất hiện độ dài từ tiếng Việt trên vdict.com 2.2.2. Biến hình từ tiếng Việt Tiếng Việt không có hiện tượng biến hình từ bằng những phụ tố mang ý nghĩa ngữ pháp bên trong từ như tiếng Anh [4]. Tuy nhiên, tiếng Việt cũng có một số hình thức biến hình như trường hợp thêm từ “sự” trước một động từ để biến nó thành danh từ hay thêm tiếng “hóa” sau một danh từ để biến nó thành động từ tương đương, ví dụ như “lựa chọn” và “sự lựa chọn”, “tin học” và “tin học hóa”. 2.2.3. Từ đồng nghĩa Từ đồng nghĩa là những từ tương đồng với nhau về nghĩa nhưng khác nhau về âm thanh và phân biệt với nhau về một vài sắc thái ngữ nghĩa hoặc phong cách nào đó, hoặc đồng thời cả hai [4]. Những từ đồng nghĩa với nhau lập thành một nhóm gọi là nhóm đồng nghĩa. Ví dụ: dễ, dễ dàng, dễ dãi là những nhóm từ đồng nghĩa. Từ đồng nghĩa thực chất không phải là những từ trùng nhau hoàn toàn về nghĩa mà có những khác biệt nhất định. Chính sự khác biệt đó là lí do tồn tại và làm nên sự khác nhau giữa các từ trong một nhóm từ đồng nghĩa. Thông thường các từ chỉ đồng nghĩa ở một nghĩa, một ngữ cảnh nào đó. Vì thế, một từ có nhiều nghĩa (đa nghĩa) có thể tham gia vào nhiều nhóm đồng nghĩa khác 11 Thuyết minh ĐT NCKH CHƯƠNG II: BÀI TOÁN SO SÁNH VĂN BẢN TIẾNG VIỆT nhau. Ví dụ, từ “coi” có thể tham gia vào các nhóm như coi – xem (coi hát, xem hát), coi – giữ (coi nhà, giữ nhà). 2.2.4. Đặc điểm chính tả Đặc điểm chính tả tiếng Việt có ý nghĩa rất quan trọng trong các hệ thống xử lý dữ liệu văn bản. Một số đặc điểm chính tả tiếng Việt cần quan tâm như [4]: - - Các tiếng đồng âm: kĩ/kỹ, lí, lý… thường bị sử dụng lẫn nhau như: lý luận, lí luận, kĩ thuật, kỹ thuật… Các từ địa phương: một số từ địa phương sử dụng thay cho các từ phổ thông, chẳng hạn: cây kiểng/cây cảnh, đờn/đàn, đậu phộng/lạc… Vị trí dấu thanh: theo quy định đánh dấu tiếng Việt, dấu được đặt trên nguyên âm có ưu tiên cao nhất. Tuy nhiên, khi soạn thảo văn bản nhiều bộ gõ không tuân thủ nguyên tắc này nên có hiện tượng dấu được đặt ở các vị trí khác nhau, chẳng hạn: toán, tóan, thuý, thúy… Cách viết hoa: theo quy định, chữ cái đầu câu và tên riêng phải viết hoa, tuy nhiên vẫn tồn tại một số cách viết tuỳ tiện. Phiên âm tiếng nước ngoài: tồn tại cách viết giữ nguyên gốc tiếng nước ngoài và phiên âm ra tiếng Việt, ví dụ: Singapore/Xin−ga−po. Từ gạch nối: do cách viết dấu gạch nối tuỳ tiện, không phân biệt được giữa nối tên riêng hay chú thích. Kí tự ngắt câu: sử dụng nhiều loại kí tự đặc biệt như “.”, “;”, “!”, “?”, “…” ngăn cách giữa các câu hoặc các vế câu trong câu ghép. 2.2.5. Bảng mã tiếng Việt trên máy tính Hiện nay có khá nhiều cách mã hoá các kí tự tiếng Việt khác nhau, dẫn tới có nhiều bảng mã khác nhau được sử dụng khi trình bày văn bản. Theo thống kê, có tới trên 40 bảng mã tiếng Việt được sử dụng [4], có thể kể đến một số bảng mã dưới đây: - - Mã dựng sẵn: o Mã dựng sẵn một bảng fonts: TCVN 5712-VN1, VISCII, BachKhoa 1, VietStar…: các bảng mã này mở rộng sang cả phần mã chuẩn, nên gây ảnh hưởng nghiêm trọng trong truyền thông. o Mã dựng sẵn hai bảng fonts: TCVN 5712-VN3 (ABC), VietSea, VNU…: sử dụng 2 bảng mã cho một kiểu chữ nên gây dư thừa và không hiện thực việc phân biệt chữ hoa chữ thường trong các chương trình xử lý số liệu. Mã tổ hợp: Các bảng mã VietWare-X, Vni for Windows, TCVN 5712-VN2, BachKhoa II, VS2, 3C25… và các trang mã 1258 (Microsoft), 1129 (IBM), ISO 10646 sử dụng phương pháp mã tổ hợp. Do chưa có sự thống nhất giữa các bảng mã biểu diễn tiếng Việt trên máy tính nên việc thu thập, khai thác xử lý tiếng Việt gặp nhiều khó khăn, đòi hỏi các hệ thống 12 Thuyết minh ĐT NCKH CHƯƠNG II: BÀI TOÁN SO SÁNH VĂN BẢN TIẾNG VIỆT xử lý văn bản tiếng Việt cần phải có bước tiền xử lý để nhận dạng và quy chuẩn các kí tự về một bảng mã chung. 2.3. Hướng tiếp cận cho bài toán so sánh văn bản tiếng Việt 2.3.1. Tiền xử lý văn bản tiếng Việt Văn bản trước khi đưa vào mô hình xử lý cần được tiền xử lý. Quá trình này sẽ giúp nâng cao hiệu quả của mô hình và giảm độ phức tạp của thuật toán được cài đặt vì nó có nhiệm vụ làm giảm số từ có trong biểu diễn văn bản. Thông thường các bước tiền xử lý văn bản gồm:  Tách văn bản thành các câu và các từ riêng lẻ để sử dụng cho mục đích tính toán sau này.  Loại bỏ từ dừng (stopwords), loại bỏ các ký tự không phải chữ cái hoặc chữ số.  Lưu các câu và các từ vào một cấu trúc dữ liệu phù hợp. 2.3.1.1. Tách từ tiếng Việt Tách từ có thể nói là giai đoạn quan trọng nhất, ảnh hưởng đến kết quả của mô hình xử lý. Bước này có nhiệm vụ xác định các từ có trong văn bản, kết quả của nó là một tập các từ riêng biệt. Các trường hợp đặc biệt như số, dấu ngoặc, dấu chấm câu thường bị loại ra trong khi phân tích vì một mình nó không mang lại ý nghĩa nào cho tài liệu (ngoại trừ một vài trường hợp đặc biệt, ví dụ trong thu thập thông tin về lĩnh vực lịch sử). Tuy nhiên trong một vài trường hợp, chẳng hạn đối với những từ ghép nối (state-of-the-art) không được phép bỏ dấu “-”, vì sẽ làm thay đổi nghĩa của từ. Trong tiếng Việt, từ là sự hoàn chỉnh về mặt nội dung, là đơn vị nhỏ nhất để đặt câu. Người ta dùng từ để kết hợp thành câu chứ không dùng tiếng. Đối với các hệ thống xử lý ngôn ngữ tiếng Anh, để xác định các từ đặc trưng cho văn bản người ta có thể dựa vào khoảng trắng làm ranh giới. Tuy nhiên, trong tiếng Việt vì từ có thể là từ đơn hay từ ghép nên khoảng trắng không còn là dấu hiệu phân cách từ nữa. Vấn đề mà các mô hình tách từ tiếng Việt đều gặp phải đó là [1]:  Xác định các từ chưa biết trước (đối với từ điển máy tính) như các câu thành ngữ, từ láy, hoặc tên người, địa điểm…  Sự nhập nhằng: - Nhập nhằng chồng chéo: chuỗi “abcd” được gọi là nhập nhằng chồng chéo nếu như từ “abc”, “bcd” đều xuất hiện trong từ điển, ví dụ: trong câu “ông già đi nhanh quá” thì chuỗi “ông già đi” nhập nhằng chồng chéo vì các từ “ông già” và “già đi” đều có trong từ điển. - Nhập nhằng kết hợp: chuỗi “abcd” gọi là nhập nhằng kết hợp nếu các từ thành phần “ab”, “cd”, “abcd” đều xuất hiện trong từ điển. Ví dụ trong câu “Tủ lạnh này còn rất mới” thì chuỗi “Tủ lạnh” bị nhập nhằng kết hợp do các từ “tủ”, “lạnh”, “tủ lạnh” đều có trong từ điển. 13 Thuyết minh ĐT NCKH CHƯƠNG II: BÀI TOÁN SO SÁNH VĂN BẢN TIẾNG VIỆT Hiện đã có nhiều công trình nghiên cứu xây dựng mô hình tách từ tiếng Việt, đa số là các mô hình đã được áp dụng thành công cho các ngôn ngữ khác (Anh, Trung, Nhật…) và được cải tiến để phù hợp với đặc điểm của tiếng Việt. Có thể kể đến các công trình điển hình như: - - - 2.3.1.2. Mô hình tách từ bằng WFST (Weighted Finit State Transduce) và mạng Neural đã được sử dụng trong công trình của tác giả Đình Điền (2001). Tác giả đã xây dựng hệ thống tách từ gồm tầng WFST để tách từ và xử lý các vấn đề liên quan đến một số đặc thù của tiếng Việt như từ láy, tên riêng… và tầng mạng Neural dùng để khử nhập nhằng về ngữ nghĩa sau khi đã tách từ nếu có. Mô hình này đạt được độ chính xác trên 97% theo như công bố của tác giả [2]. JvnTextPro: công cụ tách từ do nhóm tác giả Nguyễn Cẩm Tú, Khoa Công nghệ - Trường Đại học Quốc gia Hà Nội xây dựng có thể nhận biết được các danh từ riêng, các từ đơn và từ ghép với có độ chính xác trung bình khá cao, khoảng 94,5%. Bộ công cụ tách từ vnTokenizer thuộc nhánh đề tài “Xử lý văn bản tiếng Việt” nằm trong Đề tài thuộc Chương trình Khoa học Công nghệ cấp Nhà nước “Nghiên cứu phát triển một số sản phẩm thiết yếu về xử lý tiếng nói và văn bản tiếng Việt” (2006) cũng cho độ chính xác cao, trên 97%. Loại bỏ từ dừng (stopwords) Từ dừng là các từ thường xuất hiện nhiều trong các văn bản của tập dữ liệu, thường thì chúng không giúp ích gì trong việc phân biệt nội dung của các tài liệu. Ví dụ “như vậy”, “sau đó”, “một số”, “chỉ”… 2.3.1.3. Loại bỏ từ có tần số thấp Có nhiều từ trong tập văn bản xuất hiện rất ít lần và có ảnh hưởng rất ít trong văn bản. Vì vậy các từ này cũng nên loại bỏ. 2.3.1.4. Xác định từ đồng nghĩa Từ đồng nghĩa là những từ tương đương về nghĩa trong một số ngữ cảnh nào đó, bên cạnh sự tương đồng chúng có những khác biết nhất định mặc dù việc phát hiện những khác biệt đó không phải lúc nào cũng dễ dàng. Với bài toán so sánh trên văn bản thì việc nhận ra các từ đồng nghĩa có ý nghĩa quan trọng bởi trong các câu, các đoạn văn luôn có các từ đồng nghĩa hoặc gần nghĩa nhau được sử dụng thay thế. Việc phát hiện ra các từ đồng nghĩa sẽ làm nâng cao tính chính xác khi so sánh về độ tương đồng ngữ nghĩa giữa các đơn vị văn bản. 2.3.2. Phương pháp tính độ tương đồng giữa các văn bản Độ tương đồng ngữ nghĩa giữa các câu đóng một vai trò quan trọng trong các nghiên cứu về xử lý văn bản. Nó được sử dụng như là một tiêu chuẩn của trích chọn 14 Thuyết minh ĐT NCKH CHƯƠNG II: BÀI TOÁN SO SÁNH VĂN BẢN TIẾNG VIỆT thông tin nhằm tìm ra những tri thức ẩn trong các cơ sở dữ liệu văn bản hay trên các kho dữ liệu trực tuyến. Hiện nay tồn tại một số phương pháp tính độ tương đồng giữa các câu, điển hình là các phương pháp dựa trên tính toán thống kê và các phương pháp dựa trên quan hệ ngữ nghĩa giữa tập các từ trong các câu đó. - - Với phương pháp thống kê: sử dụng các độ đo dựa vào tần suất xuất hiện của từ trong câu như phương pháp sử dụng độ đo Cosine, độ đo khoảng cách Euclide, Manhattan... Các phương pháp này tốc độ xử lý nhanh, tốn ít chi phí nhưng không đảm bảo độ chính xác cao về mặt ngữ nghĩa. Với phương pháp dựa trên quan hệ ngữ nghĩa giữa các từ: một số hướng tiếp cận phân tích cấu trúc ngữ pháp, sử dụng mạng ngữ nghĩa đối với từ như Wordnet corpus hoặc Brown corpus... Các phương pháp này xử lý chậm hơn, tốn nhiều chi phí hơn nhưng xét về mặt ngữ nghĩa thì độ tương đồng chính xác cao hơn phương pháp thống kê. Do đặc điểm của tiếng Việt, vấn đề tương đồng ngữ nghĩa trên văn bản tiếng Việt phức tạp hơn khi so với ngôn ngữ tiếng Anh. Phần lớn các giải pháp hiện có thường quan tâm tới các độ đo dựa vào thống kê mà chưa khai thác các độ đo dựa vào xử lý ngôn ngữ tự nhiên. Các phương pháp tính dựa trên kho ngữ liệu Wordnet được đánh giá là cho kết quả cao, tuy nhiên WordNet chỉ hỗ trợ cho tiếng Anh, việc xây dựng kho ngữ liệu này cho tiếng Việt là chưa có. Một số phương pháp được đề xuất thay thế Wordnet như phương pháp phân tích chủ đề ẩn hay sử dụng mạng ngữ nghĩa Wikipedia thay thế được xem như là phương án khả thi và hiệu quả. Các phương pháp này tập trung vào việc bổ sung các thành phần ngữ nghĩa hỗ trợ cho độ đo tương đồng Cosine. Một số đề tài đáng chú ý về so sánh, đánh giá độ tương tự văn bản như “Tính toán độ tương tự ngữ nghĩa văn bản dựa vào độ tương tự giữa từ với từ” của tác giả Đỗ Thị Thanh Nga (Đại học Công nghệ Đại học Quốc gia Hà Nội, 2010), đề tài “Nghiên cứu độ đo tương đồng văn bản trong tiếng Việt và ứng dụng” của tác giả Dương Thăng Long (Viện Đại học Mở Hà Nội, 2014). Đề tài của tác giả Đỗ Thị Thanh Nga đưa ra mô hình tính độ tương tự ngữ nghĩa giữa hai văn bản dựa trên độ tương tự giữa từ với từ kết hợp với tần suất đặc trưng của từ [6]. Kết quả của đề tài tương đối khả quan với những cặp văn bản hoặc là giống nhau nhiều hoặc là khác nhau nhiều. Tuy nhiên, do phương pháp này chưa xét đến mối quan hệ về cấu trúc của từ/cụm từ, vị trí của câu… nên vẫn còn nhiều trường hợp chương trình thử nghiêm cho kết quả không chính xác. Cũng chình vì thế các văn bản có sự tương đồng cao về ngữ nghĩa không hẳn đã là giống nhau. Nói cách khác, độ tương đồng về ngữ nghĩa không phản ánh được chính xác sự sao chép trong các văn bản đem so sánh. 15 Thuyết minh ĐT NCKH CHƯƠNG II: BÀI TOÁN SO SÁNH VĂN BẢN TIẾNG VIỆT Đề tài của tác giả Dương Thăng Long giới thiệu phương pháp đánh giá độ tương tự văn bản tiếng Việt sử dụng 3 yếu tố: độ tương tự dựa trên vector đặc trưng ngữ nghĩa, độ tương tự dựa trên cấu trúc thứ tự các từ và độ tương tự dựa trên ma trận so sánh cặp từ vựng theo nhóm từ loại [5]. Sự kết hợp của 3 yếu tố trên làm tăng hiệu quả đánh giá, tuy nhiên, phương pháp đề xuất còn phụ thuộc vào kết quả của các xử lý trung gian, đặc biệt là dịch từ tiếng Việt sang tiếng Anh và đánh giá độ tương tự của cặp từ vựng tiếng Anh, dẫn đến độ tin cậy của kết quả đánh giá độ tương tự văn bản giảm nhiều. 2.3.3. Hướng tiếp cận cho bài toán so sánh văn bản tiếng Việt Do việc xây dựng bộ tách từ khá phức tạp và nằm ngoài phạm vi của đề tài nên trong thực nghiệm, chúng tôi sử dụng bộ tách từ đã được viết sẵn và cung cấp miễn phí WordSegForTV để thực hiện bước tiền xử lý văn bản. Việc xác định các từ dừng trong văn bản được thực hiện thông qua một từ điển từ dừng. Ngoài ra, đối với tiếng Việt, do có một lượng lớn các từ đồng nghĩa thường được sử dụng nên khi tính độ tương tự giữa các câu trong văn bản cần sử dụng thêm một từ điển đồng nghĩa. Sau khi phân tách từ thành công, văn bản sẽ gồm tập các từ khóa mà ngữ nghĩa của chúng tạo nên nội dung của văn bản. Trong đa số các hệ xử lý văn bản, các văn bản đều được coi là tập các từ khóa và biểu diễn chúng dưới dạng vector, chẳng hạn như Di = (di1,di2, …, din) với dik biểu diễn trọng số/tần xuất của từ tk trong Di. Việc so sánh độ tương tự giữa hai văn bản Di và Dj, kí hiêu là Sim(Di,Dj), được tính toán theo các công thức tính toán độ tương tự, ví dụ độ tương tự Cosine. Nếu độ tương tự này đạt đến một ngưỡng đủ lớn thì người 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. Tuy nhiên, đối với các văn bản tiếng Việt, phương thức ngữ pháp chủ yếu là dựa trên trật tự của từ trong câu nên nếu áp dụng mô hình biểu diễn văn bản dựa trên tần số xuất hiện của từ có thể không cho kết quả chính xác như mong đợi. Nguyên nhân là do vector biểu diễn văn bản không đảm bảo giữ được mối liên quan về mặt ngữ nghĩa giữa các từ, vị trí các từ, cụm từ và vị trí của câu trong văn bản, hai vector có trật tự từ khác nhau vẫn có thể cho độ tương tự là hoàn toàn giống nhau. Nhằm kế thừa ưu điểm của các phương pháp đã biết, hướng tiếp cận bài toán so sánh văn bản tiếng Việt là xác định độ tương tự của văn bản dựa trên độ tương tự của câu và trật tự câu, độ tương tự câu dựa trên độ tương tự của từ và trật tự của từ trong câu. Những cải tiến của phương pháp đề xuất so với so sánh văn bản tiếng Anh và các phương pháp đã biết là: - Kết hợp sử dụng bộ tách từ, từ điển từ dừng và từ điển từ đồng nghĩa làm tăng tính ngữ nghĩa của tập từ khóa và vector đặc trưng biểu diễn văn bản. 16 Thuyết minh ĐT NCKH - CHƯƠNG II: BÀI TOÁN SO SÁNH VĂN BẢN TIẾNG VIỆT Kết hợp độ tương tự ngữ nghĩa từ (có xử lý từ đồng nghĩa) và độ tương tự thứ tự từ vào tính độ tương tự của văn bản nhằm nâng cao chất lượng kết quả so sánh. Trong các chương tiếp theo, chúng tôi sẽ trình bày chi tiết về các mô hình biểu diễn văn bản, phương pháp tính độ tương đồng câu và mô hình hệ thống so sánh văn bản tiếng Việt. 17 Thuyết minh ĐT NCKH CHƯƠNG III: MÔ HÌNH BIỂU DIỄN VĂN BẢN TIẾNG VIỆT CHƯƠNG III: MÔ HÌNH BIỂU DIỄN VĂN BẢN TIẾNG VIỆT Biểu diễn văn bản là một bước quan trọng trong khai thác dữ liệu văn bản, truy vấn thông tin và xử lý ngôn ngữ tự nhiên. Các mô hình biểu diễn đóng vai trò trung gian giữa ngôn ngữ tự nhiên dạng văn bản và các chương trình xử lý. Văn bản ở dạng thô (chuỗi) sau khi được chuyển sang mô hình sẽ trở thành những cấu trúc dữ liệu trực quan, đơn giản hơn, thuận lợi cho việc hiểu và tính toán trên văn bản. Vì vậy, các mô hình biểu diễn không ngừng phát triển. Tùy thuộc vào từng bài toán, từng thuật toán khác nhau mà chúng ta có mô hình biểu diễn phù hợp. Các mô hình biểu diễn văn bản truyền thống như mô hình túi từ, mô hình không gian vector là các mô hình thường được sử dụng nhất. Tuy nhiên, các mô hình này có nhược điểm là không nắm bắt được các thông tin cấu trúc quan trong của văn bản như trật tự các từ, vị trí của từ trong văn bản. Mô hình đồ thị biểu diễn văn bản là phương pháp đang được quan tâm và sử dụng trong các lĩnh vực khai phá dữ liệu văn bản hiện tại. 3.1. Mô hình biểu diễn văn bản truyền thống 3.1.1. Mô hình logic Trong mô hình này, văn bản được biểu diễn dựa theo chỉ số của các từ có nghĩa. Từ có nghĩa là từ mang thông tin chính của văn bản, khi nhìn vào từ đó người ta biết chủ đề của văn bản cần biểu diễn là gì. Mỗi văn bản được đánh chỉ số theo qui tắc liệt kê các từ có nghĩa trong văn bản và với mỗi từ khóa, lưu vị trí xuất hiện cùng với mã của văn bản chứa nó [2]. Ví dụ, có hai văn bản VB1,VB2: “Mô hình đồ thị biểu diễn văn bản” (VB1) “Biểu diễn văn bản sử dụng mô hình đồ thị” (VB2) Khi đó ta có cách biểu diễn như sau: Từ mục Mã VB _ Vị trí XH Mô VB1(1), VB2(7) Hình VB1(2), VB2(8) Đồ VB1(3), VB2(9) Thị VB1(4), VB2(10) Biểu VB1(5), VB2(1) Diễn VB1(6), VB2(2) Văn VB1(7), VB2(3) Bản VB1(8), VB2(4) Bảng 2: Biểu diễn văn bản trong mô hình Logic 18 Thuyết minh ĐT NCKH CHƯƠNG III: MÔ HÌNH BIỂU DIỄN VĂN BẢN TIẾNG VIỆT Cách biểu diễn này cũng được các máy tìm kiếm ưa dùng. Khi biểu diễn văn bản theo mô hình này, người ta đưa các tìm kiếm sau: câu hỏi tìm kiếm được đưa ra dưới dạng Logic gồm một tập các phép toán (AND, OR,…) thực hiện trên các từ hoặc cụm từ, việc tìm kiếm dựa vào bảng Index đã tạo ra và kết quả trả lại là các văn bản thoả mãn toàn bộ các điều kiện trên Ưu điểm: việc tìm kiếm có thể thực hiện nhanh và đơn giản do trước đó ta đã sắp xếp bảng Index theo các từ khóa. Hệ thống sẽ duyệt trên bảng Index để trỏ để trỏ đến Index tương ứng với từ khóa nếu từ khóa tồn tại trong hệ thống, và cho ta biết các tài liệu chứa từ khóa cần tìm. Nhược điểm: đòi hỏi người tìm kiếm phải có kinh nghiệm tìm kiếm. Do câu hỏi tìm kiếm được đưa vào dưới dạng Logic nên kết quả trả lại cũng có giá trị Logic, một số tài liệu sẽ chỉ được trả lại khi thỏa mãn mọi điều kiện. Như vậy muốn tìm được tài liệu theo nội dung thì phải biết đích xác về tài liệu. Hơn nữa, việc Index các tài liệu phức tạp và tốn nhiều thời gian, không gian để lưu trữ; khi thêm, xóa từ khóa vào các bảng Index chỉ số Index của văn bản cũng thay đổi theo. 3.1.2. Mô hình vector Mô hình vector là một trong những mô hình đơn giản và thường được sử dụng trong phần lớn các bài toán xử lý dữ liệu văn bản. Theo mô hình này, mỗi văn bản được biểu diễn thành một vector, mỗi thành phần của vector là một từ khóa trong tập văn bản gốc và được gán một giá trị trọng số xác định tần suất xuất hiện của từ trong văn bản. Hình 1: Mô hình vector biểu diễn văn bản Phát biểu của mô hình: ⃗ (vector đặc trưng cho Mỗi văn bản D được biểu diễn dưới dạng một vector 𝑉 ⃗ = (𝑣1 , 𝑣2 , … , 𝑣𝑛 ) và n là số lượng đặc trưng hay số chiều của văn bản D). Trong đó, 𝑉 vector văn bản(thường là số từ khóa), 𝑣𝑖 là trọng số của đặc trưng thứ i (với 1 ≤ 𝑖 ≤ 𝑛). Ví dụ: xét 2 văn bản với trọng số đặc trưng là số lần xuất hiện của từ khóa thứ i trong văn bản, vector biểu diễn tương ứng như sau: VB1: Life is not only life 19 Thuyết minh ĐT NCKH CHƯƠNG III: MÔ HÌNH BIỂU DIỄN VĂN BẢN TIẾNG VIỆT VB2: To life is to fight Từ Vector VB1 Vector VB2 Life 2 1 Fight 0 1 Only 1 0 Bảng 3: Vector biểu diễn văn bản Trọng số của đặc trưng có thể tính dựa trên tần số xuất hiện của từ khóa trong văn bản. Ma trận biểu diễn trọng số (ma trận tần suất) W ={wij} được xác định dựa trên tần số xuất hiện của từ khóa ti trong văn bản dj. Một số phương pháp xác định wij:  Phương pháp Boolean weighting: giá trị là 1 nếu số lần xuất hiện của từ khóa lớn hơn một ngưỡng nào đó, ngược lại 0).  Phương pháp dựa trên tần số từ khóa (Term Frequency Weighting).  Phương pháp dựa trên nghịch đảo tần số văn bản (Inverse Document Frequency).  Tf*idf weighting. a) Phương pháp Boolean weighting Mô hình vector với trọng số từ khóa ti nhận giá trị đúng nếu và chỉ nếu ti xuất hiện trong văn bản đó. Giả sử có một cơ sở dữ liệu gồm m văn bản, D = {d1, d2,… dm}. Mỗi văn bản được biểu diễn dưới dạng một vector gồm n từ khóa T = {t1, t2,…tn}. Gọi W = {wij} là ma trận trọng số, trong đó wij là giá trị trọng số của từ khóa ti trong văn bản dj. 𝑤𝑖𝑗 = { 1 𝑛ế𝑢 𝑡𝑖 𝑐ó 𝑡𝑟𝑜𝑛𝑔 𝑑𝑗 0 𝑛ế𝑢 𝑛𝑔ượ𝑐 𝑙ạ𝑖 b) Phương pháp dựa trên tần số từ khóa (Term Frequency) Các giá trị wij được tính dựa trên tần số xuất hiện của từ khóa trong văn bản. Giả sử fij là số lần xuất hiện của từ khóa ti trong văn bản dj, khi đó wij được tính bởi một trong ba công thức: 𝑤𝑖𝑗 = 𝑓𝑖𝑗 𝑤𝑖𝑗 = 1 + 𝑙𝑜𝑔(𝑓𝑖𝑗 ) 𝑤𝑖𝑗 = √𝑓𝑖𝑗 Nếu số lần xuất hiện từ khóa ti trong văn bản dj càng lớn thì có nghĩa là văn bản dj càng phụ thuộc vào từ khóa ti, hay nói cách khác từ khóa ti mang nhiều thông tin 20