Đại Học Quốc Gia TP Hồ Chí Minh TRƯỜNG ĐẠI HỌC BÁCH KHOA -o0o LUẬN VĂN ĐẠI HỌC XỬ LÝ CÁC CÂU TRUY VẤN VÀ TÌM KIẾM TRÊN KHO TÀI LIỆU CĨ CHÚ THÍCH NGỮ NGHĨA BẰNG TIẾNG ANH Chuyên ngành: Khoa Học Máy Tính GVHD : Pgs.Ts Cao Hoàng Trụ Sinhh vi Sin viên ên : Ng Nguyễ uyễnn Tr Trần ần Đ Đăng ăng Kho Khoaa (50601130) Tạ Tất Tài (50602084) TP Hồ Chí Minh, tháng 12 – 2010   CƠNG TRÌNH ĐƯỢC HỒN THÀNH TẠI TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐẠI HỌC QUỐC QUỐC GIA TP HỒ CHÍ MI MINH NH Cán hướng dẫn khoa học : PGS.TS CAO HOÀNG TRỤ Cán chấm nhận xét : Cán chấm nhận xét : Luận văn đại học bảo vệ HỘI ĐỒNG CHẤM BẢO VỆ LUẬN VĂN ĐẠI HỌC TRƯỜNG ĐẠI HỌC BÁCH KHOA, ngày tháng năm   LỜI CAM ĐOAN Tôi cam đoan ngoại trừ kết tham khảo từ cơng trình khác ghi rõ luận văn, cơng việc trình bày luận văn tơi thực chưa có phần nội dung luận văn nộp để lấy cấp trường đại học khác  Ngày  Ngày Tháng Năm Tháng Năm Ký tên   LỜI CẢM ƠN Trước hết, xin gởi lời cảm ơn chân thành sâu sắc đến Pgs.Ts Cao Hoàng Trụ, kỹ sư Châu Kim Cường, người trực tiếp hướng dẫn tơi q trình làm luận văn Sự hướng dẫn chu đáo, tận tình, với tài liệu lời khuyên quý giá thầy anh tháng qua nhân tố thiếu để chúng tơi hồn thành nhiệm vụ Chúng tơi xin gửi lời cảm ơn đến gia đình bạn bè, người sát cánh, động viên, tạo điều kiện tốt để học tập hồn tất luận văn tốt nghiệp Chúng chân thành biết ơn tận tình dạy dỗ giúp đỡ tất quý thầy cô khoa Khoa học Kỹ thuật Máy tính trường Đại học Bách khoa Luận văn khó tránh khỏi cịn thiếu sót tầm nhìn chúng tơi cịn hạn hẹp, mong nhận góp ý q thầy bạn   TÓM TẮT Từ đời đến nay, World Wide Web trở thành công cụ quan trọng để lưu trữ chia sẻ nguồn tri thức khổng lồ Tuy nhiên, công cụ phần mềm chưa hỗ trợ thật hiểu cho người trình khai thác kho tri thức Với mong muốn làm hiệu q trình đó, luận văn xây dựng cơng cụ tìm kiếm “hiểu” nội dung câu truy vấn tiếng Anh trả kết Để biên dịch câu truy vấn ngôn ngữ tự nhiên, luận văn dựa tảng web ngữ nghĩa, kết hợp với phương pháp dịch phụ thuộc vào cú pháp nhóm VN-KIM Để thể nội dung  biên dịch được, luận văn biểu diễn đồ thị ý niệm Cuối cùng, câu truy vấn SeRQL dùng để tìm kiếm kết Hiệu hệ thống đánh giá tập câu truy vấn mẫu “TREC 2002”   MỤC LỤC TỔNG QUAN .1 1.1 13 1.2 Giới Mục thiệu tiêu phạm vi 1.3 Kết đạt được 55 1.4 Cấu trúc luận văn KIẾN THỨC NỀN TẢNG 2.1 Rút trích quan hệ 77 2.2 Đồ thị ý niệm (Conceptual Graph) 88 2.2.1 Sơ lược đồ thị ý niệm .8 2.2.2 Đồ thị ý niệm mở rộng 10 10 2.3 Tìm thực thể vài tài liệu 11 2.3.1 Câu truy vấn SeRQL [tham khảo http://www.openrdf.org/doc/sesame2/2.3.1/users/ch09.html#section-numerical-comparisons] http://www.openrdf.org/doc/sesame2/2.3.1/users/ch09.html#secti on-numerical-comparisons] 11 2.3.2TÍCH Semantic Lucen e .14 12 PHÂN VẤNLucene ĐỀ VÀ PHƯƠNG PHÁP GIẢI QUYẾT 3.1 Chuyển đổi câu truy vấn với từ để hỏi “How many” .14 14 3.2 Chuyển đổi câu truy vấn có tính từ 16 16 3.3 Chuyển đổi câu truy vấn có tính từ so sánh 18 3.4 Chuyển đổi câu truy truy vấn có tính tính từ 19 19 3.5 Chuyển đổi câu truy vấn có tính từ so sánh 21 3.5.1 Trường hợp tính từ định tính 21 3.5.2 Trường hợp tính từ định lượng [tham khảo HA] 21 21 3.6 Chuyển đổi câu truy vấn có tính từ định lượng so sánh 22 22 THIẾT TH IẾT KẾ 24 4.1 Các bước giải thuật 24 4.1.1 Phân tách vấntên 26 26 4.1.2 Nhận b iết câu biết thựctruy thể có 26 4.1.3 Nhận biết thực thể không tên 26 4.1.4 Nhận biết b iết tính từ 27 4.1.5 Nhận biết từ quan hệ 27 4.1.6 Xác định lớp thực thể 27 4.1.7 Gom thực thể 28 4.1.8 Xác định quan hệ ẩn .29 29 4.1.9 Xác định loại quan hệ thực thể 29 4.1.10 Xoá bỏ b ỏ quan hệ không phù hợp 32 4.1.11 Xác định quan hệ g iữa tính từ thực thể 33 4.1.12 Xây dựng đồ thị ý niệm .36 4.2 Tập luật 36 4.2.1 Cấu trúc hệ thống luật 37 37   4.2.2 Cấu trúc thành phần điều kiện luật 38 4.2.3 Cấu trúc thành phần hành động luật .38 4.2.4 Xây dựng số luật đặc biệt 39 4.2.5 Xây dựng từ điển luật 40 40 4.3 Kết thí nghiệm 42 42 HIỆN THỰC HỆ THỐNG .50 50 5.1 Các khối xử lý giao diện lớp lớp quan trọng 50 5.1.1 Ứng dụng web phía Client .50 50 5.1.2 Hệ thống xử lý server 50 5.2 Hệ thống luật [tham khảo CDT] 54 5.2.1 Cấu trúc hệ thống luật 55 55 5.2.2 Cấu trúc thành phần điều kiện luật 56 5.2.3 Cấu trúc thành phần hành động luật .57 5.2.4 Xây dựng số luật đặc biệt 58 5.3 Lưu trữ đồ thị hiển thị đồ thị [tham khảo HA] 58 58 5.4 Xây dựng câu truy vấn SeRQL 60 60 KẾT LUẬN 65 65 TÀI LIỆU THAM KHẢO 67 PHỤ LỤC A: TẬP CÂU MẪU TREC 2002 71 71 PHỤ LỤC C: ĐỒ THỊ Ý NIỆM SINH ĐÚNG TỪ TREC 2002 TRƯỚC KHI LÀM GIÀU ONTO ON TOLOG LOGY Y 76 PHỤ LỤC D: ĐỒ THỊ Ý NIỆM SINH ĐÚNG TỪ TREC 2002 SAU KHI LÀM GIÀU ONTO ON TOLOG LOGY Y 77   DANH MỤC HÌNH Hình 3.0.1: Ví dụ biểu diễn câu truy vấn "How many" .15 Hình 3.0.2: Ví dụ biểu diễn câu truy vấn "How many" dạng rút gọn .15 Hình 3.0.3: Ví dụ biểu diễn tổng quát cho câu truy vấn "How many" 15 Hình 4.0.4: Mô tả bước dùng để xây dựng đồ thị ý niệm cho câu truy vấn .25 Hình 4.0.5: Xác định loại quan hệ hai thực thể ei ej 30 Hình 4.0.6: Lược đồ ánh xạ kiểu quan hệ ba truy vấn 31 Hình 4.0.7: Xác định loại quan hệ tính từ adj thực thể 34 Hình 4.0.8: Lược đồ ánh xạ kiểu quan hệ tính từ thực thể 35 Hình 4.0.9: Cấu trúc tập thành phần TransformRules rule 37 Hình 4.0.10: Cấu trúc thành phần điều kiện luật 39 Hình 4.0.11: Ví dụ thành phần premise .39 Hình 4.0.12: Cấu trúc thành phần hành động .40 Hình 4.0.13: Cấu trúc từ điển quan hệ 41 Hình 4.0.14: Ví dụ luật hoàn chỉnh 41 Hình 4.0.15: Ví dụ số thành phần từ điển 41 Hình 4.0.16: Ví dụ biểu diễn câu truy vấn “Queried relation” 45 Hình 4.0.17: Ví dụ biểu diễn câu truy vấn “Advert / Temporal” 45   DANH MỤC BẢNG Bảng 4.1: Bảng thuộc tính thành phần premise 38 Bảng 4.2: Mơ tả thuộc tính thành phần entry .41 Bảng 4.3: Kết thực nghiệm TREC 2002 chưa áp dụng phương pháp đề nghị .43 Bảng 4.4: Kết thực nghiệm TREC 2002 sau áp dụng phương pháp đề nghị .43 Bảng 4.5: Kết thực nghiệm TREC 2002 sau làm giàu Ontology 44 Bảng 4.6: Bảng tổng kết kết cuối đạt tập TREC 2002 46 Bảng 4.7: Kết thực nghiệm TREC 2007 chưa áp dụng phương pháp đề nghị .47 Bảng 4.8: Kết thực nghiệm TREC 2007 sau áp dụng phương pháp đề nghị 47 Bảng 4.9: Kết thực nghiệm TREC 2007 sau làm giàu Ontology 48 Bảng 4.10: Bảng tổng kết kết cuối đạt tập TREC 2007 49   CHƯƠNG TỔNG QUAN 1.11 Giới Giới thiệ thiệuu Kể từ đời đến nay, World Wide Web (WWW (WWW)) làm thay đổi nhiều cách người trao đổi tiếp cận với thông tin, tri thức thức Và kinh tế tri thức nay, tầm quan trọng WWW lớn Điều đặt yêu cầu là: phải để trình khai thác tri thức từ WWW đạt hiệu suất tối ưu Muốn vậy, giải pháp phải tự động hóa trình đó; nói cách khác, máy móc phải có khả khai thác thông tin WWW với độ xác cao Hiện nay, có cơng cụ phần mềm nhắm đến mục tiêu Nổi bật có lẽ động tìm kiếm dựa từ khóa (keyword – based search engine), động tìm kiếm Google, Yahoo, Tuy đạt thành công định, hệ thống cịn có khuyết điểm làm cho người sử dụng chưa hài lịng Có thể nêu như: − Kết trả cho truy vấn nhiều, độ xác lại thấp Người dùng phải tốn nhiều thời gian với kết khơng thích hợp − Kết trả hoàn toàn phụ thuộc vào từ khóa cung cấp Trong khi, theo mong muốn người, truy vấn tương tự mặt ngữ nghĩa phải dẫn đến kết Do cơng cụ tìm kiếm chủ yếu so trùng, mà chưa “hiểu” nội dung thông tin chứa WWW nội dung câu truy vấn, nên dẫn đến hạn chế  Như vậy, để làm tăng hiệu trìn trìnhh tìm kiếm tự động, hướng tiếp cận làm cho máy tính “hiểu” nội dung thơng tin: thơng tin lưu trữ WWW thông tin câu truy vấn người dùng 23 23   //Function: append WHERE clause for superlative adjective to the input SeRQL Initialize the WHERE, nested SELECT and nested FROM clause //select the value of all other entities which are also qualified, then use “>= ALL” or “= ALL” or “” or “