Tài liệu ứng dụng khoảng cách levenstein để so sánh mức độ giống nhau của hai văn bản

i BỘ GIÁO DỤC ĐÀO TẠO ĐẠI HỌC ĐÀ NẴNG TRẦN NGỌC CHIẾN ỨNG DỤNG KHOẢNG CÁCH LEVENSTEIN ĐỂ SO SÁNH MỨC ĐỘ GIỐNG NHAU CỦA HAI VĂN BẢN LUẬN VĂN THẠC SĨ KỸ THUẬT Đà Nẵng - Năm 2017 i BỘ GIÁO DỤC ĐÀO TẠO ĐẠI HỌC ĐÀ NẴNG TRẦN NGỌC CHIẾN ỨNG DỤNG KHOẢNG CÁCH LEVENTEIN ĐỂ SO SÁNH MỨC ĐỘ GIỐNG NHAU CỦA HAI VĂN BẢN Chuyên ngành: Khoa học máy tính Mã số: 60.48.01.01 LUẬN VĂN THẠC SĨ KỸ THUẬT Người hướng dẫn khoa học: PGS.TS. VÕ TRUNG HÙNG Đà Nẵng - Năm 2017 i LỜI CAM ĐOAN Tôi xin cam đoan : Những nội dung trong luận văn này là do tôi thực hiện dưới sự hướng dẫn trực tiếp của PGS.TS. Võ Trung Hùng; Mọi tham khảo dùng trong luận văn đều được trích dẫn rõ ràng và trung thực tên tác giả, tên công trình, thời gian, địa điểm công bố; Mọi sao chép không hợp lệ, vi phạm quy chế đào tạo, hay gian trá, tôi xin chịu hoàn toàn trách nhiệm. Tác giả Trần Ngọc Chiến ii TÓM TẮT ỨNG DỤNG KHOẢNG CÁCH LEVENSHTEIN ĐỂ SO SÁNH MỨC ĐỘ GIỐNG NHAU CỦA HAI VĂN BẢN Tóm tắt – Đo lường mức độ giống nhau của hai văn bản đã góp phần quan trọng trong nhiều lĩnh vực công nghệ thông tin. Các phương pháp đánh giá mức độ giống nhau bao gồm: đánh giá dựa trên chuỗi ký tự, đánh giá dựa trên từ vựng, đánh giá dựa trên ngữ nghĩa. Trong mỗi phương pháp sẽ có các thuật toán khác nhau để đánh giá mức độ giống nhau của hai văn bản. Trong luận văn tập trung nghiên cứu về các phương pháp đánh giá mức độ giống nhau của văn bản dựa trên chuỗi ký tự, cụ thể sẽ ứng dụng khoảng cách Levenshtein để xây dựng công cụ so sánh mức độ giống nhau của hai văn bản. Mục tiêu của luận văn bao gồm nghiên cứu tổng quan các phương pháp đánh giá khác khau, xây dựng mô hình so sánh mức độ giống nhau của hai văn bản, xây dựng công cụ so sánh, tiến hành chạy thử nghiệm và đánh giá kết quả. Từ khóa – khoảng cách Levenshtein; so sánh hai văn bản; mức độ giống nhau; đánh giá dựa trên ký tự; công cụ so sánh. APPLYING LEVENSHTEIN DISTANCE TO MEASURE THE SIMILARITY BETWEEN TWO DOCUMENTS Abstract - Measuring the similarity between two documents plays an important role in information technology. Methods of similarity measure include: String-based, Corpus-based and Knowledge-based Similarities. Every approach has many different algorithms to measure the similarity between two documents. The Thesis focused on methods of assessing the similarity of text based on string. Specifically, Levenshtein Distance will apply to construct a tool that compares the similarity of the two texts. The objective of the thesis is to review the different methods of similarity measure, to develop a comparative model of the similarity of the two texts, to develop a comparison tool, to conduct a trial run and to evaluate the results. Key words - Levenshtein Distance; Similarity Measure; similarity of the two texts; Stringbased Similarities; comparison tool. iii MỤC LỤC LỜI CAM ĐOAN ...................................................................................................... i TÓM TẮT ................................................................................................................. ii MỤC LỤC ................................................................................................................ iii DANH MỤC CÁC TỪ VIẾT TẮT ..........................................................................v DANH MỤC CÁC BẢNG ..................................................................................... vii DANH MỤC CÁC HÌNH ..................................................................................... viii MỞ ĐẦU ....................................................................................................................1 1. Lý do chọn đề tài ..........................................................................................1 2. Mục tiêu và nhiệm vụ ...................................................................................1 3. Đối tượng và phạm vi nghiên cứu ................................................................2 4. Giả thiết nghiên cứu .....................................................................................2 5. Phương pháp nghiên cứu ..............................................................................2 7. Bố cục của luận văn .....................................................................................3 CHƯƠNG 1. TỔNG QUAN .....................................................................................4 1.1. Giới thiệu..............................................................................................................4 1.2. Các phương pháp đánh giá mức độ giống nhau của hai văn bản .........................5 1.2.1. Đánh giá dựa trên chuỗi (String-based Similarity Measures) ................5 1.2.2. Đánh giá dựa trên từ vựng (Corpus-Based Similarity Measures) ..........7 1.2.3. Đánh giá dựa trên ngữ nghĩa (Knowledge-Based Similarity Measures) . ...........................................................................................................9 1.3. Thuật toán dựa trên ký tự ...................................................................................10 1.3.1. Thuật toán Jaro - Winkler distance ......................................................10 1.3.2. Thuật toán Hamming distance .............................................................14 1.3.3. Thuật toán Smith – Waterman .............................................................15 1.3.4. Thuật toán Levenshtein distance ..........................................................21 1.3.5. So sánh các thuật toán ..........................................................................24 iv CHƯƠNG 2. GIẢI PHÁP XÂY DỰNG CÔNG CỤ ............................................25 2.1. Giới thiệu............................................................................................................25 2.2. Mô hình hệ thống ...............................................................................................25 2.3. Giải thuật ............................................................................................................27 2.3.1. Chuyển dữ liệu nguồn (word, pdf) sang dạng Text .............................27 2.3.1.1. Chuyển dữ liệu nguồn từ word sang dạng Text ................................27 2.3.1.2. Chuyển dữ liệu nguồn từ pdf sang dạng Text ...................................29 2.3.2. So sánh mức độ giống nhau của hai văn bản theo khoảng cách Levenshtein .....................................................................................................31 CHƯƠNG 3. THỰC NGHIỆM .............................................................................35 3.1. Lựa chọn công cụ phát triển ...............................................................................35 3.1.1. Ngôn ngữ lập trình ...............................................................................35 3.1.2. Môi trường phát triển tích hợp Microsoft Visual Studio .....................36 3.1.2.1. Giới thiệu ...........................................................................................36 3.1.2.2. Tính năng...........................................................................................37 3.2. Xậy dựng các mô-đun hệ thống .........................................................................41 3.2.1. Mô-đun chuyển đổi từ tập tin word sang dạng text .............................41 3.2.2. Mô-đun chuyển đổi từ tập tin pdf sang dạng text ................................42 3.2.3. Mô-đun so sánh mức độ giống nhau của hai văn bản ..........................43 3.3. Thử nghiệm ........................................................................................................45 3.4. Đánh giá kết quả.................................................................................................49 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN .............................................................54 DANH MỤC TÀI LIỆU THAM KHẢO ...............................................................55 QUYẾT ĐỊNH GIAO ĐỀ TÀI LUẬN VĂN (bản sao) BẢN SAO KẾT LUẬN CỦA HỘI ĐỒNG, BẢN SAO NHẬN XÉT CỦA CÁC PHẢN BIỆN. v DANH MỤC CÁC TỪ VIẾT TẮT Từ viết tắt Giải thích HAL Hyperspace Analogue to Language LSA Latent Semantic Analysis GLSA Generalized Latent Semantic Analysis ESA Explicit Semantic Analysis CL-ESA The cross-language explicit semantic analysis PMI-IR SCO-PMI NGD DISCO Pointwise Mutual Information - Information Retrieval Second-order co-occurrence pointwise mutual information Normalized Google Distance Extracting Distributionally similar words using Sooccurrences res Resnik lin Lin jcn Jiang & Conrath lch Leacock & Chodorow wup Wu & Palmer path Path Length hso St.Onge vi lesk Lesk vector vector pairs CLR Common Language Runtime IDE Integrated Development Environment GUI Graphical User Interface WPF Windows Presentation Foundation XAML Extensible Application Markup Language UML Unified Modeling Language LINQ Language Integrated Query ORM Object Relational Mapping T4 Text Template Transformation Toolkit vii DANH MỤC CÁC BẢNG Số hiệu bảng Tên bảng Trang 1.1 Bảng so sánh các thuật toán 24 3.1 Các phiên bản Microsoft Visual Studio 40 viii DANH MỤC CÁC HÌNH Số hiệu Tên hình Trang hình 1.1. 1.2. 1.3. Các phương pháp đánh giá mức độ giống nhau dựa trên chuỗi Các phương pháp đánh giá mức độ giống nhau dựa trên từ vựng Các phương pháp đánh giá mức độ giống nhau dựa trên ngữ nghĩa 6 9 9 2.1. Mô hình tổng thể 25 2.2. Mô hình tổng thể chi tiết 26 2.3. Lưu đồ chuyển đổi tập tin word sang dạng text 27 2.4. Lưu đồ chuyển đổi tập tin pdf sang dạng text 29 2.5. Lưu đồ so sánh mức độ giống nhau của hai văn bản 32 3.1. Giao diện chính 45 3.2. Giao diện so sánh hai văn bản 45 3.3. Giao diện so sánh hai đoạn văn bản 46 3.4. Giao diện so sánh một đoạn văn bản với một tập tin 46 3.5. Giao diện so sánh giữa hai tập tin 47 3.6. 3.7. Giao diện so sánh giữa một văn bản với nhiều văn bản được liệt kê Giao diện kết quả so sánh giữa một văn bản với nhiều văn bản 48 48 3.8. Kết quả so sánh giữa hai văn bản giống nhau 49 3.9. Kết quả so sánh giữa hai văn bản ngắn khác nhau 50 3.10. Kết quả so sánh giữa hai văn bản giống nhau (khoảng 13000 từ) 50 ix Số hiệu Tên hình Trang hình 3.11. 3.12. 3.13. Kết quả so sánh giữa hai văn bản khác nhau (khoảng 13000 từ) Kết quả so sánh giữa một văn bản (1700 từ) với 22 tập tin văn bản Kết quả so sánh giữa một văn bản (13.000 từ) với 22 tập tin văn bản 51 51 52 1 MỞ ĐẦU 1. Lý do chọn đề tài Ngày nay, mạng Internet mang lại rất nhiều lợi ích cho con người. Chúng cung cấp một khối lượng lớn thông tin và dịch vụ. Các dịch vụ phổ biến trên Internet như: hệ thống thư điện tử, mạng xã hội, công cụ tìm kiếm, các dịch vụ về thương mại, y tế, học tập, giải trí… Internet còn chứa đựng một kho kiến thức khổng lồ. Chúng ta có thể tìm kiếm hầu như mọi thông tin trong tất cả các lĩnh vực trong nước và quốc tế, các bài báo khoa học, luận văn tốt nghiệp, các công trình nghiên cứu… đều được chia sẻ cho mọi người trên toàn cầu. Do đó, việc đo lường mức độ giống nhau của các tài liệu đã đóng một vai trò quan trọng trong các lĩnh vực như: tìm kiếm thông tin dựa trên nội dung của tài liệu, phân nhóm tài liệu dựa vào sự tương đồng về nội dung, phát hiện sao chép luận văn, bài báo, [5]… Vì vậy, xây dựng một công cụ để so sánh mức độ giống nhau của hai văn bản là cần thiết. Hiện nay, trên thế giới thường sử dụng các hệ thống Turnitin, CheckforPlagiarism hay PlagScan… để kiểm tra sự trùng lặp của các văn bản, tài liệu viết bằng tiếng Anh. Tuy nhiên, không phải ai cũng có thể sử dụng được các công cụ này bởi các hệ thống có thu phí sử dụng khá cao. Xuất phát từ thực tế nêu trên cùng với sự hướng dẫn tận tình của thầy Võ Trung Hùng, tôi đề xuất thực hiện đề tài “Ứng dụng khoảng cách levenshtein để so sánh mức độ giống nhau của hai văn bản” cho luận văn tốt nghiệp. 2. Mục tiêu và nhiệm vụ a. Mục tiêu Mục tiêu của đề tài là ứng dụng giải thuật Levenshtein xây dựng công cụ kiểm tra để đánh giá mức độ giống nhau của hai văn bản. b. Nhiệm vụ của đề tài Để đạt được mục tiêu đề ra, nhiệm vụ của đề tài gồm: Nghiên cứu tổng quan các phương pháp đánh giá mức độ giống nhau của hai văn bản; 2 Nghiên cứu các giải thuật đánh giá mức độ giống nhau của văn bản dựa trên ký tự; Nghiên cứu lựa chọn ngôn ngữ và môi trường phát triển ứng dụng; Thử nghiệm giải thuật đánh giá mức độ giống nhau của văn bản. 3. Đối tượng và phạm vi nghiên cứu a. Đối tượng nghiên cứu Đối tượng nghiên cứu của đề tài là: cơ sở lý thuyết các phương pháp và các thuật toán đánh giá sự giống nhau của hai văn bản, ngôn ngữ lập trình, môi trường phát triển. b. Phạm vi nghiên cứu Trong khuôn khổ của một luận văn chỉ giới hạn thử nghiệm tạo công cụ đánh giá mức độ giống nhau của hai văn bản. 4. Giả thiết nghiên cứu Việc so sánh mức độ giống nhau của hai văn bản đáp ứng rất nhiều các nhu cầu khác nhau trong nhiều lĩnh vực từ tìm kiếm thông tin đến phát hiện sao chép văn bản. Nó cũng góp phần phân loại tài liệu dựa vào nội dung liên quan. Cụ thể, cũng có thể áp dụng để xây dựng công cụ phát hiện sao chép tài liệu giữa các sinh viên ở một trường đại học dựa vào kho dữ liệu đề tài, bài báo của trường. 5. Phương pháp nghiên cứu a. Phương pháp nghiên cứu tài liệu Các tài liệu về cơ sở lý thuyết: các phương pháp đánh giá văn bản, các giải thuật về đánh giá mức độ giống nhau của hai văn bản, các tài liệu mô tả một số công cụ lập trình, các tài liệu liên quan đến một số nghiên cứu khác. b. Phương pháp thực nghiệm Xây dựng chương trình thử nghiệm tính hiệu quả của giải thuật nghiên cứu. 6. Ý nghĩa khoa học và thực tiễn của đề tài a. Ý nghĩa khoa học Đề tài tập trung nghiên cứu các phương pháp khác nhau để đánh giá mức độ giống nhau của hai văn bản; nghiên cứu các thuật toán đánh giá dựa trên ký tự. 3 b. Ý nghĩa thực tiễn Xây dựng công cụ để đánh giá mức độ giống nhau của hai văn bản. Việc đánh giá mức độ giống nhau của hai văn bản có thể áp dụng trong các lĩnh vực như: tìm kiếm nội dung tài liệu, phân nhóm nội dung tài liệu, phát hiện sao chép,… 7. Bố cục của luận văn Chương 1. TỔNG QUAN Chương này trình bày kết quả nghiên cứu các nội dung tổng quan về các phương pháp đánh giá mức độ giống nhau của hai văn bản, các thuật toán dựa trên ký tự, so sánh các thuật toán. Chương 2. GIẢI PHÁP XÂY DỰNG CÔNG CỤ Chương này trình bày kết quả nghiên cứu các nội dung tổng quan về mô hình so sánh mức độ giống nhau của hai văn bản, giải pháp chuyển dữ liệu nguồn từ dạng word, pdf sang dạng text để so sánh, so sánh mức độ giống nhau của hai văn bản. Chương 3. THỰC NGHIỆM Chương này trình bày kết quả nghiên cứu các nội dung sau: lựa chọn công cụ phát triển, xây dựng các mô-đun ứng dụng như: chuyển đổi dữ liệu từ word, pdf sang dạng text, so sánh mức độ giống nhau của văn bản. Tiến hành chạy thử nghiệm chương trình và đánh giá kết quả thử nghiệm. 4 CHƯƠNG 1. TỔNG QUAN Chương này trình bày kết quả nghiên cứu các nội dung tổng quan về các phương pháp đánh giá mức độ giống nhau của hai văn bản, các thuật toán dựa trên ký tự, so sánh các thuật toán. 1.1. Giới thiệu Với việc phát triển mạnh mẽ của Internet trong những năm qua, chúng đã đem lại lợi ích to lớn cho người sử dụng Internet. Internet đã cung cấp nguồn thông tin khổng lồ của nhiều lĩnh vực đến người dùng cũng như những dịch vụ mà nó mang lại. Do đó, để đánh giá mức độ giống nhau của các tài liệu đã góp phần quan trọng trong các lĩnh vực như: tìm kiếm thông tin dựa vào nội dung, phân nhóm tài liệu dựa vào sự tương đồng về nội dung, kiểm tra sao chép [5],… Để đánh giá mức độ giống nhau của văn bản thì việc tìm kiếm sự giống nhau của các từ ngữ là một phần quan trọng, từ đó đánh giá sự giống nhau của một câu, một đoạn văn hay một tài liệu. Từ ngữ có thể được đánh giá giống nhau theo mặt từ vựng hoặc ngữ nghĩa. Các từ mà tương tự về từ vựng nếu chúng có các chuỗi ký tự giống nhau. Các từ mà tương tự về ngữ nghĩa nếu chúng nói về cùng một việc, sử dụng trong cùng một bối cảnh và có ý nghĩa giống nhau [5]. Các phương pháp đánh giá mức độ giống nhau của văn bản có thể chia ra như sau: - Đánh giá dựa trên chuỗi ký tự (String-Based Similarity Measures). - Đánh giá dựa trên từ vựng (Corpus-Based Similarity Measures). - Đánh giá dựa trên ngữ nghĩa (Knowledge-Based Similarity Measures) [5]. Trong luận văn tập trung nghiên cứu về các phương pháp đánh giá mức độ giống nhau của văn bản dựa trên chuỗi ký tự, cụ thể sẽ ứng dụng khoảng cách Levenshtein để so sánh mức độ giống nhau của hai văn bản. 5 1.2. Các phương pháp đánh giá mức độ giống nhau của hai văn bản 1.2.1. Đánh giá dựa trên chuỗi (String-based Similarity Measures) Đánh giá dựa trên chuỗi được thực hiện bằng cách so sánh trình tự của các chuỗi dữ liệu. Phương pháp đánh giá dựa trên chuỗi chia ra làm hai cách: đánh giá dựa trên ký tự (Character-Based Similarity Measures) và đánh giá dựa trên thuật ngữ (Term-Based Similarity Measures) [5][9]. Các thuật toán đánh giá dựa trên ký tự bao gồm: - Smith-Waterman: là thuật toán quy hoạch động, thay vì tìm kiếm toàn bộ chuỗi, thuật toán sẽ so sánh các đoạn trong chuỗi và tìm kiếm các đoạn gần giống nhau của hai chuỗi. - N-gram: là một chuỗi con gồm n thành phần (có thể là ký tự, từ,…) từ một chuỗi văn bản cho trước. Thuật toán N-gram sẽ so sánh các N-grams (chuỗi con) trong hai chuỗi cần so sánh. Khoảng cách giữa hai chuỗi được tính bằng cách chia số chuỗi con giống nhau với số chuỗi con ban đầu. - Levenshtein: là số bước ít nhất để biến đổi chuỗi này thành chuỗi kia thông qua ba phép biến đổi: thêm một ký tự, xóa một ký tự, thay thế ký tự. - Jaro–Winkler: được dùng để đánh giá mức độ giống nhau giữa hai chuỗi. Khoảng cách Jaro – Winkler có giá trị càng ngắn thì mức độ giống nhau của hai chuỗi dữ liệu càng nhiều [10]. - Needleman–Wunsch: là thuật toán quy hoạch động, thuật toán thực hiện tìm kiếm toàn cục để tìm ra các cặp trình tự giống nhau trên hai chuỗi dữ liệu. Nó thích hợp áp dụng với hai chuỗi dữ liệu có độ dài tương đương nhau. - Longest Common Substring (LCS): thuật toán so sánh sự giống nhau của hai chuỗi dựa trên chiều dài liên tục của các ký tự giống nhau của cả hai chuỗi [5][9]. Các thuật toán đánh giá dựa trên thuật ngữ bao gồm: - Block Distance: cũng được gọi là Manhattan distance, city block distance. Khoảng cách Block Distance giữa hai chuỗi dữ liệu càng lớn thì mức độ giống nhau càng ít. 6 - Cosine similarity: là cách đo lường mức độ giống nhau của hai vector bằng cách tính góc Cosine giữa hai vector. - Dice’s coefficient: được tính gấp hai lần số lượng thuật ngữ giống nhau của hai chuỗi chia cho tổng số thuật ngữ của hai chuỗi (2*(X∩Y)/(X+Y)). - Euclidean distance: còn được gọi là L2 distance là căn bậc hai của tổng bình phương giữa các thành phần tương ứng của hai vector. d(p,q) = d(q,p) = √∑𝑛𝑖=1(𝑞𝑖 − 𝑝𝑖 )2 (1.1) - Jaccard similarity: được tính như số thuật ngữ giống nhau chia cho số thuật ngữ khác nhau của hai chuỗi. - Matching Coefficient: là cách tiếp cận dựa trên vector bằng cách đếm số thuật ngữ giống nhau của hai vector. - Overlap coefficient: tương tự như Dice’s coefficient, nhưng nó sẽ xem hai chuỗi là hoàn toàn giống nhau nếu một chuỗi con của chuỗi này là phần tử của chuỗi kia [5][9]. Smith-Waterman N-gram Levenshtein Jaro–Winkler Needleman–Wunsch Character - Based LCS String - Based Block Distance Cosine similarity Dice’s coefficient Term - Based Euclidean distance Overlap coefficient Matching Coefficient Jaccard similarity Hình 1.1. Các phương pháp đánh giá mức độ giống nhau dựa trên chuỗi 7 1.2.2. Đánh giá dựa trên từ vựng (Corpus-Based Similarity Measures) Đánh giá dựa trên từ vựng được thực hiện bằng cách xác định sự tương đồng về mặt ngữ nghĩa của từ ngữ dựa trên thông tin từ một tập từ vựng (tập dữ liệu – large corpora). Tập từ vựng là một tập hợp các dữ liệu văn bản hoặc tiếng nói được sử dụng trong nghiên cứu ngôn ngữ [5][9]. Các kỹ thuật đánh giá dựa trên từ vựng gồm [5][9]: - Hyperspace Analogue to Language (HAL): tạo ra một không gian ngữ nghĩa từ các từ. Một ma trận từ (word by word) được xây dựng với mỗi phần tử ma trận là sự liên kết giữa các từ. Người sử dụng thuật toán sau đó có tùy chọn để loại bỏ các cột entropy thấp từ ma trận. Các giá trị ma trận được tích lũy bằng cách xác định trọng số tỷ lệ nghịch với khoảng cách của từ trọng tâm. Các từ gần từ trọng tâm thì nó sẽ phản ánh gần hơn ngữ nghĩa của từ trọng tâm và cũng có trọng số cao hơn. HAL cũng ghi nhận thông tin thứ tự của từ xuất hiện gần trước hay sau từ trọng tâm. - Latent Semantic Analysis (LSA): là kỹ thuật phổ biến nhất để đánh giá sự tương đồng về mặt ngữ nghĩa. LSA giả định rằng những từ gần nghĩa sẽ xuất hiện trong các mảng văn bản tương đồng. Một ma trận chứa tổng số các từ trên một đoạn văn (dòng đại diện cho các từ duy nhất và cột đại diện cho mỗi đoạn văn) được xây dựng từ một mảng lớn của văn bản và một kỹ thuật toán học được gọi là Singular Value Decomposition (SVD) được sử dụng để giảm số cột trong khi vẫn giữ được sự giống nhau về cấu trúc giữa các dòng. Các từ sau đó được so sánh bằng cách lấy cosin của góc giữa hai vectơ được hình thành bởi hai dòng bất kỳ. - Generalized Latent Semantic Analysis (GLSA): là một framework cho việc tính toán các vector văn bản và thuật ngữ dựa trên ngữ nghĩa. Nó là một mở rộng của LSA bằng cách tập trung vào các vector thuật ngữ (term vectors) thay vì biểu diễn hai văn bản. GLSA đòi hỏi sự đo lường kết hợp ngữ nghĩa của các thuật ngữ và một phương pháp giảm chiều (dimensionality reduction). Các tiếp cận GLSA có thể kết hợp với bất kỳ phương pháp đo lường sự giống nhau trên không gian của thuật ngữ với bất kỳ phương pháp giảm chiều phù hợp nào. 8 - Explicit Semantic Analysis (ESA): Là một phép đo được sử dụng để tính toán mối quan hệ ngữ nghĩa giữa hai văn bản. Kỹ thuật dựa trên Wikipedia (Wikipedia-Based) biểu diễn các thuật ngữ hay văn bản như các vector đa chiều, mỗi vector biểu diễn trọng số giữa thuật ngữ và một bài viết trên Wikipedia. Quan hệ ngữ nghĩa giữa hai thuật ngữ (hoặc văn bản) được thể hiện bằng phép đo cosine giữa các vectơ tương ứng. - The cross-language explicit semantic analysis (CL-ESA): là một dạng tổng quát đa ngôn ngữ của ESA. CL-ESA khai thác một tập các tài liệu tham khảo đa ngôn ngữ như Wikipedia để đại diện cho một tài liệu như là một vector độc lập ngôn ngữ (language-independent). Sự liên quan của hai tài liệu bằng các ngôn ngữ khác nhau được đánh giá bởi sự giống nhau cosin giữa các vector tương ứng. - Pointwise Mutual Information - Information Retrieval (PMI-IR): là phương pháp tính toán sự giống nhau của các cặp từ. Nó sử dụng truy vấn tìm kiếm nâng cao của AltaVista hoặc cú pháp (syntax) để tính xác suất. Hai từ cùng xuất hiện gần nhau trên một trang web thì có mức điểm giống nhau cao hơn. - Second-order co-occurrence pointwise mutual information (SCO-PMI): là một phép đo mức độ giống nhau về mặt ngữ nghĩa bằng cách sử dụng thông tin chung của nhau để sắp xếp danh sách các từ quan trọng gần nhau của hai từ mục tiêu trong một tập hợp các từ. Ưu điểm của việc sử dụng SCO-PMI là nó có thể tính toán sự giống nhau của hai từ mà không đồng thời xuất hiện thường xuyên bởi vì chúng có thể xuất hiện cùng với các từ lân cận. - Normalized Google Distance (NGD): là một phép đo mức độ giống nhau về mặt ngữ nghĩa thu được từ số lần truy cập trả về bởi công cụ tìm kiếm của Google (Google search engine) từ một tập hợp các từ khóa. Các từ khóa có nghĩa giống hoặc tương tự nhau có xu hướng gần nhau, trong khi các từ có nghĩa khác nhau có xu hướng cách xa nhau hơn. - Extracting Distributionally similar words using So-occurrences (DISCO): việc phân chia các từ giống nhau được giả định rằng các từ có nghĩa giống nhau sẽ xuất hiện trong cùng ngữ cảnh. Một tập hợp các văn bản được phân tích để phân 9 chia các từ giống nhau. DISCO được chia ra làm hai phép đo là DISCO1 và DISCO2. DISCO1 tính toán mức độ giống nhau theo thứ tự thứ nhất giữa hai từ đầu vào dựa trên các tập hợp được sắp xếp. DISCO2 tính toán mức độ giống nhau theo thứ tự thứ hai giữa hai từ đầu vào dựa trên các tập hợp các từ giống nhau. Corpus - Based HAL LSA ESA PMI-IR NGD DISCO GLSA CL-ESA SOC-PMI DISCO1 DISCO2 Hình 1.2. Các phương pháp đánh giá mức độ giống nhau dựa trên từ vựng 1.2.3. Đánh giá dựa trên ngữ nghĩa (Knowledge-Based Similarity Measures) Đánh giá dựa trên ngữ nghĩa được thực hiện bằng cách xác định mức độ tương đồng của từ ngữ dựa vào thông tin truy xuất từ mạng ngữ nghĩa. WordNet là mạng ngữ nghĩa phổ biến trong lĩnh vực đánh giá sự giống nhau của từ ngữ dựa trên ngữ nghĩa. WordNet là một cơ sở dữ liệu từ vựng tiếng Anh lớn. Danh từ, động từ, tính từ và trạng từ được nhóm thành tập các bộ đồng nghĩa (synsets). Synset được liên kết với nhau bằng các quan hệ ngữ nghĩa và từ vựng [5]. res Information content Similarity lin Knowledge - Based Path Length jcn hso lch lesk wup vector path Relatedness Hình 1.3. Các phương pháp đánh giá mức độ giống nhau dựa trên ngữ nghĩa