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

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ ------------------------- Đỗ Thị Thanh Nga 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Ừ LUẬN VĂN THẠC SĨ HÀ NỘI - 2010 LỜI CẢM ƠN Trước tiên, tôi xin được bày tỏ sự trân trọng và lòng biết ơn đối với TS. Nguyễn Phương Thái, giảng viên Bộ môn Khoa học máy tính - Khoa Công nghệ thông tin - Trường Đại học Công nghệ - ĐHQGHN. Trong thời gian làm luận văn tốt nghiệp, thầy đã dành nhiều thời gian quí báu và tận tình chỉ bảo, hướng dẫn tôi trong việc nghiên cứu, thực hiện luận văn. Tôi xin được cảm ơn các GS, TS đã giảng dạy tôi trong quá trình học tập và làm luận văn. Các thầy đã giúp tôi hiểu thấu đáo hơn lĩnh vực mà mình nghiên cứu để có thể vận dụng các kiến thức đó vào trong công tác của mình. Xin cảm ơn các bạn bè, đồng nghiệp và nhất là các thành viên trong gia đình đã tạo mọi điều kiện tốt nhất, động viên, cổ vũ tôi trong suốt quá trình học tập và nghiên cứu để hoàn thành tốt bản luận văn tốt nghiệp này. Tuy đã có những cố gắng nhất định nhưng do thời gian và trình độ có hạn nên chắc chắn luận văn này còn nhiều thiếu sót và hạn chế. Kính mong nhận được sự góp ý của thầy cô và các bạn. Hà Nội, ngày 20 tháng 09 năm 2010 Học viên Đỗ Thị Thanh Nga LỜI CAM ĐOAN Tôi xin cam đoan rằng, đây là công trình nghiên cứu của tôi trong đó có sự giúp đỡ rất lớn của thầy hướng dẫn và các đồng nghiệp ở cơ quan. Các nội dung nghiên cứu và kết quả trong đề tài này là hoàn toàn trung thực. Trong luận văn, tôi có tham khảo đến một số tài liệu của một số tác giả đã được liệt kê tại phần Tài liệu tham khảo ở cuối luận văn. Tôi xin hoàn toàn chịu trách nhiệm và chịu mọi hình thức kỷ luật theo quy định cho lời cam đoan của mình. Hà Nội, ngày 20 tháng 09 năm 2010 Học viên Đỗ Thị Thanh Nga MỤC LỤC DANH MỤC CÁC BẢNG..................................................................................................... 1 DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ ................................................................................. 2 MỞ ĐẦU ............................................................................................................................... 3 CHƯƠNG I. KHÁI NIỆM ĐỘ TƯƠNG TỰ.......................................................................... 5 1.1. Tổng quan về độ tương tự............................................................................................ 5 1.2. Khái niệm độ tương tự................................................................................................. 6 1.2.1. Định nghĩa độ tương tự (Definition of Similarity) ................................................ 7 1.2.2. Độ tương tự giữa các giá trị có thứ tự ưu tiên (ordinal values).............................. 8 1.2.3. Độ tương tự chuỗi (String Similarity-A case study).............................................. 9 1.3. Độ tương tự ngữ nghĩa............................................................................................... 10 CHƯƠNG II. ĐỘ TƯƠNG TỰ TỪ-TỪ............................................................................... 11 2.1. Khái niệm từ, thuật ngữ ............................................................................................. 11 2.1.1. Từ và cấu trúc từ của tiếng Việt .......................................................................... 11 2.1.1.1. Định nghĩa từ ............................................................................................... 11 2.1.1.2. Cấu trúc từ của tiếng Việt ............................................................................ 11 2.1.2. Nghĩa của từ ....................................................................................................... 12 2.1.3. Thuật ngữ (terms) ............................................................................................... 12 2.2. Từ đồng nghĩa ........................................................................................................... 12 2.3. Các cách tiếp cận xử lý tài liệu theo ngữ nghĩa .......................................................... 14 2.3.1. Dựa trên trí tuệ nhân tạo (AI-based).................................................................... 14 2.3.2. Dựa trên Cơ sở tri thức (Knowledge-based) ........................................................ 14 2.3.3. Dựa trên ngữ liệu (Corpus-based) ....................................................................... 14 2.4. Độ tương tự ngữ nghĩa từ-từ dựa trên cơ sở tri thức (từ điển WordNet)...................... 15 2.4.1. Khái quát về từ điển WordNet ............................................................................ 15 2.4.2. Độ tương tự từ-từ dựa trên từ điển WordNet ....................................................... 16 2.5. Độ tương tự ngữ nghĩa từ-từ dựa trên ngữ liệu ........................................................... 17 2.5.1. PMI (Pointwise Mutual Information) (Thông tin chung dựa trên điểm) ............... 18 2.5.2. LSA (Latent Semantic Analysis) (Phân tích ngữ nghĩa ẩn) .................................. 18 2.5.3. Phương pháp của Dekang Lin ............................................................................. 18 CHƯƠNG III. ĐỘ TƯƠNG TỰ VĂN BẢN-VĂN BẢN ..................................................... 21 3.1. Xử lý văn bản tiếng Việt............................................................................................ 21 3.1.1. Một số kết quả đã đạt được................................................................................. 21 3.1.2. Đặc trưng của cấu trúc ngữ pháp tiếng Việt ........................................................ 23 3.2. Tách từ trong văn bản tiếng Việt................................................................................ 23 3.3. Các hướng tiếp cận tách từ ........................................................................................ 24 3.3.1. Các hướng tiếp cận dựa trên “từ” ....................................................................... 24 3.3.2. Các hướng tiếp cận dựa trên ký tự ...................................................................... 25 3.4. Một số phương pháp tách từ tiếng Việt hiện nay ........................................................ 26 3.4.1. Phương pháp Maximum Matching: Forward/Backward ..................................... 26 3.4.2. Phương pháp Transformation-based Learning (TBL) ......................................... 27 3.4.3. Mô hình tách từ bằng WFST và mạng Neural .................................................... 27 3.4.3.1. Tầng WFST ................................................................................................. 27 3.4.3.2. Tầng mạng Neural ....................................................................................... 28 3.4.4. Phương pháp tách tách từ tiếng Việt dựa trên thống kê từ Internet và thuật giải di truyền........................................................................................................................... 28 3.4.4.1. Online Extractor........................................................................................... 28 3.4.4.2. GA Engine for Text Segmentation ............................................................... 29 3.4.5. Nhận xét ............................................................................................................. 29 3.5. Độ tương tự văn bản-văn bản..................................................................................... 30 CHƯƠNG IV. TÍNH ĐỘ TƯƠNG TỰ NGỮ NGHĨA VĂN BẢN DỰA VÀO ĐỘ TƯƠNG TỰ GIỮA TỪ VỚI TỪ........................................................................................................ 33 3.1. Phát biểu bài toán ...................................................................................................... 33 3.2. Giải quyết bài toán .................................................................................................... 33 3.2.1. Chuẩn bị dữ liệu ................................................................................................. 33 3.2.2. Tách từ: Tách văn bản thành các từ ghép và danh từ riêng ................................. 36 3.2.2.1. Tách từ ghép trong văn bản .......................................................................... 36 3.2.2.2. Tách danh từ riêng trong văn bản ................................................................. 39 3.2.3. Tính toán độ tương tự văn bản ............................................................................ 41 3.3. Xây dựng hệ thống .................................................................................................... 44 3.3.1. Nhập trực tiếp 2 văn bản .................................................................................... 45 3.3.2. Nhập 2 văn bản từ file ........................................................................................ 46 3.3.3. Lấy nội dung 2 văn bản từ URL ......................................................................... 47 3.4. Kết quả thử nghiệm và đánh giá ................................................................................ 48 3.4.1. Một số ví dụ cụ thể ............................................................................................. 48 3.4.2. Kết quả thử nghiệm ............................................................................................ 54 3.4.2.1. Cách tiến hành ............................................................................................. 54 3.4.2.2. Kết quả thử nghiệm...................................................................................... 54 3.4.3. Đánh giá ............................................................................................................. 59 KẾT LUẬN ......................................................................................................................... 61 HƯỚNG PHÁT TRIỂN....................................................................................................... 62 TÀI LIỆU THAM KHẢO .................................................................................................... 63 1 DANH MỤC CÁC BẢNG Bảng Trang Bảng 1. Tần suất xuất hiện độ dài từ tiếng Việt trên trang Vdict.com 11 Bảng 2. Mô tả các bộ ba của từ “giàu” 19 Bảng 3. Các điểm khác biệt chính giữa tiếng Việt và tiếng Anh 24 Bảng 4. Địa chỉ của 20 tin tức trên một số trang Web 54 Bảng 5. Một số kết quả độ tương tự của hai file bất kỳ 55 Bảng 6. Kết quả đánh giá 20 tin tức do người và máy thực hiện 56 Bảng 7. Địa chỉ của 30 tin rao vặt trên các trang Web 56 Bảng 8. Một số kết quả độ tương tự của hai tin rao vặt bất kỳ 58 Bảng 9. Kết quả đánh giá 30 tin rao vặt do người và máy thực hiện 59 2 DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ Hình Trang Hình 1. Ví dụ phân phối của các giá trị có thứ tự ưu tiên 9 Hình 2. Một phần từ điển WordNet 16 Hình 3. Các hướng tiếp cận cơ bản trong việc tách từ 24 Hình 4. Một phần của từ điển Dict 34 Hình 5. Danh sách một số file trong kho ngữ liệu đã xử lý 34 Hình 6. Một phần của từ điển các từ ghép 35 Hình 7. Một phần từ điển CompoundDict 35 Hình 8. Giao diện chính của hệ thống 45 Hình 9. Giao diện cho phép nhập trực tiếp hai văn bản 45 Hình 10. Giao diện kết quả độ tương tự sau khi nhập hai văn bản 46 Hình 11. Giao diện nhập hai văn bản từ file 46 Hình 12. Giao diện kết quả sau khi nhập hai văn bản từ file 47 Hình 13. Giao diện tính độ tương tự nội dung của hai trang Web 48 3 MỞ ĐẦU 1. Tính cấp thiết của đề tài Trong thời đại công nghệ số như hiện nay, các nguồn tài liệu là vô cùng phong phú. Việc “sao chép tài liệu” theo nghĩa tiêu cực như đạo văn, sao chép các luận án, luận văn, đồ án trở nên phổ biến và đang là vấn nạn. Ở qui mô rộng hơn, các thư viện điện tử ngày càng nhiều, một tài liệu có thể được phát hành trên internet nhiều lần trong những thư viện điện tử khác nhau, trên các trang web khác nhau. Làm thế nào để phát hiện sự sao chép tài liệu theo nghĩa tiêu cực? Làm thế nào ngăn chặn việc sao chép trái phép, đạo văn, đạo nhạc, đạo luận văn, đồ án? Chủ đề này đã được nghiên cứu từ khoảng hơn 10 năm qua. Hiện tại, đã có một số giải pháp cho việc phát hiện sao chép và một vài công cụ phần mềm cho phép phát hiện một tài liệu (gọi là văn bản kiểm tra) có sao chép từ một tập hợp các tài liệu nguồn hay không. Tập hợp các tài liệu nguồn có thể là đóng- tức là các tài liệu tập hợp trước trong một thư viện điện tử- hoặc là mở, chẳng hạn như tập các tài liệu văn bản trên internet. Đã 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 hay 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, các phương pháp so khớp chuỗi chỉ có hiệu quả nếu việc sao chép là “nguyên văn”. Do vậy một yêu cầu cấp bách đặt ra là làm thế nào để phát hiện việc sao chép khi có sửa đổi đôi chút như thay thế một số từ bằng từ đồng nghĩa hay thay đổi một ít trong thứ tự các câu trong văn bản. Chính vì vậy, đề tài “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 chọn làm đề tài luận văn tốt nghiệp của tôi. 2. Mục tiêu của luận văn Vận dụng các phương pháp tính độ tương tự giữa từ với từ để tính độ tương đồng ngữ nghĩa giữa hai văn bản giúp phát hiện một văn bản có được sao chép từ văn bản kia hay không. 3. Đối tượng và nhiệm vụ của luận văn Đối tượng:  Tập các văn bản trong bộ dữ liệu mẫu.  Tập các tài liệu trên Internet. 4 Nhiệm vụ: Luận văn tập trung vào tính độ tương tự ngữ nghĩa văn bản dựa trên tập ngữ liệu có sẵn. Trong đó có tận dụng tối đa các đặc điểm của kho ngữ liệu, đến độ tương tự giữa từ với từ và tập các từ đồng nghĩa. 4. Phương pháp và nội dung nghiên cứu  Nghiên cứu lý thuyết về độ tương tự, các cách tính độ tương tự giữa từ với từ.  Nghiên cứu về kho ngữ liệu, hiện tượng từ đồng nghĩa.  Tìm hiều các cách tách từ trong văn bản tiếng Việt.  Nghiên cứu các phương pháp tính độ tương tự ngữ nghĩa văn bản dựa trên độ tương tự giữa từ với từ. 5. Kết cấu của luận văn Nội dung chính của luận văn gồm 4 chương:  Chương I: Khái niệm độ tương tự.  Chương II: Độ tương tự từ-từ.  Chương III: Độ tương tự văn bản-văn bản.  Chương IV: Tính độ tương tự ngữ nghĩa văn bản dựa vào độ tương tự giữa từ với từ. 5 CHƯƠNG I. KHÁI NIỆM ĐỘ TƯƠNG TỰ 1.1. Tổng quan về độ tương tự Nghiên cứu “sự tương tự” (thường ở dạng đối ngẫu của nó là “khoảng cách”) thuộc phạm vi toán học, chẳng hạn trong lý thuyết tôpô và xấp xỉ; nhưng trong khoa học máy tính và các ứng dụng máy tính có phần khác. Trong khoa học máy tính, phép tính xấp xỉ thường được sử dụng theo một lối không có tính hệ thống (non-systematic) và không theo thể thức (ad-hoc). Trong ngữ cảnh này, khái niệm “sự tương tự” xuất hiện ở nhiều dạng, diễn xuất, và nhiều ứng dụng. Khái niệm “sự tương tự” có nhiều dạng khác nhau. Bất chấp những khác biệt, chúng đều có điểm chung: “sự tương tự” được sử dụng để so sánh hai (hay nhiều) đối tượng, hai hoàn cảnh, hai vấn đề, v.v… với nhiều nguyên do khác nhau. Luôn có mục đích nào đó với một phép so sánh như thế, bởi vì một hành động tiếp sau đó được thực hiện và cuối cùng thì một vấn đề nào đó phải được giải quyết. Vì lý do đó, hai đối tượng được đem so sánh giữ những vai trò khác nhau. Đối tượng thứ nhất đang được xem xét và được gọi là vấn đề (problem). Đối tượng thứ hai là đã biết và đã lưu; thường được gọi là bản mẫu (prototype) hay tình huống (case). “Sự tương tự” được sử dụng một cách gián tiếp trong quá trình giải quyết vấn đề, nổi bật là các phương pháp dựa trên phép loại suy (Analogy), lập luận dựa theo tình huống (Case-Based Reasoning), và nhận dạng mẫu (Pattern Recognition). Chúng có liên hệ với nhau và không có ranh giới rõ ràng giữa phép loại suy và các phương pháp khác. Ở đây, chúng ta chấp nhận quan điểm rằng phép loại suy gắn với các đối tượng thuộc nhiều lĩnh vực, trong khi CBR và nhận dạng mẫu sử dụng độ tương tự trong cùng một lĩnh vực. Một khác biệt cơ bản giữa CBR và phép loại suy là CBR thường (không phải luôn luôn) xét các đối tượng được mô tả theo cùng ngôn ngữ mô tả và thuật ngữ, trong khi phép loại suy có thể xét các lý thuyết hoàn toàn khác nhau. Dưới đây là một số ngữ cảnh cần đến “sự tương tự”:  Lập luận dựa theo tình huống (CBR) là một cách rất tổng quát để giải quyết vấn đề bằng cách sử dụng các kinh nghiệm trước đó. Những kinh nghiệm này được ghi lại trong một cơ sở dữ liệu gọi là kho tình huống. Ý tưởng bên dưới nhằm tái sử dụng những kinh nghiệm là: “Nếu hai vấn đề là tương tự thì chúng có các giải pháp tương tự”. CBR cũng có một giả định cơ bản là luôn tồn tại kinh nghiệm. Với điều kiện này, CBR có thể được áp dụng cho hầu hết các dạng ứng dụng. Thường thì có rất nhiều kinh nghiệm được lưu trữ và một khía cạnh thiết yếu là nhanh chóng tìm ra những kinh nghiệm hữu ích (bài toán thu hồi). 6  Trong cơ sở dữ liệu (Databases), “sự tương tự” cũng có liên quan với tìm kiếm, và có quan hệ nào đó với CBR. Đa phần cơ sở dữ liệu cần so trùng chính xác. Các phép đo độ tương tự giữ một vai trò trong một số cơ sở dữ liệu đặc biệt như cơ sở dữ liệu không gian (spatial database) hay cơ sở dữ liệu địa lý (geo- database).  Nhận dạng mẫu (Pattern Recognition) cũng là một vấn đề rất tổng quát, nghiên cứu sự vận hành và thiết kế các hệ thống nhận dạng các mẫu trong dữ liệu. Vì những mẫu như thế không phải lúc nào cũng giống hệt nhau, khái niệm “sự tương tự” thường đóng một vai trò quyết định.  Trong phân loại (Classification) và phân tích cụm (Cluster Analysis), “sự tương tự” được sử dụng để phân loại các đối tượng: các đối tượng tương tự thuộc về cùng một lớp/cụm, các đối tượng không tương tự thuộc về các lớp/cụm khác nhau.  Trong diễn xuất hình ảnh (Image Interpretation), các hình ảnh được diễn xuất theo ý nghĩa của chúng và chúng được so sánh với nhau. Ví dụ, một ảnh y khoa thực tế và một ảnh không có bệnh lý nào đó được so sánh với nhau; độ tương tự giữa những ảnh này được sử dụng để cho biết ảnh thực kia có chứa bệnh lý hay không. Xác minh hình ảnh (Image Identification) cũng thuộc về lĩnh vực này.  Trong tâm lý học nhận thức và xã hội (Cognitive and Social Psychology), “sự tương tự” là cái gì đó chủ quan; ám chỉ thái độ, giá trị, sở thích, và cá tính giữa những con người tương xứng mức độ nào. Có nhiều dạng mô hình về sự tương tự trong tâm lý học, bốn mô hình nổi bật là hình học (geometric), đặc tính (featural), dựa trên canh lề (alignment-based), và biến đổi (transformational).  Trong lĩnh vực an ninh, quốc phòng để xác định đối tượng ảnh khi muốn xác định vân tay, kiểm tra những băng đĩa mang những nội dung cần kiểm soát,… Độ đo tương tự là một trong những phương pháp tốt để máy tính phân biệt được các văn bản qua nội dung của chúng. Xét trên khía cạnh nào đó, độ tương tự càng lớn, hai văn bản giống nhau càng nhiều. 1.2. Khái niệm độ tương tự Độ tương tự là một khái niệm quan trọng và đã được sử dụng rộng rãi. Các định nghĩa trước đây về độ tương tự được trói buộc trong một ứng dụng cụ thể hoặc một dạng thể hiện của tri thức. Nhiều độ đo độ tương tự đã được đưa ra, chẳng hạn như nội dung thông tin (Resnik, 1995b), độ đo thông tin chung (mutual information – Hindle, 1990), độ đo 7 dựa trên khoảng cách (Lee et al., 1998; Rada et al 1998) và mô hình đặc trưng tương phản (Tversky, 1977). McGill etc đã khảo sát và so sánh 67 độ đo độ tương tự đã sử dụng trong tìm kiếm thông tin (McGill et al., 1979). Một vấn đề trong độ đo độ tương tự trước đây là mỗi một trong số chúng bị trói buộc trong một ứng dụng cụ thể hoặc đảm đương một mô hình cụ thể. Ví dụ độ đo về độ tương tự giữa các khái niệm dựa trên khoảng cách (Lee et al., 1989; Rada et al., 1989) thừa nhận rằng phạm vi được thể hiện trong một mạng. Nếu một tập các tài liệu không được thể hiện như một mạng, độ đo dựa trên khoảng cách sẽ không được áp dụng. Hệ số dice (súc sắc) và hệ số cosin chỉ có thể được áp dụng khi các đối tượng được thể hiện như các vecto đặc trưng bằng số. Một vấn đề khác với các độ đo độ tương tự trước đây là các điều giả định cơ bản của chúng thường không ở trạng thái rõ ràng. Ngoài việc biết các giả định này, không thể tạo ra sự tranh luận về mặt lý thuyết hay phản đối bất cứ độ đo cụ thể nào. Hầu hết tất cả các so sánh và đánh giá của các độ đo độ tương tự trước đây đều dựa trên kết quả do kinh nghiệm. Định nghĩa độ tương tự trong phần sau đạt được 2 mục đích:  Tính phổ biến (universality): Chúng ta định nghĩa độ tương tự trong thuật ngữ lý thuyết thông tin. Điều đó có thể được áp dụng miễn là phạm vi có một mô hình xác suất. Từ đó lý thuyết xác suất có thể được tích hợp với nhiều loại thể hiện của tri thức, chẳng hạn như thứ tự logic (Bacchus, 1988) và mạng ngữ nghĩa (Pearl, 1988), định nghĩa của chúng ta về độ tương tự có thể được áp dụng cho nhiều loại lĩnh vực mà mỗi độ đo có một giả định riêng trước. Hơn nữa, tính phổ biến của định nghĩa còn cho phép độ đo được sử dụng trong lĩnh vực không có giả định trước, chẳng hạn như độ tương tự giữa các giá trị có thứ tự.  Tính giả định (Theoretical Justification): độ đo độ tương tự không được định nghĩa một cách trực tiếp bởi công thức. Hơn nữa, nó được phân phát từ một tập các giả định về độ tương tự. Mặt khác, nếu các giả định được cho là hợp lý, độ đo độ tương tự cần thiết phải xảy ra. 1.2.1. Định nghĩa độ tương tự (Definition of Similarity) Mục đích của chúng ta là cung cấp định nghĩa chính thức về khái niệm độ tương tự, đầu tiên chúng ta đưa ra các trực giác (intuitions) về độ tương tự.  Trực giác 1: Độ tương tự giữa A và B có liên quan tới sự tương đồng của chúng. Sự tương đồng càng nhiều, độ tương tự càng lớn. 8  Trực giác 2: Độ tương tự giữa A và B có liên quan tới những sự khác biệt giữa chúng. Càng nhiều sự khác biệt, độ tương tự càng thấp.  Trực giác 3: Độ tương tự lớn nhất giữa A và B đạt được khi A và B giống hệt nhau (đồng nhất - identical) 1.2.2. Độ tương tự giữa các giá trị có thứ tự ưu tiên (ordinal values) Rất nhiều các đặc trưng có các giá trị ưu tiên. Ví dụ, thuộc tính “chất lượng” có thể mang một trong các giá trị sau: “excellent”, “good”, “average”, “bad”, “awful”. Không có một định nghĩa nào ở trên cung cấp độ đo độ tương tự giữa hai giá trị có thứ tự. Bây giờ chúng ta sẽ chỉ ra cách định nghĩa của chúng ta có thể được áp dụng. Nếu “chất lượng của X là excellent” và “chất lượng của Y là average”, sự mô tả cụ thể nhất của cả X và Y là “chất lượng của X và Y ở giữa hai giá trị excellent và average”. Do đó, sự tương đồng giữa hai giá trị ưu tiên được giới hạn bên trong giữa chúng. Giả sử phân phối của thuộc tính “chất lượng” được nêu ra như ở hình 1. Sau đây là 4 ví dụ tính độ tương tự: 2 log P(excellent good)(excellent, good) = log (excellent) + log P(good) sim P   2 log(0.05 0.10) 0.72 log 0.05 log 0.10      2 log P(good erage)(good, average) = log ( erage) + log P(good) avsim P av   2 log(0.10 0.50) 0.34 log 0.10 log 0.50      2 log P(excellent good average)(excellent, average) = log (excellent) + log P(average) sim P    2 log(0.05 0.10 0.50) 0.23 log 0.05 log 0.50       2 log P(good erage bad)(good, bad) = log ( ood) + log P(bad) avsim P g    2 log(0.10 0.50 0.20) 0.11 log 0.10 log 0.20       9 Kết quả chỉ ra rằng độ tương tự giữa “excellent” và “good” cao hơn độ tương tự giữa “good” và “average”, độ tương tự giữa “excellent” và “average” cao hơn độ tương tự giữa “good” và “bad”. 1.2.3. Độ tương tự chuỗi (String Similarity-A case study) Xem xét công việc tìm kiếm từ một danh sách từ các từ mà được xuất phát từ cùng một gốc như là một từ cho sẵn. Ví dụ, cho trước từ “eloquently”, mục đích của chúng ta là để tìm ra các từ liên quan khác như “ineloquent”, “ineloquently”, “eloquent” và “eloquence”. Để làm điều đó, ta có thể định nghĩa độ đo tương tự giữa hai chuỗi và xếp hạng các từ trong danh sách từ theo thứ tự giảm dần của độ tương tự với từ cho sẵn. Những từ xuất phát từ cùng một từ gốc nên xuất hiện sớm trong bảng xếp hạng. Chúng ta tiến hành thử nghiệm với 3 độ đo sau:  Độ đo đầu tiên được định nghĩa như sau: 1( , ) 1 ( , )edit sim x y editDist x y   ở đó editDist(x,y) là số kí tự nhỏ nhất cần chèn vào và xóa đi để chuyển từ xâu này thành xâu khác.  Độ đo độ tương tự thứ hai là dựa trên số bộ ba khác nhau trong hai xâu: 1( , ) 1 ( ) ( ) 2 ( ) ( )tri sim x y tri x tri y tri x tri y       Hình 1: Ví dụ phân phối của các giá trị có thứ tự ưu tiên 10 ở đó tri(x) là tập các bộ ba trong x. Ví dụ tri(eloquent) = {elo, loq, oqu, que, ent}  Độ đo độ tương tự thứ ba là dựa trên giả định là xác suất của một bộ ba xảy ra trong một từ là độc lập với các bộ ba khác trong từ đó. ( ) ( ) ( ) ( ) 2 log ( ) ( , ) log ( ) log ( ) t tri x tri y t tri x t tri y P t sim x y P t P t           1.3. Độ tương tự ngữ nghĩa Độ tương tự ngữ nghĩa là một khái niệm ở đó tập các tài liệu hoặc các thuật ngữ trong một danh sách các thuật ngữ được gán một tỷ lệ dựa trên sự giống nhau về nội dung ý nghĩa của chúng. Độ đo độ tương tự ngữ nghĩa gần đây được áp dụng và phát triển trong rất nhiều lĩnh vực như trong y học (so sánh các gen), trong phân lớp văn bản (các văn bản tương tự nhau thì cùng thuộc một lớp),… Mỗi lĩnh vực khác nhau có các cách để tính độ tương tự ngữ nghĩa khác nhau. Sau đây chúng ta sẽ tìm hiểu các phương pháp tính độ đo tương tự từ-từ và độ đo tương từ giữa văn bản-văn bản. 11 CHƯƠNG II. ĐỘ TƯƠNG TỰ TỪ-TỪ 2.1. Khái niệm từ, thuật ngữ 2.1.1. Từ và cấu trúc từ của tiếng Việt 2.1.1.1. Định nghĩa từ Khái niệm từ nghe rất thông dụng dễ hiểu nhưng định nghĩa chính xác thế nào thì không đơn giản. Từ trước tới nay cũng có nhiều định nghĩa được đưa ra, tất cả đều đúng nhưng chưa hoàn chỉnh. Dưới đây, tôi nêu ra một số định nghĩa về từ. Thời Hy Lạp cổ đại, trường phái ngôn ngữ Alexandre định nghĩa: “Từ là đơn vị nhỏ nhất trong chuỗi lời nói”. Theo E.Sapir: “Từ là một đoạn nhỏ nhất có ý nghĩa, hoàn toàn có khả năng độc lập và bản thân có thể làm thành câu tối giản”. Còn với những nhà ngôn ngữ học tiếng Việt, thì theo Lê Văn Lý: “Từ là một tín hiệu ngữ âm có thể cấu tạo bằng một âm vị hay sự kết hợp với âm vị, mà sự phát âm chỉ tiến hành trong một lần, hoặc là một âm tiết mà chữ viết biểu thị bằng một đơn vị tách rời có thể hiểu được”. Theo Nguyễn Kim Thản thì “Từ là đơn vị cơ bản của ngôn ngữ, có thể tách khỏi các đơn vị khác của lời nói để vận dụng một cách độc lập và là một khối hoàn chỉnh về mặt ý nghĩa và cấu tạo”. Quan niệm của ông về “đơn vị cơ bản” là những đơn vị có số lượng hữu hạn để thông báo, trao đổi tư tưởng cho nhau. Đơn vị này phải có ý nghĩa, và khi sử dụng, người dùng phải có ý thức về nó. Chính vì thế, từ không thể là câu, và không thể là âm tiết (vì nhiều khi âm tiết không có nghĩa và khi sử dụng, người dùng không ý thức về nó). Có người lại cho rằng “Từ là đơn vị nhỏ nhất có nghĩa, có kết cấu vỏ ngữ âm bền vững, hoàn chỉnh, có chức năng gọi tên, được vận dụng độc lập, tái hiện tự do trong lời nói để tạo câu”. Ví dụ: nhà, người, áo, nếu, sẽ, thì, đường sắt, sân bay, dạ dày, đen sì, v.v.. 2.1.1.2. Cấu trúc từ của tiếng Việt Từ tiếng Việt không giống với ngôn ngữ phương Tây khác là không thể tách để xác định từ loại. Từ trong tài liệu tiếng Việt có thể là từ đơn (từ có cấu tạo từ một âm tiết) hoặc từ ghép (từ có cấu tạo từ hai âm tiết trở lên. Theo như thống kê trên trang thì độ dài của một từ tiếng Việt được thể hiện trong bảng: Độ dài của từ Tần số Tỉ lệ % 1 8933 12.2 2 48995 67.1 12 3 5727 7.9 4 7040 9.7 ≥ 5 2301 3.1 Tổng cộng 72994 100 Bảng 1: Tấn suất xuất hiện độ dài từ tiếng Việt trên trang Vdict.com 2.1.2. Nghĩa của từ Nghĩa của từ là một khái niệm đã được nêu ra từ lâu và cũng đã có nhiều cách hiểu, nhiều định nghĩa khác nhau. Nghĩa của từ cũng phản ánh những đặc trưng chung, khái quát của sự vật, hiện tượng do con người nhận thức được trong đời sống thực tiễn tự nhiên và xã hội. Tuy nhiên, nó có thể chưa phải là kết quả của nhận thức đã tiệm cận đến chân lí khoa học. Vì thế, sự vật, hiện tượng nào mà càng ít được nghiênc cứu, phám phá thì nhận thức về nó được phản ánh trong nghĩa của từ gọi tên nó càng xa với khái niệm khoa học. Việc xác định nghĩa của từ trong văn bản là một trong những thách thức lớn nhất trong xử lý ngôn ngữ tự nhiên. Nghĩa của từ chưa biết thường được suy ra từ văn cảnh sử dụng chúng. Sự nhận dạng các từ đồng nghĩa là bước khởi đầu trong việc học định nghĩa một từ. 2.1.3. Thuật ngữ (terms) Thuật ngữ: là các từ khóa có nghĩa liên quan đến một lĩnh vực nào đó, ví dụ: “máy tính”, “công nghệ phần mềm”, “tính toán song song”. Các thuật ngữ này thuộc về lĩnh vực “tin học”. Một thuật ngữ có thể có nhiều từ. Ví dụ: Thuật ngữ “công nghệ” gồm 2 từ “công” và “nghệ”, khi tách chúng ra thì 2 từ này không có ý nghĩa gì cả. 2.2. Từ đồng nghĩa Từ đồng nghĩa không phải là những từ trùng nhau hoàn toàn về nghĩa. Chúng nhất định có những dị biệt nào đó bên cạnh sự tương đồng (mặc dù phát hiện sự dị biệt đó không phải lúc nào cũng dễ dàng). Chính sự dị biệt đó lại là lí do tồn tại và làm nên những giá trị khác nhau giữa các từ trong một nhóm từ đồng nghĩa. Rõ ràng tính đồng nghĩa có những mức độ khác nhau, và ta có thể nêu quan niệm như sau: Từ đồng nghĩa là những từ tương đồng với nhau về nghĩa, khác nhau về âm thanh và có phân biệt với nhau về một vài sắc thái ngữ nghĩa hoặc sắc thái phong cách nào đó, hoặc đồng thời cả hai. 13 Ví dụ: - start, commence, begin (trong tiếng Anh) - cố, gắng, cố gắng (trong tiếng Việt) là những nhóm từ đồng nghĩa. Những từ đồng nghĩa với nhau tập hợp thành một nhóm gọi là nhóm đồng nghĩa. Trong các ví dụ vừa nêu, ta có các nhóm đồng nghĩa của từng ngôn ngữ tương ứng. Những từ đồng nghĩa với nhau không nhất thiết phải tương đương với nhau về số lượng nghĩa, tức là các từ trong một nhóm đồng nghĩa không nhất thiết phải có dung lượng nghĩa bằng nhau: Từ này có thể có một hoặc hai nghĩa, nhưng từ kia có thể có tới dăm bảy nghĩa. Thông thường, các từ chỉ đồng nghĩa ở một nghĩa nào đó. Chính vì thế nên một từ đa nghĩa có thể tham gia vào nhiều nhóm đồng nghĩa khác nhau: Ở nhóm này nó tham gia với nghĩa này, ở nhóm khác nó tham gia với nghĩa khác. Ví dụ: Từ “coi” trong tiếng Việt là một từ đa nghĩa. Tuỳ theo từng nghĩa được nêu lên để tập hợp các từ, mà “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à Trong mỗi nhóm từ đồng nghĩa thường có một từ mang nghĩa chung, được dùng phổ biến và trung hoà về mặt phong cách, được lấy làm cơ sở để tập hợp và so sánh, phân tích các từ khác. Từ đó gọi là từ trung tâm của nhóm. Ví dụ trong nhóm từ “yếu, yếu đuối, yếu ớt” của tiếng Việt, từ “yếu” được gọi là từ trung tâm. Tuy nhiên, việc xác định từ trung tâm của nhóm không phải lúc nào cũng dễ và đối với nhóm nào cũng làm được. Nhiều khi ta không thể xác định một cách dứt khoát được theo những tiêu chí vừa nêu trên, mà phải dựa vào những tiêu chí phụ như: tần số xuất hiện cao (hay được sử dụng) hoặc khả năng kết hợp rộng. Chẳng hạn, trong các nhóm từ đồng nghĩa tiếng Việt như: hồi, thuở, thời; hoặc chờ, đợi; hoặc chỗ, nơi, chốn,... rất khó xác định từ nào là trung tâm. Tập hợp đủ các nhóm từ đồng nghĩa, phân tích cho hết được những nét giống nhau, khác nhau giữa các từ trong mỗi nhóm, luôn luôn làm mong muốn của những người nghiên cứu và xử lí vấn đề từ đồng nghĩa. 14 Nhận biết để tập hợp, phân tích thấu đáo các nhóm đồng nghĩa sẽ giúp cho người ta sử dụng được chuẩn xác và tinh tế hơn, phù hợp với tâm lí và thói quen của người bản ngữ hơn. Điều đó rất quan trọng đối với việc dạy và học tiếng. 2.3. Các cách tiếp cận xử lý tài liệu theo ngữ nghĩa Trong xử lý ngôn ngữ tự nhiên, bài toán gán nhãn ngữ nghĩa hay còn gọi là “khử sự nhập nhằng ngữ nghĩa của từ” là bài toán khó khăn nhất và cũng là bài toán trọng tâm mà đến nay trên thế giới vẫn chưa giải quyết ổn thỏa. Hiện nay, có rất nhiều mô hình với nhiều hướng tiếp cận khác nhau, chủ yếu là: 2.3.1. Dựa trên trí tuệ nhân tạo (AI-based) Đây là cách tiếp cận sớm nhất (1960) với những lý thuyết rất hay về mạng ngữ nghĩa, khung ngữ nghĩa và các ý niệm nguyên thủy và các quan hệ như IS-A, PART- OF…Tuy nhiên, do hầu hết các tri thức về ngữ nghĩa trong cách tiếp cận này đều được xây dựng bằng tay, vì vậy các mô hình đều dừng lại ở mức độ biểu diễn trên một vài câu. Vấn đề khó khăn của cách tiếp cận này là thiếu tri thức. 2.3.2. Dựa trên Cơ sở tri thức (Knowledge-based) Vào đầu thập niên 80, người ta đã chuyển sang hướng khai thác tri thức tự động từ các từ điển điện tử (MRD: Machine – Readable Dictionaries) như các từ điển đồng nghĩa…để có thể phần nào khắc phục hạn chế của hướng tiếp cận dựa trên trí tuệ nhân tạo (thiếu tri thức). Kết quả của hướng tiếp cận này là sự ra đời của mạng WordNet – Một cơ sở tri thức khổng lồ về ngữ nghĩa theo hướng liệt kê nét nghĩa. Tuy nhiên, các cơ sở tri thức nói trên cũng chỉ là những nguồn thông tin để hệ thống chọn nghĩa tham khảo, còn chọn thông tin nào trong số những thông tin có liên quan đó thì ta phải tự xác định trong từng trường hợp cụ thể. 2.3.3. Dựa trên ngữ liệu (Corpus-based) Hướng tiếp cận này sẽ rút ra các qui luật xử lý ngữ nghĩa (bằng thống kê, bằng máy học,…) từ những kho dữ liệu lớn đã có sẵn và áp dụng các luật này cho trường hợp mới. Thực ra, cách tiếp cận này đã được nêu ra rất sớm (1940), nhưng do nguồn dữ liệu hạn chế, thiết bị xử lý chưa hiện đại nên không có điều kiện phát triển. Mãi tới thập niên 1990, khi mà công nghệ phát triển mạnh, đã có thể vượt qua được khó khăn của mình, cách tiếp cận này được hồi sinh và phát triển mạnh tới ngày nay. Hiện nay, cách tiếp cận dựa trên ngữ liệu kết hợp với tri thức có sẵn là hướng tiếp cận đang được nhiều nhà ngôn ngữ học – máy tính quan tâm. 15 2.4. Độ tương tự ngữ nghĩa từ-từ dựa trên cơ sở tri thức (từ điển WordNet) 2.4.1. Khái quát về từ điển WordNet Wordnet là một cơ sở dữ liệu tri thức từ vựng học được thiết kế dựa trên những lý thuyết về ngôn ngữ tâm lý theo cách liên tưởng từ ngữ của con người. WordNet được tổ chức dựa theo các quan hệ ngữ nghĩa bởi vì một quan hệ ngữ nghĩa là một quan hệ giữa các nghĩa và các nghĩa có thể được đại diện bởi nhiều synset. Và chúng ta có thể xem những quan hệ ngữ nghĩa như là những con trỏ giữa các synset. Đó là đặc tính của quan hệ ngữ nghĩa và chúng có tác động qua lại với nhau. Một từ bất kỳ có thể có nhiều nghĩa (word meaning) và khi đó mỗi nghĩa của nó sẽ thuộc vào những tập đồng nghĩa khác nhau. Ngược lại, mỗi tập đồng nghĩa lại có thể chứa một hoặc nhiều hơn một từ khác nhau. Xét ví dụ sau: Ví dụ: Khi tìm từ letter trong WordNet ta sẽ được kết quả như sau:  The noun letter has 4 senses: i. Letter, missive: a written message addressed to a person or organization; “wrote an indignant letter to the editor” ii. Letter, letter of the alphabet, alphabetic character: the conventional characters of the alphabet used to represent speech; “his grandmother tauch him his letter”. iii. Letter: a strictly literal interpretation (as distinct from the intention); “he followed instructions to the letter ”; “he obeyed the letter of the law”. iv. Letter, varsity letter: an award earned by participation in a school sport; “he won letters in three sports ”.  Trong WordNet danh từ letter có 4 nghĩa thuộc vào 4 tập đồng nghĩa: i. Tập đồng nghĩa thứ nhất gồm: letter, missive với nghĩa tiếng Việt tương ứng là “lá thư”, “thư tín”. ii. Tập đồng nghĩa thứ hai gồm: letter, letter of the alphabet, alphabetic character với nghĩa tiếng Việt tương ứng là “ký tự”, “chữ” hay “chữ cái”. iii. Tập thứ ba chỉ gồm một từ: letter với nghĩa tiếng Việt là “nghĩa chật hẹp”, “nghĩa mặt chữ”. 16 iv. Tập cuối cùng gồm hai từ: letter, varsity letter với nghĩa tiếng Việt tương ứng là “huy hiệu”, “danh hiệu” tặng cho những sinh viên có thành tích thể thao đặc biệt ở trường. Hình 2: Một phần từ điển WordNet 2.4.2. Độ tương tự từ-từ dựa trên từ điển WordNet Một số độ đo trình bày dưới đây được nghiên cứu dựa trên từ điển phân cấp WordNet. Tất cả các độ đo này đều có đầu vào là một cặp khái niệm, giá trị trả ra là mối quan hệ ngữ nghĩa của chúng. Chúng ta có thể dễ dàng chuyển sang độ tương tự từ-từ bằng cách lựa chọn bất cứ cặp từ cho sẵn nào mà ý nghĩa của chúng dẫn tới độ tương tự cao nhất giữa khái niệm-khái niệm. (1) Leacock và Chodorow Độ tương tự được xác định bởi công thức: log 2Lch lengthSim D    Trong đó length là độ dài của đường đi ngắn nhất giữa hai khái niệm sử dụng node- counting D là độ sâu của hệ thống cây phân cấp (độ sâu lớn nhất của sự phân loại) (2) Lesk Độ tương tự giữa hai khái niệm được xác định như một hàm chồng khít giữa các định nghĩa tương ứng, cũng như được cung cấp bởi một từ điển. Ứng dụng của Lesk không được hạn cho mạng ngữ nghĩa, và nó có thể được dùng cùng với bất cứ từ điển nào cung cấp định nghĩa từ. (3) Wu và Palmer 17 Độ tương tự được đo bởi độ sâu của hai khái niệm trong WordNet và độ sâu của LCS (Least common subsumer) (nút cha chung gần nhất của cả hai khái niệm đó). Công thức như sau: wup 1 2 2 ( ) ( ) ( ) depth LCSsim depth concept depth concept    (4) Resnik Mức tương tự nhau của hai khái niệm có thể được đánh giá bằng mức độ chia sẻ thông tin giữa chúng. Resnik định nghĩa độ tương tự giữa hai khái niệm là “hàm lượng thông tin” của cha chung gần nhất của chúng: Trả về nội dung thông tin (IC) của LCS của hai khái niệm: es ( )rsim IC LCS ở đó IC được xác định như sau: IC(c) = -logP(c) và P(c) là xác suất của một ví dụ của khái niệm c trong tập dữ liệu. (5) Lin Độ đo này lấy từ lý thuyết của ông về tính tương tự giữa hai đối tượng bất kỳ. Cũng gần giống như simjnc 1 2 2 ( ) ( ) ( )lin IC LCSsim IC concept IC concept    (6) Jiang và Conrath Phương pháp này cũng sử dụng khái niệm “hàm lượng thông tin” nhưng ở dạng xác suất có điều kiện: xác suất bắt gặp một synset con khi đã có một synset cha: 1 2 1 ( ) ( ) 2 ( )jnc sim IC concept IC concept IC LCS     Trên đây là 6 phương pháp tính độ tương tự từ-từ dựa trên từ điển WordNet. Tuy nhiên từ điển này là dành cho ngôn ngữ tiếng Anh. Hiện tiếng Việt của chúng ta chưa có bộ từ điển nào có cấu trúc đầy đủ như vậy. Do đó các phương pháp trên khó có thể áp dụng được cho từ tiếng Việt. 2.5. Độ tương tự ngữ nghĩa từ-từ dựa trên ngữ liệu Độ tương tự ngữ nghĩa dựa trên tập ngữ liệu (corpus) xác định mức độ tương tự giữa các từ bằng việc sử dụng thông tin xuất phát từ tập ngữ liệu lớn. Chúng ta xét một số phương pháp sau: 18 2.5.1. PMI (Pointwise Mutual Information) (Thông tin chung dựa trên điểm) PMI sử dụng dữ liệu đã tập hợp từ việc tìm kiếm thông tin (PMI-IR) được đưa ra bởi Turney 2001 như một độ đo không giám sát để đánh giá độ tương tự ngữ nghĩa của từ. Nó dựa trên các từ đồng xảy ra trên một tập ngữ liệu lớn (large corpora). Độ đo PMI-IR cho 2 từ w1 và w2 được tính như sau: 1 2 1 2 2 1 2 (w , w )IR(w , w ) log (w ) (w ) pPMI p p    2.5.2. LSA (Latent Semantic Analysis) (Phân tích ngữ nghĩa ẩn) Trong LSA, các từ đồng xảy ra trong tập corpus được nắm bắt (capture) bằng việc giảm số chiều bởi SVD (Singular Value Decomposition) của một ma trận T (ma trận từ-tài liệu) thể hiện tập corpus. Trong các thí nghiệm ở đây, chúng ta sẽ thực hiện SVD trên tập British National Corpus. SVD là thao tác trong đại số tuyến tính, cái có thể được áp dụng cho bất kỳ ma trận chữ nhật nào để tìm ra mối tương quan giữa hàng và cột. Trong trường hợp này, SVD phân tách ma trận T thành 3 ma trận. SVD có thể được xem là cách để vượt qua một số hạn chế của mô hình không gian vecto chuẩn (số chiều cao – Sparseness and high dimensionality). Thực tế, độ tương tự LSA được tính với số chiều thấp hơn, và mối quan hệ thứ hai giữa thuật ngữ- văn bản được khai thác. Độ tương tự trong không gian kết quả được đo bằng độ tương tự cosin. Chú ý rằng LSA cũng sinh ra một mô hình không gian vecto cho phép thể hiện sự đồng nhất (và so sánh) giữa các từ, tập các từ và các văn bản. 2.5.3. Phương pháp của Dekang Lin Phương pháp này do Dekang Lin (1997) đề xuất trong bài báo “Automatic Retrieval and Clustering of Similar Words”. Kí hiệu (w, r, w’) là một bộ ba có từ trung tâm là w, từ phụ thuộc là w’ và hai từ này được quan hệ với nhau thông qua quan hệ r. Kí hiệu ||w, r, w’|| là số lượng của một loại bộ ba (w, r, w’). Nếu một giá trị trong số ba giá trị w, r hoặc w’ được thay thế bằng dấu * thì giá trị đó là một giá trị xác định bất kì trong kho ngữ liệu. Ví dụ, || gia_đình, mod, *|| là số lượng bộ ba có từ trung tâm là gia_đình và quan hệ là mod, và ||*, *, *|| là tổng số bộ ba được trích từ kho ngữ liệu cú pháp. Một từ w được mô tả thông qua những bộ ba có từ w đó là từ trung tâm hay nó được mô tả thông qua các bộ ba có dạng (w, *, *). Sự tương đồng giữa hai từ được mô 19 tả thông qua những bộ ba mà có sự xuất hiện của một hoặc hai từ đó trong kho ngữ liệu. Ví dụ : từ giàu được mô tả thông qua các bộ ba sau. bộ ba số lượng || giàu , mod-of , chuyện || 1 || giàu , mod-of , cuộc_đời || 1 || giàu , mod-of , em || 1 || giàu , mod-of , hình_ảnh || 1 || giàu , mod-of , hòn || 3 || giàu , mod-of , kính || 1 || giàu , mod-of , kịch || 1 || giàu , mod-of , người || 5 || giàu , mod-of , nhà || 7 || giàu , mod-of , quốc_gia || 1 || giàu , mod-of , tay || 1 Bảng 2 : Mô tả các bộ ba của từ giàu Giả sử rằng sự xuất hiện của các loại bộ ba là độc lập với nhau. Khi đó lượng thông tin chứa trong mô tả của một từ là tổng thông tin chứa trong tất cả các bộ ba có phần tử trung tâm là từ đó. Công thức tính lượng thông tin chứa trong một bộ ba bất kì (w, r, w’) được tính bằng tần xuất xuất hiện của bộ ba đó trong kho ngữ liệu cú pháp hoặc trong trường hợp bộ ba (w, r, w’) không tồn tại trong kho ngữ liệu thì ta có thể tính lượng thông tin đó thông qua các bộ ba chứa một trong các thành phần của bộ ba nói trên trong toàn bộ kho ngữ liệu, hay trong trường hợp một bộ ba tồn tại thì lượng thông tin trong bộ ba trên được định nghĩa là ( , , ) (|| , , ||) /(|| *,*,* ||)P w r w w r w  20 Trong trường hợp bộ ba không tồn tại trong kho ngữ liệu thu được thì nó có thể tính thông qua các bộ ba khác trong kho ngữ liệu, áp dụng công thức xác suất bayes với giả thiết A và C là các biến ngẫu nhiên độc lập với nhau ta có : P(A, B, C) = P(A|B, C) P(B, C) = P(A|B, C) P(C|B) P(B) = P(A|B) P(C|B) P(B) với các biến cố ngẫu nhiên A: một từ được chọn ngẫu nhiên w. B: một kiểu phụ thuộc được chọn ngẫu nhiên r. C: một từ được chọn ngẫu nhiên w’ trong đó ( | ) ( , ,* ) /( *, ,* )P A B w r r P P P P ( | ) ( *, , ) /( *, ,* )P C B r w r P P P P ( ) ( *, ,* ) /( *,*,* )P B r P P P P Khi có các giá trị trên ta có thể tính I(w, r, w’) là giá trị mô tả lượng thông tin chứa trong một bộ ba (w, r, w’). I (w, r, w’)= - log(P(A|B) P(C|B) P(B)) = - (- log(P(A, B, C))) hay ( , , ) log( , , *, ,* ) /( , ,* *, , )I w r w w r w r w r r w    P P P P P P P P Chú ý rằng I(w, r, w’) là lượng thông tin tương hỗ giữa w và w’ Ta định nghĩa tập T(w) là tập các cặp (r, w’) sao cho giá trị log (P(A, B, C)) dương. Khi đó độ tương tự sim(w1, w2) giữa 2 từ w1 và w2 được định nghĩa như sau:       1 2 1 2 1 2( , ) ( ) ( ) 1 2 1 2( , ) ( ) ( , ) ( ) ( , , ) ( , , ) ( , ) ( , , ) ( , , ) r w T w T w r w T w r w T w I w r w I w r w sim w w I w r w I w r w           21 CHƯƠNG III. ĐỘ TƯƠNG TỰ VĂN BẢN-VĂN BẢN 3.1. Xử lý văn bản tiếng Việt 3.1.1. Một số kết quả đã đạt được Tiếng nói và chữ viết là hai yếu tố cơ bản nhất của bất kỳ ngôn ngữ nào. Trong sự phát triển của công nghệ thông tin (CNTT) ở Việt Nam, một số việc liên quan đến “tiếng Việt” đã được làm và ít nhiều có kết quả ban đầu: (a) Trước hết là các bộ gõ chữ Việt và thành công của việc đưa được bộ mã chữ Việt vào bảng mã Unicode, cũng như việc chọn Unicode cho bộ mã chuẩn tiếng Việt (nhân đây cũng xin nói thêm, do chưa ý thức về chuẩn, rất nhiều cán bộ CNTT, nhiều cơ quan nhà nước vẫn chưa chịu đổi thói quen cũ để dùng bộ mã chuẩn Unicode, một việc rất quan trọng của xử lý tiếng Việt). Bảo tồn chữ Nôm trên máy tính cũng là một việc đầy nỗ lực và nhiều ý nghĩa được nhiều người theo đuổi lâu nay, cần được nhà nước tiếp tục ủng hộ lâu dài ( (b) Tiếp theo có thể kể đến các chương trình nhận dạng chữ Việt in (OCR: optical character recognition), như hệ VnDOCR của Viện Công nghệ Thông tin, Viện Khoa học và Công nghệ Việt Nam. Các chương trình nhận dạng chữ in nhằm chuyển các tài liệu in trên giấy thành các tài liệu điện tử (dưới dạng các tệp văn bản trên máy tính) (c) Các phần mềm hỗ trợ việc sử dụng tiếng nước ngoài, tiêu biểu là các từ điển song ngữ trên máy tính, thí dụ như các từ điển điện tử của Lạc Việt đã được dùng rộng rãi trên máy tính để tra cứu từ Anh-Việt, Việt-Anh. Điều ta cần phân biệt là các từ điển điện tử này dành cho con người sử dụng, khác với từ điển điện tử dành cho máy tính sử dụng trong xử lý ngôn ngữ tự nhiên (sẽ được đề cập ở phần sau). (d) Các nỗ lực trong việc làm các phần mềm dịch Anh-Việt, Việt-Anh, chẳng hạn như các hệ dịch EVTRAN và VETRAN. (e) Một loại việc nữa là Việt hóa các phần mềm mà gần đây tiêu biểu là kết quả Việt hóa Windows và Microsoft Office của Microsoft. Việc này có thể xem như việc “dịch” các thông báo tiếng Anh cố định trong các phần mềm thành các thông báo tiếng Việt. Các dữ liệu liên quan đến ngôn ngữ viết (văn bản) và nói (tiếng nói) đang dần trở nên kiểu dữ liệu chính con người có và lưu trữ dưới dạng điện tử. Với sự ra đời và phổ biến của Internet, của sách báo điện tử, của máy tính cá nhân,, của viễn thông, 22 của thiết bị âm thanh,…người người ai cũng có thể tạo ra dữ liệu văn bản hay tiếng nói. Vấn đề là làm sao ta có thể xử lý chúng, tức chuyển chúng từ các dạng ta chưa hiểu được thành các dạng ta có thể hiểu và giải thích được, tức là ta có thể tìm ra thông tin, tri thức hữu ích cho mình. Sau đây là một số bài toán tiêu biểu của xử lý ngôn ngữ với các mức độ khác nhau về xử lý và sử dụng ngôn ngữ tự nhiên của con người:  Nhận dạng tiếng nói (speech recognition): từ sóng tiếng nói, nhận biết và chuyển chúng thành dữ liệu văn bản tương ứng [Jelinek, 1998], [Jurafsky and Martin, 2000].  Tổng hợp tiếng nói (speech synthesis): từ dữ liệu văn bản, phân tích và chuyển thành tiếng người nói [Jelinek, 1998], [Jurafsky and Martin, 2000].  Nhận dạng chữ viết (optical character recognition, OCR): từ một văn bản in trên giấy, nhận biết từng chữ cái và chuyển chúng thành một tệp văn bản trên máy tính.  Dịch tự động (machine translation): từ một tệp dữ liệu văn bản trong một ngôn ngữ (tiếng Anh chẳng hạn), máy tính dịch và chuyển thành một tệp văn bản trong một ngôn ngữ khác (tiếng Việt chẳng hạn) [Dorr et al, 2000], [Nagao, 1989].  Tóm tắt văn bản (text summarization): từ một văn bản dài (mười trang chẳng hạn) máy tóm tắt thành một văn bản ngắn hơn (một trang) với những nội dung cơ bản [Mani and Maybury, 1999].  Tìm kiếm thông tin (information retrieval): từ một nguồn rất nhiều tệp văn bản hay tiếng nói, tìm ra những tệp có nội dung liên quan đến một vấn đề (câu hỏi) ta cần biết (hay trả lời) [Baeza-Yates and Riberio-Neto, 1999]. Điển hình của công nghệ này là Google, một hệ tìm kiếm thông tin trên Web, mà hầu như chúng ta đều dùng thường xuyên.  Trích chọn thông tin (information extraction): từ một nguồn rất nhiều tệp văn bản hay tiếng nói, tìm ra những đoạn bên trong một số tệp liên quan đến một vấn đề (câu hỏi) ta cần biết hay trả lời [Cohen and McCallum, 2003].  Phát hiện tri thức và khai phá dữ liệu văn bản (knowledge discovery and text data mining): từ những nguồn rất nhiều văn bản thậm chí hầu như không có quan hêj với nhau, tìm ra được những tri thức trước đấy chưa ai biết. Đây là một vấn đề rất phức tạp và đang ở giai đoạn đầu của các nghiên cứu trên thế giới [Berry, 2004], [Sirmakessis, 2004]. 23 Còn nhiều bài toán và công nghệ xử lý ngôn ngữ khác, như giao diện người máy bằng ngôn ngữ tự nhiên, các hệ hỏi đáp, các hệ sinh ra ngôn ngữ,… 3.1.2. Đặc trưng của cấu trúc ngữ pháp tiếng Việt Các đặc điểm trong câu của tiếng Việt:  Câu được cấu tạo đa thành phần, có câu đơn, câu ghép, câu tối giản.  Các câu được phân tách bằng các dấu chấm câu.  Câu hoàn chỉnh có hoặc không sử dụng các trạng từ, từ cảm thán (các từ dừng sẽ được loại bỏ khi phân tách để lọc thông tin)  Câu được hình thành từ các từ, hoặc các câu đơn.  Mỗi câu mang một ý nghĩa thông tin hoàn chỉnh. Với các tài liệu tiếng Anh, các từ được phân cách nhau bởi dấu cách. Việc xử lý phân tách từ từ các văn bản tiếng Anh tương đối dễ dàng. Trong tiếng Việt không thể phân tách được thành những từ riêng bởi dấu cách. Vì từ có thể gồm một, hai hoặc nhiều hơn số lượng âm tiết (số lượng từ ghép). Vì thế, việc tách từ để chính xác đòi hỏi giải thuật tách từ tốt. 3.2. Tách từ trong văn bản tiếng Việt Tách từ là một khó khăn chính trong việc xử lý văn bản theo ngữ nghĩa đối với các ngôn ngữ châu Á như tiếng Hoa, tiếng Nhật, tiếng Hàn và cả tiếng Việt. Mặc dù được viết bằng các ký tự Latinh mở rộng, tiếng Việt cũng có những đặc tính chung với các ngôn ngữ Đông Nam Á khác như khó xác định ranh giới giữa các từ và có các điểm khác biệt về ngữ âm, văn phạm và ngữ nghĩa so với các ngôn ngữ Ấn Âu. Do đó rất khó có thể áp dụng các kỹ thuật và hướng tiếp cận đã được nghiên cứu và thử nghiệm thành công trên các ngôn ngữ Ấn Âu cho tiếng Việt nếu không xây dựng thành công giải pháp cho việc tách từ trong văn bản tiếng Việt. Tuy nhiên, việc xác định ranh giới từ trong tiếng Việt lại là bài toán khó. Tại sao lại như vậy? Đơn vị cơ bản trong tiếng Việt là tiếng, không phải là từ. Từ trong tiếng Việt có một số đặc tính sau:  Từ ở dạng nguyên thể, hình thức và ý nghĩa của từ độc lập với cú pháp.  Từ được cấu trúc từ “tiếng”.  Từ bao gồm từ đơn (từ một tiếng) và từ phức (n-tiếng, với n < 5), bao gồm từ láy và từ ghép. 24 Trong khi đó, định nghĩa về từ trong tiếng Anh như sau: “Từ là một nhóm ký tự có nghĩa, được phân cách bởi ký tự khoảng trắng trong câu” (Từ điển Webster). Dưới đây là một số điểm khác biệt chính giữa tiếng Việt và tiếng Anh. Những đặc điểm này làm cho việc tách từ tiếng Việt trở nên khó khăn hơn. Đặc điểm Tiếng Việt Tiếng Anh Đơn vị cơ bản Tiếng Từ Tiền tố/Hậu tố Không có Có Từ loại Chưa được định nghĩa rõ (Not Unanimous) Được định nghĩa rõ Ranh giới từ Tổ hợp có nghĩa dựa vào ngữ cảnh của các tiếng Khoảng trắng hoặc dấu câu Bảng 3: Các điểm khác biệt chính giữa tiếng Việt và tiếng Anh 3.3. Các hướng tiếp cận tách từ Các hướng tiếp cận cơ bản trong việc tách từ: Hình 3: Các hướng tiếp cận cơ bản trong việc tách từ 3.3.1. Các hướng tiếp cận dựa trên “từ” Hướng tiếp cận dựa trên từ với mục tiêu tách được các từ hoàn chỉnh trong câu. Hướng tiếp cận này có thể chia ra theo 3 hướng: dựa trên thống kê (statistics - based), dựa trên từ điển (dictionary – based) và nhóm lai (hydrid) (kết hợp nhiều phương pháp với hy vọng đạt được những ưu điểm của các phương pháp này).  Hướng tiếp cận dựa trên thống kê: Dựa trên các thông tin thống kê như tần số xuất hiện của từ trong tập huấn luyện ban đầu. Hướng tiếp cận này đặc biệt dựa trên tập ngữ liệu huấn luyện. Nhờ vậy, hướng tiếp cận này tỏ ra linh hoạt và hữu dụng trong nhiều lĩnh vực khác nhau. Tách từ Dựa trên ký tự Dựa trên từ Uni-gram N-gram Thống kê Từ điển Lai 25  Hướng tiếp cận dựa trên từ điển: Ý tưởng của hướng tiếp cận này là những cụm từ được tách ra từ văn bản phải được so khớp với các từ trong từ điển. Do đó trong hướng tiếp cận này đòi hỏi từ điển riêng cho từng lĩnh vực quan tâm. Hướng tiếp cận “full word / phrase” cần sử dụng một từ điển hoàn chỉnh để có thể tách được đầy đủ các từ hoặc ngữ trong văn bản, trong khi đó hướng tiếp cận thành phần “component” lại sử dụng từ điển thành phần. Từ điển thành phần chỉ chứa các thành phần của từ và ngữ như hình vị và các từ đơn giản. Hướng tiếp cận theo từ điển vẫn còn một số hạn chế trong việc tách từ vì thực hiện hoàn toàn dựa vào từ điển. Nếu như thực hiện thao tác tách từ bằng cách sử dụng từ điển hoàn chỉnh thì trong thực tế việc xây dựng một bộ từ điển hoàn chỉnh là khó thực hiện vì đòi hỏi nhiều thời gian và công sức. Nếu tiếp cận theo hướng sử dụng từ điển thành phần thì sẽ giảm nhẹ hạn chế, khó khăn khi xây dựng từ điển, vì khi đó chúng ta sẽ sử dụng các hình vị từ và các từ đơn giản và các từ khác để hình thành nên từ, cụm từ hoàn chỉnh.  Hướng tiếp cận theo Hybrid: Với mục đích kết hợp các hướng tiếp cận khác nhau để thừa hưởng được các ưu điểm của nhiều kỹ thuật và các hướng tiếp cận khác nhau nhằm nâng cao kết quả. Hướng tiếp cận này thường kết hợp giữa hướng dựa trên thống kê và dựa trên từ điển nhằm tận dụng các mặt mạnh của các phương pháp này. Tuy nhiên hướng tiếp cận Hybrid lại mất nhiều thời gian xử lý, không gian đĩa và đòi hỏi nhiều chi phí. Tóm lại, các hướng tiếp cận để tách từ tiếng Việt dựa vào từ chỉ khả thi khi chúng ta có bộ từ vựng tốt hay ngữ liệu huấn luyện đủ lớn và đáng tin cậy. 3.3.2. Các hướng tiếp cận dựa trên ký tự Các hướng tiếp cận dựa trên ký tự (dựa trên “tiếng” trong tiếng Việt) có thể chia làm 2 nhóm nhỏ: uni-gram và n-gram. Trong tiếng việt, hình vị nhỏ nhất là “tiếng” được hình thành bởi nhiều ký tự trong bảng chữ cái. Hướng tiếp cận này đơn thuần rút trích ra một số lượng nhất định các tiếng trong văn bản như rút trích từ 1 ký tự (uni-gram) hay nhiều ký tự (n-gram) và cũng mang lại một số kết quả nhất định được minh chứng thông qua một số công trình nghiên cứu đã được công bố, như của tác giả Lê An Hà [2003] xây dựng tập ngữ liệu thô 10MB bằng cách sử dụng phương pháp qui hoạch động để cựa đại hóa xác suất xuất hiện của các ngữ. Rồi công trình nghiên cứu của H.Nguyễn[2005] làm theo hướng tiếp cận là thay vì sử dụng ngữ liệu thô, công trình tiếp cận theo hướng xem Internet như một kho ngữ liệu khổng lồ, sau đó tiến hành thống kê và sử dụng thuật giải di truyền để tìm cách tách từ tối ưu nhất, và một số công trình của một số tác giả 26 khác. Khi so sánh kết quả của tác giả Lê An Hà và H.Nguyễnt thì thấy công trình của H.Nguyễn cho được kết quả tốt hơn khi tiến hành tách từ, tuy nhiên thời gian xử lý lâu hơn. Ưu điểm nổi bật của hướng tiếp cận dựa trên nhiều ký tự là tính đơn giản, dễ ứng dụng, ngoài ra còn có thuận lợi là ít tốn chi phí cho thao tác tạo chỉ mục và xử lý nhiều câu truy vấn. Qua nhiều công trình nghiên cứu của các tác giả đã được công bố, hướng tiếp cận tách từ dựa trên nhiều ký tự, cụ thể là cách tách từ hai ký tự được cho là sự lựa chọn thích hợp. 3.4. Một số phương pháp tách từ tiếng Việt hiện nay 3.4.1. Phương pháp Maximum Matching: Forward/Backward Phương pháp khớp tối đa (MM - Maximum Matching) hay còn gọi là LRMM- Left Right Maximum Matching. Ở phương pháp này, chúng ta sẽ duyệt một ngữ hoặc câu từ trái sang phải và chọn từ có nhiều âm tiết nhất có mặt trong từ điển và cứ thực hiện lặp lại như vậy cho đến hết câu. Dạng đơn giản của phương pháp dùng để giải quyết nhập nhằng từ đơn. Giả sử chúng ta có một chuỗi ký tự C1, C2, …, Cn. Chúng ta sẽ áp dụng phương pháp từ đầu chuỗi. Đầu tiên kiểm tra xem C1 có phải là từ hay không, sau đó kiểm tra xem C1C2 có phải là từ hay không. Tiếp tục thực hiện như thế cho đến khi tìm được từ dài nhất. Dạng phức tạp: Quy tắc của dạng này là phân đoạn từ. Thông thường người ta chọn phân đoạn ba từ có chiều dài tối đa. Thuật toán bắt đầu từ dạng đơn giản, cụ thể là nếu phát hiện ra những cách tách từ gây nhập nhằng, như ở ví dụ trên, giả sử C1 là từ và C1C2 cũng là một từ, khi đó chúng ta kiểm tra ký tự kế tiếp trong chuỗi C1, C2, ….., Cn để tìm tất cả các đoạn có ba từ bắt đầu với C1 hoặc C1C2. Ví dụ: Giả sử chúng ta có được các đoạn sau: - C1 C2 C3 C4 -C1C2 C3C4 C5 -C1C2 C3C4 C5C6 Khi đó chuỗi dài nhất sẽ là chuỗi thứ ba. Do đó từ đầu tiên của chuỗi thứ ba (C1C2) sẽ được chọn. Thực hiện các bước cho đến khi được chuỗi từ hoành chỉnh. Nhận xét: Phương pháp này thực hiện tách từ đơn giản, nhanh và chỉ cần dựa vào từ điển để thực hiện. Tuy nhiên, khuyết điểm của phương pháp này cũng chính là từ điển, nghĩa là độ chính xác khi thực hiện tách từ phụ thuộc hoàn toàn vào tính đủ, tính chính xác của từ điển. 27 3.4.2. Phương pháp Transformation-based Learning (TBL) Phương pháp này tiếp cận dựa trên tập ngữ liệu đã đánh dấu. Theo cách tiếp cận này để cho máy tính có thể nhận biết ranh giới giữa các từ để có thể tách từ chính xác, chúng ta sẽ cho máy học các câu mẫu trong tập ngữ liệu đã được đánh dấu ranh giới giữa các từ đúng. Rõ ràng chúng ta thấy phương pháp rất đơn giản, vì chỉ cần cho máy học các tập câu mẫu và sau đó máy sẽ tự rút ra qui luật của ngôn ngữ và để từ đó sẽ áp dụng chính xác khi có những câu đúng theo luật mà máy đã rút ra. Và rõ ràng để tách từ được hoàn toàn chính xác trong mọi trường hợp thì đòi hỏi phải có một tập ngữ liệu tiếng Việt thật đầy đủ và phải được huấn luyện lâu để có thể rút ra các luật đầy đủ. 3.4.3. Mô hình tách từ bằng WFST và mạng Neural Mô hình mạng chuyển dịch trạng thái hữu hạn có trọng số WFST – Weighted Finit State Transducer đã được áp dụng trong tách từ từ năm 1996. Ý tưởng cơ bản là áp dụng WFST với trọng số là xác suất xuất hiện của mỗi từ trong kho ngữ liệu. Dùng WFST để duyệt qua các câu cần xét, khi đó từ có trọng số lớn nhất là từ được chọn để tách. Phương pháp này cũng đã được sử dụng trong công trình đã được công bố của tác giả Đinh Điền [2001], tác giả đã sử dụng WFST kèm với mạng Neural để khử nhập nhằng khi tách từ, trong công trình 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ù riêng của ngôn ngữ 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ó). Chi tiết về 2 tầng này như sau: 3.4.3.1. Tầng WFST Gồm có 3 bước: o Bước 1: Xây dựng từ điển trọng số: theo mô hình WFST, thao tác phân đoạn từ được xem như là một sự chuyển dịch trạng thái có xác suất.Chúng ta miêu tả từ điển D là một đồ thị biến đổi trạng thái hữu hạn có trọng số. Giả sử:  H là tập các từ chính tả tiếng Việt (còn gọi là “tiếng”). - P là từ loại của từ.  Mỗi cung của D có thể là: - Từ một phần tử của H tới một phần tử của H - Các nhãn trong D biểu diễn một chi phí được ước lượng theo công thức: Cost = -log(f/N) Trong đó: f là tần số của từ, N là kích thước tập mẫu. 28 o Bước 2: Xây dựng các khả năng phân đoạn từ: Để giảm sự bùng nổ tổ hợp khi sinh ra dãy các từ có thể từ một dãy các tiếng trong câu, tác giả đã đề xuất phương pháp kết hợp dùng thêm từ điển để hạn chế sinh ra các bùng nổ tổ hợp, cụ thể là nếu phát hiện thấy một cách phân đoạn từ nào đó không phù hợp ( không có trong từ điển, không phải là tứ láy, không phải là danh từ riêng,…) thì tác giả loại bỏ các nhánh xuất phát từ cách phân đoạn đoạn đó. o Bước 3: Lựa chọn khả năng phân đoạn từ tối ưu: Sau khi có được danh sách các cách phân đoạn từ có thể có của câu, tác giả đã chọn trường hợp phân đoạn từ có trọng số bé nhất. 3.4.3.2. Tầng mạng Neural Mô hình được sử dụng để khử nhập nhằng khi tách từ bằng cách kết hợp so sánh với từ điển. Nhận xét: Mô hình này đạt được độ chính xác trên 97% theo như công bố trong công trình của tác giả, bằng việc sử dụng thêm mạng Neural kết hợp với từ điển để khử các nhập nhằng có thể có khi tách ra các được nhiều từ từ một câu và khi đó tầng mạng Neural sẽ loại bỏ đi các từ không phù hợp bằng cách kết hợp với từ điển. Bên cạnh đó, cũng tương tự như phương pháp TBL điểm quan trọng của mô hình này cần tập ngữ liệu học đầy đủ. 3.4.4. Phương pháp tách tách từ tiếng Việt dựa trên thống kê từ Internet và thuật giải di truyền Phương pháp tách tách từ tiếng Việt dựa trên thống kê từ Internet và thuật giải di truyền – IGATEC (Internet and Genetics Algorithm based Text Categorization for Documents in Vietnamese) do H.Nguyễn đề xuất năm 2005 như một hướng tiếp cận mới trong tách từ với mục đích phân loại văn bản mà không cần dùng đến một từ điển hay tập ngữ liệu học nào. Trong hướng tiếp cận này, tác giả kết hợp giữa thuật toán di truyền với dữ liệu thống kê được lấy từ Internet. Trong tiếp cận của mình, tác giả đã mô tả hệ thống tách từ gồm các thành phần: 3.4.4.1. Online Extractor Thành phần này có tác dụng lấy thông tin về tần số xuất hiện của các từ trong văn bản bằng cách sử dụng một search engine nổi tiếng như Google hay Yahoo chẳng hạn. Sau đó, tác giả sử dụng các công thức dưới đây để tính toán mức độ phụ thuộc lẫn nhau MI (Mutual Information) để làm cơ sở tính fitness cho GA (Genetics Algorithm) engine.  Tính xác suất các từ xuất hiện trên Internet: 29   MAX )w2&w1count()w2&w1p( MAX count(w)wp   Trong đó: MAX = 4 * 109 count(w): số lượng văn bản trên Internet được tìm thấy có chứa từ w hoặc cùng chứa w1 và w2 đối với count(w1&w2).  Tính xác suất độ phụ thuộc của một từ lên một từ khác:  w1p )w2&w1p()w2|w1p(  Thông tin phụ thuộc lẫn nhau MI (Mutual Information) của các từ ghép được cấu tạo bởi n tiếng ( cw = w1w2…wn)      n 1j )wn&.....&w2&w1p(w jp )wn&.....&w2&w1p(MI(cw) 3.4.4.2. GA Engine for Text Segmentation Mỗi cá thể trong quần thể được biểu diễn bởi chuỗi các bit 0,1, trong đó, mỗi bit đại diện cho một tiếng trong văn bản, mỗi nhóm bit cùng loại đại diện cho cho một segment. Ví dụ: Học sinh học sinh học 0 0 1 0 0 Học sinh # học # sinh học w1 w2 w3 Các cá thể trong quần thể được khởi tạo ngẫu nhiên, trong đó mỗi segment được giới hạn trong khoảng 5. GA engine sau đó thực hiện các bước đột biến và lai ghép nhằm mục đích làm tăng giá trị fitness của các cá thể để đạt được cách tách từ tốt nhất có thể. 3.4.5. Nhận xét Sau khi xem xét một số hướng tiếp cận trong tách từ văn bản tiếng Việt, các nghiên cứu đã được công bố đều chỉ ra rằng phương pháp tách từ dựa trên từ mang lại kết quả có độ chính xác khá cao, điều này có được nhờ vào tập huấn luyện lớn, được 30 đánh dấu ranh giới giữa các từ chính xác giúp cho việc học để rút ra các luật để tách từ cho các văn bản khác được tốt đẹp, tuy nhiên chúng ta cũng dễ nhận thấy hiệu suất của phương pháp hoàn toàn phụ thuộc vào tập ngữ liệu huấn luyện. Hướng tiếp cận dựa trên ký tự có ưu điểm là dễ thực hiện , thời gian thực hiện tương đối nhanh , tuy nhiên lại cho kết qủa không chính xác bằng hướng tiếp cận dựa trên từ. Hướng tiếp cận này nói chung phù hợp cho các ứng dụng không cần độ chính xác tuyệt đối trong tách từ văn bản như ứng dụng lọc spam mail , firewall ,…Nhìn chung với hướng tiếp cận này nếu chúng ta có thể cải tiến để nâng cao độ chính xác trong tách từ thì hướng tiếp cận này là hoàn toàn khả thi và có khả năng thay thế hướng tiếp cận tách từ dựa trên từ vì đã không phải xây dựng kho ngữ liệu , một công việc đòi hỏi nhiều công sức, thời gian và sự hỗ trợ của các chuyên gia trong các lĩnh vực khác nhau. 3.5. Độ tương tự văn bản-văn bản Các độ đo độ tương tự văn bản đã được dùng từ rất lâu trong các ứng dụng của xử lý ngôn ngữ tự nhiên và các lĩnh vực liên quan. Một trong những ứng dụng sớm nhất của độ tương tự văn bản có lẽ là mô hình vecto trong tìm kiếm thông tin, ở đó tài liệu có liên quan nhất tới câu truy vấn đầu vào được xác định bằng cách xếp hạng các tài liệu trong tập theo thứ tự ngược của độ tương tự (Salton  Lesk 1971). Độ tương tự văn bản cũng được dùng cho phản hồi liên quan (relevance feedback), phân lớp văn bản (Rochio 1971), và gần đây hơn là cho trích chọn văn bản (Salton et al. 1997), và phương pháp cho việc đánh giá dịch máy tự động (Papineni et al. 2002) hay tóm tắt văn bản (Lin  Hovy 2003). Độ đo độ tương tự văn bản cũng được sử dụng cho việc đánh giá tính chặt chẽ của văn bản (Lapata  Barzilay 2005). Với một số trường hợp, phương pháp tự động tìm độ tương tự giữa hai đoạn văn bản là sử dụng việc so khớp từ đơn giản, và tạo ra một điểm tương tự dựa trên số đơn vị từ vựng xảy ra ở cả hai đoạn văn bản đầu vào. Sự cải tiến với phương pháp đơn giản này là xem xét đến gốc từ (stemming), việc loại bỏ các từ dừng, gán nhãn từ loại (part-of-speech tagging), so khớp tập con dài nhất, cũng như các trọng số và các nhân tố khác. Trong khi thành công với mức độ như vậy, phương pháp độ tương tự từ vựng không thể luôn luôn xác định độ tương tự ngữ nghĩa văn bản. Có một số lượng lớn độ đo độ tương tự ngữ nghĩa giữa từ với từ, sử dụng phương pháp hoặc là dựa trên cơ sở tri thức (knowledge-based), hoặc là dựa trên kho ngữ liệu (corpus-based). Các độ đo này được áp dụng thành công trong công việc xử 31 lý ngôn ngữ như phát hiện từ dùng sai nghĩa (Buddanitsky  Hirst 2001), nhận dạng từ đồng nghĩa. Với độ tương tự ngữ nghĩa dựa trên văn bản, có lẽ hầu hết sử dụng phương pháp xấp xỉ thu được qua việc mở rộng truy vấn, cũng như đã thực hiện trong tìm kiếm thông tin (Voorhees 1993), hay phương pháp phân tích ngữ nghĩa ẩn (Landauer, Foltz  Laham 1998), các phương pháp này đo độ tương tự của các văn bản bằng cách khai thác mối quan hệ giữa các từ một cách tự động qua tập văn bản lớn. Trong bài này, chúng ta xem xét một phương pháp đo độ tương tự ngữ nghĩa văn bản bằng cách khai thác thông tin có thể được tạo ra từ độ tương tự của các từ thành phần. Cho trước 2 đoạn văn bản, chúng ta muốn tự động nhận được một độ đo (score) chỉ tới độ tương tự của chúng ở mức độ ngữ nghĩa, do đó phương pháp so khớp từ truyền thống đã được dùng cho công việc này. Mặc dù chúng ta nhận ra sự thật là một phương pháp toàn diện về độ tương tự ngữ nghĩa văn bản cũng nên tính đến cả cấu trúc văn bản nhưng đầu tiên chúng ta cũng gác lại vấn đề này và thử mô hình độ tương tự ngữ nghĩa văn bản như là hàm của độ tương tự ngữ nghĩa của các từ thành phần. Chúng ta làm bằng cách kết hợp độ tương tự giữa từ với từ và đặc trưng của từ thành một công thức, đây là công cụ tốt cho độ tương tự ngữ nghĩa của hai đoạn văn bản. Trong phần này, ta cũng tính đến cả đặc trưng của từ (idf) để đưa ra trọng số cao hơn cho việc nhận dạng sự phù hợp ngữ nghĩa của 2 từ riêng lẻ và đưa ra trọng số kém hơn cho các khái niệm chung chung. Trong khi đặc trưng của từ cũng được đo cho một vài lĩnh vực bằng độ sâu của chúng trong phân cấp ngữ nghĩa, chúng ta cũng đang tăng cường nhân tố này với độ đo đặc trưng từ trên tập corpus, dựa trên phân phối thông tin đã nghiên cứu từ một tập văn bản lớn. Đặc trưng của một từ được xác định dựa vào tần suất tài liệu đảo ngược (idf), được tính bằng tổng số tài liệu trong tập corpus chia cho tổng số tài liệu chứa từ đó. Cho trước độ tương tự từ-từ và đặc trưng của từ, chúng ta xác định độ tương tự ngữ nghĩa của hai đoạn văn bản T1 và T2 bằng cách sử dụng phương pháp kết hợp độ tương tự ngữ nghĩa của mỗi đoạn văn này đối với đoạn văn kia. Đầu tiên, với mỗi từ w trong đoạn T1, chúng ta cố gắng xác định từ trong đoạn T2 mà có độ tương tự ngữ nghĩa cao nhất (maxSim(w, T2)), theo một trong các độ đo được mô tả dưới đây. Sau đó quá trình tương tự được áp dụng cho xác định từ tương tự nhất trong T1 bắt đầu với những từ trong T2. Độ tương tự từ sau đó được đánh trọng số với đặc trưng từ tương ứng, và được chuẩn hóa với độ dài của mỗi đoạn văn bản. Cuối cùng kết quả được tính bằng công thức trung bình đơn giản: 32     1 2 1 2 2 1 w {T } w {T } 1 2 w {T } w {T } axSim(w,T ) (w) axSim(w,T ) (w) 1( , ) 2 idf(w) idf(w) m idf m idf sim T T                     Độ tương tự là một giá trị giữa 0 và 1. Độ đo là 1 tức hai đoạn văn bản giống hệt nhau, độ đo là 0 tức hai đoạn văn khác nhau hoàn toàn. Chú ý là độ tương tự lớn nhất sẽ được tìm với các lớp từ có cùng từ loại. Chẳng hạn như từ tương tự nhất giữa danh từ “bông hoa” với đoạn văn bản “Có rất nhiều loại hoa màu đỏ ở gần ngôi nhà” sẽ được tìm với “loại hoa” và “ngôi nhà”, và sẽ bị lờ đi với các thể loại từ khác (như “màu đỏ”, “ở gần”,…). Hơn nữa, với những thể loại này (tính từ, trạng từ) độ tương tự ngữ nghĩa không thể đo được, chúng ta sử dụng độ đo dựa vào so khớp từ, hai từ cùng xảy ra ở cả hai văn bản sẽ có maxSim bằng 1. Tuy nhiên, trong khuôn khổ luận văn này, chúng tôi chưa xét đến từ loại của từ. 33 CHƯƠNG IV. TÍNH ĐỘ TƯƠNG TỰ NGỮ NGHĨA VĂN BẢN DỰA VÀO ĐỘ TƯƠNG TỰ GIỮA TỪ VỚI TỪ 3.1. Phát biểu bài toán Bài toán: 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ừ. Input:  2 văn bản hoặc 2 URL từ VnExpress.net hoặc DanTri.com.vn  Kho ngữ liệu gồm các file .seg  Tập các từ đồng nghĩa (file SameMeaning.txt) Output:  Độ đo tương tự giữa hai văn bản. 3.2. Giải quyết bài toán Các bước như sau: 3.2.1. Chuẩn bị dữ liệu Bước 1: Từ kho dữ liệu gồm các file .seg, ta tạo ra:  Từ điển Dict, file từ điển này có cấu trúc như sau: (key_word + + ':' + word_total + + list_of_docs) Trong đó key_word dùng làm khóa, cặp ký tự + ':' là dấu hiệu ngăn cách giữa khóa và value, các thành phần còn lại (sau dấu ':') là value.  Từ điển này được thể hiện bằng một danh sách gồm các cặp (key, value):  Key: danh sách các từ khóa (key_word).  Value: Gồm số lần xuất hiện của từ đó và danh sách các file .seg có chứa từ đó (cách nhau bằng dấu chấm phảy). Lấy các thành phần này ra thì cần qua thao tác bóc tách. Một phần của từ điển Dict như sau: 34 Hình 4: Một phần của từ điển Dict Như vậy sau mỗi từ khóa sẽ đến một dấu tab, đến dấu hai chấm rồi đến tổng số lần xuất hiện của từ đó trong tất cả các file tài liệu, tiếp đến lại là một dấu tab và cuối cùng là danh sách các file tài liệu có chứa từ đó.  Danh sách các file đã xử lý (lưu vào tệp processed_files.txt). Mục đích tạo ra file này là để lấy tổng số các tài liệu mà dữ liệu đã được phân tích xử lý để đưa vào từ điển Dict, phục vụ cho việc tính độ tương tự trong phần sau. Lưu lại danh sách này cũng để xác định xem nếu có một file mới đưa vào để phân tích thì kiểm tra xem file đó đã được xử lý hay chưa. Hình 5: Danh sách một số file trong kho ngữ liệu đã xử lý 35 Bước 2: Dựa vào từ điển Dict.txt, ta trích xuất ra tất cả các từ ghép và lưu vào từ điển CompoundWords, theo đó CompoundWords là bao gồm tất cả các từ ghép xuất hiện trong kho dữ liệu .seg. Hình 6: Một phần của từ điển các từ ghép Bước 3: Kết hợp từ điển CompoundWords và SameMeaning ta được từ điển CompoundDict (dùng để tách văn bản thành các từ độc lập). Từ điển này có cấu trúc gồm 2 phần:  Key: danh sách các từ khóa  Value: các số nguyên, giá trị này dùng để xác định các từ đồng nghĩa. Các từ có cùng giá trị Value thì tương tự nhau về nghĩa. Một phần của từ điển CompoundDict như sau: Hình 7: Một phần từ điển CompoundDict 36 3.2.2. Tách từ: Tách văn bản thành các từ ghép và danh từ riêng Từ ghép là một tổ hợp từ 2 từ trở lên mang đầy đủ ý nghĩa (thường là tổ hợp 2 đến 4 từ). Nếu tách các từ trong một từ ghép ra thì sẽ thành những từ có ý nghĩa khác hẳn. VD: “công nghệ thông tin”, “ngôn ngữ tự nhiên”, “siêu văn bản”, “tin học”,.... Danh từ riêng là những từ ghép mà các chữ cái đầu viết hoa. 3.2.2.1. Tách từ ghép trong văn bản Giả sử một từ ghép gồm tối đa 4 từ đơn  Đầu vào: Văn bản sText dạng chuẩn (chưa tách từ)  Đầu ra: Văn bản sOutText (đã tách thành các từ ghép)  Ý tưởng: Xét từng tổ hợp từ từ 4 đến 2 từ, so sánh các tổ hợp này với các từ ghép trong từ điển CompoundDict. Nếu nó xuất hiện trong từ điển thì nó là từ ghép, ngược lại, nó không là từ ghép. Cách làm như sau:  Thêm một dấu cách vào cuối văn bản sText để xét trường hợp cuối đoạn có dấu chấm câu. Khi đó ngắt câu sẽ dùng chung qui luật với các đoạn khác. sText += " ";  Ngắt văn bản sText ra thành các đoạn căn cứ vào các dấu chấm câu: Thay dấu "? " bằng dấu " ?\n " sText = sText.replace("? ", " ?\n "); Thay dấu ": " bằng dấu " :\n " sText = sText.replace(": ", " :\n "); Thay dấu "! " bằng dấu " !\n " sText = sText.replace("! ", " !\n "); Thay dấu ", " bằng dấu " , " sText = sText.replace(", ", " , "); Thay dấu "; " bằng dấu " ; " sText = sText.replace("; ", " ; "); Xóa bỏ dấu "\"" sText = sText.replace("\"", ""); 37 Xóa bỏ dấu "' " sText = sText.replace("' ", ""); Thay hai dấu cách bằng một dấu cách: sText = sText.replace(" ", " ");  Tiến hành ngắt đoạn  Tiếp theo, xét từng đoạn văn một: Tách đoạn văn thành mảng các từ phân cách nhau bởi dấu cách. - Xét từ đầu tiên của đoạn: + Trường hợp 1: Nếu kí tự đầu tiên của từ là kí tự đặc biệt (vd dấu câu như '?', ':',...) hoặc nó không phải là chữ cái thì bỏ qua. Ở đây các trường hợp sau không được xem là từ hợp lệ: “?Anh”, “123Em”, “$Usd”,... + Trường hợp 2: Từ đầu tiên là một từ hợp lệ (ví dụ từ “xã”), lần lượt lấy các từ tiếp theo để xét các tổ hợp từ 4 đến 2 từ: Ví dụ: Xét tổ hợp từ “xã_hội_chủ_nghĩa”: Nếu là từ ghép (tức nằm trong từ điển CompoundDict) thì thêm nó vào danh sách văn bản đầu ra sOutText và thêm dấu cách. Nếu không là từ ghép thì xét tiếp đến tổ hợp “xã_hội_chủ”, nếu vẫn không là từ ghép thì xét tổ hợp cuối cùng là “xã_hội”. - Tiếp theo ta nhảy đến xét từ ở vị trí kế tiếp, cứ tiếp tục làm như trên cho tới cuối đoạn văn. - Nếu vẫn còn từ chưa thêm vào biến sOutText (trường hợp còn từ cuối cùng) thì ta cứ thế thêm vào.  Mã nguồn của module này như sau: private static String splitKeywords(String sText) { StringBuffer sOutText = new StringBuffer(); sText += " "; sText = sText.replace(". ", " .\n "); sText = sText.replace("? ", " ?\n "); sText = sText.replace(": ", " :\n "); sText = sText.replace("! ", " !\n "); sText = sText.replace(", ", " , "); sText = sText.replace("; ", " ; "); sText = sText.replace("\"", ""); sText = sText.replace("' ", ""); sText = sText.replace(" ", " "); 38 String[] sParagraphArr = sText.split("\n"); for(String sParaItem: sParagraphArr) { String currWord[] = sParaItem.split(" "); int i = 0; while (i < currWord.length - 1) { if (currWord[i].length() <= 0) { i++; continue; } boolean isAppened = false; int t = MAX_TOTAL_WORDS_IN_A_COMPOUNDWORD - 1; char ch = currWord[i].charAt(0); //Ký tự đầu của word if (".,;?:!".indexOf(ch)>= 0 || !Character.isLetter(ch)) { t = 0; } else { while (t > 0) { StringBuffer strTemp = new StringBuffer(); strTemp.append(currWord[i]); for (int j = i + 1; j < i + 1 + t && j < currWord.length; j++) { strTemp.append("_" + currWord[j]); } String tmpWord = strTemp.toString().toLowerCase().trim(); if (WordDict.CompoundDict.containsKey(tmpWord)) { sOutText.append(strTemp + " "); isAppened = true; //đánh dấu là đã thêm vào chuỗi output break; } else { //Nếu ko phải là 1 từ ghép -> xét đến tổ hợp ngắn //hơn bằng cách giảm biến đếm đi 1. t--; } } } if (t == 0) { if (!isAppened) { sOutText.append(currWord[i] + " "); } } i += t + 1; } if (i < currWord.length) { sOutText.append(currWord[i] + " "); } sOutText.append("\n"); } return sOutText.toString(); } 39 3.2.2.2. Tách danh từ riêng trong văn bản  Đầu vào: văn bản sText là văn bản đã tách từ ghép.  Đầu ra: văn bản sOutText tách thành văn bản đã đoán nhận các danh từ riêng. - Danh từ riêng: là các từ không đứng ở đầu câu gồm ít nhất 2 từ mà chữ cái đầu viết hoa. - Dùng một vector để lưu danh sách các danh từ riêng (tên riêng) đã tìm được. - Hàm (phương thức) IsName để kiểm tra xem một từ có phải là danh từ riêng (tên riêng) hay không (tức kiểm tra xem chữ cái đầu của từ đó có viết hoa không, đồng thời nó không phải là từ ghép đã đoán nhận).  Cách tách như sau:  Bước 1: Ngắt văn bản thành các câu phân cách nhau bởi dấu xuống dòng hoặc dấu chấm câu.  Bước 2: Ngắt mỗi câu thành mảng các từ đơn.  Bước 3: Với mỗi câu văn bản:  Bỏ qua các từ viết hoa liền nhau ở đầu câu.  Xét từng từ một, nếu thấy từ dạng tên riêng mà không đứng ở đầu câu thì lưu lại vào biến tạm aName. Khi có 2 từ liền nhau trở lên được lưu vào biến tạm, đồng thời từ tiếp theo không phải là dạng tên riêng, thì ta thêm aName vào danh sách danh từ riêng (lưu vào vector).  Mỗi lần lưu một danh từ riêng vào vector xong, ta xóa rỗng biến tạm để chuẩn bị xét đến từ tiếp theo.  Cứ tiếp tục làm như vậy cho đến khi hết câu văn.  Bước 4: Xét ngược lại các trường hợp danh từ đứng ở đầu câu. Nếu một danh từ riêng đã được xác định ở chỗ khác trong câu thì khi đó, nếu nó xuất hiện ở đầu câu (trường hợp đã bỏ qua khi xét ở trên) thì nó cũng là danh từ riêng.  Với mỗi từ trong danh sách tên riêng, ta thay dấu cách phân cách từ bằng dấu gạch dưới và lưu vào biến realName.  Với mỗi câu văn bản, ta thay tất cả những tên riêng aName bằng tên riêng realName (ví dụ thay hết các từ dạng “Nguyễn Văn A” thành dạng “Nguyễn_Văn_A”). 40  Tiếp tục như trên cho tới khi hết thay thế hết tất cả các từ trong tất cả các câu văn. Hạn chế: Đối với các tên riêng chỉ xuất hiện ở đầu câu mà không xuất hiện ở những vị trí khác thì chương trình chưa phát hiện ra. Ví dụ:  Văn bản 1: Chủ tịch Hồ Chí Minh vĩ đại sống mãi trong sự nghiệp của chúng ta.  Văn bản 2: Hồ Chí Minh muôn năm. Hồ Chí Minh là một danh nhân văn hóa thế giới. Khi tính độ tương tự, hai văn bản trên được tách từ như sau:  Văn bản 1: Chủ_tịch Hồ_Chí_Minh vĩ_đại sống mãi trong sự_nghiệp của chúng_ta.  Văn bản 2: Hồ Chí Minh muôn năm. Hồ Chí Minh là một danh_nhân văn_hóa thế_giới. Ở ví dụ trên, mặc dù từ Hồ Chí Minh xuất hiện 2 lần trong văn bản 2 nhưng vì đứng ở đầu câu nên nó vẫn không được nhận biết là tên riêng.  Mã nguồn của module này như sau: private static String splitNameWords(String sText) { StringBuffer sOutText = new StringBuffer(); Vector vNameList = new Vector(); String[] sParagraphArr = sText.split("\n"); for(String sParaItem: sParagraphArr) { String strWordArr[] = sParaItem.split(" "); boolean isFirstPositionOfParagraph = true; StringBuffer aName = new StringBuffer(); for (int i = 0; i < strWordArr.length; i++) { String currWord = strWordArr[i]; if (isFirstPositionOfParagraph) { if (!isName(currWord)) { isFirstPositionOfParagraph = false; } } else { boolean hasName = false; if (isName(currWord)) { aName.append(currWord + " "); hasName = true; } if (!hasName || i == strWordArr.length - 1) { if (aName.length() > 0) { if (aName.toString().trim().indexOf(' ') > 0) { vNameList.addElement(aName.toString().trim()); } 41 aName.delete(0, aName.length()); } } } } } //Xét ngược lại các trường hợp danh từ đứng ở đầu câu. for(String sParaItem: sParagraphArr) { sParaItem = " " + sParaItem + " "; for (String aName: vNameList) { String realName = aName.replace(' ', '_'); sParaItem = sParaItem.replace(" " + aName + " ", " " + realName + " "); } sOutText.append(sParaItem.trim() + "\n"); } return sOutText.toString(); } 3.2.3. Tính toán độ tương tự văn bản  Đầu vào: Hai văn bản đã tách từ.  Đầu ra: Độ tương tự giữa hai văn bản. Độ tương tự giữa hai văn bản được tính theo công thức: Bước 1: Tính toán giá trị idf của một từ Idf của một từ được tính bằng tổng số toàn bộ tài liệu trong tập corpus chia cho tổng số tài liệu chứa từ đó. Bước 2: Tính độ tương tự lớn nhất của một từ so với một văn bản Để dễ tính toán, ta biểu diễn văn bản dưới dạng mảng các từ (từ ghép + danh từ riêng) riêng lẻ. Sau đó, ta xét các trường hợp như sau:  Nếu có 2 từ giống hệt nhau thì trả lại giá trị 1.  Nếu có 2 từ giống nhau nhưng khác nhau ở chữ hoa chữ thường thì trả lại giá trị 0.98.  Nếu có 2 từ khác nhau nhưng là từ đồng nghĩa thì trả lại giá trị 0.98.  Nếu không có từ nào khớp thì trả lại giá trị 0.     1 2 1 2 2 1 w {T } w {T } 1 2 w {T } w {T } axSim(w,T ) (w) axSim(w,T ) (w) 1( , ) 2 idf(w) idf(w) m idf m idf sim T T                     42 Bước 3: Tính toán độ tương tự giữa hai văn bản: dựa vào các tính toán từ bước 2 và theo công thức đã nêu ở trên.  Mã nguồn của module này như sau: public class Processor { /* * Tính toán IDF của 1 từ * Giá trị mặc định là 1 (khi là từ mới - chưa xuất hiện trong tài liệu nào) */ public static double getIDF(String word) { int total_doc = FileProcessor.VProcessedFiles.size(); String sValue = WordDict.HashDict.get(word); if (total_doc == 0 || sValue == null || sValue.length() == 0) return 1; int total_appear = sValue.split(";").length; if (total_appear == 0) return 1; double result = total_doc / total_appear; return result; } /* * Tính độ tương tự lớn nhất của 1 từ so với 1 văn bản (dưới dạng mảng các từ) * word: từ dùng để so khớp. * sWordArr: nội dung văn bản đã tách ra thành mảng các String riêng lẻ */ public static double getMaxSim(String word, String[] sWordArr) { double maxValue = 0; word = word.trim(); //loại bỏ các ký tự thừa ở đầu và cuối if (word.length() == 0) return 0; Integer value1 = WordDict.CompoundDict.get(word); for (String currWord: sWordArr) { currWord = currWord.trim(); 43 if (currWord.length() <= 0) continue; if (currWord.equals(word)) { maxValue = 1; break; } else if (currWord.equalsIgnoreCase(word)) { if (maxValue < 0.98) maxValue = 0.98; } else { Integer value2 = WordDict.CompoundDict.get(currWord); if (value1!= null && value2!=null && value1.intValue() == value2.intValue()) { if (maxValue < 0.98) { maxValue = 0.98; } } } } return maxValue; } /* * Tính toán độ tương tự giữa 2 văn bản * Đầu vào: 2 văn bản s1 + s2 */ public static double getSim(String s1, String s2) { String sArr1[] = s1.split(" "); String sArr2[] = s2.split(" "); double total_maxsim1 = 0; double total_idf1 = 0; 44 for (int i = 0; i < sArr1.length; i++) { String word = sArr1[i]; double word_idf = getIDF(word); total_idf1 += word_idf; total_maxsim1 += getMaxSim(word, sArr2) * word_idf; } double sim1 = 0; if (total_idf1 != 0) { sim1 = total_maxsim1 / total_idf1; } double total_maxsim2 = 0; double total_idf2 = 0; for (int i = 0; i < sArr2.length; i++) { String word = sArr2[i]; double word_idf = getIDF(word); total_idf2 += word_idf; total_maxsim2 += getMaxSim(word, sArr1) * word_idf; } double sim2 = 0; if (total_idf2 != 0) { sim2 = total_maxsim2 / total_idf2; } return (sim1 + sim2)/2; } } 3.3. Xây dựng hệ thống Giao diện chính của bài toán như sau: 45 Hình 8: Giao diện chính của hệ thống 3.3.1. Nhập trực tiếp 2 văn bản Trong tab đầu tiên là tính độ tương tự 2 văn bản, ta có thể gõ trực tiếp nội dung của hai văn bản. Sau đó nhấn nút “Tính độ tương tự” ta sẽ được kết quả cần tìm.  Ví dụ trước khi nhấn nút: Hình 9: Giao diện cho phép nhập trực tiếp hai văn bản  Sau khi nhấn nút tính, văn bản được tách từ và ta có kết quả độ tương tự giữa hai văn bản Sim(text1, text2) (là một số nằm trong khoảng [0,1]). 46 Hình 10: Giao diện kết quả độ tương tự sau khi nhập hai văn bản  Khi nhấn nút “Reset”, văn bản được thiết lập lại trạng thái lúc đầu khi người dùng nhập vào (tức văn bản khi chưa tách từ).  Khi nhấn nút “Văn bản khác”, hai văn bản được chọn ngẫu nhiên trong phần mã nguồn, giúp ta có thể test nhanh chương trình.  Khi nhấn nút “Xóa”, hệ thống cho phép người dùng nhập vào hai văn bản mới. 3.3.2. Nhập 2 văn bản từ file Để tính độ tương tự giữa hai file văn bản lưu trong máy tính, ta chọn tab thứ hai trong phần giao diện chính: “Độ tương tự 2 files”. Giao diện của lựa chọn này như sau: Hình 11: Giao diện nhập hai văn bản từ file  Đầu tiên, muốn chọn hai file văn bản nào, ta nháy vào nút “…”, sau đó chọn đường dẫn tới file cần nhập. 47  Sau đó, ta nháy vào nút “Lấy nội dung các file”, toàn bộ nội dung của hai file này sẽ được hiển thị trong phần Text 1 và Text 2.  Cuối cùng nhấn nút “Tính độ tương tự” để xem kết quả Sim(text1, text2). Hình 12: Giao diện kết quả sau khi nhập hai văn bản từ file 3.3.3. Lấy nội dung 2 văn bản từ URL Phần này có sử dụng mã nguồn mở từ một dự án nghiên cứu khác, trong mã nguồn mở này có sử dụng thư viện phân tích nội dung HTML của dự án VietSpider (file VSHTMLParser.jar). Địa chỉ gốc của tiện ích phân tích và bóc tách nội dung một số trang tin tức Việt Nam: Đây là một project mã nguồn mở, tuy đơn giản nhưng nó có đủ các tính năng để cài đặt phục vụ test chương trình. Bộ phân tích nội dung HTML (HTMLParser) lấy từ dự án phần mềm miễn phí VietSpider tại địa chỉ: VietSpider là bộ phần mềm khai thác, tổng hợp thông tin từ Internet, ở đây chỉ sử dụng một file thư viện trong bộ phần mềm này. Giao diện của lựa chọn này như sau: 48 Hình 13: Giao diện tính độ tương tự nội dung của hai trang Web  Đầu tiên, ta nhập địa chỉ của hai trang web vào URL 1 và URL 2.  Nhấn nút “Xử lý lấy nội dung” để lấy ra nội dung văn bản của hai trang web này. Khi đó, toàn bộ nội dung của chúng sẽ được hiển thị lần lượt tại Text 1 và Text 2.  Nhấn nút “Tính độ tương tự” để tìm kết quả Sim(text1, text2).  Muốn lấy nội dung của hai trang web khác, nhấn vào nút “Xét URL khác”.  Nhấn nút “Thoát” để ra khỏi hệ thống. 3.4. Kết quả thử nghiệm và đánh giá 3.4.1. Một số ví dụ cụ thể Độ tương tự ngữ nghĩa văn bản được minh họa bởi một số ví dụ sau:  Ví dụ 1: Văn bản 1 (Text 1): Một cơn giông bão dữ dội chỉ còn cách Trường Sa khoảng năm bảy km. Đừng chần chờ chống bão. Văn bản 2 (Text 2): Truyện thơ là những truyện kể bằng thơ, biểu hiện cảm nghĩ bằng ngôn ngữ giàu hình ảnh, cảm xúc, chứa đựng vấn đề xã hội. Có sư kết hợp yếu tố tự sự và trữ tình, dung lượng lớn, mang tính chất cố sự của truyện kể dân gian, biểu hiện dưới hình thức thơ ca với màu sắc trữ tình đậm. 49  Độ tương tự giữa hai văn bản: Sim(Text1, Text2) = 0.0016756471374935402 Về mặt thực tế, văn bản 1 nói về tin tức dự báo thời tiết, còn văn bản 2 nói về đặc điểm của truyện thơ. Hai nội dung này hoàn toàn khác nhau, không có từ nào trùng nhau và không có bất cứ mối liên hệ nào về mặt ý nghĩa. Còn theo thực nghiệm trên máy, chúng ta có độ tương tự giữa hai văn bản trên là 0.0016756471374935402. Độ đo này tương đối hợp lý vì hai văn bản trên khác nhau hoàn toàn.  Ví dụ 2: Văn bản 1 (Text 1): Nhận án chung thân, ông Sĩ còn bị điều tra “bỏ túi” 2 triệu USD Dù ông Sĩ một mực cho rằng không nhận hối lộ từ PCI nhưng tòa vẫn khẳng định có đủ căn cứ buộc tội nên tuyên phạt mức án chung thân. Tòa còn kiến nghị tiếp tục điều tra về cáo buộc nhận hơn 2 triệu USD trước đó của ông này. Theo HĐXX, hồ sơ vụ án đã thể hiện, để được trúng thầu gói thầu “Tư vấn thiết kế”, “Tư vấn giám sát” và được ưu ái những điều kiện có lợi, các quan chức PCI đã nhiều lần hối lộ ông Sĩ. Ngoài ra, tòa buộc ông Sĩ phải nộp lại 262.000 USD phạm tội. Do ông Sĩ đang phải chịu mức án 6 năm tù về tội “lợi chức vụ quyền hạn trong khi thi hành công vụ” nên HĐXX gộp chung hai bản án, buộc ông Sĩ phải nhận mức án chung thân cho cả hội tội. Cơ quan xét xử cũng kiến nghị cơ quan điều tra và VKSND Tối cao tiếp tục làm rõ hành vi nhận 6 lần tiền trước đó (hơn 2 triệu USD) từ phía PCI. Văn bản 2 (Text 2): Đề nghị ông Sĩ tù chung thân Đến phút cuối, ông Huỳnh Ngọc Sĩ vẫn cho rằng mình không có tội, mong HĐXX xem xét, làm rõ, đánh giá từng chi tiết để minh oan. Tiếp tục phiên tòa sơ thẩm xét xử ông Huỳnh Ngọc Sĩ, nguyên phó giám đốc Sở GTVT kiêm giám đốc Ban Quản lý dự án đại lộ Đông Tây và môi trường nước TPHCM (gọi tắt là BQLDA), về tội nhận hối lộ, ngày 16-10, VKSND TPHCM được ủy quyền của VKSND Tối cao thực hành quyền công tố tại tòa nhận định trong quá trình điều tra và tại phiên tòa, bị cáo Sĩ không thừa nhận việc nhận tiền của các quan chức Công ty Tư vấn Quốc tế Thái Bình Dương (PCI) và làm trái quy định Nhà nước. Tuy nhiên, căn cứ hồ sơ vụ án, tài liệu, chứng cứ thu thập được và lời khai nhận của 50 các quan chức PCI..., đã đủ cơ sở kết luận ông Sĩ đã nhận 262.000 USD và làm theo yêu cầu của người đưa hối lộ. Vị công tố đề nghị tù chung thân đối với bị cáo Sĩ.  Hai văn bản trên về mặt nội dung không hoàn toàn giống nhau nhưng có một số từ bị lặp lại ở cả hai văn bản (các từ in đậm). Theo thực nghiệm trên máy ta có độ tương tự giữa hai văn bản: Sim(Text1, Text2) = 0.36826248198851375  Ví dụ 3: Văn bản 1: Huỳnh Ngọc Sĩ: “Cáo trạng hoàn toàn không đúng” Ra trước vành móng ngựa, bị cáo Huỳnh Ngọc Sĩ đã phản đối toàn bộ nội dung bản cáo trạng của Viện Kiểm sát nhân dân tối cao truy tố bị cáo nhận hối lộ. Bước vào phần thẩm vấn, khi Chủ tọa phiên tòa vừa hỏi Huỳnh Ngọc Sĩ, cáo trạng truy tố đúng hay sai? Bị cáo Sĩ đã phản ứng gay gắt: "Tôi phản bác hoàn toàn nội dung cáo trạng truy tố tôi nhận hối lộ. Việc đưa nhận hối lộ chỉ là lời khai của các cá nhân PCI; không có nhân chứng, chứng cứ trực tiếp”. Bị cáo Sĩ cũng khẳng định: “Bốn vấn đề mà cáo trạng nêu tôi làm lợi cho PCI là hoàn toàn không đúng, quy kết tội cho tôi”. Văn bản 2: Huỳnh Ngọc Sĩ: “Tôi không nhận hối lộ” (Dân trí) - “Việc PCI rút tiền từ ngân hàng Tokyo chi nhánh TPHCM, đem tiền từ Nhật qua và trả lương… không đồng nghĩa là tiền hối lộ. Tôi hoàn toàn không nhận tiền hối hộ”, bị cáo Huỳnh Ngọc Sĩ liên tục “phản pháo” HĐXX. Huỳnh Ngọc Sĩ nói: “Lời khai như thế là không đúng. Tôi không tiếp ai tại phòng làm việc riêng hay thương lượng với ai tại khách sạn cả”. Suốt phiên tòa, bị cáo Sĩ đều không thừa nhận mình đã nhận “bôi trơn” số tiền 262.000 USD. Sĩ khai mình không hề biết đến ông Takasu Kunio, nguyên giám đốc điều hành PCI (người được xác định đã đưa tiền hối lộ cho ông Sĩ). Bị cáo Sĩ vẫn giữ nguyên quan điểm: “Không chính xác. Không đúng sự thật. Không nhận…”. Để làm rõ sự việc, cơ quan điều tra cho các quan chức PCI nhận dạng thì họ nhận đúng hình và vẽ đúng sơ đồ phòng làm việc của ông Sĩ. Bị cáo Sĩ quả quyết: “Việc PCI rút tiền từ ngân hàng Tokyo chi nhánh TPHCM, đem tiền từ Nhật qua và trả lương… không đồng nghĩa là tiền hối lộ. Tôi hoàn toàn không nhận tiền hối hộ”.  Độ tương tự giữa hai văn bản: Sim(Text1, Text2) = 0.5206761702244165 51 Hai văn bản trên có số từ ngữ bị lặp lại không nhiều nhưng về mặt ý nghĩa chúng cũng có điểm tương đồng. Độ tương tự của chúng là 0.5206761702244165 cũng phản ánh được phần nào nội dung đó.  Ví dụ 4 Văn bản 1 (Text 1): Bán chung cư Văn Phú Victoria-Hà Nội LH: 0943212996 Dự án nằm giữa khu đô thị Văn Phú, quận Hà Đông, TP.Hà Nội, được tư vấn thiết kế và giám sát bởi các công ty Nhật Bản với phong cách độc đáo, hiện đại. Khu vực: Q. Hà Đông, Hà Nội . Tổng diện tích: 94,1 ha Khởi công: 2009 Dự kiến hoàn thành: 2012 Trạng thái dự án: Đang thi công Chủ đầu tư: Công ty cổ phần đầu tư Văn Phú-invest + Căn hộ 95,3m2: 01 Phòng khách, 01 bếp, 01 Phòng ăn, 02 Phòng ngủ, 02 phòng WC. + Căn hộ 116,2 m2: 01 Phòng khách, 01 Phòng bếp, 01 Phòng ăn, 02 Phòng ngủ, 02 Phòng WC. + Căn hộ 117m2: 01 Phòng khách, 01 bếp, 01 Phòng ăn. 03 Phòng ngủ, 02 Phòng WC. Hiện nay tôi đang có các căn tầng 23, 24 với đủ loại S trên. Giá bán cực kỳ hợp lí. Văn bản 2 (Text 2): Bán căn hộ chung cư dự án văn phú victoria- diện tích 95m2 giá 19.7tr DỰ ÁN VĂN PHÚ VICTORIA Dự án nằm giữa khu đô thị Văn Phú, quận Hà Đông, TP.Hà Nội, được tư vấn thiết kế và giám sát bởi các công ty Nhật Bản với phong cách độc đáo, hiện đại. Khu vực: Q. Hà Đông, Hà Nội Loại hình: Chung cư/Căn hộ cao cấp Tổng diện tích: 94,1 ha Khởi công: 2009 52 Dự kiến hoàn thành: 2012 Trạng thái dự án: Đang thi công Chủ đầu tư: Công ty cổ phần đầu tư Văn Phú-invest + Căn hộ 95,3m2: 01 Phòng khách, 01 bếp, 01 Phòng ăn, 02 Phòng ngủ, 02 phòng WC. + Căn hộ 116,2 m2: 01 Phòng khách, 01 Phòng bếp, 01 Phòng ăn, 02 Phòng ngủ, 02 Phòng WC. + Căn hộ 117m2: 01 Phòng khách, 01 bếp, 01 Phòng ăn. 03 Phòng ngủ, 02 Phòng WC.  Độ tương tự giữa hai văn bản: Sim(Text1, Text2) = 0.81338799771947 Hai văn bản trên có khá nhiều từ giống nhau, chúng chỉ khác nhau ở một số chỗ: dòng đầu tiên và dòng cuối cùng trong cả hai văn bản. Các từ ngữ trong câu cuối cùng của văn bản 1 (các từ in nghiêng) không xuất hiện trong văn bản 2. Và độ tương tự tính được theo công thức là 0.81338799771947. Tuy nhiên, ở đây ta cũng cần chú ý đến những trường hợp văn bản là các tài liệu có cùng cấu trúc, cùng khuôn dạng nhất định. Chắc chắn chúng sẽ có nhiều từ giống nhau nhưng về mặt nội dung lại khác nhau, chẳng hạn: Văn bản 1 (Text 1): Khu vực: Đan Phượng, Hà Nội . Tổng diện tích: 80 ha Khởi công: 2007 Dự kiến hoàn thành: 2010 Trạng thái dự án: Đã thi công xong Chủ đầu tư: Công ty TNHH Sơn Hà + Căn hộ 70 m2: 01 Phòng khách, 01 bếp, 02 Phòng ngủ, 01 phòng WC. + Căn hộ 80 m2: 01 Phòng khách, 01 Phòng bếp, 01 Phòng ăn, 02 Phòng ngủ, 01 Phòng WC. Văn bản 2 (Text 2): Khu vực: Hà Đông, Hà Nội . Tổng diện tích: 99 ha Khởi công: 2010 53 Dự kiến hoàn thành: 2012 Trạng thái dự án: Đang thi công Chủ đầu tư: Công ty xây dựng Hà Nhung Căn hộ 100 m2: 01 Phòng khách, 01 Phòng bếp, 01 Phòng ăn, 02 Phòng ngủ, 02 Phòng WC  Độ tương tự giữa hai văn bản: Sim(Text1, Text2) = 0.9442956354090183 Như vậy độ đo này chưa được chính xác bởi vì hai văn bản có nhiều từ giống nhau nhưng trên thực tế lại khác nhau.  Ví dụ 5: Văn bản 1: Lúc 12h55 hôm nay (giờ Hà Nội), tại lễ khai mạc Đại hội Toán học thế giới tổ chức ở Hyderabad, Ấn Độ, bà Pratibha Patil - Tổng thống Ấn Độ đã trao huy chương Fields - giải thưởng cao quý nhất trong lĩnh vực toán học cho GS Ngô Bảo Châu. Văn bản 2: Tại Hyderabad, Ấn Độ, Tổng thống Ấn Độ, bà Pratibha Patil trao huy chương Fields - giải thưởng toán học cao quý nhất thế giới – cho giáo sư Ngô Bảo Châu lúc 12:55 hôm nay (giờ Hà Nội).  Hai văn bản trên khá giống nhau, chúng chỉ khác nhau về thứ tự xuất hiện của các từ trong câu và có một số từ (in nghiêng) xuất hiện trong văn bản 1 mà không có trong văn bản 2. Theo thực nghiệm trên máy: Độ tương tự giữa hai văn bản: Sim(Text1, Text2) = 0.9256739306748865  Ví dụ 6: Văn bản 1 (Text 1): Sáng 28/8, máy bay chở giáo sư Ngô Bảo Châu, người vừa giành giải thưởng Fields dự kiến hạ cánh xuống sân bay Nội Bài. Các hoạt động chào mừng, đón tiếp trọng thị đang được Chính phủ và các bộ gấp rút chuẩn bị. Văn bản 2 (Text 2): Sáng 28/8, phi cơ chở giáo sư Ngô Bảo Châu, người vừa đoạt giải thưởng Fields dự định hạ cánh xuống phi trường Nội Bài. Các hoạt động chào mừng, tiếp đón trọng thị đang được Chính phủ và các bộ gấp rút chuẩn bị. Độ tương tự giữa hai văn bản: Sim(Text1, Text2) = 0.996660325250488 54 Trong ví dụ này, hai văn bản chỉ khác nhau duy nhất hai cặp từ:  Cặp thứ nhất: Văn bản 1 dùng từ “máy bay” còn văn bản 2 dùng từ “phi cơ”.  Cặp thứ hai: Văn bản 1 dùng từ “ đón tiếp” còn văn bản 2 dùng từ “tiếp đón”. Tuy nhiên, đây lại là các cặp từ đồng nghĩa trong tập từ đồng nghĩa “Same Meaning”. Do vậy độ tương tự của chúng là 0.996660325250488 3.4.2. Kết quả thử nghiệm 3.4.2.1. Cách tiến hành Để đánh giá độ tương tự của các tài liệu, chúng tôi sử dụng 2 phương pháp:  Phương pháp 1: Con người đánh giá Tập các tài liệu sẽ được giao cho một nhóm gồm 5 người ở 5 địa điểm khác nhau. Họ có nhiệm vụ đọc nội dung và đánh giá độ tương tự của hai tài liệu bất kỳ dựa trên cảm tính của mình.  Phương pháp 2: Thực nghiệm trên máy. 3.4.2.2. Kết quả thử nghiệm Chúng tôi tiến hành thử nghiệm dựa trên hai tập dữ liệu: tập các văn bản là các tin tức trên Internet và tập các tin rao vặt trên Internet.  Tập dữ liệu 1: Tập gồm 20 văn bản gồm các tin tức trên một số trang Web: Địa chỉ của các tài liệu này như sau: File Địa chỉ 1 cao/11186417/218/ 2 3 toan-bo-noi-dung-cao-trang.htm 4 5 6 Ngoc-Sy-nhan-hoi-lo-tien-ti.html 7 trang-hoan-toan-khong-dung/201010/115255.datviet 55 8 1341775005/ong_si_lien_tiep_khang_dinh_khong_nhan_hoi_lo_t u_pci.html 9 nhan-hoi-lo.htm 10 chung-than.htm 11 12 13 14 dien-de-ket-an-toi/11186642/218/ 15 16 voi-de-nghi-tu-chung-than-cua-vks.htm 17 si-bi-de-nghi-tu-chung-than.htm 18 tu-chung-than.htm 19 cao-trang.htm 20 con-bi-dieu-tra-bo-tui-2-trieu-USD/11186794/218/ Bảng 4: Địa chỉ của 20 tin tức trên một số trang Web Chẳng hạn ta có kết quả đánh giá độ tương tự ngữ nghĩa của hai file nào đó trong tổng số các tài liệu có địa chỉ được nêu ở trên như sau: File 1 File 2 Người đánh giá Thực nghiệm trên máy 13 15 0.4 0.21854826011617284 2 4 0.4 0.24008952428716562 13 17 0.3 0.29548872180126395 3 8 0.2 0.3297415587214319 6 8 0.4 0.364800386307795 4 7 0.5 0.39024157344076293 1 7 0.4 0.4247928748969288 1 6 0.5 0.4621222286840157 56 13 19 0.6 0.500689564972599 10 19 0.6 0.5501094543011812 10 15 0.7 0.5768032097459137 3 9 0.7 0.5912167395883572 15 16 0.7 0.6367496647525064 4 5 0.8 0.6504860662096876 15 18 0.6 0.6749330889903177 3 7 0.6 0.702918830317079 6 7 0.6 0.7650383060856087 16 18 0.9 0.863923370318344 1 2 0.9 0.9279451135471808 13 20 0.9 0.9523695076604557 11 14 1.0 0.9706441434356016 Bảng 5: Một số kết quả độ tương tự của hai file bất kỳ Kết quả độ tương tự của 20 tin tức trên như sau: Độ tương tự Người đánh giá Thực nghiệm trên máy 0.0-0.3 7,1% 8% 0.3-0.5 50% 56% 0.5-0.7 32,5% 30% 0.7-0.8 4% 2% 0.8-1.0 6,4% 4% Bảng 6: Kết quả đánh giá 20 tin tức do người và máy thực hiện  Tập gồm 30 tin rao vặt trên một số trang web: File Đường dẫn 30 cccc-du-a-n-van-phu-victoria.html 31 mat-san-chung-cu-victoria-van-phu-gia-hop-ly-d.html 32 chung-cu-van-phu-victoria-ha-dong.html 33 can-ho-chung-cu-victoria-van-phu-du-an-van-phu.html 34 can-ho-chung-cu-du-an-van-phu-victoria-dien-ti.html 35 57 phu-victoria-chung-cu-van-phu-victoria-can-ho-.html 36 mat-san-chung-cu-victoria-van-phu-gia-hop-ly-d.html 37 chcc-van-phu-toa-v1-gia-hap-dan.html 38 ban-mot-so-can-ho-chung-cu-van-phu-gia-chi-19-.html 39 ban-mot-so-can-ho-chung-cu-van-phu-victoria.html 40 san-victoria-van-phu-pm-gap-de-co-xuat-vip.html 41 san-victoria-van-phu-pm-gap-de-co-xuat-vip.html 42 san-victoria-van-phu-pm-som-de-co-suat-vip.html 43 chung-cu-van-phu.html 44 chcc-the-van-phu-victoria-dt-95-112-114-116m2.html 45 chcc-the-van-phu-victoria-dt-95-112-114-116m2.html 46 chcc-the-van-phu-victoria-dt-95-112-114-116m2.html 47 the-van-phu-victoria-dt-95-112-114-116m2.html 48 ban-chcc-cao-cap-van-phu-victoria.html 49 can-ho-toa-v1-tang-25-van-phu-victoria-gia-hap.html 31.2 chung-cu-victoria-